Chaitin-Kolmogorov Complexity and Generalization in Neural Networks

Barak A. Pearlmutter, Ronald Rosenfeld

This paper, published in the early 1990s, provides a fascinating information-theoretic perspective on why ensembling—what the authors call "replicated networks"—actually works. It argues that the random choices we make during training (such as initial weights) add "accidental" complexity to a model. By averaging multiple models, we can "wash out" this noise, leading to simpler functions that generalize more effectively.

What Problem Does This Paper Address?

A central mystery in machine learning is why some models generalize well while others "overfit" or fail to capture the underlying logic of the data. The authors tackle this through the lens of Chaitin-Kolmogorov Complexity—the idea that the complexity of a function is equivalent to the length of the shortest program required to compute it.

In theory, a perfect learner should produce a model no more complex than the training data plus the learning algorithm itself. However, in practice, neural networks are stochastic. Because they start with random weights or encounter noise during training, they "break symmetries" in arbitrary ways. This adds "random information" to the model that isn't present in the data, effectively making the model more complex than it needs to be. This excess complexity is a primary driver of poor generalization.

Methods: Replicated Networks

The authors propose a unified framework using a Complexity Bound. They mathematically demonstrate that the expected complexity of a trained network is bounded by the complexity of the data, the complexity of the program, and the "information" introduced by the specific training run (the bias distribution).

To combat the information contamination of a single run, they analyze Replicated Networks:

  1. Train multiple identical network architectures on the same data.
  2. Use different random initializations for each.
  3. Average their outputs to form an ensemble.

Theoretically, as the number of networks in the ensemble approaches infinity, the random "symmetry-breaking" decisions average out. The resulting "ensemble machine" can be described solely by the training data and the program, effectively removing the unbounded complexity introduced by random internal parameters.

Datasets

The authors used a synthetic stochastic 2D linear discriminator task to test their theory:

  • Data Generation: Points were drawn from a Gaussian distribution centered at (0,0).
  • Labels: Points with $x \geq 0$ were labeled 1, and $x < 0$ were labeled 0, but with a 10% probability of the label being reversed (adding noise).
  • Training Set: 200 points.
  • Test Set: 1,000 points.
  • Architecture: 17 standard backpropagation networks (2-20-1 architecture) were used for the experiment.

Key Insights and Ideas

  • Symmetry Breaking as a Liability: When a network faces a problem it cannot perfectly solve (like XOR without hidden units), it hits a "saddle point." To move past it, the network must break symmetry—choosing to favor one data point over another. This choice is often random, adding noise to the final function.
Illustration of symmetry breaking in a simple network.
  • The Complexity Paradox: A single network has a finite VC dimension (a measure of representational power). An ensemble of these networks technically has a much higher (even infinite) VC dimension. Traditional theory might suggest the ensemble should overfit more, but the authors show that because the ensemble is "simpler" in terms of Kolmogorov complexity, it actually generalizes better.
  • Tightening the Bound: The authors argue that common techniques like weight decay and cross-validation are essentially just different ways of "tightening" the complexity bound by preventing the network from making arbitrary, high-complexity decisions.

Key Results

The empirical results strongly supported the theoretical framework:

  • Individual Performance: The 17 individual networks had a mean Squared Error (MSE) of 0.214 on the test set.
  • Ensemble Performance: The averaged ensemble achieved an MSE of 0.160, significantly outperforming the average of its parts.
  • Generalization: The ensemble's test set error (200 misclassifications) was better than any single network in the group (the best individual network had 205).
  • Visual Evidence: By plotting the functions implemented by each network, the authors showed that individual networks created jagged, highly complex decision boundaries. The ensemble's boundary was much smoother and closer to the "theoretically perfect" linear discriminator.
Decision boundaries of 17 individual networks and their smoother ensemble (bottom right).

Limitations and Future Work

  • Computational Cost: The authors acknowledge that training an ensemble requires "buying a bigger computer," which was a more significant constraint in 1991 than it is today.
  • Infinite Ensembles: While the paper discusses the theory of an "infinite ensemble," the experiments were limited to 17 networks.
  • Task Simplicity: The empirical support relies on a 2D synthetic dataset. The authors do not explore how this complexity bound behaves in high-dimensional, real-world datasets like images or text (though modern deep learning has since validated the power of ensembling in those domains).
  • Watershed Structure: The paper mentions the "entropy of the watershed structure" as a potential bound for complexity but notes it is difficult to calculate and potentially unbounded.

Summary updated

Abstract

We present a unified framework for a number of different ways of failing to generalize properly. During learning, sources of random information contaminate the network, effectively augmenting the training data with random information. The complexity of the function computed is therefore increased, and generalization is degraded. We analyze replicated networks, in which a number of identical networks are independently trained on the same data and their results averaged. We conclude that replication almost always results in a decrease in the expected complexity of the network, and that replication therefore increases expected generalization. Simulations confirming the effect are also presented. 1 BROKEN SYMMETRY CONSIDERED HARMFUL Consider a one-unit backpropagation network trained on exclusive or. Without hidden units, the problem is insoluble. One point where learning would stop is when all weights are zero and the output is always ~, resulting in an mean squared error of ~. But this is a saddle point; by placing the discrimination boundary properly, one point can be gotten correctly, two with errors of ~, and one with error of i, giving an MSE of i, as shown in figure 1. Networks are initialized with small random weights, or noise is injected during train(cid:173) ing to break symmetries of this sort. But in breaking this symmetry, something has been lost. Consider a kNN classifier, constructed from a kNN program and the training data. Anyone who has a copy of the kNN program can construct an iden(cid:173) tical classifier if they receive the training data. Thus, considering the classification
BibTeX
@inproceedings{pearlmutter1990chaitin,
  author = {Barak A. Pearlmutter and Ronald Rosenfeld},
  title = {{Chaitin-Kolmogorov Complexity and Generalization in Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1990},
}
Figure