Machine Super Intelligence - vetta

1 Machine Super IntelligenceDoctoral Dissertation submitted to theFaculty of Informatics of the University of Luganoin partial fulfillment of the requirements for the degree ofDoctor of Philosophypresented byShane Leggunder the supervision ofProf. Dr. Marcus HutterJune 2008 Copyright Shane Legg 2008 This document is licensed under a Creative CommonsAttribution-Share Alike Switzerland CommitteeProf. Dr. Marcus HutterAustralian National University, AustraliaProf. Dr. J urgen SchmidhuberIDSIA, SwitzerlandTechnical University of Munich, GermanyProf. Dr. Fernando PedoneUniversity of Lugano, SwitzerlandProf. Dr. Matthias HauswirthUniversity of Lugano, SwitzerlandProf.

2 Dr. Marco WieringUtrecht University, The NetherlandsSupervisorPhD program directorProf. Dr. Marcus HutterProf. Dr. Fabio CrestaniContentsPrefaceiThesis outline .. iiiPrerequisite knowledge .. viAcknowledgements .. vi1. Nature and Measurement of Theories of Intelligence .. Definitions of human Intelligence .. Definitions of Machine Intelligence .. Intelligence testing .. Human Intelligence tests .. Animal Intelligence tests .. Machine Intelligence tests .. Conclusion .. 222. Universal Artificial Inductive inference .. Bayes rule .. Binary sequence prediction .. Solomonoff s prior and Kolmogorov complexity.

3 Solomonoff-Levin prior .. Universal inference .. Solomonoff induction .. Agent-environment model .. Optimal informed agents .. Universal AIXI agent .. 473. Taxonomy of Passive environments .. Active environments .. Some common problem classes .. Ergodic MDPs .. Environments that admit self-optimising agents .. Conclusion .. 684. Universal Intelligence A formal definition of Machine Intelligence .. Universal Intelligence of various agents .. Properties of universal Intelligence .. Response to common criticisms .. Conclusion .. 935. Limits of Computational Preliminaries .. Prediction of computable sequences.

4 Prediction of simple computable sequences .. Complexity of prediction .. Hard to predict sequences .. The limits of mathematical analysis .. Conclusion .. 1066. Temporal Difference Updating without a Learning Temporal difference learning .. Derivation .. Estimating a small Markov process .. A larger Markov process .. Random Markov process .. Non-stationary Markov process .. Windy Gridworld .. Conclusion .. 1237. Are Super intelligent machines possible? .. How could intelligent machines be developed? .. Is building intelligent machines a good idea? .. 135A. Notation and Conventions139B. Ergodic MDPs admit self-optimising Basic definitions.

5 Analysis of stationary Markov chains .. An optimal stationary policy .. Convergence of expected average value ..155C. Definitions of Collective definitions .. Psychologist definitions .. AI researcher definitions .. 164 Bibliography167 Index179 Mystics exult in mystery and want it to stay exult in mystery for a different reason:it gives them something to Dawkins inThe God DelusionPrefaceThis thesis concerns the optimal behaviour of agents in unknown computableenvironments, also known asuniversal artificial Intelligence . These theoreticalagents are able to learn to perform optimally in many types they are able to optimally use prior information about the environ-ment if it is available, in many cases they also learn to perform optimally in theabsence of such information.

6 Moreover, these agents can be proven to upperbound the performance of general purpose computable agents. Clearly suchagents are extremely powerful and general, hence the such agents can be mathematically defined at all might come as a sur-prise to some. Surely then artificial Intelligence has been solved? Not problem is that the theory behind these universal agentsassumes infinitecomputational resources. Although this greatly simplifiesthe mathematicaldefinitions and analysis, it also means that these models cannot be directlyimplemented as artificial Intelligence algorithms. Effortshave been made toscale these ideas down, however as yet none of these methods have producedpractical algorithms that have been adopted by the mainstream.

7 The mainuse of universal artificial Intelligence theory thus far hasbeen as a theoreti-cal tool with which to mathematically study the properties of Machine foundations of universal Intelligence date back to the origins of philos-ophy and inductive inference. Universal artificial Intelligence proper startedwith the work of Ray J. Solomonoff in the 1960 s. Solomonoff wasconsideringthe problem of predicting binary sequences. What he discovered was a for-mulation for an inductive inference system that can be proven to very rapidlylearn to optimally predictany sequencethat has a computable probabilitydistribution. Not only is this theory astonishingly powerful, it also brings to-gether and elegantly formalises key philosophical principles behind inductiveinference.

8 Furthermore, by considering special cases of Solomonoff s model,one can recover well known statistical principles such as maximum likelihood,minimum description length and maximum entropy. This makesSolomonoff smodel a kind of grand unified theory of inductive inference. Indeed, if itwere not for its incomputability, the problem of induction might be consideredsolved. Whatever practical concerns one may have about Solomonoff s model,most would agree that it is nonetheless a beautiful blend of mathematics main theoretical limitation of Solomonoff induction is that it onlyaddresses the problem of passive inductive learning, in particular sequenceprediction.

9 Whether the agent s predictions are correct ornot has no effect onthe future observed sequence. Thus the agent is passive in the sense that itis unable to influence the future. An example of this might be predicting themovement of the planets across the sky, or maybe the stock market, assumingthat one is not wealthy enough to influence the the more general active case the agent is able to take actions whichmay affect the observed future. For example, an agent playingchess not onlyobserves the other player, it is also able to make moves itself in order toincrease its chances of winning the game. This is a very general setting inwhich seemingly any kind of goal directed problem can be framed.

10 It is notnecessary to assume, as is typically done in game theory, that the environment,in this case other player, plays optimally. We also do not assume that thebehaviour of the environment is Markovian, as is typically done in controltheory and reinforcement the late 1990 s Marcus Hutter extended Solomonoff s passive inductionmodel to the active case by combining it with sequential decision theory. Thisproduced a theory of universal agents, and in particular a universal agent fora very general class of interactive environments, known as was able to prove that the behaviour of universal agents converges tooptimal in any setting where this is at all possible for a general agent, andthat these agents are Pareto optimal in the sense that no agent can performas well in all environments and strictly better in at least one.