Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability (Texts in Theoretical Computer Science. An EATCS Series) [Englisch] [Taschenbuch]

This book differs from most books on the theoretical formulations of artificial intelligence in that it attempts to give a more rigorous accounting of machine learning and to rank machines according to their intelligence. To accomplish this ranking, the author introduces a concept called `universal artificial intelligence,' which is constructed in the context of algorithmic information theory. In fact, the book could be considered to be a formulation of artificial intelligence from the standpoint of algorithmic information theory, and is strongly dependent on such notions as Kolmogorov complexity, the Solomonoff universal prior, Martin-Lof random sequences and Occam's razor. These are all straightforward mathematical concepts with which to work with, the only issue for researchers being their efficacy in giving a useful notion of machine intelligence.

The author begins the book with a "short tour" of what will be discussed in the book, and this serves as helpful motivation for the reader. The reader is expected to have a background in algorithmic information theory, but the author does give a brief review of it in chapter two. In addition, a background in sequential decision theory and control theory would allow a deeper appreciation of the author's approach. In chapter four, he even gives a dictionary that maps concepts in artificial intelligence to those in control theory. For example, an `agent' in AI is a `controller' in control theory, a `belief state' in AI is an `information state' in control theory, and `temporal difference learning' in AI is `dynamic programming' or `value/policy iteration' in control theory. Most interestingly, this mapping illustrates the idea that notions of learning, exploration, adaptation, that one views as "intelligent" can be given interpretations that one does not normally view as intelligent. The re-interpretation of `intelligent' concepts as `unintelligent' ones is typical in the history of AI and is no doubt responsible for the belief that machine intelligence has not yet been achieved.

The author's formulations are very dependent on the notion of Occam's razor with its emphasis on simple explanations. The measurement of complexity that is used in algorithmic information theory is that of Kolmogorov complexity, which one can use to measure the a prior plausibility of a particular string of symbols. The author though wants to use the `Solomonoff universal prior', which is defined as the probability that the output of a universal Turing machine starts with the string when presented with fair coin tosses on the input tape. As the author points out, this quantity is however not a probability measure, but only a `semimeasure', since it is not normalized to 1, but he shows how to bound it by expressions involving the Kolmogorov complexity.

The author also makes use of the agent model, but where now the agent is assumed to be acting in a probabilistic environment, with which it is undergoing a series of cycles. In the k-th cycle, the agent performs an action, which then results in a perception, and the (k+1)-th cycle then begins. The goal of the agent is to maximize future rewards, which are provided by the environment. The author then studies the case where the probability distribution of the environment is known, in order to motivate the notion of a `universal algorithmic agent (AIXI).' This type of agent does not attempt to learn the true probability distribution of the environment, but instead replaces it by a generalized universal prior that converges to it. This prior is a generalization of the Solomonoff universal prior and involves taking a weighted sum over all environments (programs) that give a certain output given the history of a particular sequence presented to it. The AIXI system is uniquely defined by the universal prior and the relation specifying its outputs. The author is careful to point out that the output relation is dependent on the lifespan or initial horizon of the agent. Other than this dependence the AIXI machine is a system that does not have any adjustable parameters.

The author's approach is very ambitious, for he attempts to define when an agent or machine could be considered to be `universally optimal.' Such a machine would be able to find the solution to any problem (with the assumption that it is indeed solvable) and be able to learn any task (with the assumption that it is learnable). The process or program by which the machine does this is `optimal' in the sense that no other program can solve or learn significantly faster than it can. The machine is `universal' in that it is independent of the true environment, and thus can function in any domain. This means that a universal optimal machine could perform financial time series prediction as well as discover and prove new results in mathematics, and do so better than any other machine. The notion of a universally optimal machine is useful in the author's view since it allows the construction of an `intelligence order relation' on the "policies" of a machine. A policy is thought of as a program that takes information and delivers it to the environment. A policy p is `more intelligent' than a policy p' if p delivers a higher expected reward than p'.

The author is aware that his constructions need justification from current practices in AI if they are to be useful. He therefore gives several examples dealing with game playing, sequence prediction, function minimization, and reinforcement and supervised learning as evidence of the power of his approach. These examples are all interesting in the abstract, but if his approach is to be fruitful in practice it is imperative that he give explicit recommendations on how to construct a policy that would allow a machine to be as universal and optimal (realistically) as he defines it (formally) in the book. Even more problematic though would be the awesome task of checking (proving) whether a policy is indeed universally optimal. This might be even more difficult than the actual construction of the policy itself.

Solomonoff's famous inference model solves the inductive learning problem in a universal and provably very powerful way. Many methods from statistics (maximum likelihood, maximum entropy, minimum description length...) can be shown to be special cases of the model described by Solomonoff. However Solomonoff Induction has two significant shortcomings: Firstly it is not computable, and secondly it only deals with passive environments. Although many problems can be formulated in terms of sequence prediction (for example categorisation), in AI in general an agent must be able to deal with an active environment where the agent's decisions affect the future state of the environment.

In essence, the AIXI model, the main topic of this book, is an extension of Solomonoff Induction to this much more general space of active environments. Although the model itself is very simple (it is really just Solomonoff's model with an expectimax tree added to examine the potential consequences of the agent's actions) the resulting analysis is now more difficult than in the passive case. While optimality can be show in certain senses, the powerful convergence bounds that Solomonoff induction has now appear to be difficult to establish.

Like Solomonoff induction, AIXI also suffers from computability problems. In the one of the final sections a modified version of AIXI is presented which is shown to be computable and optimal in some sense. Practically this algorithm would be much too slow, but this is a clear step away from abstract models which can in theory be implemented.

For anybody interested in universal theories of artificial intelligence this book is a must. The presentation is quite technical in places and thus the reader should have some understanding of theoretical computer science, statistics and Kolmogorov complexity.

This is probably the most rigorous attempt to formalize AI. The book succeeds in presenting the state-of-the-art AI theory from a technical point of view, but neglects intuition, and is difficult to read for the novice and thus inaccessible to a wider audience.

The main idea of the book in combining classical control theory concepts with Bayesian inference and algorithmic information theory. The author avoids to struggle with anthropocentric aspects of intelligence (which are subject to a fierce debate) by defining intelligent agents as utility maximizing-systems. The core ideas are, in a nutshell (informally):

1) Goal: Build a system with an I/O stream interfaced with an environment, where inputs are observations and outputs are actions, that optimizes some cumulative reward function over the observations. Two ingredients are necessary: model the a priori unknown environment and solve for the reward-maximizing actions.

2) Model: This is a probability distribution over future observations conditioned on the past (actions and observations). Instead of using any particular domain-specific model, the author uses a weighted mixture over "all" models. By "all models", the set of all mechanically calculable models is meant, i.e. the set of all algorithmically approximable probabilistic models.

3) Policy: Given the model, all possible futures can be simulated (up to a predefined horizon) by trying out all possible interaction paths. Essentially, a huge decision tree is constructed. Having this information, it is "easy" to solve for the best policy. Just pick at each step the action that promises the highest expected future rewards. These are calculated recursively using Bellman's optimality equations.

Why does this work in theory? If the environment is equal to one of the models in the mixture (or "close enough"), then the mixture model converges to the true environment. The model is updated step by step using Bayes' rule. Since the model becomes more accurate, the policy based on it converges to the optimum. Algorithmic information theory is the main tool to derive the mathematical results.

Does it work in practice? Unfortunately, the presented solution cannot be implemented in practice, because the mixture model is incomputable. Even worse, there is currently no principled way to downscale his approach (and make it practical), since we don't know how to simplify (a) the mixture model and (b) the computation of the policy. The author makes these points very clear in his book. IMHO these are the main challenges for future AI research.

The PROs: This is the first time I see a unified, formal and mathematically sound presentation of artificial intelligence. The proposed theoretical solution provides invaluable insight about the nature of learning and acting - hidden even in very subtle details in his approach and in his equations. Whereas you might feel that classical AI or commonplace Machine Learning theory looks like a patchwork of interesting concepts and methods, here (almost) everything fits nicely together into a coherent and elegant solution. Once you have studied and understood this book (which took years in my case), it is very difficult to go back to the traditional approaches of AI.

The CONTRAs: However, there are some downsides to this book. Hutter is a brilliant mathematician and sharp thinker. Unfortunately his writing style is very formal and many times he neglects intuition. The book introduces difficult notation (although some of it pays off in the long run) that ends up obfuscating simple ideas. The mathematical style of the book is difficult to digest.

To summarize, this books represents a giant leap in the theory of AI. If you have advanced mathematical training and enough patience to study it, then this book is for you. For the more practically-oriented researcher who wants to learn about Universal AI, I recommend reading Shane Legg's "Machine Super Intelligence".