TLDR: The simplicity bias in Bayesian statistics is not just a bias towards short description length. 

The folklore relating the simplicity bias in Bayesian statistics to description length is incomplete: while it is true that the fewer parameters you use the better, the true complexity measure which appears in the mathematical theory of Bayesian statistics (that is, singular learning theory) is more exotic. The content of this complexity measure remains quite mysterious, but in this note we point out that in a particular setting it includes a bias towards runtime error-correction. This suggests caution when reasoning about the role of inductive biases in neural network training.

Acknowledgements. Thanks to Jesse Hoogland, Liam Carroll, Rumi Salazar and Simon Pepin Lehalleur for comments.

1. Background

1.1 Relevance to Deep Learning

Consider the problem of solving an ordinary differential equation. A constructive proof involves actually writing down a solution, or an algorithm that in finite time will produce a solution. The Picard-Lindelöf theorem proves that a solution to a broad class of initial value problems exists, but the proof is not constructive: it sets up a contraction mapping on a complete metric space and appeals to the Banach fixed point theorem. 

While the Picard-Lindelöf theorem uniquely characterises the solution as the fixed point of a contraction mapping, and gives an iterative process for approximating the solution, it does not construct the solution. However a construction is not necessary for many of the applications of Picard-Lindelöf (in differential geometry, topology and many parts of analysis). This mode of reasoning about mathematical objects, where it suffices to have characterised^[1] them by (universal) properties, is pervasive in modern mathematics (in the above example, the characterising property is the differential equation, or its associated contraction mapping). However this may seem quite alien to a computer scientist or programmer, who for historical reasons tend to think that there is only one mode of reasoning about mathematical objects, and that is centred on the study of a construction.

In an era where programs are increasingly the product of gradient descent rather than human construction, this attitude is untenable. We may have to accept a mode of reasoning about learned programs, based on understanding the nature of the problems to which they are a solution and the iterative processes that produce them. To understand the implicit algorithms learned by neural networks, it may be necessary from this perspective to understand 

• the computational structures latent in the data distribution, and
• the inductive biases of neural network training.

We do not currently have a good understanding of these matters. If we understood these inductive biases better, it could conceivably help us in the context of AI alignment to answer questions like "how likely is deceptive alignment", "how likely is consequentialism", and "what goals are instrumentally convergent"?

This note is about the inductive biases of the Bayesian learning process (conditioned on more samples, the posterior increasingly localises around true parameters). Since Bayesian statistics is both fundamental and theoretically tractable, this seems potentially useful for understanding the inductive biases of neural network training. However it is worth noting that the relation between these is not understood at present.

1.2 Singular Learning Theory

The asymptotic expansion of the Bayesian free energy, or "free energy formula'', proven by Watanabe in Singular Learning Theory (SLT) introduces the learning coefficient $\lambda$ as a measure of complexity that balances model accuracy in the process of model selection. 

In models that are regular or minimally singular the learning coefficient is easy to understand: it is the effective number of parameters in the model, in a suitable sense. More precisely if a parameter is irrelevant, in the sense that any variation does not change the prediction, this leads to a decrease of $\frac{1}{2}$ in the learning coefficient and thus $2\lambda$ agrees with an effective parameter count in minimally singular models.^[2] Therefore, in these cases, the tradeoff between model accuracy and complexity embodied in the minimisation of the free energy is familiar.

However, in more degenerate models such as neural networks, this connection between the learning coefficient and parameter counting breaks down. In particular, the learning coefficient depends on the data distribution. This is not an obstacle to theoretically deriving or empirically estimating the learning coefficient, but it does mean that we may lack good intuitions for what this (positive, rational) number is measuring.

1.3 Minimum Description Length

There is a circle of ideas containing Occam's razor, Kolmogorov complexity and the Minimum Description Length (MDL) which strongly informs the intuitions in the machine learning community about the meaning of "simplicity" and its role in determining the inductive biases of neural network training. However it is important to note that the mathematical hypotheses required for the attractive coherence among these ideas do not apply to neural networks.

A good reference for the classical treatment of the MDL is

• Grünwald, P. D. (2007). The Minimum Description Length Principle, MIT press.

For the relation of the MDL to Bayesian model selection and the asymptotic expansion of the free energy (in the minimally singular case) see

• Balasubramanian, V. (1997). Statistical inference, Occam's razor, and statistical mechanics on the space of probability distributions, Neural Computation, 9(2), 349-368.

There has been some attempt in recent years to address the fact that the classical treatment of MDL is not applicable to singular models like neural networks:

• Dwevedi, R., Singh, C., Yu, B., Wainwright, M., (2023), Revisiting minimum description length complexity in overparametrized models.

It seems that using SLT one could give a generally correct treatment of MDL. However, until such results are established, one should not presume any fundamental theoretical connection between the simplicity bias of Bayesian statistics of neural networks and any simple notion of "description length". 

2. Turing Machines With Errors

In this section we give an example where the complexity measure in the free energy asymptotic for singular statistical models (the learning coefficient) is sensitive to algorithmic structure that goes beyond the number of effective parameters.

The example is derived from a literature that has attempted to bridge semantics of logic with statistical learning theory, based on ground-breaking work of Ehrhard-Regnier on differential linear logic. We have tried to make the presentation here self-contained, but the reader can find more information in the following references:

• Clift, J., (2017), Turing Machines and Differential Linear Logic, MSc thesis.
• Clift, J., Murfet, D., Wallbridge, J. (2021), Geometry of Program Synthesis.
• Waring, T., (2021), Geometric Perspectives on Program Synthesis and Semantics, MSc thesis.

We consider the problem of predicting the outputs of a computable generating process by finding codes for a Universal Turing Machine (UTM). We have in mind a standard kind of UTM $U$ with a description tape (where we write the code which specifies the machine to be simulated), a state tape (where the state of the simulated machine is written) and a work tape (containing the state of the tape of the simulated machine). Some input sequence $x\in {\Sigma }^{\ast }$ is written to the work tape, a code $c$ is written to the description tape, an initial state is written to the state tape, and then the UTM proceeds to simulate the Turing Machine $M$ with code $c$ until it halts with the output $M\left(x\right)$ on the work tape, if it halts.

We can consider this process as actually instantiated in a machine or, more abstractly, an automata. The role of error in such processes is very interesting and leads ultimately to the problem of run-time error correction in modern computing: every step of communication or processing in a computer involves some probability of error and, although small, the large number of steps and size of the messages involved means that some error correction may be necessary for meaningful computation to take place.

We suppose that some computable process in the environment is outputting strings $y\in {\Sigma }^{\ast }$ according to some true distribution $q\left(y|x\right)$, with each symbol having some small error from the output $T\left(x\right)$ of a TM $T$. The problem of statistical inference is to figure out which TM it is, from a given set of input-output pairs $D_n=\left\{\right(x_i,y_i){\}}_{i=1}^n$. Of course there will be (infinitely) many TMs consistent with the set of samples $D_n$, so we expect that the result of statistical inference will be a probability distribution over codes. This is what we call the Bayesian posterior $p\left(c|D_n\right)$. We might bias this towards shorter machines by putting a prior $\phi \left(c\right)$ over the space of models (codes).

This is an old problem, but we consider it from a new angle. Rather than considering a discrete space of codes with a special prior, we extend our set of allowed models of the generating process beyond TMs (as represented by their codes) to include codes with error channels. In just the same way that each "organ'' of the automata^[3] in von Neumann's work may have some probability of error, we allow each symbol $c_i$ of the code $c$ of $M$ to have some probability of error when it is read by the UTM. The specification of the allowed distribution of errors for each symbol in $c$ defines a point in the space $W$ of codes-with-error-channels, which we take as the parameter space of our new extended statistical model.

Given one of these codes-with-error-channels $w\in W$ and an input sequence $x\in {\Sigma }^{\ast }$ the contents of the work tape of $U$ after some given number of steps depends on the errors encountered during the execution of the UTM; that is, it is a probability distribution $p(y|x,w)$. This is our model. Those parameters $w\in W$ which lead to final work tapes close to the true output $y$, in the sense that the KL divergence between the two probability distributions is small, are more highly preferred by the Bayesian posterior $p\left(w|D_n\right)$, which is now defined on the extended space of models $W$.

2.1 Error as a Probe of Structure

Of course, if the generating process $T$ is computable then its distribution of outputs $q\left(y|x\right)$ can be realised by a model $p(y|x,w)$ where $w$ has no errors (for example, the code of $T$). So what is there to be gained by considering this larger space of models?

The distribution over outputs that results from a given distribution of possible errors in reading a symbol $c_i$ of the code $c$ reflects the way that the symbol is used in the computation. While this is clear informally (to understand how something works, try perturbing one of its components and see what happens) this can be given a formal interpretation in the context of differential linear logic, where there is a connection between this sensitivity analysis and the Taylor series expansion of a proof. The simplest example is that if the introduction of errors in $c_i$ does not affect the output distribution at all then it is reasonable to conclude that $c_i$ is irrelevant to the computation. This already suggests a natural connection between the local learning coefficient $\lambda \left(c\right)$ and the program length of $c$ whereby the posterior $p\left(w|D_n\right)$ tends to concentrate around shorter programs which predict the dataset $D_n$ to the same degree of accuracy. We will turn to more interesting examples soon.

The upshot is that given a TM $M$ with code $c$ the way that the probability distribution $p(y|x,w)$ varies when we vary $w$ near $c\in W$ (noting that $p\left(M\right(x)|x,c)=1$) encodes a lot of information about the structure of the algorithm $M$ when executed on the input $x$, via the effects of perturbing each one of the bits in the code $c$. This variation in turn is reflected in the local geometry of the function

near $c$, of which the local learning coefficient $\lambda \left(c\right)$ is a scalar invariant. The conclusion is that the algebraic geometry of the function germ $(K,c)$ should be expected to reflect the internal structure of the TM $M$ to some degree. At the moment it remains unclear how strong this connection between geometry of $K$ and internal structure of $M$ actually is.

2.2 The Example

We fix an input $x\in {\Sigma }^{\ast }$ for which the true output is $T\left(x\right)\in \Sigma$. For simplicity we assume this is a single symbol and that we judge models $p(y|x,w)$ on their predictions for the contents of this single tape square. The contribution of the data sample $x$ to the KL divergence $K\left(w\right)$ can be shown to be equivalent^[4] to $\int q\left(x\right)H(x,w)dx$ where

which is a polynomial in the coefficients specifying the probability distributions that make up $w$. Here ${\delta }_{\sigma ,T\left(x\right)}$ is the Kronecker delta which is $1$ if $\sigma =T\left(x\right)$ and zero otherwise.

Let us now consider the local behaviour of $K$ (equivalently $H$) at a point of parameter space which represents a TM $M$ with code $c$. We fix a single symbol of this code and a perturbation of this code in some direction $u$. That is, we consider a parameter $w=w\left(\epsilon \right)$ which agrees with $c$ except that in the $i$th position we replace the symbol $c_i$ by the distribution $c_i+\epsilon u$. For concreteness let us take the original symbol of the code to be $c_i=\underset{–}{0}$ and take $u$ to be the formal linear combination of symbols $\underset{–}{1}-\underset{–}{0}$ so that for small $\epsilon$$c_i+\epsilon u$ is a probability distribution representing a small chance of reading a $\underset{–}{1}$ instead of a $\underset{–}{0}$. Then we can expand $H(x,w)$ in powers of $\epsilon$

where each $h_i=h_i\left(x\right)$ is a function of $x$ only (since we assume there is no uncertainty in the other positions of $c$). Taking $\epsilon \to 0$ we obtain $H(x,c)$ which we may assume is zero; that is, we assume that $M$ gives the correct answer $M\left(x\right)=T\left(x\right)$ for the fixed input $x$. Thus $h_0=0$ and we have

We are interested in the order of this polynomial, that is the least $i$ such that $h_i\ne 0$.

To go further we have to think in more detail about how the UTM $U$ computes the probability $p(\sigma |x,w)$ that is, how the uncertainty in the code $w$ is propagated to uncertainty in the output. Since we run the simulated machine for some fixed number of steps, the UTM itself is run for some number of steps, and thus makes use of exactly $l$ samples from the $i$th symbol of the code for some $l$ that is independent of $x$. The possible trajectories of $U$ are thus dictated by the sequences of possible results $\mu =({\mu }_1,\dots ,{\mu }_l)\in {\Sigma }^l$ and to each we assign a probability

In our example, the distribution in $w$ at the $i$th position is

so that we need only consider sequences where samples $\underset{–}{0},\underset{–}{1}$ appear, and

where $a=a\left(\mu \right)$ is the number of times $\underset{–}{0}$ is sampled in $\mu$ and $a+b=l$.

One can compute that when you run the UTM $U$ as above the resulting probability distribution over outputs is

where the sum is over all executions of $U$ making use of a sequence of samples $\mu$ that, on input $x$, leads to the output symbol $U(\mu ,x)$ equal to $\sigma$. Here $U(\mu ,x)\in \Sigma$ is defined by running the UTM and intervening in any step where the UTM goes to read from the $i$th symbol of the code, so that on the $r$th read for $1\le r\le l$ the UTM sees the symbol ${\mu }_r$.

Combining the above equations

which is zero since when $\epsilon =0$ we have $w=c$ and $p\left(T\right(x)|x,c)=1$ so the first factor in every summand vanishes. Thus $h_1=0$. For $t\ge 2$

For $s\ge 1$

Recall that $b=b\left(\mu \right)$ is $l-a\left(\mu \right)$ where $a\left(\mu \right)$ is the number of $\underset{–}{0}$'s appearing in the sequence $\mu$. Thus $b\left(\mu \right)$ is the number of $\underset{–}{1}$s sampled in the sequence $\mu$, that is, the number of errors. The derivative is nonzero only when $s=b+j$ which for $0\le j\le a$ is only possible (given that $s\ge 1$ and $0\le b\left(\mu \right)\le l$) if $b\le s\le l$. The only "paths'' or sequences $\mu$ that contribute to the $s$-fold derivative are ones which contain $\le s$ errors. Substituting in the above yields

where we have used that

We can use this formula to compute the coefficient $h_t$. 
 

Definition. We say that the Turing Machine $M$ with code $c$ is robust to $s$ errors on input $x$ in position $i$ if, for any execution path $\mu$ of the UTM $U$ initialised with $c$ on the description tape and $x$ on the work tape involving $b\left(\mu \right)\le s$ errors, $U(\mu ,x)=M\left(x\right)$.

Lemma. If $M$ is robust to $s$ errors on input $x$ in position $i$ then $h_t=0$ for $t\le s+1$. That is, the order of $H(x,w)$ in $\epsilon$ is strictly greater than $s+1$.

Proof. We set $A_{\sigma ,j}=\frac{{\partial }^j}{\partial {\epsilon }^j}p(\sigma |x,w){|}_{\epsilon =0}$. If $M$ is robust to $s$ errors in the stated sense, then it is clear from the above that $A_{\sigma ,j}=0$ when $\sigma \ne M\left(x\right)$ and $j\le s$ since it is never true that $U(\mu ,x)=\sigma$ when $\mu$ is such that $b\left(\mu \right)\le j$. In the case where $\sigma =M\left(x\right)$ and $j\le s$

Hence for any $\sigma \in \Sigma$ and any $j\le s$ we have $A_{\sigma ,j}=0$. Thus for $t\le s+1$

since every summand involves a term $A_{M\left(x\right),j}$ with $j\le s$. $\square$
 

Example. Since any TM is robust to zero errors, we always have $h_1=0$. If $M$ is robust to one error on input $x$ then $h_2=0$, so the polynomial $H(x,w)$ is at least cubic in $\epsilon$.

If $M$ is robust to $s$ errors on every input $x$ then $H\left(w\right)=\int H(x,w)dx$ has order $>s+1$ in $\epsilon$, from which we infer that $K\left(w\right)$ has order $>s+1$ in $\epsilon$ locally at $c$. If $\underset{–}{0},\underset{–}{1}$ are the only allowed symbols in the code at this position then the local learning coefficient satisfies $\lambda \left(c\right)\le \frac{1}{s+2}$.

2.3 Summary

The example illustrates one simple way in which the structure of a TM $M$ with code $c$ (in this case, the capability to recover from read errors in its specification during run-time) influences the geometry of the function germ $(K,c)$. We expect there are many further forms of degeneracy, which for example involve sophisticated interactions between bits of the code.

In a minimally singular model every used parameter costs $\frac{1}{2}$ (in the sense that it increases $\lambda$ by that amount) and so our intuition might suggest that in the current setting every used bit in the code should cost $\frac{1}{2}$. It is true that every used bit costs at most $\frac{1}{2}$ but we have just seen that not all bits are created equal: a bit which is "error-corrected" in the sense that when the UTM executes $c$ it is robust to $\le s$ errors in that bit, only costs $\frac{1}{s+2}<\frac{1}{2}$. The principle of minimisation of free energy therefore suggests that, all else being equal, the Bayesian posterior will prefer codes where the bits are error-corrected in this way. That is, two codes of equal length and matching the outputs of the generating process equally well, may nonetheless have neighbourhoods assigned different probability by the posterior, if one of them has error-correction and the other does not. Thus "simplicity'' (in the sense of $\lambda$) includes robustness to errors.

We note that it is straightforward to provide a TM with run-time error-correction at the cost of execution time, by running the program multiple times and applying a majority vote to determine the answer. More sophisticated schemes are possible, and there is a literature that has worked out various ways of doing this.

3. Conclusion

The relation between description length and simplicity biases in Bayesian statistics is well-known, but is a phenomena that is confined to regular models and this class of models does not include neural networks. We do not yet possess conceptually simple general intuitions about the inductive biases of Bayesian statistics. In this note we have exhibited one case in which the simplicity bias is more exotic. 

3.1 Questions and Open Problems

The analysis in this note is preliminary. The set of people working on ideas like this is small, and if you have relevant background in mathematics or ML you could probably figure out something useful. Notes:

• It is not known whether the inductive bias of neural network training contains a preference for run-time error-correction. The phenomenon of "backup heads" observed in transformers seems like a good candidate. Can you think of others?
• It seems that in deep RL, policies which take effective control of the environment might be able to achieve a kind of run-time error-correction which allows them to simplify their policies and thus minimise the free energy. This might lead to a connection between simplicity in Bayesian statistics and the emergence of goal-directedness.
• Simon Pepin Lehalleur (henceforth SPLH) asks "It would be remarkable if some related fact or downstream consequence of this observation had not been observed somewhere in the literature on error-correction and information theory?" There is an extensive literature on error-correction in naturally occurring computational systems. Interesting observations can be found in "Noisy dynamical systems evolve error correcting codes and modularity" by T. McCourt et al, "Resource savings from fault-tolerant circuit design" by A. K. Tan and I. L. Chuang, "Biological error correction codes generate fault-tolerant neural networks" by A. Zlokapa et al. I have only a superficial familiarity with the literature, but it seems to me one could make a career out of bringing modern mathematical techniques to bear on this field.
• SPLH suggests the modest open problem of proving this is a consequence of SLT :) 

1. ^{^}

   Simon Pepin Lehalleur says: "defined implicitly" is another common way to get at the same idea. Statistics is in some sense all about implicit definitions ("Statistics is the inverse problem to probability").

2. ^{^}

   In the case where the KL divergence or loss function is locally, after a change of variables, a sum of squares ${\sum }_{i=1}^{d^{\prime }}{w}_i^2$ in $R^d$ then since changing each of the $w_i$ for $1\le i\le d^{\prime }$ increases the loss, we refer to these parameters as "relevant" whereas changing each of the $w_i$ for $i>d^{\prime }$ does not change the loss so we refer to these parameters as "irrelevant". More precisely, there is a finite range within which these parameters can be varied without changing the loss.

3. ^{^}

   By an "organ" von Neumann means a fundamental unit, from which more complicated computations can be built.

4. ^{^}

   In the sense that there exist $c_1,c_2>0$ such that with $H\left(w\right)=\int H(x,w)dx$ we have $c_{1}H\left(w\right)\le K\left(w\right)\le c_{2}H\left(w\right)$. In particular the local learning coefficients of $K$ and $H$ agree.