Algorithmic Simplicity Priors for Universal Learning

45 concepts36 papers1 proposal

In machine learning, we routinely rely on Occam’s Razor: the philosophical principle that the simplest explanation is usually the best. Yet, for decades, theoretical computer science presented a stark counter-warning. The No Free Lunch (NFL) theorem mathematically demonstrated that across all possible problem domains, no learning algorithm can outperform a purely random search on average.

If the NFL theorem holds, why does machine learning work so well in practice? The answer lies in a profound mismatch between the assumptions of the theorem and the nature of our universe. The NFL theorem assumes a uniform distribution over all mathematically possible worlds, treating highly chaotic, completely random environments as just as likely as structured ones.

But our universe is not uniformly random; it is highly structured, predictable, and computable. By formalizing Occam's Razor through the lens of algorithmic information theory, we can replace uniform distributions with algorithmic simplicity priors. This shift not only bypasses the limitations of the No Free Lunch theorem but also provides a mathematically optimal framework for universal prediction, optimization, and artificial intelligence.


Quantifying Occam's Razor

To transform Occam’s Razor from a vague philosophical preference into a rigorous mathematical tool, we must define "simplicity" objectively. As proposed by R. Solomonott in the foundational paper Inductive Inference Theory - A Unified Approach to Problems in Pattern Recognition and Artificial Intelligence, the simplicity of a hypothesis can be measured by the length of the shortest computer program required to generate it on a universal computer. This shortest program length is known as its Kolmogorov complexity.

If we want to predict future observations based on historical data, a rational agent should consider all computable hypotheses that explain the data, but weight them based on their simplicity. This is formalized by the Solomonoff prior, where the prior probability $P(x)$ of a sequence $x$ is dominated by its shortest program description:

$$P(x) \approx 2^{-K(x)}$$

where $K(x)$ is the Kolmogorov complexity of $x$.

Why does this specific weighting work mathematically? In Principles of Solomonoff Induction and AIXI, Peter Sunehag and Marcus Hutter derived this scheme by applying a principle of indifference to the individual bits of a program representation. By using prefix-free codes (where no valid program is a prefix of another), Kraft's inequality ensures that the sum of these probabilities across all possible programs remains bounded ($\sum 2^{-l} \le 1$). This mathematical constraint allows us to construct a valid, universal probability distribution over an infinite space of computable hypotheses.


Why Simplicity Dominates: The Algorithmic Coding Theorem

The intuition for why an algorithmic simplicity prior reflects reality is deeply tied to the algorithmic coding theorem. Imagine a universal Turing machine whose inputs are chosen by flipping a fair coin for each bit. What kind of outputs will this machine generate most often?

As explored by Iain G. Johnston et al. in Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolution, the frequency of an output is inversely proportional to its algorithmic complexity. If you randomly mash keys on a computer terminal, you are exponentially more likely to accidentally write a short program that outputs a highly symmetric pattern (like 101010...) than you are to write a program that outputs a specific, highly chaotic sequence of random numbers.

Because simpler outputs have vastly more programs that can generate them, they dominate the probability distribution of any system driven by algorithmic processes—including biology, physics, and data generation.


Defeating the No Free Lunch Theorem

By biasing our priors toward simpler, computable environments, we fundamentally break the symmetry required for the No Free Lunch theorem to hold.

In No Free Lunch versus Occam's Razor in Supervised Learning, Tor Lattimore and Marcus Hutter demonstrated that an algorithm that systematically favors the simplest consistent hypothesis will successfully learn across all structured problem domains, provided the training data is sufficiently diverse.

This principle applies directly to optimization problems as well. Tom Everitt et al. proved in Free Lunch for Optimisation under the Universal Distribution that a "free lunch" exists if we evaluate optimization functions under the universal distribution. By prioritizing functions with shorter description lengths over completely random ones, optimization algorithms can bypass linear search times and find solutions with remarkable efficiency.


Universal Prediction and Intelligence

The ultimate theoretical realization of this idea is Universal Sequence Prediction. In a series of papers, including General Loss Bounds for Universal Sequence Prediction, Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences, and Optimality of Universal Bayesian Sequence Prediction for General Loss and Alphabet, Marcus Hutter proved that a Bayesian mixture of all computable distributions, weighted by their algorithmic complexity, acts as a near-perfect predictor.

Why does it converge so fast?

If the true environment generating our data is computable, it must have a finite Kolmogorov complexity, $K(\mu)$. Because our universal prior assigns a weight of at least $2^{-K(\mu)}$ to this true distribution, the predictor can never be completely blind to it. As data arrives, the Bayesian update rapidly prunes away incorrect, overly complex hypotheses. The total expected error or loss of this universal predictor over an infinite horizon is strictly bounded by a constant proportional to the complexity of the true environment. It performs nearly as well as an omniscient predictor that knew the true distribution from the start (Self-Optimizing and Pareto-Optimal Policies in General Environments based on Bayes-Mixtures).

This framework provides a rigorous foundation for defining and measuring intelligence itself. In A Universal Measure of Intelligence for Artificial Agents, Tests of Machine Intelligence, and Universal Intelligence: A Definition of Machine Intelligence, Shane Legg and Marcus Hutter quantified intelligence ($\Upsilon$) as an agent’s expected reward across all possible computable environments. Crucially, each environment's contribution to the score is weighted by its algorithmic probability:

$$\Upsilon(\pi) = \sum_{\mu \in E} 2^{-K(\mu)} V_\mu^\pi$$

This mathematical formulation ensures that an agent's score is primarily determined by its ability to master fundamental, simple patterns before dealing with highly specific, complex scenarios.


Applications Across Learning Systems

While true Kolmogorov complexity is uncomputable (because we can never be certain if a short program will eventually halt and generate our data), the core mechanism of weighting by description length serves as a powerful normative guide across practical domains.

1. Linear Algebra and Optimization

When solving an underdetermined system of linear equations (where there are more unknowns than data points), there are infinitely many valid solutions. In The Simplest Solution to an Underdetermined System of Linear Equations, Hossein Kakavand and James Mammen demonstrated that the "true" underlying vector can be recovered by selecting the candidate vector that minimizes Kolmogorov complexity. This extends the logic of Occam's Razor directly into matrix equations.

2. Automata and Language Learning

Learning Deterministic Finite Automata (DFAs) from arbitrary data distributions is notoriously hard. However, Rajesh Parekh and Vasant G Honavar proved in Learning DFA from Simple Examples that DFAs become efficiently learnable when examples are biased toward simplicity using the Solomonoff-Levin universal distribution.

In modern deep learning, Anna Mészáros et al. utilized the Solomonoff prior in Rule Extrapolation in Language Modeling: A Study of Compositional Generalization on OOD Prompts to study how language models generalize. When a model encounters ambiguous, out-of-distribution prompts, the algorithmic simplicity principle dictates that a rational model should default to the simplest possible rule that explains its training data.

3. Transfer Learning and Online Learning

Algorithmic complexity can also measure task relatedness. In Transfer Learning using Kolmogorov Complexity: Basic Theory and Empirical Evaluations, M. M. Hassan Mahmud and Sylvian R. Ray designed a Bayesian framework where the prior probability of a target hypothesis is inversely proportional to its conditional complexity given a previously learned solution. This guarantees that the system prioritizes new solutions that are easily derived from existing knowledge.

Similarly, in online learning, Vidya Muthukumar et al. showed in Best of many worlds: Robust model selection for online supervised learning that complexity-dependent priors allow a learner to dynamically balance approximation and estimation errors, starting with simple hypotheses and scaling up to complex ones only when the evidence demands it.


The Limits of Pure Simplicity

While algorithmic simplicity priors offer a powerful framework for prediction, they are not a universal cure-all, particularly when human behavior is involved.

In Occam's razor is insufficient to infer the preferences of irrational agents, Stuart Armstrong and Sören Mindermann proved a critical limitation in reward inference. When an AI tries to infer a human's internal values or rewards from their actions, there are always multiple combinations of human preferences and human planning flaws that explain the same behavior.

If the AI relies purely on Kolmogorov complexity to resolve this ambiguity, it often selects "degenerate" solutions—such as concluding that the human is perfectly rational but possesses an incredibly bizarre, mathematically simple reward function. This warning highlights that while a simplicity bias is optimal for predicting passive environments, aligning intelligent systems with human values requires normative assumptions that go beyond pure description length.

Key Foundational Work

Inductive Inference Theory - A Unified Approach to Problems in Pattern Recognition and Artificial Intelligence (1975) — contributed 2 concept elements to this direction.
Inductive Inference Theory - A Unified Approach to Problems in Pattern Recognition and Artificial Intelligence (1975) — contributed 2 concept elements to this direction.
The Very Particular Structure of the Very Hard Instances (1996) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_algorithmic_simplicity_prior_957e911f,
  title = {algorithmic simplicity prior},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algorithmic-simplicity-prior/rdr_957e911f5b8240088f9ceb00bb7154a6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_algorithmic_simplicity_prior_957e911f_v1,
  title = {algorithmic simplicity prior},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algorithmic-simplicity-prior/rdr_957e911f5b8240088f9ceb00bb7154a6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake