Universal Algorithmic Intelligence: A mathematical top->down approach
Keywords: Artificial intelligence; algorithmic probability;
sequential decision theory; rational agents;
value function; Solomonoff induction; Kolmogorov complexity;
reinforcement learning; universal sequence prediction;
strategic games; function minimization; supervised learning.
Abstract: 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 AIXItl, which is still effectively more intelligent than
any other time t and space l bounded agent. The computation time of
AIXItl is of the order t·2l.
Other discussed topics are formal
definitions of intelligence order relations, the horizon problem and
relations of the AIXI theory to other AI approaches.
BibTeX Entry
@InCollection{Hutter:07aixigentle,
author = "Marcus Hutter",
title = "Universal Algorithmic Intelligence: A Mathematical Top$\rightarrow$Down Approach",
_oldtitle = "A Gentle Introduction to The Universal Algorithmic Agent {AIXI}",
booktitle = "Artificial General Intelligence",
editor = "B. Goertzel and C. Pennachin",
publisher = "Springer",
address = "Berlin",
series = "Cognitive Technologies",
_number = "IDSIA-01-03",
_month = _jan,
year = "2007",
pages = "227--290",
isbn = "3-540-23733-X",
url = "http://www.hutter1.net/ai/aixigentle.htm",
http = "http://arxiv.org/abs/cs.AI/0701125",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-01-03.ps.gz",
categories = "I.2. [Artificial Intelligence]",
keywords = "Artificial intelligence; algorithmic probability;
sequential decision theory; rational agents;
value function; Solomonoff induction;
Kolmogorov complexity; reinforcement learning;
universal sequence prediction; strategic games;
function minimization; supervised learning.",
abstract = "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 parameter-free
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$ that is still
effectively more intelligent than any other time $t$ and length $l$
bounded agent. The computation time of AIXI$tl$ is of the order $t
\cdot 2^l$. Other discussed topics are formal definitions of
intelligence order relations, the horizon problem and relations of
the AIXI theory to other AI approaches.",
}