Justin Lloyd's Thinkering

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.

Today I read a paper titled “A better lower bound for quantum algorithms searching an ordered list”

The abstract is:
We show that any quantum algorithm searching an ordered list of n elements needs to examine at least 1/12 log n-O(1) of them.

Classically, log n queries are both necessary and sufficient.

This shows that quantum algorithms can achieve only a constant speedup for this problem.

Our result improves lower bounds of Buhrman and de Wolf(quant-ph/9811046) and Farhi, Goldstone, Gutmann and Sipser (quant-ph/9812057).

Today I read a paper titled “Perception games, the image understanding and interpretational geometry”

The abstract is:
The interactive game theoretical approach to the description of perception processes is proposed.

The subject is treated formally in terms of a new class of the verbalizable interactive games which are called the perception games.

An application of the previously elaborated formalism of dialogues and verbalizable interactive games to the visual perception allows to combine the linguistic (such as formal grammars), psycholinguistic and (interactive) game theoretical methods for analysis of the image understanding by a human that may be also useful for the elaboration of computer vision systems.

By the way the interactive game theoretical aspects of interpretational geometries are clarified.