justin

Today I read a paper titled “A Maximum-Entropy Partial Parser for Unrestricted Text”

The abstract is:
This paper describes a partial parser that assigns syntactic structures to sequences of part-of-speech tags.

The program uses the maximum entropy parameter estimation method, which allows a flexible combination of different knowledge sources: the hierarchical structure, parts of speech and phrasal categories.

In effect, the parser goes beyond simple bracketing and recognises even fairly complex structures.

We give accuracy figures for different applications of the parser.

Today I read a paper titled “Similarity-Based Estimation of Word Cooccurrence Probabilities”

The abstract is:
In many applications of natural language processing it is necessary to determine the likelihood of a given word combination.

For example, a speech recognizer may need to determine which of the two word combinations “eat a peach” and “eat a beach” is more likely.

Statistical NLP methods determine the likelihood of a word combination according to its frequency in a training corpus.

However, the nature of language is such that many word combinations are infrequent and do not occur in a given corpus.

In this work we propose a method for estimating the probability of such previously unseen word combinations using available information on “most similar” words.

We describe a probabilistic word association model based on distributional word similarity, and apply it to improving probability estimates for unseen word bigrams in a variant of Katz’s back-off model.

The similarity-based method yields a 20% perplexity improvement in the prediction of unseen bigrams and statistically significant reductions in speech-recognition error..

Today I read a paper titled “Principles and Implementation of Deductive Parsing”

The abstract is:
We present a system for generating parsers based directly on the metaphor of parsing as deduction.

Parsing algorithms can be represented directly as deduction systems, and a single deduction engine can interpret such deduction systems so as to implement the corresponding parser.

The method generalizes easily to parsers for augmented phrase structure formalisms, such as definite-clause grammars and other logic grammar formalisms, and has been used for rapid prototyping of parsing algorithms for a variety of formalisms including variants of tree-adjoining grammars, categorial grammars, and lexicalized context-free grammars..

Today I read a paper titled “Constraint-Based Categorial Grammar”

The abstract is:
We propose a generalization of Categorial Grammar in which lexical categories are defined by means of recursive constraints.

In particular, the introduction of relational constraints allows one to capture the effects of (recursive) lexical rules in a computationally attractive manner.

We illustrate the linguistic merits of the new approach by showing how it accounts for the syntax of Dutch cross-serial dependencies and the position and scope of adjuncts in such constructions.

Delayed evaluation is used to process grammars containing recursive constraints..

Today I read a paper titled “Lessons from a Restricted Turing Test”

The abstract is:
We report on the recent Loebner prize competition inspired by Turing’s test of intelligent behavior.

The presentation covers the structure of the competition and the outcome of its first instantiation in an actual event, and an analysis of the purpose, design, and appropriateness of such a competition.

We argue that the competition has no clear purpose, that its design prevents any useful outcome, and that such a competition is inappropriate given the current level of technology.

We then speculate as to suitable alternatives to the Loebner prize..

Today I read a paper titled “Structural Tags, Annealing and Automatic Word Classification”

The abstract is:
This paper describes an automatic word classification system which uses a locally optimal annealing algorithm and average class mutual information.

A new word-class representation, the structural tag is introduced and its advantages for use in statistical language modelling are presented.

A summary of some results with the one million word LOB corpus is given; the algorithm is also shown to discover the vowel-consonant distinction and displays an ability to cluster words syntactically in a Latin corpus.

Finally, a comparison is made between the current classification system and several leading alternative systems, which shows that the current system performs respectably well..

Today I read a paper titled “A complete anytime algorithm for balanced number partitioning”

The abstract is:
Given a set of numbers, the balanced partioning problem is to divide them into two subsets, so that the sum of the numbers in each subset are as nearly equal as possible, subject to the constraint that the cardinalities of the subsets be within one of each other.

We combine the balanced largest differencing method (BLDM) and Korf’s complete Karmarkar-Karp algorithm to get a new algorithm that optimally solves the balanced partitioning problem.

For numbers with twelve significant digits or less, the algorithm can optimally solve balanced partioning problems of arbitrary size in practice.

For numbers with greater precision, it first returns the BLDM solution, then continues to find better solutions as time allows.