A Model of One-Shot Generalization

Thomas Laurent, James H. von Brecht, Xavier Bresson

Abstract

We propose a simple data model inspired from natural data such as text or images, and use it to study the importance of learning features in order to achieve good generalization. Our data model follows a long-tailed distribution in the sense that some rare subcategories have few representatives in the training set. In this context we provide evidence that a learner succeeds if and only if it identifies the correct features, and moreover derive non-asymptotic generalization error bounds that precisely quantify the penalty that one must pay for not learning features.

Introduction

In real-world datasets, distributions are rarely balanced. While a few "head" categories appear frequently, a vast number of "tail" subcategories appear only a handful of times. Traditional machine learning theory often relies on asymptotic guarantees—the idea that models converge given infinite data. However, for the long tail, data is perpetually scarce. This research addresses a fundamental question: Why do neural networks generalize so well to rare instances while other methods, such as SVMs or Nearest Neighbors with fixed kernels, fail? The authors argue that the key lies in "feature learning"—the ability to discover latent structures from common examples and apply that knowledge to the rare ones.

A Synthetic Model for Natural Data

To study this phenomenon, the authors introduce a novel data model mimicking the hierarchical nature of text or images.

  • Latent Structure: A vocabulary of "words" is partitioned into "concepts" (e.g., "dairy" includes "cheese" and "butter").
  • Sentences and Categories: A "sentence" is a sequence of these concepts. Some sequences are "familiar" (frequent), while others are "unfamiliar" (rare).
  • The Generalization Challenge: To classify an unfamiliar test sentence correctly, an algorithm must recognize that different words belong to the same concept. For instance, if the model has seen "cheese" in a specific context but encounters "butter" in a rare test case, it must understand their functional equivalence as "dairy."
The data generation process: latent concepts are sequenced to form categories, which then generate specific word-based sentences.

Theoretical Framework: The Necessity of Feature Learning

The core insight of the paper is that success on the "tail" is impossible without identifying features from the "head." The authors derive non-asymptotic generalization error bounds that precisely quantify the penalty for failing to learn features. They introduce a mathematical tool called the "permuted moment" to analyze distribution "peakedness," linking it directly to classification success.

The theory suggests that features must be task-dependent. You cannot pre-craft a "universal" feature map (a task-agnostic kernel) that works for all tasks. Neural networks succeed because they adapt their internal representations to the specific task during training, whereas fixed-feature methods are theoretically destined to fail on rare subcategories.

Architectural Comparison and Results

The study compares a simple neural network architecture against several task-agnostic methods, including Nearest Neighbor classifiers on fixed feature maps, an "Optimal Kernel" ($K^*$) representing the best possible hand-crafted similarity measure, and SVMs with standard RBF kernels.

The feature-learning architecture: individual words are processed by a shared MLP and normalized before being concatenated for final classification.

The empirical results reveal a massive performance gap:

  • Neural Networks: Achieved >99.8% accuracy on unfamiliar test sentences by sharing representations learned from common data.
  • Fixed Feature Maps: Even the "Optimal Kernel" ($K^*$) failed catastrophically, achieving less than 2.5% accuracy.
  • Theoretical Bound: The authors proved that for their specific settings, any task-agnostic feature map must have an error rate of at least 98.4%.

Interestingly, the specific classifier used on top of the features (Linear vs. Nearest Neighbor) was largely irrelevant. The bottleneck was entirely in whether the features themselves were learned or fixed.

Conclusion

This work provides a mathematical foundation for the dominance of neural networks in real-world, long-tailed scenarios. By learning the meta-structure of the data—such as the fact that data is composed of interchangeable "words" or "patches"—neural networks can generalize from a single example in a way that fixed-kernel methods cannot. Future work may extend these non-asymptotic bounds to more complex architectures like Transformers and continuous, high-dimensional data like raw pixels.

Summary updated

Abstract

We propose a simple data model inspired from natural data such as text or images, and use it to study the importance of learning features in order to achieve good generalization. Our data model follows a long-tailed distribution in the sense that some rare subcategories have few representatives in the training set. In this context we provide evidence that a learner succeeds if and only if it identifies the correct features, and moreover derive non-asymptotic generalization error bounds that precisely quantify the penalty that one must pay for not learning features.
BibTeX
@inproceedings{laurent2023model,
  author = {Thomas Laurent and James H. von Brecht and Xavier Bresson},
  title = {{A Model of One-Shot Generalization}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=S-h1oFv-mq},
}

Loading related content...

Figure