Abstract: International audience. This paper introduces the Excess-Mass (EM) curve, a new functional criterion for ranking anomalies in multivariate data. Unlike previous methods that struggle with slow convergence and infinite tails, the EM approach offers a faster $n^{-1/2}$ convergence rate and a robust framework for prioritizing "abnormal" observations in both bounded and unbounded datasets.
Introduction: From Classification to Ranking
Anomaly detection research has traditionally focused on binary classification: determining whether a data point is "normal" or "abnormal." However, in real-world applications such as fraud detection or system monitoring, human experts have limited time and resources. In these scenarios, it is far more useful to rank observations by their degree of abnormality, allowing the most suspicious cases to be investigated first.
Mathematically, this requires finding a scoring function where lower scores correspond to more abnormal points. The standard metric for evaluating such functions has been the Mass-Volume (MV) curve, which seeks the smallest volume containing a specific amount of probability mass. Despite its intuitive appeal, the MV curve has two major flaws: slow convergence rates (often $O(n^{-1/4})$) and an inability to handle heavy-tailed distributions effectively without restrictive assumptions.
The Excess-Mass (EM) Framework
The authors propose the Excess-Mass (EM) curve as a superior alternative. The core innovation lies in flipping the optimization problem. Instead of minimizing volume under a mass constraint (the MV approach), the EM approach maximizes mass under a volume penalty. This results in a Lagrangian formulation:
$$\max_{\Omega} \{P(X \in \Omega) - t \cdot \text{Leb}(\Omega)\}$$
where $t$ is a threshold and $\text{Leb}(\Omega)$ represents the Lebesgue measure (volume).
As illustrated in the figure above, while the MV curve (left) fixes the mass $\alpha$ to find the optimal volume $\Gamma_\alpha^*$, the EM curve (right) uses the threshold $t$ to define the optimal set $\Omega_t^*$. This duality transforms a constrained optimization problem into a simpler, more statistically stable one.
Handling Heavy Tails and Faster Convergence
A significant "aha" moment in this research is the proof that the EM curve converges at a rate of $O(n^{-1/2})$. This is a substantial improvement over the $O(n^{-1/4})$ rate associated with MV curves, meaning the model achieves higher accuracy with less data. Furthermore, because the EM formulation penalizes volume linearly, it remains stable when dealing with the "tails" of a distribution.
Figure 5 demonstrates how the EM curve characterizes various distribution types. It is particularly effective for "heavy-tailed" distributions (unbounded support), a scenario where traditional methods typically fail. The EM-based scoring function successfully recovers underlying density clusters even when data spreads out infinitely.
Algorithmic Implementation
The paper provides an adaptive algorithm to build a practical scoring function:
- Discretize the threshold: Select a sequence of values for $t$.
- Empirical Optimization: For each $t$, identify the set in a collection $\mathcal{G}$ (e.g., a grid of hypercubes) that maximizes the empirical excess mass.
- Nested Sets: The algorithm ensures these sets are "nested" (each set is contained within the next as $t$ decreases), which naturally defines a consistent ranking.
- Scoring: The final scoring function is a piecewise constant function constructed from these nested sets.
Limitations and Future Work
While the theoretical results are promising, challenges remain. The "curse of dimensionality" means that using a fixed grid of hypercubes scales poorly to high-dimensional data. Additionally, performance depends heavily on the choice of the set collection $\mathcal{G}$. Future work will explore using more flexible collections, such as those defined by decision trees or kernel methods, to implement the EM criterion in high-dimensional settings.
Summary updated