Abstract
Machine learning models generalize to unseen data thanks to "inductive biases"—inherent architectural assumptions like translation invariance in CNNs. However, quantifying exactly how much bias a model contains has historically been difficult. This paper introduces a novel, efficient method to directly compute the exact amount of inductive bias (measured in bits) required to solve a task. By modeling the test-error distribution of sampled hypotheses, the authors reveal that neural networks inherently encode massive amounts of inductive bias compared to generic kernel methods, and that higher-dimensional tasks demand exponentially more bias.
Quantifying the "No Free Lunch"
The "No Free Lunch" theorem tells us that no single learning algorithm can perform well on all possible tasks; models require prior assumptions (inductive biases) tailored to specific problems to learn efficiently from limited data. While we intuitively know that Convolutional Neural Networks (CNNs) have a good inductive bias for images, quantifying this bias in an information-theoretic sense has remained elusive.
Previous attempts to measure inductive bias either provided extremely loose upper bounds or were restricted to very narrow model families. This research frames inductive bias as a measurable quantity: the amount of information (in bits) required to specify a well-generalizing model out of a broader "hypothesis space" of models that all perfectly fit the training data.
Methodology: Sampling and Distribution Modeling
The authors propose a two-phase sampling-based algorithm to compute the inductive bias of a task within a specific hypothesis space:
- Efficiently Sampling the Hypothesis Space: The authors sample models (hypotheses) that successfully fit the training data. This is achieved via direct optimization (training NNs multiple times) or kernel-based sampling (using Gaussian Processes to sample functions from an RBF kernel).
- Modeling the Test Error Distribution: Because finding a perfectly generalizing model by random sampling is computationally infeasible, the authors evaluate sampled models on a test set and fit their mean squared errors to a scaled non-central Chi-squared distribution.
- Computing the Bias: Using this distribution, they calculate the negative log probability of a hypothesis achieving a target test error rate. This value represents the inductive bias in bits.
Key Insights
- The Curse of Dimensionality: Tasks with higher intrinsic dimensionality require exponentially more bits of inductive bias to solve.
- Neural Networks are Heavily Biased: Compared to a highly expressive Gaussian RBF kernel space, simply choosing to use a Neural Network provides a massive amount of inductive bias. The inherent structure of NNs (smoothness, compositionality) naturally aligns with realistic tasks.
- Architecture vs. Class: When comparing different NN architectures (Linear, Fully Connected, AlexNet) on the same task, the amount of inductive bias they provide is surprisingly similar. The bulk of the bias comes from using the neural network class itself.
Results and Impact
The proposed exact computation yields estimates that are orders of magnitude tighter than prior upper bounds. For example, previous bounds suggested MNIST required $1.48 \times 10^{16}$ bits of bias; this paper calculates it exactly at ~2568 bits for Kernel space and just 37.6 bits for NN space. On CIFAR-10, a Kernel requires 2670 bits of inductive bias to generalize, while an NN requires only 327.3 bits, proving mathematically how much "guidance" the NN architecture provides the optimization process.
This framework allows researchers to intentionally design harder benchmarks that demand higher inductive bias, pushing the boundaries of current machine learning architectures.
Summary updated