Let's read: Machine Super Intelligence, preface and outline

Machine Super Intelligence (2008) is the PhD thesis of Shane Legg, a previous student of Marcus Hutter, and a cofounder of DeepMind.

Let's start at the Preface:

Meaning of UAI

This thesis concerns the optimal behaviour of agents in unknown computable environments, also known as universal artificial intelligence [UAI]. These theoretical agents are able to learn to perform optimally in many types of environments... Moreover, these agents can be proven to upper bound the performance of general purpose computable agents.

Okay, the first paragraph is heavy, and summarizes the whole point of UAI. Let me unpack it for you.

• Optimal behavior: Here, we need to know what "optimal" is supposed to optimize, and the answer is... a number. Yeah. The agent is really playing a game with the environment that it is in. The agent does something, and the environment replies with a number called the "reward". The agent's sole purpose of life is to get as much reward as possible over its whole entire life, by learning to make the right moves in this game of life. This is basically the idea of reinforcement learning (RL).
• Unknown environment: If the environment were to be fully known, then there's no more learning about it to be done, and the problem becomes purely optimization. The agent, instead of wondering "what would happen if I do this? Let's try and find out." would only ever think "Okay, if I do this I get that, and if I do that I get that... which is the best way to maximize reward?". RL would be like learning to play chess without knowing the rules beforehoof, and pure optimization would be like playing chess with all the rules known.
• Computable environment: Here, we are assuming that the environment can be simulated by a Turing machine. This is a reasonable assumption, in two ways: 

• One, it is basically the Church-Turing thesis, which states that any function that can be computed in this universe is Turing-computable, and there are strong reasons to believe that. 

• Two, even if there are things that are not computable in our universe, we should pass them over in silence here, because they are beyond mathematical understanding ["What we cannot talk about we must pass over in silence." ---- Ludwig Wittgenstein]. 

• Proven to upper bound: It's entirely possible to make an AI that beats the UAI soundly in some special environments. In one extreme, consider making an AI that plays chess tournaments. You can use a UAI that explores and plays chess better and better, or a special chess AI that plays perfect chess. But that's not the point of UAI. UAI doesn't have to be better than everyone in every environment. It just has to be able to do well in a lot of environments. Imagine putting the chess AI and a UAI at checkers. The chess AI would never learn, while the UAI would. Further, the UAI is an upper bound of the performance of general purpose computable agents [AGI: artificial general intelligence], meaning than any AGI can't be substantially better than this UAI, in the same way that even the fanciest computer is not "really" better than a Turing machine.

Great, now we know what this UAI means, great news! The problem of AGI is solved! Not so fast.

... The problem is that the theory ... assumes infinite computational resources. Although this greatly simplifies the mathematical definitions and analysis, it also means that these models cannot be directly implemented as artificial intelligence algorithms. Efforts have been made to scale these ideas down, however as yet none of these methods have produced practical algorithms that have been adopted by the mainstream.

Bummer, why even bother with this, then?

The main use of universal artificial intelligence theory thus far has been as a theoretical tool with which to mathematically study the properties of machine super intelligence. 

 Just like how we study calculus about the real numbers, even if most real numbers are not computable, we study UAI even if it is not computable. The hope is that, by starting with a beautiful mathematical theory that's elegant, powerful, and close enough to reality, we can eventually get to a point where we can approach reality enough that something practical can come out of it.

Just like how calculus gave us finite element analysis, finite difference engine, and all its power, so would UAI eventually give us powerful AGI, and we will all hail CelestAI.

Celestia... we will meet one day.

Solomonoff induction

Now that UAI is explained, the author reviews the history behind UAI:

The foundations of universal intelligence date back to the origins of philosophy and inductive inference.

 Hold up, what's that? Well, it's the problem of induction, something philosophers have puzzled a lot about. In one sentence, it's the problem of: Given what we saw about the world, how do we infer from it beliefs bout the world, and how can we justify those beliefs? If it sounds obvious to you, try reading the raven paradox, and the grue paradox, and come back after you are thoroughly puzzled!

However, in the 1960s, a new breakthrough:

Solomonoff was considering the problem of predicting binary sequences. What he discovered was a formulation for an inductive inference system that can be proven to very rapidly learn to optimally predict any sequence that has a computable probability distribution.

If you hear this sequence: 1, 2, 4, 8, 16... you'd say 32 should come next, but why? To justify it, you need to solve the problem of induction: how to predict the future based on the past. Solomonoff's induction turns out to give a very elegant way to justify it. Moreover, it is fast, and optimal, for the task of predicting any computable sequence[what's noncomputable, again, must be passed over in silence].

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 makes Solomonoff’s model a kind of grand unified theory of inductive inference. 

Beautiful, but just one problem...

Indeed, if it were not for its incomputability, the problem of induction might be considered solved. Whatever practical concerns one may have about Solomonoff’s model, most would agree that it is nonetheless a beautiful blend of mathematics and philosophy.

Basically, as a simple corollary that the halting problem is incomputable, so is Solomonoff's induction incomputable. But that's okay. Just as the incomputability of real numbers does not make calculus useless for numerical analysis, so won't Solomonoff's induction become useless.

Passive to active

Solomonoff induction... only addresses the problem of passive inductive learning... the agent is passive in the sense that it is unable to influence the future. An example of this might be predicting the movement of the planets across the sky, or maybe the stock market, assuming that one is not wealthy enough to influence the market.

In the more general active case the agent is able to take actions which may affect the observed future. For example, an agent playing chess not only observes the other player, it is also able to make moves itself in order to increase its chances of winning the game. This is a very general setting in which seemingly any kind of goal directed problem can be framed.

Solomonoff induction is not strong enough for UAI. A truly powerful AI must be able to not merely explain the world like a philosopher, but must be able to change it. ["The philosophers have only interpreted the world, in various ways. The point, however, is to change it." -- Karl Marx]

Then, Legg contrasted the UAI with game theory, control theory, and RL:

It is not necessary 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 the behaviour of the environment is Markovian, as is typically done in control theory and reinforcement learning.

Basically, UAI only assumes the environment is computable, which subsumes them all.

Finally, enter Marcus Hutter's AIXI agent, proven to be UAI in a very strong sense:

In the late 1990’s Marcus Hutter extended Solomonoff’s passive induction model to the active case by combining it with sequential decision theory. This produced a theory of universal agents... known as the AIXI agent. Hutter was able to prove that the behaviour of universal agents converges to optimal in any setting where this is at all possible for a general agent, and that these agents are Pareto optimal in the sense that no agent can perform as well in all environments and strictly better in at least one. These are the strongest known results for a completely general purpose agent.

Given that AIXI has such generality and extreme performance characteristics, it can be considered to be a theoretical model of a super intelligent agent.

So it's been 20 years, and still no CelestAI? Why? Incomputability, just like the Solomonoff induction being incomputable.

And that's not all, it does not even converge in some situations.

Unfortunately, even stronger results showing that AIXI converges to optimal behaviour rapidly, similar to Solomonoff’s convergence result, have been shown to be impossible in some settings, and remain open questions in others.

 It seems to be a general trend, that the more powerful something is, the less controlled its behavior is. Finite state machines behave well, Turing machines behave incomputably in general, and Turing machines with oracles behave even more incomputably...

Ah well, it's just something we have to accept and understand.

The goal of this thesis is to explore some of the open issues surrounding universal artificial intelligence. In particular:

1. in which settings the behaviour of universal agents converges to optimal, 
2. the way in which AIXI theory relates to the concept and definition of intelligence, 
3. the limitations that computable agents face when trying to approximate theoretical super intelligent agents such as AIXI, 
4. some of the big picture implications of super intelligent machines and whether this is a topic that deserves greater study.

If we run with our previous analogy with calculus, then the issues are:

1. When does the function converge?
2. Does derivatives, gradients, etc actually have physical meanings? What are they?
3. What functions are computable? What functions are efficiently computable? What functions are numerically stable/unstable?
4. Should we even study calculus at all or is there something better to do with our lives?

And that's the end of the preface!

Outline

Then, Legg details the contents of each chapter. There are 7 in all.

1. Nature and Measurement of Intelligence. 

What is intelligence? Amazingly, books and papers on artificial intelligence rarely delve into what intelligence actually is... we must first explore the different tests and definitions of intelligence that have been proposed for humans, animals and machines. We draw from these an informal definition of intelligence that we will use throughout the rest of the thesis.

This chapter would be very philosophical, discussing all the tests and definitions of intelligence, like the Turing test and such.

2. UAI 

AIXI the UAI agent was not yet popularly known in 2008. And now, in 2018, it's still not popular. One reason, it seems, is because it's too technical. (Another reason is surely that it has not led to any practical breakthrough, unlike deep neural networks.) 

To fix this, a gentle introduction to AIXI is given in this chapter.

It starts with the basics of inductive inference and slowly builds up to the AIXI agent and its key theoretical properties.

3. Optimality of AIXI

The claim that AIXI behaves "optimally" in certain environments, is true in many ways. Hutter proved a few:

Hutter has proven that universal agents converge to optimal behaviour in any environment where this is possible for a general agent. He further showed that the result holds for certain types of Markov decision processes, and claimed that this should generalise to related classes of environments.

 To prove even more such optimality theorems, the author would define a way to classify environments, so that AIXI can be shown to deal with even more kinds of environments, and thus is probably super intelligent.

4. Universal Intelligence Measure

... we take the informal definition of intelligence from Chapter 1 and abstract and formalise it using ideas from the theory of UAI. The result is an alternate characterisation of Hutter’s intelligence order relation.

Hold up, what's Hutter's intelligence order relation?

Back in A Theory of Universal Artificial Intelligence based on Algorithmic Complexity (2000), Marcus Hutter defined an ordering of AGI, and showed that AIXI is the highest in such an ordering. The details are highly technical and I'll read it at a later time, but the idea is that it is a mathematical way to ranks the intelligence of any agent at all, human or not.

Legg then quantifies it into some kind of universal IQ score for everyone.

5. Limits of Computational Agents

AIXI is no good if it can't be implemented practically at all. And so far, it is hardly practical, even its approximations. Is it merely a technical issue, or is it because AIXI can't even be well approximated? In this chapter, 

... reveal a number of fundamental constraints on any endeavour to construct very general artificial intelligence algorithms.

6. Fundamental Temporal Difference Learning.

In Chapter 6 we derive an equation for temporal difference learning from statistical principles... [some abstract stuff about $TD(\lambda)$]... Finally, we make some preliminary investigations into how to extend our new temporal difference algorithm to reinforcement learning.

I'll be honest. It's too technical for me right now. I should read Sutton's RL textbook first. 

7. Discussion

discussion on the future development of machine intelligence.

Appendices

A gives math conventions in the paper. B gives a proof of a technical result. C is the most interesting. It reprints A Collection of Definitions of Intelligence (2007), which gives > 70 definitions of "intelligence".

Prerequisite knowledge

Before we jump into the paper, let's check the math prerequisites:

Fortunately, I am doubly-checker-checked, so no wreckage for me!

• general mathematics: linear algebra, calculus, basic set theory and logic. 
• statistics: basic probability theory and elementary distributions such as the uniform and binomial distributions. 
• measure theory is useful but not essential. 
• theoretical computer science: Turing computation, universal Turing machines, incomputability and the halting problem. 

Okay, that's all for the preface and outline. We'll get to chapter 1 next time. And without this exhausting kind of close-reading, I think...