TL;DR
This paper introduces ACODE, a novel method for detecting and quantifying groups of outliers, even when individual outliers are hard to spot. It leverages conformal inference and closed testing to provide statistically guaranteed bounds on the number of outliers, adapting to the data to select the best machine learning and testing strategies.
What Problem Does This Paper Address?
Outlier detection is crucial in many fields, from fraud detection to scientific discovery. Traditional methods often focus on identifying individual outliers. However, in many real-world scenarios, outliers are weak, sparse, or only reveal themselves collectively. This makes individual detection difficult or impossible. Furthermore, the rise of complex, high-dimensional data and AI-generated synthetic data necessitates reliable and transparent outlier detection methods. This paper addresses the challenge of detecting and enumerating groups of outliers, especially when individual outliers are elusive, by developing a flexible, distribution-free approach with strong statistical guarantees.
Methods
ACODE combines several powerful statistical and machine learning techniques:
- Conformal Inference: This framework provides a principled way to generate prediction intervals and statistical guarantees for any machine learning model, even with mild assumptions. ACODE uses it to produce "conformity scores" that quantify how "outlier-like" a data point is.
- Closed Testing: This is a multiple testing procedure that allows for simultaneous inference on all possible subsets of hypotheses. ACODE uses it to construct lower confidence bounds for the number of outliers in any subset of the test data, ensuring valid inferences across all possible subsets.
- Machine Learning Classifiers: ACODE can leverage various "black-box" machine learning models (e.g., one-class classifiers, binary classifiers) to generate the conformity scores.
- Local Testing Procedures: A variety of statistical tests (e.g., Simes, Fisher, Wilcoxon-Mann-Whitney) are used to test local hypotheses about outliers within subsets.
- Data-Driven Adaptivity: A key innovation is ACODE's ability to automatically select the most effective combination of machine learning classifier and local testing procedure for a given dataset. This is achieved through a principled tuning process that avoids "cherry-picking" and maintains statistical validity.
Datasets
The paper evaluates ACODE on:
- Synthetic Data: Generated to mimic scenarios with weak or sparse outliers, and also to test adversarial anomaly detection.
- LHCO High-Energy Particle Collision Data: A real-world dataset from a challenge for anomaly detection in high-energy physics.
- Several publicly available datasets: Used in related literature (e.g., ALOI, Covertype, CreditCard, Mammography, Pendigits, Shuttle) to compare ACODE's performance against existing methods.
Key Insights and Ideas
- Collective detection is powerful: Even when individual outliers are too weak to be detected, their collective behavior can be a strong signal. ACODE excels in these scenarios.
- Adaptivity is crucial: The best machine learning classifier and statistical test depend heavily on the data. ACODE's ability to automatically select these components leads to better performance and avoids manual tuning pitfalls.
- Conformal inference + Closed testing = Robust guarantees: Combining these frameworks provides statistically sound lower bounds on the number of outliers, even in complex settings.
- Individual vs. Collective inference: The paper highlights that collective outlier enumeration can be more powerful and informative than individual outlier identification, especially when outliers are subtle.
Key Results
- ACODE successfully detects and enumerates outliers in both synthetic and real-world datasets, often outperforming existing methods, especially in challenging scenarios with weak or sparse outliers.
- The adaptive nature of ACODE allows it to achieve near-oracle performance by selecting the most effective classifier and testing procedure for each dataset.
- ACODE provides statistically guaranteed lower confidence bounds for the number of outliers, ensuring reliable inferences.
- The method is shown to be robust to different data distributions and outlier characteristics.
Limitations and Future Work
- Computational Cost: While ACODE offers computational shortcuts, some local testing procedures (like Shiraishi's) can still be computationally expensive, especially for large datasets. Future work could focus on developing faster shortcuts for these procedures.
- Reference Data: The current method assumes an ideal reference dataset of inliers. Future research could explore relaxations of this assumption to account for potential contamination or distribution shifts in the calibration data.
- More Sophisticated Conformal Frameworks: Extensions to more advanced conformal inference frameworks, such as cross-validation, could potentially improve performance, though at the cost of increased computational expense.
- Optimality of Local Tests for Closed Testing: An intriguing open question is whether the optimality of local tests extends to closed testing procedures, which could lead to more efficient methods.
Summary updated