conclusion.tex

In this thesis, three different problems have been addressed.
Building scoring functions, % the problem of extending the use of random forests to one-class classification,
 gaining in accuracy on low probability regions, and evaluating algorithms in the case of unlabeled data.


For the first problem, two solutions have been proposed.
The excess-mass based performance criterion has been defined and used in a empirical risk minimization framework. %, in order to compare scoring functions and to pick one eventually.
While theoretical guaranties have been derived (resp. exists) for scoring functions produced by optimizing the excess-mass (resp. mass-volume) curves, more work is needed for them to achieve efficiency in practice. In particular, the choice of the functional class on which the criterion is optimized (which is typically the class of stepwise functions on very simple sets) is challenging. This class has to be rich enough to provide a good approximation while simple enough to control the convergence rate and the algorithmic complexity, which is a hard trade-off to achieve when no information on the underlying distribution is used.
%
The second solution is based on random forests. It consists in extending naturally standard splitting criteria to the one-class setting. This structural generalization of random forests to one-class classification produces competitive scoring functions with respect to many state-of-the-art anomaly detection algorithms commonly used in industrial setups. Its principal limitations, which also are perspectives, lie in the fact that this is essentially a heuristic method, and it lacks of theoretical guaranties.


For the accuracy gain on low probability regions, tools borrowed from multivariate extreme value theory have been used to defined a possibly sparse representation of the dependence structure of extremes, and the associated scoring functions. Besides, non-asymptotic bounds have been derived on the estimation procedure.
An intermediate step was to study the non-asymptotic behavior of the stable tail dependence function, a functional characterizing the extreme dependence structure. 
Novel bounds have been derived to control the error of its natural empirical version, as well as a methodology for deriving VC-type bounds on low-probability regions.
Moreover, the sparsity pattern in multivariate extremes we exhibit can be used as a preprocessing step to scale up multivariate extreme values modeling to high dimensional settings, which is currently one of the major challenges in multivariate EVT.
%
Because no assumption is made on the underlying distribution other than the existence of the STDF, the non-asymptotic bounds on the estimation procedure contain separated bias terms corresponding to the (distribution-dependent) convergence speed to the asymptotic behavior, which are not controlled explicitly.
% The bound derived here includes a separated bias, which cannot been expressed or control explicitly
This prevents us to choose in an adaptive way the parameters of our representation of extreme dependence. Since these parameters cannot be chosen by cross-validation as no labeled data is available in our setting, default parameters have to be chosen. While results seem accurate in our benchmarks, this is a limitation of this approach.
A possible future direction is to make an additional hypothesis of  `second order regular variation'  \citep[see \emph{e.g.}][]{deHaan1996} in order to express these bias terms, and possibly to refine the results.
%One perspective could be for instance to assume a second order regular variation, in order to obtain an explicit form for this problematic bias.
%One limitation is that 

For the evaluation of anomaly detection algorithms in the case of unlabeled data, the theory is built on the excess-mass and mass-volume curves.
%
As these criterion have originally been introduced to build scoring functions using empirical risk minimization, no empirical study has been made in the literature on their ability to discriminate between existing scoring functions. %, in the same way ROC or PR scores do using the labels. 
%Such an empirical study for the use of excess-Mass and mass-Volume curves as evaluation criteria in the absence of labeled data. 
To this end, we present a benchmark showing that EM and MV criteria are able to recover the ranking induced by ROC/PR over scoring functions, when labels are hidden.
Besides, as these curves can only be estimated in small dimensions (they involve volume computations), a methodology based on feature sub-sampling and aggregating is described and tested. It allows an extension of the use of these criteria to high-dimensional datasets. It also solves major drawbacks inherent to standard EM and MV curves, allowing \eg~features selection in the unsupervised setting.
%
This heuristic (random projections and aggregating) works well in practice, but suffers from a lack of theoretical guaranties. Note that it does not evaluate a fixed scoring function, but multiple scoring functions (output by the algorithm to be evaluated) defined on different sub-spaces with the same dimension. 
Thus, it could be of great interest to study if the quantity estimated here really converges when the number of random projections go to infinity, and to find out if the limit somehow corresponds to a scoring function defined on the entire input space. In particular, this may allow to choose in an optimal way the sub-sampling parameters.

% the underlying quantity estimated here (if any). If we can define a scoring function on the input space whose restrictions to the random sub-spaces correspond to the scoring functions output by the algorithm, is there a 
%  and to study how fast is the convergence depending on the sub-sampling parameters. This would allow in particular to choose adaptively these parameters.




% Staying in the scope of multivariate extremes, the non-asymptotic bounds in the two main results contain separated bias terms corresponding to the (distribution-dependent) convergence speed to the asymptotic behavior, which are not controlled explicitly.
% A possible future direction is to make an additional hypothesis
% of  `second order regular variation'  \citep[see \emph{e.g.}][]{deHaan1996}
% in order to express these bias terms, and possibly to refine the results.
% With such explicit bounds, parameters of the Damex algorithm (third contribution) could be chosen optimally as the ones minimizing the obtained bound.

% From the scope of one-class random forests, a possible research direction would be to develop theoretical grounds for the level sets estimation procedure. Classical studies from the two-class framework should be adapted to one-class classification.











% Anomaly, outlier or novelty detection is not only a useful preprocessing step for training machine learning algorithms. It is also a crucial component of lots of real-world applications, from various fields like finance, insurance, telecommunication, computational biology, health or environmental sciences. Anomaly detection is also more and more relevant in the modern world, as an increasing number of autonomous systems need to be monitored and diagnosed -- \eg~with the rise of Internet-of-Things.
% %
% Important research areas in anomaly detection include the design of efficient algorithms and their theoretical study %(derived from a mathematical theory as well as heuristic-based ones), 
% %the theoretical study of existing algorithms lacking from such guaranties, 
% but also the evaluation of such algorithms, in particular when no labeled data is available -- as in lots of industrial setups. 
% In other words, model design and study, and model selection.

% In this thesis, we focuse on both of these aspects. 
% In practice, anomaly detection algorithms output a real valued \emph{scoring function} on the feature space so as to quantify to which extent observations should be considered as abnormal.
% %
% We first propose a criterion for measuring the performance of scoring functions, alternative to the existing \emph{Mass-Volume curve}. %-- function outputed by anomaly detection algorithms and measuring the supposed degree of abnormality of the observations.
% This criterion, refered as \emph{Excess-Mass curve}, aims at building scoring functions \emph{via} empirical risk minimization (ERM).


% The second part of this work focuses on \emph{extreme} regions, which are of particular interest in anomaly detection. In particular, probabilistic tools borrowed from (multivariate) Extreme Value Theory (EVT), such as the stable tail dependence function (STDF) and the angular measure, can be combined with classical anomaly detection approaches to gain in accuracy on such extreme regions.
% %
% Advances in multivariate EVT are brought by providing non-asymptotic bounds for the estimation of the STDF, which characterizes the extreme dependence structure.
% %
% Then a statistical method that produces a (possibly sparse) representation of the dependence structure of extremes is derived from an estimate of the angular measure. This representation can be used directly to produce a scoring function accurate on extremes regions.
% Non-asymptotic bounds to assess the accuracy of the estimation procedure are established.


% The last part of this work compiles some limitations of previous parts, and proposes two heuristics, one from the model selection / algorithms evaluation point of view, the other from the algorithms design. %and proposes solutions to the two major drawbacks raised by the Excess-Mass and Mass-Volume curves: poor performance in practice

% From the model selection point of view, no empirical study has been made on Excess-Mass and Mass-Volume curves for evaluating anomaly detection algorithms without using any labels. Besides, these curves can only been estimated in small dimensions as they involve some volume computation. % and no study has been done on their capacity to discriminate between scoring functions with respect to ROC and PR curves when labels are used.
% %If default parameters usually work well for the EVT-based scoring function we promote next, accurate
% We derive then such empirical study for the use of Excess-Mass and Mass-Volume curves as evaluation criteria in the absence of labeled data. 
% % As they generally cannot be well estimated in large dimension,
% A methodology based on feature sub-sampling and aggregating is also described and tested, extending the use of these criteria to high-dimensional datasets and solving major drawbacks inherent to standard EM and MV curves. 

% From the model design point of view,
% while theoretical guaranties are derived for scoring functions produced by optimizing EM and MV curves, more work is needed for them to achieve efficiency in practice. In particular concerning the choice of the functional class on which the criterion is optimized (which is typically the class of stepwise functions on very simple sets). % When used as evaluation criteria, these criteria cannot be used in large dimension.
% An efficient way based on random forests to produce accurate scoring functions is proposed. It consists in extending naturally standard splitting criteria to the one-class setting. This structural generalizion of random forests to one-class classification produces competitive scoring functions, according to an extensive benchmmark which includes many state-of-the-art anomaly detection algorithm commonly used in industrial setups.



% A drawback of this approach is that performance depends on hyper-parameters. They cannot be settled using the theoretical bounds as the latter include a non-explicit bias term. Most of the time, they cannot be settled from the data either, as often no labeled data is available for \eg~cross-validation.