Marcus Hutter
Encyclopedia
Marcus Hutter is a German computer scientist and professor at the Australian National University
. Hutter was born and educated in Munich
, where he studied physics
and computer science
. In 2000 he joined Jürgen Schmidhuber
's group at the Swiss Artificial Intelligence
lab IDSIA
, where he developed the first mathematical theory of optimal Universal Artificial Intelligence, based on Kolmogorov complexity
and Ray Solomonoff
's theory of universal inductive inference
. In 2006 he also accepted a professorship at the Australian National University in Canberra
.
Hutter's notion of universal AI describes the optimal strategy of an agent that wants to maximize its future expected reward in some unknown dynamic environment, up to some fixed future horizon. This is the general reinforcement learning
problem. Solomonoff/Hutter's only assumption is that the reactions of the environment in response to the agent's actions follow some unknown but computable
probability distribution
.
as a mathematical formalization of Occam's razor. Hutter adds to this formalization the expected value of an action: shorter (kolmogorov complexity
) computable theories have more weight when calculating the expected value
of an action across all computable theories which perfectly describe previous observations.
At any time, given the limited observation sequence so far, what is the Bayes-optimal
way of selecting the next action? Hutter proved that the answer is to use Solomonoff's universal prior to predict the future, and execute the first action of the action sequence that will maximize the predicted reward up to the horizon. He called this universal algorithm AIXI.
This is mainly a theoretical result. To overcome the problem that Solomonoff's prior is incomputable, in 2002 Hutter also published an asymptotically
fastest algorithm for all well-defined problems. Given some formal description of a problem class, the algorithm systematically generates all proofs
in a sufficiently powerful axiomatic system
that allows for proving time bounds of solution-computing programs. Simultaneously, whenever a proof has been found that shows that a particular program has a better time bound than the previous best, a clever resource allocation scheme will assign most of the remaining search time to this program. Hutter showed that his method is essentially as fast as the unknown fastest program for solving problems from the given class, save for an additive constant
independent of the problem instance. For example, if the problem size is
, and there exists an initially unknown program that solves any problem in the class within 
computational steps, then Hutter's method will solve it within 
steps. The additive constant hidden in the 
notation
may be large enough to render the algorithm practically infeasible despite its useful theoretical properties.
Several algorithms approximate AIXI in order to make it run on a modern computer, at the expense of its perfect optimality.
for Lossless Compression of Human Knowledge with an initial purse of 50,000 Euros, the intent of which is to encourage the advancement of artificial intelligence
through the exploitation of Hutter's theory of optimal universal artificial intelligence.
Australian National University
The Australian National University is a teaching and research university located in the Australian capital, Canberra.As of 2009, the ANU employs 3,945 administrative staff who teach approximately 10,000 undergraduates, and 7,500 postgraduate students...
. Hutter was born and educated in Munich
Munich
Munich The city's motto is "" . Before 2006, it was "Weltstadt mit Herz" . Its native name, , is derived from the Old High German Munichen, meaning "by the monks' place". The city's name derives from the monks of the Benedictine order who founded the city; hence the monk depicted on the city's coat...
, where he studied physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. In 2000 he joined Jürgen Schmidhuber
Jürgen Schmidhuber
Jürgen Schmidhuber is a computer scientist and artist known for his work on machine learning, universal Artificial Intelligence , artificial neural networks, digital physics, and low-complexity art. His contributions also include generalizations of Kolmogorov complexity and the Speed Prior...
's group at the Swiss Artificial Intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
lab IDSIA
IDSIA
The Swiss institute for Artificial Intelligence IDSIA was founded in 1988 by the private Dalle Molle foundation...
, where he developed the first mathematical theory of optimal Universal Artificial Intelligence, based on Kolmogorov complexity
Kolmogorov complexity
In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
and Ray Solomonoff
Ray Solomonoff
Ray Solomonoff was the inventor of algorithmic probability, and founder of algorithmic information theory, He was an originator of the branch of artificial intelligence based on machine learning, prediction and probability...
's theory of universal inductive inference
Inductive inference
Around 1960, Ray Solomonoff founded the theory of universal inductive inference, the theory of prediction based on observations; for example, predicting the next symbol based upon a given series of symbols...
. In 2006 he also accepted a professorship at the Australian National University in Canberra
Canberra
Canberra is the capital city of Australia. With a population of over 345,000, it is Australia's largest inland city and the eighth-largest city overall. The city is located at the northern end of the Australian Capital Territory , south-west of Sydney, and north-east of Melbourne...
.
Hutter's notion of universal AI describes the optimal strategy of an agent that wants to maximize its future expected reward in some unknown dynamic environment, up to some fixed future horizon. This is the general reinforcement learning
Reinforcement learning
Inspired by behaviorist psychology, reinforcement learning is an area of machine learning in computer science, concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward...
problem. Solomonoff/Hutter's only assumption is that the reactions of the environment in response to the agent's actions follow some unknown but computable
Computability theory (computer science)
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science...
probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
.
Universal artificial intelligence
Hutter uses Solomonoff's inductive inferenceInductive inference
Around 1960, Ray Solomonoff founded the theory of universal inductive inference, the theory of prediction based on observations; for example, predicting the next symbol based upon a given series of symbols...
as a mathematical formalization of Occam's razor. Hutter adds to this formalization the expected value of an action: shorter (kolmogorov complexity
Kolmogorov complexity
In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
) computable theories have more weight when calculating the expected value
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
of an action across all computable theories which perfectly describe previous observations.
At any time, given the limited observation sequence so far, what is the Bayes-optimal
Bayes estimator
In estimation theory and decision theory, a Bayes estimator or a Bayes action is an estimator or decision rule that minimizes the posterior expected value of a loss function . Equivalently, it maximizes the posterior expectation of a utility function...
way of selecting the next action? Hutter proved that the answer is to use Solomonoff's universal prior to predict the future, and execute the first action of the action sequence that will maximize the predicted reward up to the horizon. He called this universal algorithm AIXI.
This is mainly a theoretical result. To overcome the problem that Solomonoff's prior is incomputable, in 2002 Hutter also published an asymptotically
Asymptote
In analytic geometry, an asymptote of a curve is a line such that the distance between the curve and the line approaches zero as they tend to infinity. Some sources include the requirement that the curve may not cross the line infinitely often, but this is unusual for modern authors...
fastest algorithm for all well-defined problems. Given some formal description of a problem class, the algorithm systematically generates all proofs
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
in a sufficiently powerful axiomatic system
Axiomatic system
In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A mathematical theory consists of an axiomatic system and all its derived theorems...
that allows for proving time bounds of solution-computing programs. Simultaneously, whenever a proof has been found that shows that a particular program has a better time bound than the previous best, a clever resource allocation scheme will assign most of the remaining search time to this program. Hutter showed that his method is essentially as fast as the unknown fastest program for solving problems from the given class, save for an additive constant
Constant (mathematics)
In mathematics, a constant is a non-varying value, i.e. completely fixed or fixed in the context of use. The term usually occurs in opposition to variable In mathematics, a constant is a non-varying value, i.e. completely fixed or fixed in the context of use. The term usually occurs in opposition...
independent of the problem instance. For example, if the problem size is
, and there exists an initially unknown program that solves any problem in the class within computational steps, then Hutter's method will solve it within steps. The additive constant hidden in the notationBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
may be large enough to render the algorithm practically infeasible despite its useful theoretical properties.
Several algorithms approximate AIXI in order to make it run on a modern computer, at the expense of its perfect optimality.
Hutter Prize for Lossless Compression of Human Knowledge
On August 6, 2006, Hutter announced the Hutter PrizeHutter Prize
The Hutter Prize is a cash prize funded by Marcus Hutter which rewards data compression improvements on a specific 100 MB English text file. Specifically, the prize awards 500 euros for each one percent improvement in the compressed size of the file enwik8, which is the smaller of two files used...
for Lossless Compression of Human Knowledge with an initial purse of 50,000 Euros, the intent of which is to encourage the advancement of artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
through the exploitation of Hutter's theory of optimal universal artificial intelligence.
Partial bibliography
- Universal Artificial Intelligence: Sequential Decisions Based On Algorithmic Probability ISBN 3-540-22139-5
- On Generalized Computable Universal Priors and their Convergence. Theoretical Computer Science, 2005.
- Optimality of Universal Bayesian Sequence Prediction for General Loss and Alphabet. Journal of Machine Learning Research 4, 971-1000, 2003.
- The Fastest and Shortest Algorithm for All Well-Defined Problems. International Journal of Foundations of Computer Science, 13:3 (2002) 431-443, 2002.