Archives for 2001

Today I read a paper titled “Memory-Based Lexical Acquisition and Processing”

The abstract is:
Current approaches to computational lexicology in language technology are knowledge-based (competence-oriented) and try to abstract away from specific formalisms, domains, and applications.

This results in severe complexity, acquisition and reusability bottlenecks.

As an alternative, we propose a particular performance-oriented approach to Natural Language Processing based on automatic memory-based learning of linguistic (lexical) tasks.

The consequences of the approach for computational lexicology are discussed, and the application of the approach on a number of lexical acquisition and disambiguation tasks in phonology, morphology and syntax is described..

Today I read a paper titled “A Learning Approach to Natural Language Understanding”

The abstract is:
In this paper we propose a learning paradigm for the problem of understanding spoken language.

The basis of the work is in a formalization of the understanding problem as a communication problem.

This results in the definition of a stochastic model of the production of speech or text starting from the meaning of a sentence.

The resulting understanding algorithm consists in a Viterbi maximization procedure, analogous to that commonly used for recognizing speech..

Today I read a paper titled “A Theory of Universal Artificial Intelligence based on Algorithmic Complexity”

The abstract is:
Decision theory formally solves the problem of rational agents in uncertain worlds if the true environmental prior probability distribution is known.

Solomonoff’s theory of universal induction formally solves the problem of sequence prediction for unknown prior distribution.

We combine both ideas and get a parameterless theory of universal Artificial Intelligence.

We give strong arguments that the resulting AIXI model is the most intelligent unbiased agent possible.

We outline for a number of problem classes, including sequence prediction, strategic games, function minimization, reinforcement and supervised learning, how the AIXI model can formally solve them.

The major drawback of the AIXI model is that it is uncomputable.

To overcome this problem, we construct a modified algorithm AIXI-tl, which is still effectively more intelligent than any other time t and space l bounded agent.

The computation time of AIXI-tl is of the order tx2^l.

Other discussed topics are formal definitions of intelligence order relations, the horizon problem and relations of the AIXI theory to other AI approaches.

Today I read a paper titled “A note on quantum black-box complexity of almost all Boolean functions”

The abstract is:
We show that, for almost all N-variable Boolean functions f, at least N/4-O(\sqrt{N} log N) queries are required to compute f in quantum black-box model with bounded error.

Today I read a paper titled “Chess Pure Strategies are Probably Chaotic”

The abstract is:
It is odd that chess grandmasters often disagree in their analysis of positions, sometimes even of simple ones, and that a grandmaster can hold his own against an powerful analytic machine such as Deep Blue.

The fact that there must exist pure winning strategies for chess is used to construct a control strategy function.

It is then shown that chess strategy is equivalent to an autonomous system of differential equations, and conjectured that the system is chaotic.

If true the conjecture would explain the forenamed peculiarities and would also imply that there cannot exist a static evaluator for chess.

Today I read a paper titled “A Scrollbar-based Visualization for Document Navigation”

The abstract is:
We are interested in questions of improving user control in best-match text-retrieval systems, specifically questions as to whether simple visualizations that nonetheless go beyond the minimal ones generally available can significantly help users.

Recently, we have been investigating ways to help users decide-given a set of documents retrieved by a query-which documents and passages are worth closer examination.

We built a document viewer incorporating a visualization centered around a novel content-displaying scrollbar and color term highlighting, and studied whether the visualization is helpful to non-expert searchers.

Participants’ reaction to the visualization was very positive, while the objective results were inconclusive.

Today I read a paper titled “Towards a computational theory of human daydreaming”

The abstract is:
This paper examines the phenomenon of daydreaming: spontaneously recalling or imagining personal or vicarious experiences in the past or future.

The following important roles of daydreaming in human cognition are postulated: plan preparation and rehearsal, learning from failures and successes, support for processes of creativity, emotion regulation, and motivation.

A computational theory of daydreaming and its implementation as the program DAYDREAMER are presented.

DAYDREAMER consists of 1) a scenario generator based on relaxed planning, 2) a dynamic episodic memory of experiences used by the scenario generator, 3) a collection of personal goals and control goals which guide the scenario generator, 4) an emotion component in which daydreams initiate, and are initiated by, emotional states arising from goal outcomes, and 5) domain knowledge of interpersonal relations and common everyday occurrences.

The role of emotions and control goals in daydreaming is discussed.

Four control goals commonly used in guiding daydreaming are presented: rationalization, failure/success reversal, revenge, and preparation.

The role of episodic memory in daydreaming is considered, including how daydreamed information is incorporated into memory and later used.

An initial version of DAYDREAMER which produces several daydreams (in English) is currently running.

Today I read a paper titled “Average-Case Complexity of Shellsort”

The abstract is:
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $\Omega (pn^{1 + 1/p)$ for all $p \leq \log n$.

Using similar arguments, we analyze the average-case complexity of several other sorting algorithms.

Today I read a paper titled “Speech Dialogue with Facial Displays: Multimodal Human-Computer Conversation”

The abstract is:
Human face-to-face conversation is an ideal model for human-computer dialogue.

One of the major features of face-to-face communication is its multiplicity of communication channels that act on multiple modalities.

To realize a natural multimodal dialogue, it is necessary to study how humans perceive information and determine the information to which humans are sensitive.

A face is an independent communication channel that conveys emotional and conversational signals, encoded as facial expressions.

We have developed an experimental system that integrates speech dialogue and facial animation, to investigate the effect of introducing communicative facial expressions as a new modality in human-computer conversation.

Our experiments have shown that facial expressions are helpful, especially upon first contact with the system.

We have also discovered that featuring facial expressions at an early stage improves subsequent interaction..