Archives for 2007

Today I read a paper titled “A constructive and unifying framework for zero-bit watermarking”

The abstract is:
In the watermark detection scenario, also known as zero-bit watermarking, a watermark, carrying no hidden message, is inserted in content.

The watermark detector checks for the presence of this particular weak signal in content.

The article looks at this problem from a classical detection theory point of view, but with side information enabled at the embedding side.

This means that the watermark signal is a function of the host content.

Our study is twofold.

The first step is to design the best embedding function for a given detection function, and the best detection function for a given embedding function.

This yields two conditions, which are mixed into one `fundamental’ partial differential equation.

It appears that many famous watermarking schemes are indeed solution to this `fundamental’ equation.

This study thus gives birth to a constructive framework unifying solutions, so far perceived as very different.

Today I read a paper titled “Design Guidelines for Landmarks to Support Navigation in Virtual Environments”

The abstract is:
Unfamiliar, large-scale virtual environments are difficult to navigate.

This paper presents design guidelines to ease navigation in such virtual environments.

The guidelines presented here focus on the design and placement of landmarks in virtual environments.

Moreover, the guidelines are based primarily on the extensive empirical literature on navigation in the real world.

A rationale for this approach is provided by the similarities between navigational behavior in real and virtual environments.

Today I read a paper titled “Lexical Acquisition via Constraint Solving”

The abstract is:
This paper describes a method to automatically acquire the syntactic and semantic classifications of unknown words.

Our method reduces the search space of the lexical acquisition problem by utilizing both the left and the right context of the unknown word.

Link Grammar provides a convenient framework in which to implement our method..

Today I read a paper titled “Achievable Rates for Pattern Recognition”

The abstract is:
Biological and machine pattern recognition systems face a common challenge: Given sensory data about an unknown object, classify the object by comparing the sensory data with a library of internal representations stored in memory.

In many cases of interest, the number of patterns to be discriminated and the richness of the raw data force recognition systems to internally represent memory and sensory information in a compressed format.

However, these representations must preserve enough information to accommodate the variability and complexity of the environment, or else recognition will be unreliable.

Thus, there is an intrinsic tradeoff between the amount of resources devoted to data representation and the complexity of the environment in which a recognition system may reliably operate.

In this paper we describe a general mathematical model for pattern recognition systems subject to resource constraints, and show how the aforementioned resource-complexity tradeoff can be characterized in terms of three rates related to number of bits available for representing memory and sensory data, and the number of patterns populating a given statistical environment.

We prove single-letter information theoretic bounds governing the achievable rates, and illustrate the theory by analyzing the elementary cases where the pattern data is either binary or Gaussian.

Today I read a paper titled “Chaos and Annealing in Social networks”

The abstract is:
In this work we compare social clusters with spin clusters and compare different properties.

We also try to compare phase changes in market and labor stratification with phase changes of spin clusters.

Then we compare the requisites for redrawing the boundaries of social clusters with respect to energy minimization and efficiency.

We finally do a simulation experiment and show that by choosing suitable link matrices for agents and attributes of the same and of different agents it is possible to have at the same time behavior similar to chaos or punctuated equilibrium in some attributes or fairly regular oscillations of preferences for other attributes, using greatest utility or efficiency as a criterion for change in conflicting social networks with different agents having different preferences with respect to the attributes in the agent himself or with similar attributes in other agents.

Today I read a paper titled “On the Implicit and on the Artificial – Morphogenesis and Emergent Aesthetics in Autonomous Collective Systems”

The abstract is:
Imagine a “machine” where there is no pre-commitment to any particular representational scheme: the desired behaviour is distributed and roughly specified simultaneously among many parts, but there is minimal specification of the mechanism required to generate that behaviour, i.e.

the global behaviour evolves from the many relations of multiple simple behaviours.

A machine that lives to and from/with Synergy.

An artificial super-organism that avoids specific constraints and emerges within multiple low-level implicit bio-inspired mechanisms.

KEYWORDS: Complex Science, ArtSBots Project, Swarm Intelligence, Stigmergy, UnManned Art, Symbiotic Art, Swarm Paintings, Robot Paintings, Non-Human Art, Painting Emergence and Cooperation, Art and Complexity, ArtBots: The Robot Talent Show.

Today I read a paper titled “Intelligent Systems: Architectures and Perspectives”

The abstract is:
The integration of different learning and adaptation techniques to overcome individual limitations and to achieve synergetic effects through the hybridization or fusion of these techniques has, in recent years, contributed to a large number of new intelligent system designs.

Computational intelligence is an innovative framework for constructing intelligent hybrid architectures involving Neural Networks (NN), Fuzzy Inference Systems (FIS), Probabilistic Reasoning (PR) and derivative free optimization techniques such as Evolutionary Computation (EC).

Most of these hybridization approaches, however, follow an ad hoc design methodology, justified by success in certain application domains.

Due to the lack of a common framework it often remains difficult to compare the various hybrid systems conceptually and to evaluate their performance comparatively.

This chapter introduces the different generic architectures for integrating intelligent systems.

The designing aspects and perspectives of different hybrid archirectures like NN-FIS, EC-FIS, EC-NN, FIS-PR and NN-FIS-EC systems are presented.

Some conclusions are also provided towards the end.

Today I read a paper titled “Bidding to the Top: VCG and Equilibria of Position-Based Auctions”

The abstract is:
Many popular search engines run an auction to determine the placement of advertisements next to search results.

Current auctions at Google and Yahoo! let advertisers specify a single amount as their bid in the auction.

This bid is interpreted as the maximum amount the advertiser is willing to pay per click on its ad.

When search queries arrive, the bids are used to rank the ads linearly on the search result page.

The advertisers pay for each user who clicks on their ad, and the amount charged depends on the bids of all the advertisers participating in the auction.

In order to be effective, advertisers seek to be as high on the list as their budget permits, subject to the market.

We study the problem of ranking ads and associated pricing mechanisms when the advertisers not only specify a bid, but additionally express their preference for positions in the list of ads.

In particular, we study “prefix position auctions” where advertiser $i$ can specify that she is interested only in the top $b_i$ positions.

We present a simple allocation and pricing mechanism that generalizes the desirable properties of current auctions that do not have position constraints.

In addition, we show that our auction has an “envy-free” or “symmetric” Nash equilibrium with the same outcome in allocation and pricing as the well-known truthful Vickrey-Clarke-Groves (VCG) auction.

Furthermore, we show that this equilibrium is the best such equilibrium for the advertisers in terms of the profit made by each advertiser.

We also discuss other position-based auctions.

Today I read a paper titled “Evolution of Neural Networks to Play the Game of Dots-and-Boxes”

The abstract is:
Dots-and-Boxes is a child’s game which remains analytically unsolved.

We implement and evolve artificial neural networks to play this game, evaluating them against simple heuristic players.

Our networks do not evaluate or predict the final outcome of the game, but rather recommend moves at each stage.

Superior generalisation of play by co-evolved populations is found, and a comparison made with networks trained by back-propagation using simple heuristics as an oracle.

Today I read a paper titled “Distributed Control by Lagrangian Steepest Descent”

The abstract is:
Often adaptive, distributed control can be viewed as an iterated game between independent players.

The coupling between the players’ mixed strategies, arising as the system evolves from one instant to the next, is determined by the system designer.

Information theory tells us that the most likely joint strategy of the players, given a value of the expectation of the overall control objective function, is the minimizer of a Lagrangian function of the joint strategy.

So the goal of the system designer is to speed evolution of the joint strategy to that Lagrangian minimizing point, lower the expectated value of the control objective function, and repeat.

Here we elaborate the theory of algorithms that do this using local descent procedures, and that thereby achieve efficient, adaptive, distributed control.

Today I read a paper titled “Self-organizing traffic lights: A realistic simulation”

The abstract is:
We have previously shown in an abstract simulation (Gershenson, 2005) that self-organizing traffic lights can improve greatly traffic flow for any density.

In this paper, we extend these results to a realistic setting, implementing self-organizing traffic lights in an advanced traffic simulator using real data from a Brussels avenue.

On average, for different traffic densities, travel waiting times are reduced by 50% compared to the current green wave method.

Today I read a paper titled “The Google Similarity Distance”

The abstract is:
Words and phrases acquire meaning from the way they are used in society, from their relative semantics to other words and phrases.

For computers the equivalent of `society’ is `database,’ and the equivalent of `use’ is `way to search the database.’ We present a new theory of similarity between words and phrases based on information distance and Kolmogorov complexity.

To fix thoughts we use the world-wide-web as database, and Google as search engine.

The method is also applicable to other search engines and databases.

This theory is then applied to construct a method to automatically extract similarity, the Google similarity distance, of words and phrases from the world-wide-web using Google page counts.

The world-wide-web is the largest database on earth, and the context information entered by millions of independent users averages out to provide automatic semantics of useful quality.

We give applications in hierarchical clustering, classification, and language translation.

We give examples to distinguish between colors and numbers, cluster names of paintings by 17th century Dutch masters and names of books by English novelists, the ability to understand emergencies, and primes, and we demonstrate the ability to do a simple automatic English-Spanish translation.

Finally, we use the WordNet database as an objective baseline against which to judge the performance of our method.

We conduct a massive randomized trial in binary classification using support vector machines to learn categories based on our Google distance, resulting in an a mean agreement of 87% with the expert crafted WordNet categories.