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 learning a scoring function that reflects the degree of nominality. This paper introduces the Excess-Mass (EM) curve as a novel theoretical and practical framework for evaluating and building anomaly ranking functions. By maximizing probability mass while penalizing volume through a Lagrangian formulation, the EM approach achieves significantly faster learning rates ($O(n^{-1/2})$) and superior performance on unbounded data compared to traditional Mass-Volume (MV) curves.
Introduction
In multivariate anomaly detection, the goal is often to produce a ranked list of observations rather than a simple binary classification. This requires a scoring function $s(x)$ where lower values indicate higher abnormality. Historically, the performance of such functions was measured using Mass-Volume (MV) curves, which represent the minimum volume required to capture a specific amount of probability mass. However, MV curves suffer from slow convergence rates ($O(n^{-1/4})$), difficulties with distributions having infinite support, and issues with non-nested empirical solutions.
The Excess-Mass (EM) Framework
The authors propose the Excess-Mass (EM) curve as a more robust alternative. Instead of minimizing volume for a fixed mass, the EM approach maximizes mass for a fixed volume penalty $t$. The EM curve is defined as:
$$EM^*(t) = \max_{\Omega} \{P(X \in \Omega) - t \cdot \text{Leb}(\Omega)\}$$
where $t \ge 0$ acts as a "price" for volume. As $t$ increases, the optimal region $\Omega$ shrinks toward the highest-density areas of the distribution.
This "Lagrangian flip" transforms a constrained optimization problem into a penalized one, making the mathematics more tractable and ensuring that the resulting optimal regions are naturally nested, which is essential for a valid ranking.
Algorithm and Implementation
The paper introduces an adaptive algorithm to construct a piecewise constant scoring function. The process involves partitioning the space into a collection of subsets (e.g., hypercubes) and identifying regions that maximize the empirical excess mass for a sequence of prices $t_k$. A scoring function is then built by stacking these regions. Through simulations on 2D heavy-tailed data, the authors demonstrated that this approach successfully recovers density level sets even in non-compact cases.
Key Insights and Results
A major contribution of this work is the proof of a faster convergence rate. The error in the empirical EM curve decreases at a rate of $O(n^{-1/2})$, a substantial improvement over the $O(n^{-1/4})$ rate associated with MV curves. This faster learning is critical for practical applications where data may be limited.
Furthermore, the EM framework is uniquely suited for distributions with infinite support. While MV curves often fail when "normal" behavior lacks a hard boundary, the EM curve remains well-defined and effective for heavy-tailed distributions.
Discussion and Limitations
While the EM framework offers significant theoretical advantages, practical implementation faces the "curse of dimensionality." The partitioning method scales exponentially with the number of dimensions $d$. Additionally, the choice of partition granularity introduces a bias-variance tradeoff: smaller bins reduce model bias but may lead to overfitting in sparse regions. Future work involves testing these algorithms on high-dimensional real-world datasets like network intrusion or credit card fraud.
Conclusion
The Excess-Mass curve provides a powerful new lens for anomaly ranking. By addressing the theoretical and practical shortcomings of Mass-Volume curves—specifically regarding convergence speed and handling unbounded support—this framework offers a more reliable foundation for building and evaluating anomaly detection systems in complex, high-dimensional environments.
Summary updated