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:
- Train multiple identical network architectures on the same data.
- Use different random initializations for each.
- 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.
- 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.
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