justin

Today I read a paper titled “Natural Language Parsing as Statistical Pattern Recognition”

The abstract is:
Traditional natural language parsers are based on rewrite rule systems developed in an arduous, time-consuming manner by grammarians.

A majority of the grammarian’s efforts are devoted to the disambiguation process, first hypothesizing rules which dictate constituent categories and relationships among words in ambiguous sentences, and then seeking exceptions and corrections to these rules.

In this work, I propose an automatic method for acquiring a statistical parser from a set of parsed sentences which takes advantage of some initial linguistic input, but avoids the pitfalls of the iterative and seemingly endless grammar development process.

Based on distributionally-derived and linguistically-based features of language, this parser acquires a set of statistical decision trees which assign a probability distribution on the space of parse trees given the input sentence.

These decision trees take advantage of significant amount of contextual information, potentially including all of the lexical information in the sentence, to produce highly accurate statistical models of the disambiguation process.

By basing the disambiguation criteria selection on entropy reduction rather than human intuition, this parser development method is able to consider more sentences than a human grammarian can when making individual disambiguation rules.

In experiments between a parser, acquired using this statistical framework, and a grammarian’s rule-based parser, developed over a ten-year period, both using the same training material and test sentences, the decision tree parser significantly outperformed the grammar-based parser on the accuracy measure which the grammarian was trying to maximize, achieving an accuracy of 78% compared to the grammar-based parser’s 69%..

Today I read a paper titled “Reversible Simulation of Irreversible Computation by Pebble Games”

The abstract is:
Reversible simulation of irreversible algorithms is analyzed in the stylized form of a `reversible’ pebble game.

While such simulations incur little overhead in additional computation time, they use a large amount of additional memory space during the computation.

The reacheable reversible simulation instantaneous descriptions (pebble configurations) are characterized completely.

As a corollary we obtain the reversible simulation by Bennett and that among all simulations that can be modelled by the pebble game, Bennett’s simulation is optimal in that it uses the least auxiliary space for the greatest number of simulated steps.

One can reduce the auxiliary storage overhead incurred by the reversible simulation at the cost of allowing limited erasing leading to an irreversibility-space tradeoff.

We show that in this resource-bounded setting the limited erasing needs to be performed at precise instants during the simulation.

We show that the reversible simulation can be modified so that it is applicable also when the simulated computation time is unknown.

Today I read a paper titled “Differential interactive games: The short-term predictions”

The abstract is:
Procedures of the short-term predictions for processes in general 2-person differential interactive games are proposed.

Their effectiveness is discussed.

Today I read a paper titled “Priority Union and Generalization in Discourse Grammars”

The abstract is:
We describe an implementation in Carpenter’s typed feature formalism, ALE, of a discourse grammar of the kind proposed by Scha, Polanyi, et al.

We examine their method for resolving parallelism-dependent anaphora and show that there is a coherent feature-structural rendition of this type of grammar which uses the operations of priority union and generalization.

We describe an augmentation of the ALE system to encompass these operations and we show that an appropriate choice of definition for priority union gives the desired multiple output for examples of VP-ellipsis which exhibit a strict/sloppy ambiguity..

Today I read a paper titled “Lifeworld Analysis”

The abstract is:
We argue that the analysis of agent/environment interactions should be extended to include the conventions and invariants maintained by agents throughout their activity.

We refer to this thicker notion of environment as a lifeworld and present a partial set of formal tools for describing structures of lifeworlds and the ways in which they computationally simplify activity.

As one specific example, we apply the tools to the analysis of the Toast system and show how versions of the system with very different control structures in fact implement a common control structure together with different conventions for encoding task state in the positions or states of objects in the environment.