Characterizing Structural Regularities of Labeled Data in Overparameterized Models

Ziheng Jiang, Chiyuan Zhang, Kunal Talwar, Michael C. Mozer

Deep neural networks are renowned for their dual ability to generalize—finding broad rules that apply to unseen data—and memorize—learning specific, irregular examples by heart. However, the boundary between a "regular" example (like a generic photo of a cat) and an "exception" (like a cat in a bizarre costume or a mislabeled dog) is often fuzzy.

Standard evaluation metrics typically look at average model performance across an entire dataset. While useful, these averages obscure the "structural regularity" of individual data points. This paper asks a fundamental question: Can we quantify how much a specific data point belongs to the "mainstream" of its class versus being a weird outlier? Answering this can help researchers clean datasets, design better training curriculums, and diagnose underlying model behaviors.

The Consistency Score (C-score)

To quantify this regularity, the authors introduce the Consistency Profile. This profile measures the probability that a model will correctly classify a specific held-out point $(x, y)$ when trained on a random subset of the remaining data of size $n$.

By varying the training set size $n$ and averaging over many random subsets, the authors generate a curve for each data point. The Consistency Score (C-score) is the integral (or average) of this profile:

  • High C-score: The point is "easy" to generalize to, even when the model is trained on very little data. These are prototypical examples.
  • Low C-score: The point is only learned when the model has seen almost the entire dataset, or it is never learned at all. These are outliers or mislabeled points.
Conceptual overview showing the data manifold, consistency profiles for regular vs. irregular examples, and ImageNet images ranked by their C-score.

Because training thousands of models to calculate exact C-scores is computationally expensive, the authors utilized efficient approximations. They trained models on subset ratios (e.g., 10% to 90% of the data) and used a "leave-one-out" style reuse of models to evaluate multiple held-out points simultaneously. They also discovered that learning speed—how early in training a model correctly classifies a point—serves as an excellent, cheap proxy for the C-score.

Key Insights: The Regularity Continuum

By evaluating the C-score across standard computer vision benchmarks (MNIST, CIFAR-10/100, ImageNet, and SVHN), the authors uncovered several crucial insights about how models learn:

  • A Smooth Continuum: Data doesn't simply fall into binary "easy" or "hard" buckets. There is a smooth continuum from "dense modes" (highly prototypical examples) to "sparse modes" (rare but valid examples) to "outliers" (mislabeled or nonsensical data).
  • Generalization vs. Memorization: High C-score examples are supported by many "neighbors" in the data manifold, allowing the model to infer them through statistical regularity (generalization). Low C-score examples lack this support and must be learned by rote (memorization).
  • SGD as a Natural Curriculum: The study revealed that Stochastic Gradient Descent (SGD) naturally focuses on high C-score (regular) examples early in training before moving on to low C-score examples. In contrast, adaptive optimizers like Adam tend to learn all examples at a more uniform pace. This implicit "curriculum" effect in SGD may explain why it often achieves better final generalization than Adam.

Detecting Mislabeled and Atypical Data

The C-score proves to be remarkably effective at flagging bad data. The authors found that the bottom 1% of C-scores in common datasets almost exclusively contains mislabeled images, highly ambiguous cases, or completely atypical forms.

Examples from MNIST and CIFAR datasets with the lowest C-scores, revealing mislabeled (red), ambiguous (blue), and atypical (purple) data points.

In a controlled experiment on CIFAR-10 with 25% random label noise, C-score proxies successfully identified over 95% of the outliers. Furthermore, on the SVHN dataset, removing the lowest C-score examples initially improved model performance, confirming these points were mostly detrimental noise. However, removing too many eventually hurt performance, as the model lost the ability to learn rare but legitimate "sparse modes."

Limitations and Future Directions

While the C-score provides a powerful new lens for understanding data, it comes with practical constraints:

  • Computational Cost: Even with optimizations, calculating the "ground truth" C-score requires training hundreds of models, which is prohibitive for massive datasets. Fortunately, proxies like cumulative softmax confidence during training correlate highly (Spearman $\approx 0.9$) with the true C-score.
  • Architecture Dependence: The C-score is technically a property of the model-dataset pair, not just the data itself. While scores remain relatively consistent across various CNNs (Inception, ResNet, VGG), future work is needed to explore how these scores shift with vision transformers or self-supervised learning paradigms.
  • Beyond Classification: The current formulation is specific to supervised classification. Extending this framework to generative modeling or reinforcement learning remains an exciting open challenge.

Summary updated

Abstract

Humans are accustomed to environments that contain both regularities and exceptions. For example, at most gas stations, one pays prior to pumping, but the occasional rural station does not accept payment in advance. Likewise, deep neural networks can generalize across instances that share common patterns or structures yet have the capacity to memorize rare or irregular forms. We analyze how individual instances are treated by a model via a consistency score. The score characterizes the expected accuracy for a held-out instance given training sets of varying size sampled from the data distribution. We obtain empirical estimates of this score for individual instances in multiple data-sets, and we show that the score identifies out-of-distribution and mislabeled examples at one end of the continuum and strongly regular examples at the other end. We identify computationally inexpensive proxies to the consistency score using statistics collected during training. We apply the score toward understanding the dynamics of representation learning and to filter outliers during training, and we discuss other potential applications including curriculum learning and active data collection.
BibTeX
@inproceedings{jiang2021characterizing,
  author = {Ziheng Jiang and Chiyuan Zhang and Kunal Talwar and Michael C. Mozer},
  title = {{Characterizing Structural Regularities of Labeled Data in Overparameterized Models}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=LYtzVihRte},
}
Figure