What Can We Learn by Predicting Accuracy?

Olivier Risser-Maroix, Benjamin ChamandWACV 2023

TL;DR

This paper introduces a novel data-driven approach to understanding machine learning by using symbolic regression to discover a mathematical formula that predicts a linear classifier's accuracy based on dataset statistics. This formula is not only highly accurate but also interpretable, offering new insights into the factors that influence model performance.

What Problem Does This Paper Address?

Designing effective loss functions in machine learning has traditionally relied on intuition and theoretical validation. This paper proposes a paradigm shift: using experimentation to discover theoretical insights. Specifically, the authors aim to answer "What can we learn by predicting accuracy?" by identifying the key characteristics of datasets that lead to high classification performance. This is crucial for understanding the intrinsic mechanisms of representation learning and for developing more principled approaches to model design, moving beyond purely empirical performance gains.

Methods

The core of this work lies in a two-pronged approach:

  1. Meta-Dataset Creation: The authors construct a comprehensive meta-dataset (M) by combining embeddings from 12 diverse datasets and 22 different feature extractors. This creates a rich collection of data points, each representing a unique dataset-feature extractor combination.
  2. Symbolic Regression (SR): To find a predictive formula, they employ symbolic regression, a technique that automatically discovers mathematical expressions. Unlike traditional regression that assumes a model structure, SR searches for the optimal functional form.
  3. Feature Engineering: Datasets are represented by a set of 19 "domain-agnostic" statistics (e.g., dimensionality of embeddings, number of classes, covariance matrix traces, kurtosis, etc.). These statistics are chosen to be diverse and uncorrelated.
  4. Fitness Function: A novel fitness function is designed for the genetic programming (GP) algorithm used in SR. This function specifically penalizes solutions that only correlate well with either pretrained or untrained embeddings, encouraging a formula that works for both.
  5. Formula Discovery: The GP algorithm evolves a population of mathematical expressions to find one that best predicts the optimal accuracy achievable by a linear classifier on the generated embeddings.

Datasets

The meta-dataset M is constructed from a combination of:

  • 12 Datasets: MNIST, CIFAR10, DTD, PhotoArt, CIFAR100, 105-PinterestFaces, CUB200, ImageNet-R, Caltech256, FSS1000, ImageNetMini, THINGS. These datasets vary significantly in the number of classes (from 10 to 1854) and image characteristics.
  • 22 Feature Extractors: This includes various pretrained architectures like AlexNet, ResNet, DenseNet, SqueezeNet, MobileNetv2/v3, FaceNet, and CLIP, as well as untrained versions of some of these. This ensures a broad range of embedding dimensions (256 to 2048) and potential biases.

The authors also tested their approach on 7 text datasets and 4 text feature extractors to assess generalization.

Key Insights and Ideas

  • Data-Driven Theory Discovery: The paper champions an experimental approach to uncovering theoretical principles in ML, mirroring methods used in physics. This challenges the traditional intuition-first approach to loss function design.
  • Interpretable Formula for Accuracy Prediction: The discovered formula is not a black box; it's a concise mathematical expression that reveals which dataset statistics are most predictive of linear classification accuracy.
  • SEP-COR Decomposition: The formula can be decomposed into two parts: SEP (related to class separability, akin to Fisher's criterion) and COR (negatively correlated with accuracy, influenced by class count and decorrelation terms). This decomposition offers a more nuanced understanding of what drives accuracy.
  • Importance of Decorrelation: The formula highlights the significance of decorrelation (both feature and prototype decorrelation) for achieving higher accuracy, aligning with recent findings in self-supervised learning.
  • Generalizability (with caveats): While the formula was derived from vision datasets, it shows promising transferability to text data, albeit with a performance drop, suggesting that the underlying principles might be domain-agnostic.

Key Results

  • High Predictive Accuracy: The discovered symbolic regression formula (GPF) achieved a Pearson's correlation of 0.96 and an R² of 0.93 with the actual optimal accuracy.
  • Simplicity and Explainability: The formula uses only 5 key variables and has a complexity of 6 nodes, making it significantly simpler and more interpretable than other methods like Cubist rules or traditional regressors.
  • Outperforms Baselines: The GPF outperformed linear regression, decision trees, and random forests in terms of predictive accuracy and explainability. Even when baselines were restricted to the 5 variables identified by the GPF, the GPF still performed better.
  • Ablation Studies Confirm Importance: Removing individual variables from the formula led to a significant drop in performance, confirming the importance of each component, with Sb_trace being the least impactful when ablated.

Limitations and Future Work

  • Domain Specificity: While the formula shows some transferability, its initial derivation was from vision datasets. The authors question its generalization to other domains like audio, video, or graph-based data and suggest incorporating more meta-datasets from these areas.
  • Linear Transformation: The paper notes that a simple linear transformation (learned on the training set) can further improve the R² score of the GPF, but this comes at the cost of reduced explainability.
  • Future Directions: The authors propose extending this AI-assisted research approach to other areas, such as predicting hyperparameters (regularization, temperature, tree depth) and understanding their impact on model performance. They also suggest exploring the formula's components (SEP and COR) in more detail as potential loss functions.

Summary updated

BibTeX
@inproceedings{rissermaroix2023what,
  author = {Olivier Risser-Maroix and Benjamin Chamand},
  title = {{What Can We Learn by Predicting Accuracy?}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2023},
}
Figure