Universal Artificial Intelligence (AIXI)
Hutter uses Solomonoff's inductive inference 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 probability of each possible future, and execute the first action of the best policy (a policy is any program that will output all the next actions and input all the next perceptions up to the horizon). A policy is the best if, on a weighted average of all the possible futures, it 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. The more they are given computing power, the more they behave like AIXI (their limit is AIXI).
Read more about this topic: Marcus Hutter
Famous quotes containing the words universal, artificial and/or intelligence:
“The axioms of physics translate the laws of ethics. Thus, the whole is greater than its part; reaction is equal to action; the smallest weight may be made to lift the greatest, the difference of weight being compensated by time; and many the like propositions, which have an ethical as well as physical sense. These propositions have a much more extensive and universal sense when applied to human life, than when confined to technical use.”
—Ralph Waldo Emerson (18031882)
“People who have realized that this is a dream imagine that it is easy to wake up, and are angry with those who continue sleeping, not considering that the whole world that environs them does not permit them to wake. Life proceeds as a series of optical illusions, artificial needs and imaginary sensations.”
—Alexander Herzen (18121870)
“There are whole precincts of voters in this country whose united intelligence does not equal that of one representative American woman.”
—Carrie Chapman Catt (18591947)