Universal Algorithmic Intelligence

Aram Ebtekar, a returning speaker and founding research scientist at AIXI Labs, will present his (new) justification for Solomonoff induction at tomorrow’s regular research meeting, Monday July 13th at 3 pm EDT. Aram discusses the obstacle that No Free Lunch poses for developing a theory of generalization, and a practical sense in which Solomonoff induction, relativized to the user’s information vantage point, is optimal, even on finite data. We will use the regular zoom link.

Title:

Understanding Generalization Requires Universal Induction

Abstract:

Classical statistical theory is insufficient to explain the successes of general-purpose
AI models, because it depends on handcrafted inductive biases that it cannot justify.
No Free Lunch theorems force any learner that beats chance on some environments
to underperform on others. We might hope that past experience informs which
environments to expect, but No Free Lunch applies equally to meta-learning.
Thus, any method that makes meaningful predictions necessarily begins with
an inductive bias external to the data. Choosing to bias toward short programs
yields Solomonoff induction (SI), whose performance is competitive against all
computable learners – albeit up to “constants” that become large when comparing
against specialized methods that exploit background information. We therefore
relativize SI to an information vantage point, biasing toward short programs with
access to all preexisting information. This reframes the inductive bias: instead
of seeking some absolute notion of simplicity, we favor accessibility with respect
to our vantage point. On finite data, the relativized SI is sample-optimal, in the
sense that one can only do better by acquiring additional information about the
data. While SI is incomputable and hence not a practical algorithm, it provides a
formal optimum for inference in the limit of infinite compute. We argue that this
type of analysis, rooted in algorithmic information theory, is necessary to explain
the generalization behavior of modern (and future) AI systems.

Full preprint: https://djsutherland.ml/papers/nfl-ait.pdf

Hope to see you all there!