Sparse Representation of Multivariate Extremes with Applications to Anomaly Ranking

Capturing the dependence structure of multivariate extreme events is a major concern in many fields involving the management of risks stemming from multiple sources, e.g. portfolio monitoring, insurance, environmental risk management and anomaly detection.
One convenient (nonparametric) characterization of extremal dependence in the framework of multivariate Extreme Value Theory (EVT) is the angular measure, which provides direct information about the probable 'directions' of extremes, that is, the relative contribution of each feature/coordinate of the 'largest' observations. Modeling the angular measure in high dimensional problems is a major challenge for the multivariate analysis of rare events. We propose here a novel methodology aiming at exhibiting a sparsity pattern within the dependence structure of extremes. This is done in a non-parametric way by estimating the amount of mass spread by the angular measure on representative sets of directions, corresponding to specific sub-cones of (R+)^d (after non-linear transform of the data). This method performs linearly with the dimension and almost linearly in the data (in O(dn log n)), and can thus be used for large scale problems. This dimension reduction technique paves the way towards scaling up existing multivariate EVT methods.
Beyond a non-asymptotic study providing a theorical validity framework for our method, we propose as a direct application an anomaly detection algorithm based on multivariate EVT. Although multivariate extremes play a special role when trying to rank observations with respect to their degree of abnormality, no established anomaly detection (AD) algorithm takes into account this specificity. Our algorithm builds a sparse 'normal profile' of extreme behaviours, to be confronted with new (possibly abnormal) extreme observations.

This is a joint work with Anne Sabourin & Stéphan Clémençon