Archives for 2003

Today I read a paper titled “Forgetting Exceptions is Harmful in Language Learning”

The abstract is:
We show that in language learning, contrary to received wisdom, keeping exceptional training instances in memory can be beneficial for generalization accuracy.

We investigate this phenomenon empirically on a selection of benchmark natural language processing tasks: grapheme-to-phoneme conversion, part-of-speech tagging, prepositional-phrase attachment, and base noun phrase chunking.

In a first series of experiments we combine memory-based learning with training set editing techniques, in which instances are edited based on their typicality and class prediction strength.

Results show that editing exceptional instances (with low typicality or low class prediction strength) tends to harm generalization accuracy.

In a second series of experiments we compare memory-based learning and decision-tree learning methods on the same selection of tasks, and find that decision-tree learning often performs worse than memory-based learning.

Moreover, the decrease in performance can be linked to the degree of abstraction from exceptions (i.e., pruning or eagerness).

We provide explanations for both results in terms of the properties of the natural language processing tasks and the learning algorithms.

Today I read a paper titled “Word-Sense Disambiguation Using Decomposable Models”

The abstract is:
Most probabilistic classifiers used for word-sense disambiguation have either been based on only one contextual feature or have used a model that is simply assumed to characterize the interdependencies among multiple contextual features.

In this paper, a different approach to formulating a probabilistic model is presented along with a case study of the performance of models produced in this manner for the disambiguation of the noun “interest”.

We describe a method for formulating probabilistic models that use multiple contextual features for word-sense disambiguation, without requiring untested assumptions regarding the form of the model.

Using this approach, the joint distribution of all variables is described by only the most systematic variable interactions, thereby limiting the number of parameters to be estimated, supporting computational efficiency, and providing an understanding of the data..

Today I read a paper titled “The Minimum Expectation Selection Problem”

The abstract is:
We define the min-min expectation selection problem (resp.

max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp.

maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions.

We assume each distribution has finitely many atoms.

Let d be the number of distinct values in the support of the distributions.

We show that if d is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme.

For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor.

The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d.

We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.

Today I read a paper titled “The Generalized Universal Law of Generalization”

The abstract is:
It has been argued by Shepard that there is a robust psychological law that relates the distance between a pair of items in psychological space and the probability that they will be confused with each other.

Specifically, the probability of confusion is a negative exponential function of the distance between the pair of items.

In experimental contexts, distance is typically defined in terms of a multidimensional Euclidean space-but this assumption seems unlikely to hold for complex stimuli.

We show that, nonetheless, the Universal Law of Generalization can be derived in the more complex setting of arbitrary stimuli, using a much more universal measure of distance.

This universal distance is defined as the length of the shortest program that transforms the representations of the two items of interest into one another: the algorithmic information distance.

It is universal in the sense that it minorizes every computable distance: it is the smallest computable distance.

We show that the universal law of generalization holds with probability going to one-provided the confusion probabilities are computable.

We also give a mathematically more appealing form .