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:
“Not because Socrates has said it, but because it is really in my nature, and perhaps a little more than it should be, I look upon all humans as my fellow-citizens, and would embrace a Pole as I would a Frenchman, subordinating this national tie to the common and universal one.”
—Michel de Montaigne (1533–1592)
“The most revolutionary invention of the Nineteenth Century was the artificial sterilization of marriage.”
—George Bernard Shaw (1856–1950)
“It is worth the while to detect new faculties in man,—he is so much the more divine; and anything that fairly excites our admiration expands us. The Indian, who can find his way so wonderfully in the woods, possesses an intelligence which the white man does not,—and it increases my own capacity, as well as faith, to observe it. I rejoice to find that intelligence flows in other channels than I knew. It redeems for me portions of what seemed brutish before.”
—Henry David Thoreau (1817–1862)