Precision-Recall versus Accuracy and the Role of Large Data Sets

Brendan Juba, Hai S. Le

Introduction

In machine learning, a persistent disconnect exists between statistical learning theory and the practical realities of imbalanced datasets. Standard theory, often rooted in VC-dimension, suggests that the sample complexity required to achieve a certain level of accuracy depends primarily on model complexity, largely ignoring class distribution. However, practitioners working with rare target classes—the "needle in a haystack" problems—frequently observe that imbalance makes learning significantly more difficult.

To address this, practitioners often shift their evaluation from accuracy to Precision and Recall (PR). This paper investigates whether the sample complexity for achieving high PR is inherently tied to class imbalance, ultimately proving that high-quality PR requires a massive "data tax" proportional to the rarity of the target class.

The Theoretical "Data Tax"

The core contribution of this research is the formalization of Precision-Recall as "Imbalance-Weighted Accuracy." The authors derive a relationship showing that achieving a specific precision and recall is mathematically equivalent to achieving a much higher level of accuracy, scaled by the imbalance factor.

Using VC-dimension theory, the authors establish new bounds for sample complexity. They demonstrate a $1/\mu$ penalty, where $\mu$ represents the "base rate" (the fraction of positive examples). Formally, the number of examples needed scales as $O(\frac{1}{\mu \epsilon} (d + \log \frac{1}{\delta}))$. This means if a target class is 100 times rarer, a model requires roughly 100 times more data to maintain the same PR performance.

Experimental Methodology

The study validates these theoretical findings through empirical tests across several standard classifiers, including K-Nearest Neighbors (K-NN), Support Vector Machines (SVM), Logistic Regression, and Random Forests. These models were tested against various "imbalance-correction" algorithms such as SMOTE (Synthetic Minority Over-sampling Technique), undersampling, and Easy Ensemble.

Summary of datasets used, highlighting varying sizes and class imbalance ratios.

The experiments utilized four primary datasets: standard benchmarks from the UCI Repository (Abalone, Letter, and Satimage) and a large-scale Drug Discovery dataset containing over one million examples, representing a real-world imbalanced task.

Results: Data vs. Algorithms

The results consistently show that simply increasing the training set size is more effective than applying algorithmic corrections to smaller datasets. For most classifiers, correction methods like SMOTE or undersampling often improved recall but at a significant cost to precision, or vice versa. In contrast, increasing the raw data volume tended to improve both metrics simultaneously.

Performance on the Drug Discovery dataset: increasing data size (950K) significantly outperforms algorithmic corrections on smaller samples (50K).

As seen in the Drug Discovery results, the "No correction" baseline at a larger scale (950K examples) achieved a precision of 0.9474 and recall of 0.6429, vastly outperforming the precision-recall trade-offs offered by any correction technique applied to the 50K sample.

Discussion and Implications

The "Placebo Effect" of Correction

The paper suggests that popular techniques like SMOTE do not actually lower the statistical barrier imposed by rarity. While they can shift the trade-off between precision and recall, they are not a substitute for raw data. Interestingly, decision-tree-based methods like Random Forests were the only models that consistently benefited from these corrections, likely due to their unique method of partitioning feature space.

Real-World Applications: Machine Translation

The authors use their theory to explain why industrial machine translation models require hundreds of billions of examples. To use a rare word with high precision, a model must encounter enough instances of that specific rarity to distinguish signal from noise. Without sufficient data, the "data tax" of rarity makes high-precision usage impossible.

Conclusion

This research proves that for highly imbalanced tasks, there is no algorithmic shortcut to high Precision and Recall. The only robust solution is a significantly larger dataset. While accuracy remains "cheap" regardless of imbalance, high-quality PR is "expensive," requiring a data investment that scales inversely with the rarity of the target class.

Summary updated

Abstract

Practitioners of data mining and machine learning have long observed that the imbalance of classes in a data set negatively impacts the quality of classifiers trained on that data. Numerous techniques for coping with such imbalances have been proposed, but nearly all lack any theoretical grounding. By contrast, the standard theoretical analysis of machine learning admits no dependence on the imbalance of classes at all. The basic theorems of statistical learning establish the number of examples needed to estimate the accuracy of a classifier as a function of its complexity (VC-dimension) and the confidence desired; the class imbalance does not enter these formulas anywhere. In this work, we consider the measures of classifier performance in terms of precision and recall, a measure that is widely suggested as more appropriate to the classification of imbalanced data. We observe that whenever the precision is moderately large, the worse of the precision and recall is within a small constant factor of the accuracy weighted by the class imbalance. A corollary of this observation is that a larger number of examples is necessary and sufficient to address class imbalance, a finding we also illustrate empirically.
BibTeX
@inproceedings{juba2019precision,
  author = {Brendan Juba and Hai S. Le},
  title = {{Precision-Recall versus Accuracy and the Role of Large Data Sets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33014039},
}
Figure