From SLT to AIT: NN generalisation out-of-distribution

[Lucius Bushnaq]

TL;DR: This post derives an upper bound on the prediction error of Bayesian learning on neural networks. Unlike the bound from vanilla Singular Learning Theory (SLT), this bound also holds for out-of-distribution generalization, not just for in-distribution generalization. Along the way, it shows some connections between SLT and Algorithmic Information Theory (AIT).

Written at Goodfire AI

Introduction

Singular Learning Theory (SLT) describes Bayesian learning on neural networks. But it currently has some limitations. One of these limitations is that it assumes model training data are drawn independently and identically (IID) from some distribution, making it difficult to use SLT to describe out-of-distribution (OOD) generalization. For example, if we train a model to classify pictures of animals taken outdoors, it’s very difficult to use vanilla SLT to reason about whether this model will generalize to correctly classify pictures of animals taken indoors. Vanilla SLT also assumes that the model has been trained on an asymptotically infinite number of data points.^[1]

Another theory about Bayesian learning is Algorithmic Information Theory (AIT), which describes Solomonoff induction (SI) [1,2].^[2] Solomonoff induction is Bayesian learning over an (infinite) ensemble of programs. It is, unfortunately, uncomputable. But it does not require an IID sampling assumption, does not rely on asymptotically infinite data, and does describe OOD generalization. AIT is also older, more developed, and more established than SLT. A lot of agent foundations work builds on the AIT framework.

So if we could derive an AIT-style description of Bayesian learning on neural networks, that description might tell us things about neural network generalization out-of-distribution.

Here, we:

1. Derive error bounds for a computationally bounded Solomonoff induction (SI).

   1. First, we import Solomonoff induction to the learning-theoretic setting of data coming in input-label pairs $(x,y)$, with the inductor trying to predict the labels $y$ conditional on the inputs $x$ and show that the standard error bound for SI still holds there.

   2. Then, we define a bounded, computable form of induction over programs. We show that it still satisfies a weaker SI-style error bound. We also show that this bounded induction is still somewhat invariant to our choice of universal Turing machine.

2. Derive a bound on the expected prediction error of Bayesian learning on neural networks.

   1. Specifically, we derive an error bound for Bayesian learning over parametrized functions, starting from a uniform prior over real-valued parameters. In contrast to SLT-style error bounds, we do not need to assume that our data are drawn IID. Hence the bound will also hold under distributional shifts.

   2. We show how this error bound relates to the notion of $ϵ$-volumes that define the learning coefficient in Singular Learning Theory.

The first part is mainly supposed to build intuition for the second, and help people see how the AIT picture and Bayesian learning on neural networks connect.^[3]

I also hope that this post might help readers used to thinking about probability from a more E. T. Jaynes-esque/​native-Bayesian point of view a little with grokking Singular Learning Theory, which is usually described in a pretty stat-mech-esque/​second-language-Bayesian manner.

Prediction error bounds for a computationally bounded Solomonoff induction

Claim 1: We can import Solomonoff induction into the learning-theoretic setting

We consider a prediction setting with inputs $x_n\in \{0,1{\}}^{\ast }$ (finite binary strings) and labels $y_n\in \{0,1\}$. We assume that the labels were generated by a probabilistic program $\mu$ ^[4], i.e., $P_{\mu }(y_n\mid x_n)$ is set by $\mu \left(x_n\right)$. We are given $N\ge 1$ such input-label pairs $\left\{\right(x_n,y_n){\}}_{n=1}^N$.

Our goal is to construct an inductor that predicts whether $y_n$ is $1$ given $x_n$, using Bayesian updating on past input-label pairs $(x_1,y_1),\dots ,(x_{n-1},y_{n-1})$ that it has already seen. To do this, we will just slightly modify the standard Solomonoff setup for probabilistic programs.

Let $M_1$ be a plain^[5] monotone^[6] universal Turing machine (UTM) with a binary alphabet, one-way read-only input and output tapes, and a two-way work tape. We define the set of all programs $p$ of length $T\in N$ bits, and the set of augmented programs $p_n:=(p_{\text{read}},x_n,p)$, where $p_{\text{read}}$ is some ‘read-in’ program that first copies $x_n$ from the input tape to the first $L_{\text{in}}$ cells of the work tape, then sets the read head to the first bit of the program string $p$ and finally resets the UTM’s internal state to its starting configuration.

Our inductor then makes its predictions using the ensemble of augmented programs:

$$P_{M_1}(y_n\mid x_n,D_{<n})=\sum _p{P}_{M_1}(y_n\mid p_n)P(p\mid D_{<n}),$$

where $P_{M_1}(y_n=1\mid p_n)=M_1\left(p_n\right)=M_1(p_{\text{read}},x_n,p)$ is the output bit string of our UTM on input string $p_n$ interpreted as the probability that $y_n=1$^[7], $P_{M_1}(y_n=0\mid p_n)=1-P_{M_1}(y_n=1\mid p_n)$ and $P(p\mid D_{<n})$ is the probability we assign to program $p$ after updating on the past prediction performance of $p_{n-1},\dots ,p_1$ on the input-label pairs $(x_{n-1},y_{n-1}),\dots ,(x_1,y_1)$. For our starting prior $P(p\mid D_{<1})=P\left(p\right)$, we take the uniform distribution $P\left(p\right)=2^{-T}$ over our set of programs $p$.

Note that this setup does not make any assumptions about how the inputs $x_n$ are sampled. This is in contrast to the Singular Learning Theory (SLT) setup, which needs to assume that the inputs $x_n$ are sampled IID from some underlying distribution. This assumption makes it difficult to use SLT to say anything about the generalization behavior of a trained network under distributional shifts, such as switching from the training distribution to a very different deployment distribution. We do not have that problem here.

Claim

So long as the program that generated the data $\mu$ has a minimum length less than or equal to $T$ on our UTM $M_1$, $C(\mu ,M_1)\le T$, the conventional error bound for Solomonoff induction still applies in this setting. i.e., the total expected prediction error of our inductor will be bounded by

$$\begin{array}{}\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{M_1}(\cdot \mid x_n,D_{<n}\left)\right)\le C(\mu ,M_1)+\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n\left)\right),& \text{(1.1)}\end{array}$$

for all $N\in N_{>0}$. In other words, the inductor’s total expected prediction error over the first $N$ data it sees, scored in bits of cross-entropy

$$\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{M_1}(\cdot \mid x_n,D_{<n}\left)\right):=-\sum _{n=1}^N\sum _{y_n}{P}_{\mu }(y_n\mid x_n){\log }_2{P}_{M_1}(y_n\mid x_n,D_{<n})$$

is bounded to stay below the Kolmogorov complexity of the data-generating process $\mu$ on $M_1$, $C(\mu ,M_1)$, meaning the minimum description length of the program $\mu$ on the machine $M_1$, plus the Shannon entropy $H\left(P_{\mu }\right(\cdot \mid x_n\left)\right)$ of $\mu$ on each data point $x_n$ summed:^[8]

$$\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n\left)\right):=-\sum _{n=1}^N\sum _{y_n}{P}_{\mu }(y_n\mid x_n){\log }_2{P}_{\mu }(y_n\mid x_n).$$

High-level proof summary

The proof works analogously to the derivation of the bound in the conventional SI setup found in most textbooks. The only differences are that

1. We have not taken program length $T$ to infinity, as is done in the universal prior. We just assume that it is set to some number larger than $C(\mu ,M_1)$.

2. $M_1$ is a plain UTM rather than a prefix-free UTM, and thus our starting prior over programs is just uniform, rather than falling off exponentially with program length. The degeneracy of program implementations ensures that simpler programs are exponentially preferred; we don’t need to insert a term favoring simpler programs in the prior by hand.

3. Our programs $p_n=(p_{\text{read}},x_n,p)$ start with a prefix $(p_{\text{read}},x_n)$, where $x_n$ changes between data points.

None of these changes affect the structure of the proof much. We rearrange the expression for ${\sum }_{n}H\left(P_{\mu }\right(\cdot \mid x_n),P_{M_1}(\cdot \mid x_n,D_{<n}\left)\right)$ to make its dependence on the prior $P\left(p\right)$ manifest, then use the existing result that the implementation of program $\mu$ must be assigned probability $\ge 2^{-C(\mu ,M_1)}$ in the prior due to degeneracy of implementation. I.e., there are at least $2^{T-C(\mu ,M_1)}$ programs of length $T$ that give the same output as $\mu$ on all data, since we can just append $T-C(\mu ,M_1)$ arbitrary ‘garbage bits’ to the shortest implementation of $\mu$ to increase its length to $T$ without affecting the computation. So, the total probability mass in $P\left(p\right)$ assigned to programs that output the same probability as $\mu$ on all data must be at least $\frac{2^{T-C(\mu ,M_1)}}{2^T}=2^{-C(\mu ,M_1)}$.

Proof

First, we rearrange our expression for the total cross-entropy:

$$\begin{array}{cc}& \sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{M_1}(\cdot \mid x_n,D_{<n}\left)\right)=-\sum _{n=1}^N\sum _{y_n}{P}_{\mu }(y_n\mid x_n){\log }_2\left(P_{M_1}\right(y_n\mid x_n,D_{<n}\left)\right)\\ & =-\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(\sum _p{P}_{M_1}\right(y_N\mid p_N\left)P\right(p\mid D_{<N}\left)\right)\\ & -\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1)\sum _{n=1}^{N-1}{\log }_2\left(P_{M_1}\right(y_n\mid x_n,D_{<n}\left)\right)\\ & =-\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(\sum _p\frac{{\prod }_{n=1}^N{P}_{M_1}(y_n\mid p_n)}{{\prod }_{n=1}^{N-1}{P}_{M_1}(y_n\mid x_n,D_{<n})}P\right(p\left)\right)\\ & -\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1)\sum _{n=1}^{N-1}{\log }_2\left(P_{M_1}\right(y_n\mid x_n,D_{<n}\left)\right)\\ & =-\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(\sum _p{P}_{M_1}\right(y_N\mid p_N)\dots P_{M_1}(y_1\mid p_1\left)P\right(p\left)\right)\end{array}$$

In the second equality, we used the assumption that our inductor adjusts its probabilities according to incoming evidence using Bayesian updating.

According to result 3.8.1 in this book, the semimeasure for programs on a monotone, plain UTM matching the outputs of a program $\mu$ must be $\ge 2^{-C(\mu ,M_1)}$. Inserting this bound yields:

$$\begin{array}{cc}& \sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{M_1}(\cdot \mid x_n,D_{<n}\left)\right)\\ & =-\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(\sum _p{P}_{M_1}\right(y_N\mid p_N)\dots P_{M_1}(y_1\mid p_1\left)P\right(p\left)\right)\\ & \le -\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_n\mid x_n)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(2^{-C(\mu ,M_1)}{P}_{\mu }\right(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1\left)\right)\\ & =C(\mu ,M_1)+\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n\left)\right).\end{array}$$

Claim 2: A bounded induction still efficiently predicts efficiently predictable data

Setup

Now, we’re going to modify the setup from the previous section, bounding our induction to make it computable. Instead of running programs $(p_{\text{read}},x_n,p)$, where $p$ is drawn from the set of all bit strings of length $T$, we restrict ourselves to programs of length $T$ that require a maximum of $s$ space and a maximum of $t$ time steps.

Specifically, we construct a new bounded UTM $M_2$ from our UTM $M_1$. $M_2$ only has $s+1$ cells of work tape available. If the head moves to the last cell of the work tape, $M_2$ immediately halts. Further, $M_2$ always halts itself after $t$ execution steps if it has not halted yet. This bounded induction will no longer be optimal in the sense of having an SI-style bound on its total error that depends only on the entropy and Kolmogorov complexity of the data-generating process $\mu$, because $\mu$ might not be computable in time $t$ and space $s$.

Claim

Our bounded induction still has a weaker upper bound on its total expected prediction error: If there is some program ${\mu }^{\ast }$ that is an “efficient predictor” of $\mu$, in the sense that ${\mu }^{\ast }$ approximates the probability assignments of $\mu$ up to some error we deem ‘acceptable’, our induction will predict the data as well as this efficient predictor, up to an offset equal to the efficient predictor’s description length.

Specifically, for any program ${\mu }^{\ast }$ included in the set of programs our bounded induction runs over, we have the bound:^[9]

$$\begin{array}{}\begin{array}{cc}\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{M_2}(\cdot \mid x_n,D_{<n}\left)\right)\le & C({\mu }^{\ast },M_2)\\ & +\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{{\mu }^{\ast }}(\cdot \mid x_n\left)\right),\end{array}& \text{(1.2)}\end{array}$$

for all $N\in N_{>0}$. So, for any program ${\mu }^{\ast }$ with minimum description length $\le T$ on $M_2$ that is computable in time $t$ and space $s$, the computationally bounded induction will have its total prediction error bounded by the prediction error of ${\mu }^{\ast }$ plus the minimum description length of ${\mu }^{\ast }$ on $M_2$.

Proof

Proceeds completely analogously to the proof for Claim 1, except that we substitute in $P_{{\mu }^{\ast }}(y_n\mid x_n)$ instead of $P_{\mu }(y_n\mid x_n)$. So we won’t write it out again.

Because

$$\begin{array}{cc}& \sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{{\mu }^{\ast }}(\cdot \mid x_n\left)\right)=\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n\left)\right)+\sum _{n=1}^N{D}_{\text{KL}}\left(P_{\mu }\right(\cdot \mid x_n),P_{{\mu }^{\ast }}(\cdot \mid x_n\left)\right),\end{array}$$

the only difference between this bound and the bound for the computationally unbounded induction from Equation (1.1) is an additional term ${\sum }_{n=1}^N{D}_{\text{KL}}\left(P_{\mu }\right(\cdot \mid x_n),P_{{\mu }^{\ast }}(\cdot \mid x_n\left)\right)$, the KL divergence between the data-generating process $\mu$ and the program ${\mu }^{\ast }$, summed over all input-label pairs.

Why would we suppose that a program ${\mu }^{\ast }$ that gets low prediction error with limited compute exists? Well, for some problems, an efficient predictor probably doesn’t exist. But empirically, we can do pretty well on many prediction problems we encounter in the real world using an amount of compute that’s practically feasible to obtain. Why that is, I don’t know. Perhaps it is somehow related to why a lot of the world seems to abstract well.

Claim 3: The bounded induction is still somewhat invariant under our choice of UTM

Given any program ${\mu }^{\ast }$ that can run on a plain, monotone, bounded UTM $M_3$ in space $s$ and time $t$, we can run it on some other plain, monotone, bounded UTM $M_2$ in space $O\left(s\right)$ and time $O\left(t{\log }_2\right(t\left)\right)$.^[10] Thus, the Kolmogorov complexity $C({\mu }^{\ast },M_3)$ of ${\mu }^{\ast }$ on $M_3$ is bounded by

$$\begin{array}{cc}& C({\mu }^{\ast },M_3)\le C({\mu }^{\ast },M_2)+C(M_2,M_3)\end{array}$$

provided $M_3$ has sufficient computational resources available, because we can just simulate $M_2$ on $M_3$ and then run ${\mu }^{\ast }$ on the simulated $M_2$.

Therefore, our total prediction error for bounded induction on any other plain monotone UTM $M_3$ bounded to $s^{\prime }\ge c_{s}s$ space and $t^{\prime }\ge c_{t}t{\log }_2\left(t\right)$ time, where $c_s,c_t\ge 1$ are the constant prefactors for simulating $M_2$ on $M_3$, will still be bounded by

$$\begin{array}{}\begin{array}{cc}\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{M_3}(\cdot \mid x_n,D_{<n}\left)\right)\le & C({\mu }^{\ast },M_2)+C(M_2,M_3)\\ & +\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{{\mu }^{\ast }}(\cdot \mid x_n\left)\right).\end{array}& \text{(1.3)}\end{array}$$

for all $N\in N_{>0}$. So, our choice of UTM matters somewhat, since we might need more space and execution time on a different UTM to implement an equally efficient predictor. However, converting to a different UTM only increases the required execution time from $t$ to $O\left(t{\log }_2\right(t\left)\right)$ and the required space from $s$ to $O\left(s\right)$. So, provided $M_3$ has sufficient space $s^{\prime }$ and time $t^{\prime }$, the additional prediction error we get is just $C(M_2,M_3)$, which is typically small for most $M_2,M_3$ we might usually consider using.

Prediction error bound for Bayesian learning on neural networks

Claim 4: We can obtain a similar prediction error bound for Bayesian learning on neural networks

Now, we will derive a similar style of bound for an inductor using Bayesian learning on neural networks.

Setup

In this setting, our inputs $x$ are finite-dimensional vectors of real numbers $x\in X\subseteq R^{d_{\text{in}}}$. The labels are still binary, $y\in \{0,1\}$.^[11] The inductor now makes its predictions using functions $f\left(w\right)$, which take vectors $x_n\in X$ as input and output probabilities for the data labels $y_n$. The functions are all part of some space of functions $f\in F$. The functions are parametrized by a parameter-function map $M:R^D\to F$ with $D\in N$. We call $D$ the number of neural network parameters. We refer to the probabilities the function $f\left(w\right)$ outputs for input vector $x_n$ as $f(y_n\mid x_n,w)$. As in the previous sections, we assume that the data labels $y_n$ were generated from the inputs $x_n$ by some probabilistic program $\mu$. Note that we do not make any assumptions about the inputs $x_n$ being drawn IID.

The inductor starts with a uniform prior over some finite hypervolume $W$ in parameter space: $W=(-\frac{L}{2},\frac{L}{2}{)}^D\subset R^D$. The inductor makes its predictions as

$$P_f(y_n\mid x_n,D_{<n})=\int dwf(y_n\mid x_n,w)P(w\mid D_{<n}).$$

where $P(w\mid D_{<n})$ is the probability density the inductor places on parameter configuration $w$ after updating on data-label pairs $(x_1,y_1,\dots ,x_{n-1},y_{n-1})$.

Claim

The total expected prediction error of this induction measured in bits of cross-entropy is upper bounded by

$$\begin{array}{}\begin{array}{cc}\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_f(\cdot \mid x_n,D_{<n}\left)\right)\le & C(w^{\ast },ϵ,f)+Nϵ\\ & +\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),f(\cdot \mid x_n,w^{\ast }\left)\right),\end{array}& \text{(2.1)}\end{array}$$

for all $N\in N_{>0}$, all parameter configurations $w^{\ast }\in W$, and all $ϵ\in R_{\ge 0}$. Here, $C(w^{\ast },ϵ,f)$ is the logarithm of the ratio between the volume of the whole prior $V_W:={\int }_{W}dw=L^D$, and the volume taken up by the set $W_{ϵ,w^{\ast }}$ of parameter configurations that are mapped to functions which match the log-probabilities of $f(y_n\mid x_n,w^{\ast })$ up to tolerance $ϵ$:

$$\begin{array}{cc}& C(w^{\ast },ϵ,f):=-{\log }_2\left(\frac{{\int }_{W_{ϵ,w^{\ast }}}dw}{V_W}\right)\\ & W_{ϵ,w^{\ast }}:=\{w\in W\mid |{\log }_{2}f(y\mid x,w)-{\log }_{2}f(y\mid x,w^{\ast })|\le ϵ\forall (x,y)\in X\times \{0,1\left\}\right\}\end{array}$$

In other words, if there is a parameter configuration $w^{\ast }\in (-\frac{L}{2},\frac{L}{2}{)}^D$ that is mapped to a function $f\left(w^{\ast }\right)$ that is an efficient predictor of the data, in the sense that $f\left(w^{\ast }\right)$ approximates the probability assignments of $\mu$ up to some error, the inductor will predict the data as well as this efficient predictor $f\left(w^{\ast }\right)$, plus a tolerance $ϵ\in R_{\ge 0}$ we can freely choose, up to an offset equal to the cost in bits of specifying the predictor $f\left(w^{\ast }\right)$ in the parameter space to $ϵ$ precision. Intuitively, the reason we don’t just always choose $ϵ=0$ in this bound is that our parameters are real numbers, so describing the location of $f\left(w^{\ast }\right)$ in parameter space exactly could sometimes take infinitely many bits.

High-level proof summary

The proof works analogously to the proof for the error bound in Equation (1.1), except that sums over programs are replaced by integrals over parameters, and the semimeasure of programs in the prior matching the outputs of efficient predictor ${\mu }^{\ast }$ on all possible input bit strings $x\in \{0,1{\}}^{\ast }$ is replaced by the volume of $W_{ϵ,w^{\ast }}$, the set of parameter configurations matching the log-probabilities output by function $f\left(w^{\ast }\right)$ to $ϵ$ precision.

Proof

As before, we start by rearranging our expression for the total cross-entropy:

$$\begin{array}{cc}& \sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_f(\cdot \mid x_n,D_{<n}\left)\right)\\ & =-\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1)\sum _{n=1}^N{\log }_2\left({\int }_{W}dwf\right(y_n\mid x_n,w\left)P\right(w\mid D_{<n}\left)\right)\\ & =-\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(\frac{1}{V_W}{\int }_{W}dw\prod _{n=1}^{N}f\right(y_n\mid x_n,w\left)\right)\end{array}$$

In the second equality, we used the assumption that our inductor adjusts its probabilities over parameter configurations in response to incoming evidence using Bayesian updating.

Now, we restrict the integral ${\int }_{W}dw$ to points in $W_{ϵ,w^{\ast }}$, then use the bound $\left|{\log }_{2}f\right(y\mid x,w)-{\log }_{2}f(y\mid x,w^{\ast }\left)\right|\le ϵ$ we have for points in this set:

$$\begin{array}{cc}& \sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_f(\cdot \mid x_n,D_{<n}\left)\right)\\ & =-\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(\frac{1}{V_W}{\int }_{W}dw\prod _{n=1}^{N}f\right(y_n\mid x_n,w\left)\right)\\ & \le -\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(\frac{1}{V_W}{\int }_{W_{ϵ,w^{\ast }}}dw\prod _{n=1}^{N}f\right(y_n\mid x_n,w\left)\right)\\ & \le -\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(\frac{1}{V_W}{\int }_{W_{ϵ,w^{\ast }}}dw{2}^{{\sum }_{n=1}^N{\log }_2\left(f\right(y_n\mid x_n,w^{\ast }\left)\right)-Nϵ}\right)\\ & =-\sum _{y_N,\dots ,y_1}{P}_{\mu }(y_N\mid x_N)\dots P_{\mu }(y_1\mid x_1){\log }_2\left(\frac{{\int }_{W_{ϵ,w^{\ast }}}dw}{V_W}{2}^{{\sum }_{n=1}^N{\log }_2\left(f\right(y_n\mid x_n,w^{\ast }\left)\right)}{2}^{-Nϵ}\right)\\ & =-{\log }_2\left(\frac{{\int }_{W_{ϵ,w^{\ast }}}dw}{V_W}\right)+\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),f(\cdot \mid x_n,w^{\ast }\left)\right)+Nϵ\\ & =C(w^{\ast },ϵ,f)+\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),f(\cdot \mid x_n,w^{\ast }\left)\right)+Nϵ\end{array}$$

Comments

1. The bound holds for any $w^{\ast }\in W$ and any $ϵ\in R_{\ge 0}$, though the tightest bound will of course come from the $w^{\ast }$ and $ϵ$ that balance the tradeoff between predictive accuracy and description length best.

2. The larger $N$ is, the more predictive accuracy matters relative to description length, and the smaller we might want to set $ϵ$ if we want to obtain the tightest bound.

3. If we have a more specific question about generalization error, we can get a tighter bound by restricting $W_{ϵ,w^{\ast }}$ to range over a more limited set of possible input/​output pairs. For example, if we’re confident an image classifier will never receive input images above a certain brightness, we can exclude all images above that brightness level from the set $X$ in the definition of $W_{ϵ,w^{\ast }}$, which might make $C(w^{\ast },ϵ,f)$ smaller and the upper bound tighter.

4. This derivation assumes a uniform prior over parameters for simplicity, but it goes through analogously for other priors such as Gaussians.

Relating $C(w^{\ast },ϵ,f)$ to SLT quantities

$C(w^{\ast },ϵ,f)$ is a pretty similar quantity to the $ϵ$-ball that defines the learning coefficient in Singular Learning Theory. There, the prediction error in-distribution includes the logarithm of a term of the form^[12]

$$\begin{array}{cc}& V\left(ϵ\right):=\frac{{\int }_{W_{ϵ}}dw}{V_W}\\ & W_{ϵ}:=\{w\in W\mid L(w)<ϵ\}\\ & L\left(w\right):=\int dxq\left(x\right)\sum _y{D}_{\text{KL}}\left(P_{\mu }\right(y\mid x),f(y\mid x,w\left)\right)\end{array}$$

where $q\left(x\right)$ is the ‘training distribution’ over inputs $x$.

Comparing $-{\log }_{2}V\left(ϵ\right)$ to $C(w^{\ast },ϵ,f)$:

1. The uniform distribution over all inputs $x$ over the whole domain $X$ plays the same role for the definition of $C(w^{\ast },ϵ,f)$ that the ‘training distribution’ does for $V\left(ϵ\right)$.

2. In $C(w^{\ast },ϵ,f)$, the outputs $f(y\mid x,w^{\ast })$ of the reference function $f\left(w^{\ast }\right)$ play the role that the ‘data labels’ $P_{\mu }(y\mid x)$ do in $V\left(ϵ\right)$.

3. $C(w^{\ast },ϵ,f)$ cares about the supremum of divergences over the distribution, $V\left(ϵ\right)$ cares about the average.$V\left(ϵ\right)$ is defined as the integral over the set of parameter configurations that diverge from the data labels by less than $ϵ$ on average over the training data, as scored by KL-divergence, whereas $C(w^{\ast },ϵ,f)$ is defined as the volume of the set of points that diverge from $f\left(w^{\ast }\right)$ by epsilon or less on all data points, as scored by log‑probability difference.

These differences are the price of describing prediction error in general instead of ‘in-distribution’. In SLT, we assume that our data $x_n$ are drawn IID from some known distribution $q\left(x\right)$. In that case, average error over that distribution is enough to bound the inductor’s expected average error on future data. Without this assumption of IID sampling, we need to classify functions $f\left(w\right)$ based on how closely their outputs align with our reference $f\left(w^{\ast }\right)$ on all possible inputs $x$. Or at least, all inputs $x$ we think the inductor might possibly encounter.

In SLT, $ϵ$ is also set to $ϵ\propto \frac{1}{N}$ in the expression for the prediction error instead of being left free as in Equation (2.1), because the theory is primarily concerned with the infinite data limit $N\to \infty$, where describing the solution to exact precision is ‘worth it’ and yields a tighter bound. To put that slightly more quantitatively: One term for the prediction error in SLT scales as $Nϵ$, while $-{\log }_{2}V\left(ϵ\right)$ can be shown to only scale as $-\lambda {\log }_2ϵ+o\left({\log }_2ϵ\right)$^[13], where $\lambda$ is a scalar number called the learning coefficient. So, in the vanilla SLT setup, letting $ϵ$ go to zero for $N\to \infty$ as $ϵ\propto \frac{1}{N}$ yields a tighter bound for the prediction error than setting it to some finite non-zero value. But the bound in this post is supposed to work for any amount of data $N$, so we don’t set $ϵ$ to any particular value.

Open problems and questions

Section TL;DR: What kind of neural network architectures have a prior equivalent to that of a bounded universal Turing machine? How can we estimate the description length $C(w^{\ast },ϵ,f)$ in practice?

How do the priors actually relate to each other?

So, we can sort of think about Bayesian learning on neural networks and compute-bounded Solomonoff induction using a similar set of mathematical tools. But how similar are these induction processes really? That is, how much does a uniform prior over parameter configurations on some neural network architecture resemble a uniform prior over programs on some compute-bounded UTM?

Another way of asking that question is whether we can get something like Equation (1.3) for switching between a bounded UTM and a neural network, and vice versa. So, can we get something like:

Conjecture 1: For any parameter vector $w^{\ast }$ parametrizing some function $f\left(w^{\ast }\right)\in F$, the prediction error of an inductor using bounded UTM $M_2$ is bounded by

$$\begin{array}{cc}\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{M_2}(\cdot \mid x_n,D_{<n}\left)\right)\le & C(w^{\ast },ϵ,f)+C(f,M_2)+N(ϵ+\widetilde{ϵ})\\ & +\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),f(\cdot \mid x_n,w^{\ast }\left)\right),\end{array}$$

where $C(f,M_2)$ is the description length of the neural network architecture on UTM $M_2$ to precision $\widetilde{ϵ}$.^[14] Provided $M_2$ has enough time and memory to simulate $f\left(w^{\ast }\right)$, of course.

Conjecture 2 (Likely false for arbitrary NN architectures): For any program ${\mu }^{\ast }$ on bounded UTM $M_2$, the prediction error of an inductor using neural network architecture $f$ is bounded by

$\begin{array}{cc}\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_f(\cdot \mid x_n,D_{<n}\left)\right)\le & C({\mu }^{\ast },M_2)+C(M_2,ϵ,f)+Nϵ\\ & +\sum _{n=1}^{N}H\left(P_{\mu }\right(\cdot \mid x_n),P_{{\mu }^{\ast }}(\cdot \mid x_n\left)\right),\end{array}$

where $C(M_2,ϵ,f)$ is the description length in bits of bounded UTM $M_2$ on neural network architecture $f$ to precision $ϵ$.

If both of these conjectures were true, doing Bayesian learning using neural networks instead of an ensemble of programs would be almost no more of a change than doing Bayesian learning in one programming language instead of another.^[15]

My guess is that something vaguely like Conjecture 1 is true. With sufficient compute, we can use a UTM to simulate any neural network architecture to some arbitrary desired floating point precision. But I think Conjecture 2 is generally false, because not every neural network architecture can simulate a bounded UTM. Remember, our definition of ‘neural network’ here was basically just ‘a space of functions $F$ parametrized by some parameter-function map $M:R^D\to F$’. A family of polynomials would satisfy that definition. And I doubt a uniform prior over polynomials acts much like a uniform prior over compute-bounded programs.

But maybe Conjecture 2 still holds for some more restricted set of neural network architectures? Like, say, architectures capable of simulating a bounded UTM. RNNs and transformers run in chain-of-thought mode can do this, for example.^[16] I originally thought that this condition would be sufficient. But proving the conjecture for transformers in chain-of-thought mode turned out to be trickier than I thought.^[17] Maybe you just need to be a bit cleverer about how to do the UTM simulation than I was so far. Or maybe, being able to simulate a bounded UTM actually isn’t a sufficient requirement for Conjecture 2, and the architecture needs to have some additional property. In that case, it’d be interesting to find out what that property is.

What does $C(w^{\ast },ϵ,f)$ look like in practice?

For example, does $C(w^{\ast },ϵ,f)$ behave like $V\left(ϵ\right)$ in vanilla SLT in the limit $ϵ\to 0$? That is, for small enough $ϵ$ and some reasonable conditions on the NN architecture^[18] do we often get something like

$$C(w^{\ast },ϵ,f)\propto -{\lambda }^{\prime }{\log }_2ϵ$$

where ${\lambda }^{\prime }$ would then be some number analogous to the learning coefficient $\lambda$ in vanilla SLT? Can we use stochastic gradient Langevin dynamics (SGLD) sampling to estimate $C(w^{\ast },ϵ,f)$ on neural networks in real life, the same way people use it to determine the learning coefficient? If a solution can generalize out-of-distribution, it can certainly generalize in-distribution, but the reverse is generally not true. So, presumably $C(w^{\ast },ϵ,f)$ would tend to be smaller than $-{\log }_{2}V\left(ϵ\right)$. But how much smaller does it tend to be in practice? In other words, how much does OOD generalization error usually differ from in-distribution generalization error?

Acknowledgments

Thanks to Aram Ebtekar for providing many useful citations. Thanks to Lee Sharkey for helping me come up with a title. Thanks to Cole Wyeth for spotting an unnecessary condition in my original definition of the bounded UTM. And thanks to Aram Ebtekar as well as Mathias Dellago, Alexander Gietelink Oldenziel, Daniel Murfet, David Quarel, Kaarel Hänni, John Wentworth, Dmitry Vaintrob, Jake Mendel, Linda Linsefors, and Scott Aaronson for various discussions and ideas that were causally upstream of my writing this.

1. ^

   Though in practice, using the formulas for models trained on finite amounts of data does seem to (maybe?) work alright a lot of the time. In our experience so far at least. Provided we aren’t screwing up things without noticing, which tends to happen a lot in research.

2. ^

   It also does other things, but this is maybe its most famous result, and the one that matters most for this post.

3. ^

   I expect that basically nothing in the first part is actually novel, though I haven’t managed to track down citations for every result in it in the exact form given here. If you think you know your AIT and don’t need to read this part, you might be right. But I’d advise some caution before skipping it. I wrote it partially because many AIT-knowledgeable people I talked to about this topic turned out not to know these things.^[19]

4. ^

   As in a program that outputs probabilities as strings. Those probabilities are then used to sample the labels. Note that the program can output probabilities $1.0$ and $0$, so the labels $y_n$ can be deterministic functions of the inputs $x_n$, they just don’t need to be.

5. ^

   So, not prefix-free. Lots of standard AIT results assume a prefix-free UTM. This post does not. AIT-savvy skim readers beware. If you compare the theorems here to results phrased for the setting of prefix-free programs, you might become pretty confused.

6. ^

   See e.g. the start of section three here for more on the definition of monotone Turing machines.

7. ^

   As in the standard setup for Solomonoff induction with probabilistic programs, $M_1\left(p_n\right)$ can keep running and printing more output digits indefinitely, representing the output probabilities with ever higher precision.

8. ^

   So, if $\mu$ is a deterministic program, this second term will vanish.

9. ^

   See also, for example, theorem 1 this paper, which shows almost the same thing in an RL setting.

10. ^

    See the proof here for example.

11. ^

    The derivation should work for other kinds of settings as well though, such as next token prediction in language modelling. I’m just sticking to a specific simple case to make the math easier to follow.

12. ^

    For the special case of uniform prior, discrete outputs $y$, and our loss function being cross-entropy error measured in bits.

13. ^

    SLT convention usually considers prediction error scored in nats, I’m translating to bits here.

14. ^

    For some to-be-determined definition of ‘precision’ that makes the conjecture work. Basically, we’d want some measure of the floating‑point precision the UTM uses to approximate the real-number-valued parameters and network inputs.

15. ^

    Still only “almost”, because of the extra $ϵ$ terms. Those don’t show up when converting between UTMs.

16. ^

    The results in those links come with some annoying caveats, so if you want to jump on this you might want to use different constructions to do the UTM emulation.

17. ^

    Basically, making unused NN parameters not interfere with the computation no matter what values they’re set to is kind of tough. As a consequence, I keep ending up with prefactors $>1.0$ in front of the $C({\mu }^{\ast },M_2)$ term.

18. ^

    e.g., analyticity.

19. ^

    Not judging. I also thought myself somewhat AIT-knowledgeable, but I did not realize some of what it had to say about degeneracy until fairly recently. I spent years being very confused about how learning works because of this.

[testingthewaters]

First of all, this is great stuff and very clearly written.

With regards to this:

Now, we’re going to modify the setup from the previous section, bounding our induction to make it computable. Instead of running programs $(p_{\text{read}},x_n,p)$, where $p$ is drawn from the set of all bit strings of length $T$, we restrict ourselves to programs of length $T$ that require a maximum of $s$ space and a maximum of $t$ time steps.

Specifically, we construct a new bounded UTM $M_2$ from our UTM $M_1$. $M_2$ only has $s+1$ cells of work tape available. If the head moves to the last cell of the work tape, $M_2$ immediately halts. Further, $M_2$ always halts itself after $t$ execution steps if it has not halted yet. This bounded induction will no longer be optimal in the sense of having an SI-style bound on its total error that depends only on the entropy and Kolmogorov complexity of the data-generating process $\mu$, because $\mu$ might not be computable in time $t$ and space $s$.

And the open question

What kind of neural network architectures have a prior equivalent to that of a bounded universal Turing machine?

It seems intuitive to me that what you’re describing is an RNN. Recalling Andrei Karpathy’s writing on the unreasonable effectiveness of RNNs:

Moreover, as we’ll see in a bit, RNNs combine the input vector with their state vector with a fixed (but learned) function to produce a new state vector. This can in programming terms be interpreted as running a fixed program with certain inputs and some internal variables. Viewed this way, RNNs essentially describe programs. In fact, it is known that RNNs are Turing-Complete in the sense that they can to simulate arbitrary programs (with proper weights). But similar to universal approximation theorems for neural nets you shouldn’t read too much into this. In fact, forget I said anything.

If training vanilla neural nets is optimization over functions, training recurrent nets is optimization over programs.

More directly: Instead of bit-string programs with length T, we have the parameters of the RNN. The “work tape” with fixed length s+1 can be compared to the hidden state vector of the RNN, which also has a fixed length. The enforced halting condition is similar to running an RNN for t steps.

Edited to add: I see that you also noted the ability of RNNs to simulate UTMs with regards to conjecture 2. Sorry for the somewhat redundant comment. However, you noted that you didn’t succeed in proving conjecture 2 wrt transformers and chain of thought. Did you succeed for RNNs?

[Lucius Bushnaq]

The same could be said of transformers run in chain of thought mode. But I tried deriving conjecture 2 for those, and didn’t quite succeed.

The trouble is that you need to store the programs $p$ in the RNN/​transformer weights, and do it in a way that doesn’t ‘waste’ degrees of freedom. Suppose for example that we try to store the code for the programs in the MLPs, using one ReLU neuron to encode each bit via query/​key lookups. Then, if we have more neurons than we need because the program $p$ is short, we have a lot of freedom in choosing the weights and biases of those unnecessary neurons. For example, we could set their biases to some very negative value to ensure the neurons never fire, and then set their input and output weights to pretty much any values. So long as the weights stay small enough to not overwhelm the bias, the computation of the network won’t be affected by this, since the ReLUs never fire.

The problem is that this isn’t enough freedom. To get $C({\mu }^{\ast },M_2)$ in the formula without a prefactor $>1.0$, we’d need the biases and weights for those neurons to be completely free, able to take any value in $W$.

EDIT: Wrote the comment before your edit. No, I haven’t tried it for RNNs.

[testingthewaters]

Just to clarify, if there was some way to “fill up” the weights of the RNN/​Transformer such that no weights are “free”, that would satisfy the conditions that you’ve set up? As in, if the encoding of $p$ takes up every parameter, that would qualify as a valid solution for the purposes of $C({\mu }^{\ast },M_2)$? (Forgive me, I’m still very new to AIT and the associated work, and my knowledge is still very poor)

[Lucius Bushnaq]

If every bit of every weight were somehow used to store one bit of $p$, excepting those weights used to simulate the UTM, that should suffice to derive the conjecture, yes.^[1]

I think that’s maybe even harder than what I tried to do though. It’s theoretically fine if our scheme is kind of inefficient in terms of how much code it can store in a given number of parameters, so long as the leftover parameter description bits are free to vary.

1. ^

   There’d be some extra trickiness in that under these definitions, the parameters are technically real numbers and thus have infinity bits of storage capacity, though in real life they’re of course actually finite precision floating point numbers.

[testingthewaters]

the parameters are technically real numbers and thus have infinity bits of storage capacity

Yeah, a lot of the stuff about ARNNs having superturing computing capacity rely on the Analog part of the (A)RNN and the weights being therefore real valued. RNNs with rational weights are strictly turing complete I think. (cf. this article)

If every bit of every weight were somehow used to store one bit of p, excepting those weights used to simulate the UTM, that should suffice to derive the conjecture, yes

It’s theoretically fine if our scheme is kind of inefficient in terms of how much code it can store in a given number of parameters

Assuming that the bits to parameters encoding can be relaxed, there’s some literature about redundant computations in neural networks. If the feature vectors in a weight matrix aren’t linearly independent, for example, the same computation can be “spread” over many linearly dependent features, with the result that there are no free parameters but the total amount of computational work is the same.

Otherwise, I don’t think it’ll be easy find a way for the remaining parameters to be fully free to vary, since it is a densely connected network. It might be interesting for you to look into the lottery ticket hypothesis literature, though even there I don’t think the remaining non-ticket weights can be set to any value.

[Lucius Bushnaq]

Assuming that the bits to parameters encoding can be relaxed, there’s some literature about redundant computations in neural networks. If the feature vectors in a weight matrix aren’t linearly independent, for example, the same computation can be “spread” over many linearly dependent features, with the result that there are no free parameters but the total amount of computational work is the same.

There’s a few other cases like this where we know how various specific forms of simplicity in the computation map onto freedom in the parameters. But those are not enough in this case. We need more freedom than that.