Towards Exact Computation of Inductive Bias

Akhilan Boopathy, William Yue, Jaedong Hwang, Abhiram Iyer, Ila R FieteSubmission to ICLR 2024 · Rejected

Abstract

Researchers from MIT have developed a novel method to precisely quantify inductive bias—the "prior knowledge" an AI model uses to generalize—in terms of information-theoretic bits. By modeling the test-loss distribution of random models, they can calculate exactly how much guidance a specific architecture provides for a task. Their findings reveal that neural networks offer orders of magnitude more bias than previously estimated, providing a rigorous metric for comparing architectures and understanding generalization.

Introduction: The Challenge of Measuring Bias

In machine learning, we know that certain architectures "fit" certain problems better than others. For example, Convolutional Neural Networks (CNNs) are the standard for images because they assume spatial patterns are important. This set of assumptions is known as inductive bias.

While we intuitively understand that inductive bias is the secret sauce behind generalization, measuring it accurately has been difficult. Previous attempts were either limited to specific model classes or only provided loose "upper bounds" (overestimates). Without a precise metric, it is hard to compare architectures objectively or design new benchmarks that intentionally challenge a model's existing biases. This research introduces a way to compute a direct estimate of the "amount" of bias required for a task.

Methodology: Quantifying Information in Hypothesis Spaces

The authors define inductive bias as the amount of information (in bits) required to identify a well-generalizing model within a broad "hypothesis space." Their approach follows a three-step pipeline:

  1. Define the Context: They distinguish between a model class (e.g., a specific CNN) and a broader hypothesis space (e.g., all possible functions). Inductive bias is measured relative to this broader space.
  2. Efficient Sampling: To see how a "random" model performs, they sample hypotheses that fit the training data. For high-dimensional spaces where training thousands of models is too slow, they use a kernel-based sampling method that treats the hypothesis space like a Gaussian Process.
  3. Distribution Modeling: Since most random models generalize poorly, the authors fit the empirical test-loss distribution to a scaled non-central Chi-squared distribution. This allows them to calculate the probability of a model achieving a target error rate, even if that rate is in the extreme "tail" of the distribution.
Conceptual diagram of hypothesis spaces and model classes. Inductive bias represents the information needed to narrow down from the total function space to the region of well-generalizing hypotheses.

Key Insights: The Information Theory of Generalization

The core of this research is the translation of generalization into information theory. Inductive bias ($I$) can be visualized as the negative log-probability of picking a "good" model by chance. If only 1 in 8 models generalizes well, the bias is 3 bits ($-\log_2(1/8)$).

Illustration of how inductive bias (I) scales with the restriction of the hypothesis space. A more constrained space requires fewer bits to identify a successful model.

Several critical findings emerged from this quantification:

  • Neural Networks are Highly "Opinionated": The results show that neural networks as a class encode massive amounts of inductive bias compared to other expressive models like RBF kernels. This explains why they can generalize so well even when the number of parameters far exceeds the number of data points.
  • The Curse of Dimensionality: The paper confirms that as the intrinsic dimensionality of a task increases, the amount of inductive bias needed to solve it grows exponentially.
  • Architecture Matters: The metric can quantify the difference between specific designs. For instance, they can measure exactly how many more bits of bias a DenseNet provides over a simple MLP for a specific dataset.

Experimental Results

The method was evaluated across several diverse domains, including MNIST (handwritten digits), CIFAR-10 (object recognition), Omniglot (few-shot character recognition), and the Inverted Pendulum (reinforcement learning). The authors' estimates are significantly more precise (and much lower) than previous theoretical bounds.

Task Prior Upper Bound (bits) New Result (Kernel Space) New Result (NN Space)
MNIST $1.48 \times 10^{16}$ 2568 37.6
CIFAR-10 $3.43 \times 10^{32}$ 2670 327.3
Omniglot $1.79 \times 10^{145}$ 2857 1925.6

The massive gap between the "Kernel" and "NN" columns highlights that the neural network architecture itself is doing a lot of the heavy lifting—it "knows" more about the task structure before it even sees the data.

Conclusion and Future Work

While this framework provides a powerful new tool for understanding AI, some limitations remain. The current statistical modeling (the Chi-squared fit) is optimized for Mean Squared Error (MSE). While classification tasks were adapted to MSE for this paper, future work is needed to extend this directly to Cross-Entropy loss. Additionally, while more efficient than previous methods, sampling enough hypotheses to fit a distribution still requires significant GPU resources. Finally, because "bits" are always relative to the chosen hypothesis space, standardizing these spaces will be crucial for comparing results across the field.

Summary updated

Abstract

Much research in machine learning involves finding appropriate inductive biases (e.g. convolutional neural networks, momentum-based optimizers, transformers) to promote generalization on tasks. However, quantification of the amount of inductive bias associated with these architectures and hyperparameters has been limited. We propose a novel method for efficiently computing the inductive bias required for generalization on a task with a fixed training data budget; formally, this corresponds to the amount of information required to specify well-generalizing models within a specific hypothesis space of models. Our approach involves sampling from the hypothesis space and modeling the loss distribution of hypotheses to estimate the required inductive bias for a task. Unlike prior work, our method provides a direct estimate of inductive bias without using bounds and is applicable to diverse hypothesis spaces. Moreover, we derive approximation error bounds for our estimation approach in terms of the number of sampled hypotheses. Consistent with prior results, our empirical results demonstrate that higher dimensional tasks require greater inductive bias. We show that relative to other expressive model classes, neural networks as a model class encode massive amounts of inductive bias. Furthermore, our measure quantifies the relative difference in inductive bias between different neural network architectures (e.g. with varying width and depth). Our proposed inductive bias metric provides an information-theoretic interpretation of the benefits of specific model architectures for certain tasks and provides a quantitative guide to developing tasks requiring greater inductive bias, thereby encouraging the development of more powerful inductive biases.
BibTeX
@misc{boopathy2024towards,
  author = {Akhilan Boopathy and William Yue and Jaedong Hwang and Abhiram Iyer and Ila R Fiete},
  title = {{Towards Exact Computation of Inductive Bias}},
  year = {2024},
  eprint = {2406.15941},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.15941},
}
Figure