On Anomaly Ranking and Excess-Mass Curves

Nicolas Goix, Anne Sabourin, Stéphan Clémençon

TL;DR

This paper introduces the Excess-Mass (EM) curve, a new functional criterion for ranking anomalies in multivariate, unlabeled datasets. By reframing anomaly detection as a mass-maximization problem under volume constraints, the authors develop an adaptive algorithm that achieves significantly faster convergence rates ($n^{-1/2}$) than previous methods and works effectively even when data distributions have infinite support.

What Problem Does This Paper Address?

In one dimension, identifying "abnormal" data is easy: just look at the tails of the distribution (the very high or very low values). However, in multivariate spaces (e.g., fraud detection or system monitoring), there is no natural "order." We need a scoring function to rank how abnormal a point is.

Existing methods often use the Mass-Volume (MV) curve, which looks for the smallest possible volume that contains a certain percentage of the data. While useful, the MV curve has two major drawbacks:

  1. Slow Convergence: Theoretically, it learns at a rate of $n^{-1/4}$, which is quite slow for massive datasets.
  2. Support Issues: It struggles when the data isn't confined to a "compact" (bounded) area, making it difficult to analyze heavy-tailed distributions.

Methods

The authors propose a "Lagrangian" swap. Instead of minimizing volume for a fixed mass (MV approach), they maximize Excess Mass: the probability mass of a region minus its volume scaled by a threshold $t$.

The EM Curve: The EM curve plots this maximum excess mass against the threshold $t$. An optimal scoring function is one whose level sets coincide with the density level sets of the underlying distribution.

The Algorithm: 1. Discretization: They create a grid of thresholds $t_1, t_2, \dots, t_N$. 2. Empirical Optimization: For each threshold, they find a set in a collection $\mathcal{G}$ (like a collection of hypercubes) that maximizes the empirical excess mass. 3. Scoring Function Construction: They build a piecewise constant scoring function by stacking these optimized sets. This ensures the resulting ranking is monotonic and consistent.

Datasets

The paper primarily uses simulated 2D heavy-tailed data for evaluation.

  • Distribution: A product of two heavy-tailed densities: $f(x, y) = \frac{1}{2} \times \frac{1}{(1+|x|)^3} \times \frac{1}{(1+|y|)^2}$.
  • Scale: A training set of $10^5$ points and a test set of $10^6$ points.
  • Partitioning: They used a grid of hypercubes (bins) to approximate the density, adjusting the bin width ($l$) to study model bias and overfitting.

Key Insights and Ideas

  • The Convergence Leap: By switching to the EM formulation, the authors prove a convergence rate of $O(n^{-1/2})$. This is a significant theoretical improvement over the $O(n^{-1/4})$ rate associated with MV curves.
  • Handling the Infinite: Unlike previous methods, the EM curve remains well-defined and statistically consistent even for distributions with "unbounded support" (data that can theoretically appear anywhere in space).
  • The "Aha" Moment on Bias: The authors show that the error in the EM curve can be decomposed into two parts: estimation error (from having finite data) and model bias (from the limitations of the shapes in $\mathcal{G}$, like using square bins to approximate a circular density).
  • Adaptivity: The algorithm naturally prioritizes regions with high local density, which is crucial for distinguishing "normal" from "abnormal" in high-dimensional spaces.

Key Results

  • Theoretical Robustness: The paper provides rigorous proofs that the empirical EM curve converges uniformly to the optimal EM curve.
  • Simulation Performance: In 2D tests, the algorithm successfully recovered the ranking of the heavy-tailed distribution.
  • Overfitting Control: The experiments demonstrated that while very small bins (small $l$) reduce model bias, they can lead to overfitting in the "tails" (low-density regions) where data is sparse. The EM curve provides a way to visualize and manage this trade-off.

Limitations and Future Work

  • The Choice of $\mathcal{G}$: The performance is highly dependent on the class of sets $\mathcal{G}$ used. While hypercubes are simple, they might not scale well to very high dimensions due to the "curse of dimensionality."
  • Computational Complexity: While the paper mentions the use of sparse matrices to keep the procedure efficient, implementing this for extremely high-dimensional features remains a challenge.
  • Future Directions: The authors suggest that further research could involve more complex set classes or automated ways to tune the "bin width" or model complexity parameters dynamically as the threshold $t$ changes.

Summary updated

Abstract

Learning how to rank multivariate unlabeled observations depending on their degree of abnormality/novelty is a crucial problem in a wide range of applications. In practice, it generally consists in building a real valued "scoring" function on the feature space so as to quantify to which extent observations should be considered as abnormal. In the 1-d situation, measurements are generally considered as "abnormal" when they are remote from central measures such as the mean or the median. Anomaly detection then relies on tail analysis of the variable of interest. Extensions to the multivariate setting are far from straightforward and it is precisely the main purpose of this paper to introduce a novel and convenient (functional) criterion for measuring the performance of a scoring function regarding the anomaly ranking task, referred to as the Excess-Mass curve (EM curve). In addition, an adaptive algorithm for building a scoring function based on unlabeled data X1 , . . . , Xn with a nearly optimal EM is proposed and is analyzed from a statistical perspective.
BibTeX
@inproceedings{goix2015anomaly,
  author = {Nicolas Goix and Anne Sabourin and Stéphan Clémençon},
  title = {{On Anomaly Ranking and Excess-Mass Curves}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=vEsb17WJhA},
}

Loading related content...

Figure