Needle in a Haystack: Label-Efficient Evaluation under Extreme Class Imbalance
This addresses the challenge of label-efficient evaluation for tasks like record linkage and extreme classification, which is incremental as it builds on importance sampling with improved guarantees and adaptability.
The paper tackles the problem of evaluating machine learning models under extreme class imbalance, where obtaining sufficient minority class samples is costly, by developing an online evaluation framework based on adaptive importance sampling. The result is a method that provides strong statistical guarantees and demonstrates superior mean squared error compared to state-of-the-art approaches on fixed label budgets.
Important tasks like record linkage and extreme classification demonstrate extreme class imbalance, with 1 minority instance to every 1 million or more majority instances. Obtaining a sufficient sample of all classes, even just to achieve statistically-significant evaluation, is so challenging that most current approaches yield poor estimates or incur impractical cost. Where importance sampling has been levied against this challenge, restrictive constraints are placed on performance metrics, estimates do not come with appropriate guarantees, or evaluations cannot adapt to incoming labels. This paper develops a framework for online evaluation based on adaptive importance sampling. Given a target performance metric and model for $p(y|x)$, the framework adapts a distribution over items to label in order to maximize statistical precision. We establish strong consistency and a central limit theorem for the resulting performance estimates, and instantiate our framework with worked examples that leverage Dirichlet-tree models. Experiments demonstrate an average MSE superior to state-of-the-art on fixed label budgets.