Seminars at the Faculty of Informatics

Mr. Shane Legg, Tuesday 17 June 2008 at 10:30, SI-008

The Defence Committee is composed of:

Prof. Marcus Hutter, Australian National University (research advisor)
Prof. Jürgen Schmidhuber, IDSIA and Technical University of Munich (co-advisor)
Prof. Fernando Pedone, USI Università della Svizzera italiana (internal member)
Prof. Matthias Hauswirth, USI Università della Svizzera italiana (internal member)
Prof. Marco Wiering, Utrecht University (external member)

This thesis explores a theoretical model of universal optimal artificial intelligence known as AIXI.  By merging Solomonoff's model of optimal universal sequence prediction with sequential decision theory, Hutter was able to define a completely universal agent with provably optimal behaviour. Unfortunately, this "perfect" artificial
intelligence requires infinite computer power and thus in practice it can only be  approximated.  To date the most important use of AIXI has been as a theoretical tool to mathematically study the nature of machine intelligence, and in particular the nature of super intelligent machines and some of their limitations.

As this thesis concerns theoretical systems that we claim to be intelligent, it begins by exploring the many definitions of intelligence that have been proposed for humans, animals and machines. What we have assembled is the largest published collection of definitions of intelligence.  From this we draw our informal working definition of intelligence to be used for the thesis.

The thesis then introduces AIXI, starting from basic philosophical principles of inductive inference and working up through probability theory, Kolmogorov complexity theory, Solomonoff induction, sequential decision theory and finally arriving at the definition of AIXI.  We then show that AIXI meets our informal definition of intelligence by showing that it is able to learn to behave optimally in an extremely wide range of classes of environments.

Given that AIXI is in some sense an optimal artificial intelligence, this suggests that it might be able to shed some light of the nature of machine intelligence itself.  Starting with our informal definition of intelligence, we mathematically formalise this definition using ideas from AIXI theory where necessary.  We then compare this formal definition of intelligence with a range of tests and measures of machine intelligence that have been proposed.  This is the widest survey of tests of machine intelligence that exists.

As AIXI is so powerful in theory, it is interesting to ask to what extent a computable algorithm can approximate it.  To study this we consider the relationship between the performance of algorithms and their Kolmogorov complexity in the domain of sequence prediction. What we find is that an algorithm's performance can be bounded in terms of its complexity.  This implies that simple but extremely powerful artificial intelligence algorithms are impossible. Furthermore, we show that the very powerful but complex algorithms that do exist cannot be discovered due to Gödel incompleteness.  In other words, we know that very powerful prediction algorithms exist, however proving that any specific algorithm belongs to this set is mathematically impossible.

These negative results need not stop us from attempting more modest approximations of AIXI.  One such attempt led to the creation of a temporal difference learning algorithm that is able to optimally tune its learning rate based on experience.  In a number of experiments this new approach is shown to significantly outperform the standard algorithm for temporal difference learning.

The thesis ends on a more speculative note considering the possibility of highly intelligent machines existing in the foreseeable future, what the significance of this might be, and whether theoretical models such as AIXI might be able to help us understand the nature of these machines.