Prediction and outlier detection in classification problems

Leying GuanOpenReview 2024 · OpenReview

TL;DR

This paper introduces BCOPS, a novel method for classification that constructs prediction sets, not just single labels, to handle situations where test data distributions differ from training data. BCOPS aims to provide reliable predictions for "inliers" while abstaining from making predictions for "outliers," a crucial capability for robust real-world applications.

What Problem Does This Paper Address?

Traditional classification models assume that training and test data come from the same distribution. However, in many real-world scenarios, this assumption is violated (e.g., evolving user behavior, sensor drift). When faced with data from a different distribution, standard classifiers can produce unreliable predictions, especially for "outliers" that are far from the training data. This paper tackles the challenge of building classification systems that can not only predict the correct class for familiar data but also identify and abstain from predicting for unfamiliar or outlier data, all while maintaining guaranteed coverage for the predicted classes.

Methods

The core of the proposed method is BCOPS (Balanced and Conformal Optimized Prediction Sets). BCOPS constructs a prediction set $C(x)$ for each input $x$, which can be a single class label, multiple labels, or even an empty set. The empty set signifies an outlier.

Key methodological components include:

  • Conformal Prediction: This framework provides a principled way to construct prediction sets with finite-sample coverage guarantees without making strong distributional assumptions. It essentially uses a "score" to determine if a new data point is consistent with the training data.
  • Optimized Objective Function: BCOPS aims to minimize a misclassification loss averaged over the out-of-sample distribution, which is crucial for handling distribution shifts. This is achieved by optimizing a specific objective function that balances coverage requirements with the desire to minimize prediction set size.
  • Mixture Model with Outlier Class: The authors model the out-of-sample data distribution as a mixture of known classes and a new, unobserved "outlier" class. This explicitly accounts for distributional changes and the presence of outliers.
  • Density Ratio Estimation: A key component for distinguishing inliers from outliers is estimating the ratio of class densities to the overall test density. BCOPS uses supervised learning (e.g., random forest, logistic regression) within a conformal prediction framework to estimate this ratio robustly.
  • Outlier Abstention Rate Estimation: The paper also proposes a method to estimate the "outlier abstention rate" (how often the model correctly abstains on outliers) and the "false labeling rate" (how often outliers are incorrectly labeled).

Datasets

The paper uses the following datasets:

  • Simulated Data: A synthetic dataset is generated to illustrate the differences between BCOPS and other methods in controlled scenarios.
  • MNIST Handwritten Digit Dataset: Used for evaluating performance on a real-world image classification task. The training data contains digits 0-5, while the test data includes digits 0-9, creating a scenario with "unobserved" classes in the test set.
  • Network Intrusion Detection Dataset: A subset of the 1999 KDD intrusion detection contest data is used to evaluate BCOPS on a multi-class classification problem with a significant proportion of "other intrusions" (outliers).

Key Insights and Ideas

  • Prediction Sets are More Informative than Single Labels: For classification problems with potential distribution shifts, providing a set of plausible labels (or no label at all) is more robust and informative than forcing a single, potentially incorrect, prediction.
  • Conformal Prediction is Key for Distribution-Free Guarantees: The use of conformal prediction is essential for achieving finite-sample coverage guarantees without relying on strong assumptions about the underlying data distributions, which is critical when dealing with distribution shifts.
  • Explicitly Modeling Outliers is Crucial: By treating outliers as a separate class in the out-of-sample distribution, BCOPS can learn to abstain from prediction, a more desirable behavior than making a confident but wrong prediction.
  • Balancing Coverage and Abstention is a Trade-off: The parameter $\alpha$ (related to coverage) directly influences the abstention rate. A higher $\alpha$ (lower coverage guarantee) generally leads to more abstentions, which can be beneficial for outlier detection.
  • Estimating Outlier Behavior is Possible and Useful: The proposed methods for estimating the outlier abstention rate and false labeling rate provide valuable metrics for understanding and tuning the outlier detection capabilities of a model.

Key Results

  • Improved Outlier Detection: In simulated and real-world examples (MNIST, network intrusion), BCOPS demonstrates a significantly higher abstention rate for outliers compared to density-level set methods, while maintaining competitive accuracy for observed classes.
  • Guaranteed Coverage: BCOPS provides finite-sample coverage guarantees for the predicted classes, meaning that for a given confidence level $\alpha$, the true class will be in the prediction set at least $1-\alpha$ of the time for inliers.
  • Asymptotic Optimality: Theoretical results show that BCOPS is asymptotically optimal in terms of minimizing prediction set size while satisfying coverage requirements, and the mixture proportion estimates converge to their true values under certain conditions.
  • Performance Comparison: BCOPS generally outperforms the density-level set (DLS) and in-sample ratio set (IRS) methods, especially for unobserved classes or outliers. For observed classes, BCOPS is competitive with or slightly worse than IRS, trading some accuracy for better outlier detection.

Limitations and Future Work

  • Computational Cost: While BCOPS offers theoretical advantages, the conformal prediction construction can be computationally intensive, especially for large datasets or high dimensions. The paper mentions using sample-splitting to manage this cost.
  • High Dimensionality: The paper acknowledges that density estimation can suffer in high dimensions, and BCOPS's reliance on learned density ratios aims to mitigate this, but performance in extremely high-dimensional settings might still be a challenge.
  • Single New Observation: The paper suggests an extension to handle the case where only a single new observation is available, which poses a challenge due to limited information about the out-of-sample distribution.
  • Robustness to Feature Perturbations: Future work could explore making BCOPS more robust to small, systematic transformations (e.g., affine transformations) of features between training and test data.
  • Extension to BBSE: The proposed method can be viewed as an extension of existing methods like BBSE to handle outliers. Further exploration of this connection could be fruitful.

Summary updated

Abstract

We consider the multi-class classification problem when the training data and the out-of-sample test data may have different distributions and propose a method called BCOPS (balanced and conformal optimized prediction sets). BCOPS constructs a prediction set C(x) as a subset of class labels, possibly empty. It tries to optimize the out-of-sample performance, aiming to include the correct class and to detect outliers x as often as possible. BCOPS returns no prediction (corresponding to C(x) equal to the empty set) if it infers x to be an outlier. The proposed method combines supervised learning algorithms with conformal prediction to minimize a misclassification loss averaged over the out-of-sample distribution. The constructed prediction sets have a finite sample coverage guarantee without distributional assumptions. We also propose a method to estimate the outlier detection rate of a given procedure. We prove asymptotic consistency and optimality of our proposals under suitable assumptions and illustrate our methods on real data examples.
BibTeX
@misc{guan2024prediction,
  author = {Leying Guan},
  title = {{Prediction and outlier detection in classification problems}},
  year = {2024},
  url = {https://openreview.net/forum?id=tXxWXwFuxX},
  howpublished = {OpenReview},
}
Figure