Archives for 2009

Today I read a paper titled “Support Vector classifiers for Land Cover Classification”

The abstract is:
Support vector machines represent a promising development in machine learning research that is not widely used within the remote sensing community.

This paper reports the results of Multispectral(Landsat-7 ETM+) and Hyperspectral DAIS)data in which multi-class SVMs are compared with maximum likelihood and artificial neural network methods in terms of classification accuracy.

Our results show that the SVM achieves a higher level of classification accuracy than either the maximum likelihood or the neural classifier, and that the support vector machine can be used with small training datasets and high-dimensional data.

Today I read a paper titled “Weighted Automata in Text and Speech Processing”

The abstract is:
Finite-state automata are a very effective tool in natural language processing.

However, in a variety of applications and especially in speech precessing, it is necessary to consider more general machines in which arcs are assigned weights or costs.

We briefly describe some of the main theoretical and algorithmic aspects of these machines.

In particular, we describe an efficient composition algorithm for weighted transducers, and give examples illustrating the value of determinization and minimization algorithms for weighted automata.

Today I read a paper titled “Pattern Recognition for Conditionally Independent Data”

The abstract is:
In this work we consider the task of relaxing the i.i.d assumption in pattern recognition (or classification), aiming to make existing learning algorithms applicable to a wider range of tasks.

Pattern recognition is guessing a discrete label of some object based on a set of given examples (pairs of objects and labels).

We consider the case of deterministically defined labels.

Traditionally, this task is studied under the assumption that examples are independent and identically distributed.

However, it turns out that many results of pattern recognition theory carry over a weaker assumption.

Namely, under the assumption of conditional independence and identical distribution of objects, while the only assumption on the distribution of labels is that the rate of occurrence of each label should be above some positive threshold.

We find a broad class of learning algorithms for which estimations of the probability of a classification error achieved under the classical i.i.d.

assumption can be generalised to the similar estimates for the case of conditionally i.i.d.

examples.

Today I read a paper titled “Characterizing Optimal Adword Auctions”

The abstract is:
We present a number of models for the adword auctions used for pricing advertising slots on search engines such as Google, Yahoo! etc.

We begin with a general problem formulation which allows the privately known valuation per click to be a function of both the identity of the advertiser and the slot.

We present a compact characterization of the set of all deterministic incentive compatible direct mechanisms for this model.

This new characterization allows us to conclude that there are incentive compatible mechanisms for this auction with a multi-dimensional type-space that are {\em not} affine maximizers.

Next, we discuss two interesting special cases: slot independent valuation and slot independent valuation up to a privately known slot and zero thereafter.

For both of these special cases, we characterize revenue maximizing and efficiency maximizing mechanisms and show that these mechanisms can be computed with a worst case computational complexity $O(n^2m^2)$ and $O(n^2m^3)$ respectively, where $n$ is number of bidders and $m$ is number of slots.

Next, we characterize optimal rank based allocation rules and propose a new mechanism that we call the customized rank based allocation.

We report the results of a numerical study that compare the revenue and efficiency of the proposed mechanisms.

The numerical results suggest that customized rank-based allocation rule is significantly superior to the rank-based allocation rules.

Today I read a paper titled “Diversity of Online Community Activities”

The abstract is:
Web sites where users create and rate content as well as form networks with other users display long-tailed distributions in many aspects of behavior.

Using behavior on one such community site, Essembly, we propose and evaluate plausible mechanisms to explain these behaviors.

Unlike purely descriptive models, these mechanisms rely on user behaviors based on information available locally to each user.

For Essembly, we find the long-tails arise from large differences among user activity rates and qualities of the rated content, as well as the extensive variability in the time users devote to the site.

We show that the models not only explain overall behavior but also allow estimating the quality of content from their early behaviors.

Today I read a paper titled “Approximately Efficient Cost-Sharing Mechanisms”

The abstract is:
We make three different types of contributions to cost-sharing: First, we identify several new classes of combinatorial cost functions that admit incentive-compatible mechanisms achieving both a constant-factor approximation of budget-balance and a polylogarithmic approximation of the social cost formulation of efficiency.

Second, we prove a new, optimal lower bound on the approximate efficiency of every budget-balanced Moulin mechanism for Steiner tree or SSRoB cost functions.

This lower bound exposes a latent approximation hierarchy among different cost-sharing problems.

Third, we show that weakening the definition of incentive-compatibility to strategyproofness can permit exponentially more efficient approximately budget-balanced mechanisms, in particular for set cover cost-sharing problems.

Today I read a paper titled “A syntax-based part-of-speech analyser”

The abstract is:
There are two main methodologies for constructing the knowledge base of a natural language analyser: the linguistic and the data-driven.

Recent state-of-the-art part-of-speech taggers are based on the data-driven approach.

Because of the known feasibility of the linguistic rule-based approach at related levels of description, the success of the data-driven approach in part-of-speech analysis may appear surprising.

In this paper, a case is made for the syntactic nature of part-of-speech tagging.

A new tagger of English that uses only linguistic distributional rules is outlined and empirically evaluated.

Tested against a benchmark corpus of 38,000 words of previously unseen text, this syntax-based system reaches an accuracy of above 99%.

Compared to the 95-97% accuracy of its best competitors, this result suggests the feasibility of the linguistic approach also in part-of-speech analysis..

Today I read a paper titled “Curve Shortening and the Rendezvous Problem for Mobile Autonomous Robots”

The abstract is:
If a smooth, closed, and embedded curve is deformed along its normal vector field at a rate proportional to its curvature, it shrinks to a circular point.

This curve evolution is called Euclidean curve shortening and the result is known as the Gage-Hamilton-Grayson Theorem.

Motivated by the rendezvous problem for mobile autonomous robots, we address the problem of creating a polygon shortening flow.

A linear scheme is proposed that exhibits several analogues to Euclidean curve shortening: The polygon shrinks to an elliptical point, convex polygons remain convex, and the perimeter of the polygon is monotonically decreasing.

Today I read a paper titled “Novel Reversible Multiplier Architecture Using Reversible TSG Gate”

The abstract is:
In the recent years, reversible logic has emerged as a promising technology having its applications in low power CMOS, quantum computing, nanotechnology, and optical computing.

The classical set of gates such as AND, OR, and EXOR are not reversible.

Recently a 4 * 4 reversible gate called TSG is proposed.

The most significant aspect of the proposed gate is that it can work singly as a reversible full adder, that is reversible full adder can now be implemented with a single gate only.

This paper proposes a NXN reversible multiplier using TSG gate.

It is based on two concepts.

The partial products can be generated in parallel with a delay of d using Fredkin gates and thereafter the addition can be reduced to log2N steps by using reversible parallel adder designed from TSG gates.

Similar multiplier architecture in conventional arithmetic (using conventional logic) has been reported in existing literature, but the proposed one in this paper is totally based on reversible logic and reversible cells as its building block.

A 4×4 architecture of the proposed reversible multiplier is also designed.

It is demonstrated that the proposed multiplier architecture using the TSG gate is much better and optimized, compared to its existing counterparts in literature; in terms of number of reversible gates and garbage outputs.

Thus, this paper provides the initial threshold to building of more complex system which can execute more complicated operations using reversible logic.

Today I read a paper titled “Watermark Embedding and Detection”

The abstract is:
The embedder and the detector (or decoder) are the two most important components of the digital watermarking systems.

Thus in this work, we discuss how to design a better embedder and detector (or decoder).

I first give a summary of the prospective applications of watermarking technology and major watermarking schemes in the literature.

My review on the literature closely centers upon how the side information is exploited at both embedders and detectors.

In Chapter 3, I explore the optimum detector or decoder according to a particular probability distribution of the host signals.

We found that the performance of both multiplicative and additive spread spectrum schemes depends on the shape parameter of the host signals.

For spread spectrum schemes, the performance of the detector or the decoder is reduced by the host interference.

Thus I present a new host-interference rejection technique for the multiplicative spread spectrum schemes.

Its embedding rule is tailored to the optimum detection or decoding rule.

Though the host interference rejection schemes enjoy a big performance gain over the traditional spread spectrum schemes, their drawbacks that it is difficult for them to be implemented with the perceptual analysis to achieve the maximum allowable embedding level discourage their use in real scenarios.

Thus, in the last chapters of this work, I introduce a double-sided technique to tackle this drawback.

It differs from the host interference rejection schemes in that it utilizes but does not reject the host interference at its embedder.

The perceptual analysis can be easily implemented in our scheme to achieve the maximum allowable level of embedding strength.

Today I read a paper titled “Implementation of perception and action at nanoscale”

The abstract is:
Real time combination of nanosensors and nanoactuators with virtual reality environment and multisensorial interfaces enable us to efficiently act and perceive at nanoscale.

Advanced manipulation of nanoobjects and new strategies for scientific education are the key motivations.

We have no existing intuitive representation of the nanoworld ruled by laws foreign to our experience.

A central challenge is then the construction of nanoworld simulacrum that we can start to visit and to explore.

In this nanoworld simulacrum, object identifications will be based on probed entity physical and chemical intrinsic properties, on their interactions with sensors and on the final choices made in building a multisensorial interface so that these objects become coherent elements of the human sphere of action and perception.

Here we describe a 1D virtual nanomanipulator, part of the Cit\’e des Sciences EXPO NANO in Paris, that is the first realization based on this program.

Today I read a paper titled “Toward Psycho-robots”

The abstract is:
We try to perform geometrization of psychology by representing mental states, <>, by points of a metric space, <>.

Evolution of ideas is described by dynamical systems in metric mental space.

We apply the mental space approach for modeling of flows of unconscious and conscious information in the human brain.

In a series of models, Models 1-4, we consider cognitive systems with increasing complexity of psychological behavior determined by structure of flows of ideas.

Since our models are in fact models of the AI-type, one immediately recognizes that they can be used for creation of AI-systems, which we call psycho-robots, exhibiting important elements of human psyche.

Creation of such psycho-robots may be useful improvement of domestic robots.

At the moment domestic robots are merely simple working devices (e.g.

vacuum cleaners or lawn mowers) .

However, in future one can expect demand in systems which be able not only perform simple work tasks, but would have elements of human self-developing psyche.

Such AI-psyche could play an important role both in relations between psycho-robots and their owners as well as between psycho-robots.

Since the presence of a huge numbers of psycho-complexes is an essential characteristic of human psychology, it would be interesting to model them in the AI-framework.

Today I read a paper titled “Partnering Strategies for Fitness Evaluation in a Pyramidal Evolutionary Algorithm”

The abstract is:
This paper combines the idea of a hierarchical distributed genetic algorithm with different inter-agent partnering strategies.

Cascading clusters of sub-populations are built from bottom up, with higher-level sub-populations optimising larger parts of the problem.

Hence higher-level sub-populations search a larger search space with a lower resolution whilst lower-level sub-populations search a smaller search space with a higher resolution.

The effects of different partner selection schemes for (sub-)fitness evaluation purposes are examined for two multiple-choice optimisation problems.

It is shown that random partnering strategies perform best by providing better sampling and more diversity.

Today I read a paper titled “Is there an Elegant Universal Theory of Prediction?”

The abstract is:
Solomonoff’s inductive learning model is a powerful, universal and highly elegant theory of sequence prediction.

Its critical flaw is that it is incomputable and thus cannot be used in practice.

It is sometimes suggested that it may still be useful to help guide the development of very general and powerful theories of prediction which are computable.

In this paper it is shown that although powerful algorithms exist, they are necessarily highly complex.

This alone makes their theoretical analysis problematic, however it is further shown that beyond a moderate level of complexity the analysis runs into the deeper problem of Goedel incompleteness.

This limits the power of mathematics to analyse and study prediction algorithms, and indeed intelligent systems in general.

Today I read a paper titled “Multimedia Content Distribution in Hybrid Wireless Networks using Weighted Clustering”

The abstract is:
Fixed infrastructured networks naturally support centralized approaches for group management and information provisioning.

Contrary to infrastructured networks, in multi-hop ad-hoc networks each node acts as a router as well as sender and receiver.

Some applications, however, requires hierarchical arrangements that-for practical reasons-has to be done locally and self-organized.

An additional challenge is to deal with mobility that causes permanent network partitioning and re-organizations.

Technically, these problems can be tackled by providing additional uplinks to a backbone network, which can be used to access resources in the Internet as well as to inter-link multiple ad-hoc network partitions, creating a hybrid wireless network.

In this paper, we present a prototypically implemented hybrid wireless network system optimized for multimedia content distribution.

To efficiently manage the ad-hoc communicating devices a weighted clustering algorithm is introduced.

The proposed localized algorithm deals with mobility, but does not require geographical information or distances.

Today I read a paper titled “The Core of Directed Network Problems with Quotas”

The abstract is:
This paper proves the existence of non-empty cores for directed network problems with quotas and for those combinatorial allocation problems which permit only exclusive allocations.