Marcus Hutter | Universal Artificial Intelligence and Solomonoff Induction

The Cartesian Cafe

Marcus Hutter is an artificial intelligence researcher who is both a Senior Researcher at Google DeepMind and an Honorary Professor in the Research School of Computer Science at Australian National University. He is responsible for the development of the theory of Universal Artificial Intelligence, for which he has written two books, one back in 2005 and one coming right off the press as we speak. Marcus is also the creator of the Hutter prize, for which you can win a sizable fortune for achieving state of the art lossless compression of Wikipedia text.

Patreon (bonus materials + video chat): https://www.patreon.com/timothynguyen

In this technical conversation, we cover material from Marcus’s two books “Universal Artificial Intelligence” (2005) and “Introduction to Universal Artificial Intelligence” (2024). The main goal is to develop a mathematical theory for combining sequential prediction (which seeks to predict the distribution of the next observation) together with action (which seeks to maximize expected reward), since these are among the problems that intelligent agents face when interacting in an unknown environment. Solomonoff induction provides a universal approach to sequence prediction in that it constructs an optimal prior (in a certain sense) over the space of all computable distributions of sequences, thus enabling Bayesian updating to enable convergence to the true predictive distribution (assuming the latter is computable). Combining Solomonoff induction with optimal action leads us to an agent known as AIXI, which in this theoretical setting, can be argued to be a mathematical incarnation of artificial general intelligence (AGI): it is an agent which acts optimally in general, unknown environments. The second half of our discussion concerning agents assumes familiarity with the basic setup of reinforcement learning.

I. Introduction

• 00:38 : Biography
• 01:45 : From Physics to AI
• 03:05 : Hutter Prize
• 06:25 : Overview of Universal Artificial Intelligence
• 11:10 : Technical outline

II. Universal Prediction

• 18:27 : Laplace’s Rule and Bayesian Sequence Prediction
• 40:54 : Different priors: KT estimator
• 44:39 : Sequence prediction for countable hypothesis class
• 53:23 : Generalized Solomonoff Bound (GSB)
• 57:56 : Example of GSB for uniform prior
• 1:04:24 : GSB for continuous hypothesis classes
• 1:08:28 : Context tree weighting
• 1:12:31 : Kolmogorov complexity
• 1:19:36 : Solomonoff Bound & Solomonoff Induction
• 1:21:27 : Optimality of Solomonoff Induction
• 1:24:48 : Solomonoff a priori distribution in terms of random Turing machines
• 1:28:37 : Large Language Models (LLMs)
• 1:37:07 : Using LLMs to emulate Solomonoff induction
• 1:41:41 : Loss functions
• 1:50:59 : Optimality of Solomonoff induction revisited
• 1:51:51 : Marvin Minsky

III. Universal Agents

• 1:52:42 : Recap and intro
• 1:55:59 : Setup
• 2:06:32 : Bayesian mixture environment
• 2:08:02 : AIxi. Bayes optimal policy vs optimal policy
• 2:11:27 : AIXI (AIxi with xi = Solomonoff a priori distribution)
• 2:12:04 : AIXI and AGI. Clarification: ASI (Artificial Super Intelligence) would be a more appropriate term than AGI for the AIXI agent.
• 2:12:41 : Legg-Hutter measure of intelligence
• 2:15:35 : AIXI explicit formula
• 2:23:53 : Other agents (optimistic agent, Thompson sampling, etc)
• 2:33:09 : Multiagent setting
• 2:39:38 : Grain of Truth problem
• 2:44:38 : Positive solution to Grain of Truth guarantees convergence to a Nash equilibria
• 2:45:01 : Computable approximations (simplifying assumptions on model classes): MDP, CTW, LLMs
• 2:56:13 : Outro: Brief philosophical remarks

Further Reading:
M. Hutter, D. Quarrel, E. Catt. An Introduction to Universal Artificial Intelligence
M. Hutter. Universal Artificial Intelligence
S. Legg and M. Hutter. Universal Intelligence: A Definition of Machine Intelligence

Twitter: @iamtimnguyen

Webpage: http://www.timothynguyen.org