Archives for 2002

Today I read a paper titled “The Rough Guide to Constraint Propagation”

The abstract is:
We provide here a simple, yet very general framework that allows us to explain several constraint propagation algorithms in a systematic way.

In particular, using the notions commutativity and semi-commutativity, we show how the well-known AC-3, PC-2, DAC and DPC algorithms are instances of a single generic algorithm.

The work reported here extends and simplifies that of Apt, cs.AI/9811024.

Today I read a paper titled “Mutual Search”

The abstract is:
We introduce a search problem called “mutual search” where $k$ \agents, arbitrarily distributed over $n$ sites, are required to locate one another by posing queries of the form “Anybody at site $i$?”.

We ask for the least number of queries that is necessary and sufficient.

For the case of two \agents using deterministic protocols we obtain the following worst-case results: In an oblivious setting (where all pre-planned queries are executed) there is no savings: $n-1$ queries are required and are sufficient.

In a nonoblivious setting we can exploit the paradigm of “no news is also news” to obtain significant savings: in the synchronous case $0.586n$ queries suffice and $0.536n$ queries are required; in the asynchronous case $0.896n$ queries suffice and a fortiori 0.536 queries are required; for $o(\sqrt{n})$ \agents using a deterministic protocol less than $n$ queries suffice; there is a simple randomized protocol for two \agents with worst-case expected $0.5n$ queries and all randomized protocols require at least $0.125n$ worst-case expected queries.

The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.

Today I read a paper titled “Evolution of genetic organization in digital organisms”

The abstract is:
We examine the evolution of expression patterns and the organization of genetic information in populations of self-replicating digital organisms.

Seeding the experiments with a linearly expressed ancestor, we witness the development of complex, parallel secondary expression patterns.

Using principles from information theory, we demonstrate an evolutionary pressure towards overlapping expressions causing variation (and hence further evolution) to sharply drop.

Finally, we compare the overlapping sections of dominant genomes to those portions which are singly expressed and observe a significant difference in the entropy of their encoding.

Today I read a paper titled “Constraint Logic Programming for Natural Language Processing”

The abstract is:
This paper proposes an evaluation of the adequacy of the constraint logic programming paradigm for natural language processing.

Theoretical aspects of this question have been discussed in several works.

We adopt here a pragmatic point of view and our argumentation relies on concrete solutions.

Using actual contraints (in the CLP sense) is neither easy nor direct.

However, CLP can improve parsing techniques in several aspects such as concision, control, efficiency or direct representation of linguistic formalism.

This discussion is illustrated by several examples and the presentation of an HPSG parser..

Today I read a paper titled “From Alife Agents to a Kingdom of N Queens”

The abstract is:
This paper presents a new approach to solving N-queen problems, which involves a model of distributed autonomous agents with artificial life (ALife) and a method of representing N-queen constraints in an agent environment.

The distributed agents locally interact with their living environment, i.e., a chessboard, and execute their reactive behaviors by applying their behavioral rules for randomized motion, least-conflict position searching, and cooperating with other agents etc.

The agent-based N-queen problem solving system evolves through selection and contest according to the rule of Survival of the Fittest, in which some agents will die or be eaten if their moving strategies are less efficient than others.

The experimental results have shown that this system is capable of solving large-scale N-queen problems.

This paper also provides a model of ALife agents for solving general CSPs.

Today I read a paper titled “A Classification Approach to Word Prediction”

The abstract is:
The eventual goal of a language model is to accurately predict the value of a missing word given its context.

We present an approach to word prediction that is based on learning a representation for each word as a function of words and linguistics predicates in its context.

This approach raises a few new questions that we address.

First, in order to learn good word representations it is necessary to use an expressive representation of the context.

We present a way that uses external knowledge to generate expressive context representations, along with a learning method capable of handling the large number of features generated this way that can, potentially, contribute to each prediction.

Second, since the number of words “competing” for each prediction is large, there is a need to “focus the attention” on a smaller subset of these.

We exhibit the contribution of a “focus of attention” mechanism to the performance of the word predictor.

Finally, we describe a large scale experimental study in which the approach presented is shown to yield significant improvements in word prediction tasks.

Today I read a paper titled “Linear and Order Statistics Combiners for Pattern Classification”

The abstract is:
Several researchers have experimentally shown that substantial improvements can be obtained in difficult pattern recognition problems by combining or integrating the outputs of multiple classifiers.

This chapter provides an analytical framework to quantify the improvements in classification results due to combining.

The results apply to both linear combiners and order statistics combiners.

We first show that to a first order approximation, the error rate obtained over and above the Bayes error rate, is directly proportional to the variance of the actual decision boundaries around the Bayes optimum boundary.

Combining classifiers in output space reduces this variance, and hence reduces the “added” error.

If N unbiased classifiers are combined by simple averaging, the added error rate can be reduced by a factor of N if the individual errors in approximating the decision boundaries are uncorrelated.

Expressions are then derived for linear combiners which are biased or correlated, and the effect of output correlations on ensemble performance is quantified.

For order statistics based non-linear combiners, we derive expressions that indicate how much the median, the maximum and in general the ith order statistic can improve classifier performance.

The analysis presented here facilitates the understanding of the relationships among error rates, classifier boundary distributions, and combining in output space.

Experimental results on several public domain data sets are provided to illustrate the benefits of combining and to support the analytical results.