Classification of finite sequences without explicit knowledge of their statistical nature is a fundamental problem with many important applications. We propose a new information theoretic approach to this problem which is based on the following ingredients: (i) sequences aresimilar when they are likely to be generated by the same source; (ii) cross entropies can be estimated via "universal compression"; (iii)Markovian sequences can be asymptotically-optimally merged. With these ingredients we design a method for the classification of discrete sequences whenever they can be compressed. We introduce the method and illustrate its application for hierarchical clustering of languages and for estimating similarities of protein sequences.

The inverse of the Fisher information matrix is used in the natural gradientdescent algorithm to train single-layer and multi-layer perceptrons. We have discovered a new scheme to represent the Fisher information matrix of a stochastic multi-layer perceptron. Based on this scheme, we have designed an algorithm to compute the natural gradient. When the input dimension n is much larger than the number of hidden neurons, the complexity of this algorithm isof order O(n). It is confirmed by simulations that the natural gradient descent learning rule is not only efficient but also robust. 1 INTRODUCTION The inverse of the Fisher information matrix is required to find the Cramer-Rae lower bound to analyze the performance of an unbiased estimator. It is also needed in the natural gradient learning framework (Amari, 1997) to design statistically efficient algorithms for estimating parameters in general and for training neural networks in particular. In this paper, we assume a stochastic model for multilayer perceptrons.Considering a Riemannian parameter space in which the Fisher information matrix is a metric tensor, we apply the natural gradient learning rule to train single-layer and multi-layer perceptrons. The main difficulty encountered is to compute the inverse of the Fisher information matrix of large dimensions when the input dimension is high. By exploring the structure of the Fisher information matrix and its inverse, we design a fast algorithm with lower complexity to implement the natural gradient learning algorithm.

Using displays of line orientations taken from Wolfe's experiments [1992], we study the hypothesis that the distinction between parallel versus serial processes arises from the availability of global information in the internal representations of the visual scene. The model operates in two phases. First, the visual displays are compressed via principal-component-analysis. Second, the compressed data is processed by a target detector module inorder to identify the existence of a target in the display. Our main finding is that targets in displays which were found experimentally tobe processed in parallel can be detected by the system, while targets in experimentally-serial displays cannot. This fundamental difference is explained via variance analysis of the compressed representations, providing a numerical criterion distinguishing parallelfrom serial displays. Our model yields a mapping of response-time slopes that is similar to Duncan and Humphreys's "search surface" [1989], providing an explicit formulation of their intuitive notion of feature similarity. It presents a neural realization ofthe processing that may underlie the classical metaphorical explanations of visual search.

The problem of time series prediction is studied within the uniform convergence frameworkof Vapnik and Chervonenkis. The dependence inherent in the temporal structure is incorporated into the analysis, thereby generalizing the available theory for memoryless processes. Finite sample boundsare calculated in terms of covering numbers of the approximating class,and the tradeoff between approximation and estimation is discussed. A complexity regularization approach is outlined, based on Vapnik's method of Structural Risk Minimization, and shown to be applicable inthe context of mixing stochastic processes.

Using displays of line orientations taken from Wolfe's experiments [1992], we study the hypothesis that the distinction between parallel versus serial processes arises from the availability of global information in the internal representations of the visual scene. The model operates in two phases. First, the visual displays are compressed via principal-component-analysis. Second, the compressed data is processed by a target detector module inorder to identify the existence of a target in the display. Our main finding is that targets in displays which were found experimentally tobe processed in parallel can be detected by the system, while targets in experimentally-serial displays cannot. This fundamental difference is explained via variance analysis of the compressed representations, providing a numerical criterion distinguishing parallelfrom serial displays. Our model yields a mapping of response-time slopes that is similar to Duncan and Humphreys's "search surface" [1989], providing an explicit formulation of their intuitive notion of feature similarity. It presents a neural realization ofthe processing that may underlie the classical metaphorical explanations of visual search.

The National Aeronautics and Space Administration Jet Propulsion Laboratory (Pasadena, Calif.) has developed The chip, which has The National Aeronautics and Chester, N.Y.) to improve its ability to been licensed by automaker Ford Space Administration (NASA) Goddard match reported wage information. Motor (Dearborn, Mich.), is designed Space Flight Center (Greenbelt, The solution will help the agency to augment current vehicle on-board Md.) has developed the The Philippines (Quezon City, The process for outside scientists wanting RoyScot Trust, the asset finance arm Philippines) has adopted an intelligent to use NASA's space telescopes. of the Royal Bank of Scotland (Edinburgh, agent-based software system to The system is designed to capture and Scotland), has implemented an manage mission-critical tax processes maintain key scientific knowledge expert system-based solution to automate across The Philippines. The intelligent while it reduces common errors made the credit-underwriting process. The firm has set up a credit control management of the bureau's entire Johnson Controls (Milwaukee, Wis.), system, The turnkey expert installs and maintains. By integrating component has deployed a speech-recognition- frequent air travelers through U.S. math data with work-cell visualization based application for its frequent flier Immigration inspection in less than software, engineers can simulate customers.

This article introduces a generic framework for constraint-directed search. The research literature in constraint-directed scheduling is placed within the framework both to provide insight into, and examples of, the framework and to allow a new perspective on the scheduling literature. We show how a number of algorithms from the constraint-directed scheduling research can be conceptualized within the framework. This conceptualization allows us to identify and compare variations of components of our framework and provides new perspective on open research issues. We discuss the prospects for an overall comparison of scheduling strategies and show that firm conclusions vis-a-vis such a comparison are not supported by the literature. Our principal conclusion is the need for an empirical model of both the characteristics of scheduling problems and the solution techniques themselves. Our framework is offered as a tool for the development of such an understanding of constraint-directed scheduling and, more generally, constraint-directed search.

A class of interval-based temporal languages for uniformly representing and reasoning about actions and plans is presented. Actions are represented by describing what is true while the action itself is occurring, and plans are constructed by temporally relating actions and world states. The temporal languages are members of the family of Description Logics, which are characterized by high expressivity combined with good computational properties. The subsumption problem for a class of temporal Description Logics is investigated and sound and complete decision procedures are given. The basic language TL-F is considered first: it is the composition of a temporal logic TL -- able to express interval temporal networks -- together with the non-temporal logic F -- a Feature Description Logic. It is proven that subsumption in this language is an NP-complete problem. Then it is shown how to reason with the more expressive languages TLU-FU and TL-ALCF. The former adds disjunction both at the temporal and non-temporal sides of the language, the latter extends the non-temporal side with set-valued features (i.e., roles) and a propositionally complete language.

This paper presents a general and efficient framework for probabilistic inference and learning from arbitrary uncertain information. It exploits the calculation properties of finite mixture models, conjugate families and factorization. Both the joint probability density of the variables and the likelihood function of the (objective or subjective) observation are approximated by a special mixture model, in such a way that any desired conditional distribution can be directly obtained without numerical integration. We have developed an extended version of the expectation maximization (EM) algorithm to estimate the parameters of mixture models from uncertain training examples (indirect observations). As a consequence, any piece of exact or uncertain information about both input and output values is consistently handled in the inference and learning stages. This ability, extremely useful in certain situations, is not found in most alternative methods. The proposed framework is formally justified from standard probabilistic principles and illustrative examples are provided in the fields of nonparametric pattern classification, nonlinear regression and pattern completion. Finally, experiments on a real application and comparative results over standard databases provide empirical evidence of the utility of the method in a wide range of applications.

Robot soccer competition provides an excellent opportunity for integrated robotics research. In particular, robot players in a soccer game must recognize and track objects in real time, navigate in a dynamic field, collaborate with teammates, and strike the ball in the correct direction. All these tasks demand robots that are autonomous (sensing, thinking, and acting as independent creatures), efficient (functioning under time and resource constraints), cooperative (collaborating with each other to accomplish tasks that are beyond an individual's capabilities), and intelligent (reasoning and planning actions and perhaps learning from experience). Furthermore, all these capabilities must be integrated into a single and complete system, which raises a set of challenges that are new to individual research disciplines. This article describes our experience (problems and solutions) in these aspects. Our robots share the same general architecture and basic hardware, but they have integrated abilities to play different roles (goalkeeper, defender, or forward) and use different strategies in their behavior. Our philosophy in building these robots is to use the least sophistication to make them as robust and integrated as possible. At RoboCup-97, held as part of the Fifteenth International Joint Conference on Artificial Intelligence, these integrated robots performed well, and our DREAMTEAM won the world championship in the middle-size robot league.