Deep-layered machines have a built-in Occam's razor
summary
The gist
Deep-layered machines have a built-in Occam’s razor because they are inherently biased towards simplicity in the models they generate This paper presents a unified understanding of two seemingly…
In short
The paper shows that deep-layered machines naturally favor simple outputs due to an inherent Occam's razor. It develops a mathematical theory confirming that output distributions become exponentially biased towards simplicity as network depth increases, linking this to the structure of transition matrices and spectral gaps.
Key concepts
- Hamming Weight
- This is the number of '1's in a truth table, representing how many inputs result in a true output. The paper uses this to describe the distribution of outputs from deep machines, showing that simple functions (low Hamming weight) are more likely as depth grows.
- Critical Network Depth (ncrit)
- This is a specific network depth where the bias towards simplicity becomes irrelevant because true and false outputs start dominating the output distribution. This depth is suggested to grow with 2k, allowing systems to choose complexity based on this point.
- Spectral Gap
- The difference between eigenvalues governing different parts of the network's behavior. A specific gap relates to how quickly the true/false outputs equilibrate compared to the bulk outputs, indicating when simplicity bias loses its dominance.
Terminology used across episodes
This episode discusses
The paper
Deep-layered machines have a built-in Occam's razor · Read on arXiv
London Institute for Mathematical Sciences · Royal Institution
Many complex systems map vast numbers of microscopic descriptions onto far fewer macroscopic outcomes. Surprisingly, these input-output maps strongly favor simple outputs. In an exactly solvable deep-layered machine, we prove that simplicity bias strengthens with every layer. The probability of an output function F approaches (F) proportional to 2-K(F), where K is the Kolmogorov complexity. Our results show that hierarchical composition alone can generate an intrinsic Occam's razor, suggesting a general mechanism for simplicity bias in learning and evolution.
Transcript
Introduction to the show: ident: Condensed Matter. The day in condensed matter: materials, phases and the measurements under them.
Kai: We're looking at the paper: "Deep-layered machines have a built-in Occam's razor".
Mira: Here's the gist of the paper. Deep-layered machines have a built-in Occam’s razor because they are inherently biased towards simplicity in the models they generate This paper presents a unified understanding of two seemingly different scientific puzzles: the observed tendency of input-output maps to be biased towards simple outputs and the success of deep-layered machines at producing parsimonious solutions The authors introduce an exact theory for the output distribution of deep-layered machines, confirming that this output is exponentially biased towards simplicity as network depth increases.
Kai: The Core Theory of Output Distribution The paper establishes a mathematical theory for the distribution of outputs given a random choice of inputs to a deep-layered machine The output distribution depends only on the Hamming weight of the output function, which is the number of 1s in its truth table.
Mira: For general k arguments, this probability is related to a vector of probabilities p(n) derived from a transition matrix A such that q(n) = Anq(0).
Kai: The elements of the transition matrix A are defined by the formula Ai,j = 1/l(l/j!) (l − i)/(l−j).
Title and authors: Kai: So we're looking at this paper called "Deep-layered machines have a built-in Occam's razor". It basically says that deep layers of machines are naturally biased towards simple outputs, which is something we see in input output maps generally.
Mira: I think the key thing here is connecting that observation to how these deep machines actually work. They're not just random; they generate these simpler functions more often than we'd expect from a purely random process <ref:2603.01217#pg1>.
Lev: From an engineering standpoint, it’s interesting because it suggests we might be designing systems that inherently favor the simplest possible solutions, which could affect how we approach model complexity in real hardware <ref:2603.01217#pg4>.
Kai: Exactly. It's about moving from just observing that simple outputs are common to understanding the mechanism behind why they happen in these specific architectures.
The paper's summary: Mira: The paper sets out to give an exact theory for how the output distribution looks for a deep-layered machine, and it confirms that this output is exponentially biased towards simplicity as you increase the network depth <ref:2603.01217#pg1>.
Kai: They establish that this distribution only depends on the Hamming weight of the output function, which is just how many ones are in its truth table <ref:2603.01217#pg3>.
Lev: So they model this using a transition matrix A where q n equals A n q zero, and they define the elements of that matrix by this formula involving l and i and j <ref:2603.01217#pg3>.
Mira: The core mathematical structure involves a transition matrix with two k plus one eigenvalues; specifically, the first two eigenvalues are one, corresponding to the true and false outputs <ref:2603.01217#pg3>.
Kai: And for large network depths, they show that the probabilities of all other outputs vanish exponentially fast <ref:2603.01217#pg3>.
The paper's improvements: Lev: One major finding is the identification of a critical network depth, n crit, which is related to two k plus one, and beyond that point, this simplicity bias becomes irrelevant because the true and false outputs start dominating <ref:2603.01217#pg3>.
Mira: They also quantify this simplicity bias using information content, defined as I of f equals log base two of twenty k plus one plus log base two of two to the k divided by the Hamming weight <ref:2603.01217#pg4>.
Kai: The visualization they show in figure four for k equals four, six, and eight arguments shows this bias as the logarithm of the probability distribution rotating clockwise from horizontal to a nearly straight line with a slope of negative one <ref:2603.01217#pg4>.
Lev: They also connect this to Kolmogorov complexity, showing that at the critical network depth, the output can be compressed by s bits with probability one over two k plus one, which is constant regardless of s <ref:2603.01217#pg5>.
Conclusion: Mira: So what this means is that we have a very quantifiable way to see this exponential bias towards simplicity getting stronger as the network depth increases in these deep-layered machines <ref:2603.01217#pg4>.
Kai: The main idea they push is that this simplicity bias isn't an isolated incident; it's just one example of a broader phenomenon where repeated application of irreversible local rules generates a global bias towards simplicity <ref:2603.01217#pg4>.
Lev: And they conjecture that this is just one instance, suggesting that the repeated application of irreversible local rules generates this global bias towards simplicity >
Mira: They also suggest studying the opposite extreme, looking at architectures like f of g one g two c d with branching degree two and depth n equal to one, and they found an exponential bias towards simplicity in that structure <ref:2603.01217#pg4>.
Kai: It's a lot to take in because it suggests that the bias towards simplicity isn't just a quirk of these machines but potentially a rule for many learning frameworks <ref:2603.01217#pg1>.
More episodes
- 2610.32678-Probing the limits of materials design via a comprehensive crystal database of 14.6 million structures with 140 properties
- 2610.33595-Native-oxide-driven layer asymmetry, two-step switching and exchange bias in Co/Ir/Co trilayers
- 2503.19572-Spin models from nonlinear cellular automata
- 2606.23350-Irreversibility Enhances Quantum-Enhanced Markov-Chain Monte Carlo
- 2608.02744-Two-Parameter Ansatz for the Violation of Eigenstate Thermalization
- 2210.00806-Low- and high-energy localization landscapes for tight-binding Hamiltonians in two-dimensional lattices
- 2409.09625-Selective switch for band-edge alignments in pentagonal CdSeTe monolayer: Atom-valley locking
- 2606.20168-Norms, overlaps and Yangian descendants for the Haldane-Shastry spin chain
- 2512.19503-Strain-induced splitting of the CCDW-NCCDW phase transition in 1T-TaS 2
- 2307.12638-Strong localization of microwaves beyond two dimensions in aperiodic Vogel spirals