GRASP: A Goodness-of-Fit Test for Classification Learning

Adel Javanmard, Mohammad MehrabiJournal of the Royal Statistical Society Series B (Statistical Methodology) 2022 · arXiv

GRASP: A New Way to Judge How Well Classifiers Learn

TL;DR

This paper introduces GRASP, a novel goodness-of-fit test for binary classifiers that goes beyond simple accuracy to assess how well a model captures the true underlying relationship between features and labels. GRASP is distribution-free and works even for complex, black-box models, offering a more robust evaluation of classifier performance.

What Problem Does This Paper Address?

In machine learning, we often evaluate classifiers by their accuracy on test data. However, this metric can be misleading. A classifier might achieve high accuracy by "memorizing" the training data (overfitting), or it might fail to capture the true underlying data-generating process due to model misspecification or high-dimensional data. The authors argue that a more fundamental question is: "How well does a classifier learn the ground truth data generating law between the feature vector and the label?" Existing goodness-of-fit tests often rely on specific parametric assumptions about the data or the model, limiting their applicability to more complex, modern machine learning models like neural networks or random forests. This paper aims to fill this gap by providing a general, flexible, and powerful goodness-of-fit test.

Methods

The core of GRASP is a hypothesis testing framework. It formulates the goodness-of-fit problem as testing whether the expected f-divergence between the true conditional label distribution and the classifier's predicted distribution is below a certain tolerance threshold ($\tau$). This framework is "distribution-free," meaning it doesn't assume any specific distribution for the data or the model.

The key innovation lies in the "Counterfeit sampling" and "Scoring Procedure" used to construct the test statistic. For each data point, GRASP generates "counterfeit" samples and uses a score function to rank the true data point against these counterfeits. This ranking is then used to assign a label to the original data point, forming a multinomial distribution of labels. The test statistic is derived from the counts of these assigned labels.

Two variants are proposed:

  • Distribution-free GRASP: This version works without any knowledge of the feature distribution.
  • Model-X GRASP: This variant leverages the knowledge of the feature distribution (e.g., from abundant unlabeled data) to improve statistical power.

Datasets

The paper uses synthetic datasets for its numerical experiments. These datasets are generated based on logistic regression models and neural networks, with varying dimensions and parameters to simulate different scenarios. No new benchmarks are introduced; instead, existing synthetic data generation techniques are employed.

Key Insights and Ideas

  • Beyond Accuracy: The paper strongly emphasizes that accuracy alone is insufficient for evaluating classifier performance, especially in complex scenarios. GRASP provides a more nuanced assessment by looking at how well the classifier's predictions align with the true underlying data-generating process.
  • Black-Box Compatibility: GRASP's ability to treat classifiers as black boxes (only requiring query access) makes it applicable to a wide range of modern machine learning models, including deep neural networks, for which traditional parametric tests are unsuitable.
  • Model-X Advantage: Leveraging the distribution of features (even without labels) can significantly boost the power of the goodness-of-fit test, as demonstrated by the Model-X GRASP variant. This highlights the value of unsupervised data in model evaluation.
  • Tolerance Testing: The framework allows for a tolerance parameter ($\tau$), making it more practical. Instead of demanding a perfect fit (which is often unrealistic), it tests if the model's deviation is within an acceptable range.

Key Results

The paper demonstrates that GRASP controls the Type I error (false positive rate) in both finite sample and asymptotic settings. Extensive numerical experiments show that GRASP achieves high statistical power in detecting deviations from the true conditional law, outperforming simpler methods in various scenarios. The Model-X GRASP variant consistently shows higher power than the distribution-free version when feature distributions are known. The experiments also explore the impact of different f-divergence functions and score functions on the test's performance.

Limitations and Future Work

  • Computational Complexity: While GRASP is designed to be flexible, solving the optimization problems within the test can be computationally intensive, especially for a large number of labels ($L$). The paper discusses using conditional gradient methods to address this.
  • Choice of Score Function: The performance of GRASP can depend on the choice of the score function $T$. While simple choices like $T(x, w) = w$ are competitive, finding an optimal score function that accounts for the dependence between features and labels can be challenging. The paper explores model-agnostic and GAN-based approaches for score function selection.
  • Future Work: The authors suggest exploring more sophisticated GAN-based approaches for learning optimal score functions and extending the framework to multi-class classification problems. Further investigation into the theoretical properties of different score functions and their impact on power is also a promising direction.

Summary updated

Abstract

Abstract Performance of classifiers is often measured in terms of average accuracy on test data. Despite being a standard measure, average accuracy fails in characterising the fit of the model to the underlying conditional law of labels given the features vector (Y∣X), e.g. due to model misspecification, over fitting, and high-dimensionality. In this paper, we consider the fundamental problem of assessing the goodness-of-fit for a general binary classifier. Our framework does not make any parametric assumption on the conditional law Y∣X and treats that as a black-box oracle model which can be accessed only through queries. We formulate the goodness-of-fit assessment problem as a tolerance hypothesis testing of the form H0:E[Df(Bern(η(X))‖Bern(η^(X)))]≤τ where Df represents an f-divergence function, and η(x), η^(x), respectively, denote the true and an estimate likelihood for a feature vector x admitting a positive label. We propose a novel test, called Goodness-of-fit with Randomisation and Scoring Procedure (GRASP) for testing H0, which works in finite sample settings, no matter the features (distribution-free). We also propose model-X GRASP designed for model-X settings where the joint distribution of the features vector is known. Model-X GRASP uses this distributional information to achieve better power. We evaluate the performance of our tests through extensive numerical experiments.
BibTeX
@misc{javanmard2022grasp,
  author = {Adel Javanmard and Mohammad Mehrabi},
  title = {{GRASP: A Goodness-of-Fit Test for Classification Learning}},
  year = {2022},
  eprint = {2209.02064},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.02064},
}
Figure