Archives for 2001

Today I read a paper titled “Syntactic-Head-Driven Generation”

The abstract is:
The previously proposed semantic-head-driven generation methods run into problems if none of the daughter constituents in the syntacto-semantic rule schemata of a grammar fits the definition of a semantic head given in Shieber et al.

1990.

This is the case for the semantic analysis rules of certain constraint-based semantic representations, e.g.

Underspecified Discourse Representation Structures (UDRSs) (Frank/Reyle 1992).

Since head-driven generation in general has its merits, we simply return to a syntactic definition of `head’ and demonstrate the feasibility of syntactic-head-driven generation.

In addition to its generality, a syntactic-head-driven algorithm provides a basis for a logically well-defined treatment of the movement of (syntactic) heads, for which only ad-hoc solutions existed, so far..

Today I read a paper titled “Complexity limitations on quantum computation”

The abstract is:
We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation.

We show several results for the probabilistic quantum class BQP.

1.

BQP is low for PP, i.e., PP^BQP=PP.

2.

There exists a relativized world where P=BQP and the polynomial-time hierarchy is infinite.

3.

There exists a relativized world where BQP does not have complete sets.

4.

There exists a relativized world where P=BQP but P is not equal to UP intersect coUP and one-way functions exist.

This gives a relativized answer to an open question of Simon.

Today I read a paper titled “Character design for soccer commmentary”

The abstract is:
In this paper we present early work on an animated talking head commentary system called {\bf Byrne}\footnote{David Byrne is the lead singer of the Talking Heads.}.

The goal of this project is to develop a system which can take the output from the RoboCup soccer simulator, and generate appropriate affective speech and facial expressions, based on the character’s personality, emotional state, and the state of play.

Here we describe a system which takes pre-analysed simulator output as input, and which generates text marked-up for use by a speech generator and a face animation system.

We make heavy use of inter-system standards, so that future versions of Byrne will be able to take advantage of advances in the technologies that it incorporates.

Today I read a paper titled “Simple and Superlattice Turing Patterns in Reaction-Diffusion Systems: Bifurcation, Bistability, and Parameter Collapse”

The abstract is:
This paper investigates the competition between both simple (e.g.

stripes, hexagons) and “superlattice” (super squares, super hexagons) Turing patterns in two-component reaction-diffusion systems.

“Superlattice” patterns are formed from eight or twelve Fourier modes, and feature structure at two different length scales.

Using perturbation theory, we derive simple analytical expressions for the bifurcation equation coefficients on both rhombic and hexagonal lattices.

These expressions show that, no matter how complicated the reaction kinectics, the nonlinear reaction terms reduce to just four effective terms within the bifurcation equation coefficients.

Moreover, at the hexagonal degeneracy — when the quadratic term in the hexagonal bifurcation equation disappears — the number of effective system parameters drops to two, allowing a complete characterization of the possible bifurcation results at this degeneracy.

The general results are then applied to specific model equations, to investigate the stability of different patterns within those models.

Today I read a paper titled “Cached Sufficient Statistics for Efficient Machine Learning with Large Datasets”

The abstract is:
This paper introduces new algorithms and data structures for quick counting for machine learning datasets.

We focus on the counting task of constructing contingency tables, but our approach is also applicable to counting the number of records in a dataset that match conjunctive queries.

Subject to certain assumptions, the costs of these operations can be shown to be independent of the number of records in the dataset and loglinear in the number of non-zero entries in the contingency table.

We provide a very sparse data structure, the ADtree, to minimize memory use.

We provide analytical worst-case bounds for this structure for several models of data distribution.

We empirically demonstrate that tractably-sized data structures can be produced for large real-world datasets by (a) using a sparse tree structure that never allocates memory for counts of zero, (b) never allocating memory for counts that can be deduced from other counts, and (c) not bothering to expand the tree fully near its leaves.

We show how the ADtree can be used to accelerate Bayes net structure finding algorithms, rule learning algorithms, and feature selection algorithms, and we provide a number of empirical results comparing ADtree methods against traditional direct counting approaches.

We also discuss the possible uses of ADtrees in other machine learning methods, and discuss the merits of ADtrees in comparison with alternative representations such as kd-trees, R-trees and Frequent Sets.