Finite Sample Complexity of Rare Pattern Anomaly Detection.

Md Amran Siddiqui, Alan Fern, Thomas G. Dietterich, Shubhomoy DasUAI 2016 · OpenReview

Abstract

Anomaly detection in high-dimensional spaces often performs surprisingly well despite limited training data, a phenomenon that contradicts the traditional "curse of dimensionality." This paper introduces the PAC-RPAD (Probably Approximately Correct Rare Pattern Anomaly Detection) framework to provide a theoretical foundation for this success. By shifting the focus from density estimation to the complexity of "pattern spaces," the authors demonstrate that sample complexity scales with the VC-dimension of the patterns rather than the data's dimensionality. Empirical evaluations on benchmark datasets confirm that simple pattern-based algorithms converge rapidly, often requiring as few as 1,024 samples to reach peak performance.

Introduction

In supervised learning, PAC theory provides rigorous bounds on the data required for generalization. Unsupervised anomaly detection has historically lacked such a foundation, leaving practitioners to wonder why algorithms like Isolation Forest succeed in high-dimensional settings where data is inherently sparse. This paper addresses this gap by formalizing the sample complexity of identifying rare patterns, proving that dimensionality does not always ruin performance if the algorithm searches for simple patterns.

The PAC-RPAD Framework

The authors propose Rare Pattern Anomaly Detection (RPAD), which identifies anomalies by searching for "patterns"—subsets of the feature space—that are rarely satisfied by normal data relative to a reference distribution.

Key components include:

  • Pattern Spaces ($\mathcal{H}$): A collection of possible properties a data point might have (e.g., axis-aligned rectangles).
  • Sample Complexity: The authors prove that if the pattern space has a low VC-dimension, the amount of data needed to reliably detect anomalies scales linearly with that complexity, bypassing the exponential requirements typically associated with high-dimensional density estimation.
Convergence of Pattern Average on the Covertype dataset illustrates how AUC plateaus quickly as sample size increases.

Experimental Evaluation

The theory was tested using three UCI benchmark datasets: Covertype (10 features), Particle (50 features), and Shuttle (9 features). Rare classes were treated as anomalies to create a "needle-in-a-haystack" scenario. The authors compared standard Isolation Forest against their proposed MIN and Average scoring methods, which are simplified versions of the RPAD framework.

Key Results

The experiments validated the theoretical predictions across all datasets. Performance (measured by AUC) typically plateaued around 1,024 samples, regardless of the feature count. Notably, the simple MIN scoring method—which identifies the single rarest pattern a point satisfies—performed competitively with, and sometimes outperformed, state-of-the-art Isolation Forests.

Comparative performance of Isolation Forest, Pattern Average, and Pattern Min across three datasets.

Insights and Discussion

  • Isolation Forest as Pattern Search: The success of Isolation Forest is attributed to its implicit search through a pattern space of axis-aligned hyper-rectangles, which has a low VC-dimension ($2d$).
  • Non-Monotonic Learning: Unlike supervised tasks, adding more data or complex patterns can sometimes degrade performance. This occurs when the algorithm begins identifying "distractor" patterns that are statistically rare but semantically irrelevant to the user.
  • Semantic Mismatch: The choice of pattern space is the primary mechanism for encoding what constitutes an "interesting" anomaly for a specific domain, as statistical rareness does not always equal practical importance.

Conclusion

The PAC-RPAD framework provides a much-needed theoretical lens for understanding anomaly detection. By demonstrating that sample complexity is a function of pattern complexity rather than dimensionality, it explains why modern algorithms are effective in high-dimensional spaces and suggests that future research should focus on efficient search strategies within low-complexity pattern spaces.

Summary updated

BibTeX
@inproceedings{siddiqui2016finite,
  author = {Md Amran Siddiqui and Alan Fern and Thomas G. Dietterich and Shubhomoy Das},
  title = {{Finite Sample Complexity of Rare Pattern Anomaly Detection.}},
  booktitle = {UAI},
  year = {2016},
  url = {https://openreview.net/forum?id=xS_iC6WhLKW7},
}
Figure