Reinforcement Learning (RL) describes a family of algorithms teaching an agent to determine a policy for interacting with its surrounding environment. Recently, the RL paradigm has been successfully applied to the anomaly detection problem by learning a meta-policy on a set of already labelled datasets. The meta-policy is subsequently actively applied to a flow of incoming unseen observations, representing the test environment. The interesting point of this approach is that one can apply the meta-policy without further tuning to a small number of meta-features that can be directly extracted from any new dataset.
dataset that are suspected of being generated by a diferent process with respect to the rest of the data.
errors, instrument errors, or simply through natural deviations in populations. We can distinguish
three approaches to anomaly detection, namely supervised, semi-supervised, and unsupervised [
this setting usually, the classes are unbalanced since the anomalies are rare. Semi-supervised methods are trained with examples of just the normal class, thus they are also called one-class classifiers.
each object. Several statistical, data mining and machine learning approaches have been proposed to
detect outliers, namely, statistical-based [
CEUR ceur-ws.org
Description
in the -nearest neighbors A1: minimum distance between and the set of instances currently labelled as anomalous A2: mean distance between and the set of instances currently labelled as anomalous
list of , that is min∈ , where is the set of the known anomaly indices A4: the position occupied by in the nearest neighbors
list of , where = arg min∈ N1: minimum distance between and the set of instances
currently labelled as normal N2: mean distance between and the set of instances
currently labelled as normal
list of , that is min∈ , where is the set of the known normal items indices
N4: the position occupied by in the nearest neighbors list of , where = arg min∈ ( () () ( () () () ( () Cost 2) 2) 2) a ranked list of anomalies to identify as many true anomalies as possible. In AAD this human feedback can be leveraged to help the system to identify more anomalies. In this work, we consider the AAD scenario in which the anomaly detector queries the analyst by selecting instances one at a time. In this scenario, the system can adjust the decision functions by leveraging the expert’s knowledge gained from their responses to the queries. This human feedback can help the anomaly detector to promote the instances of interest and discourage the instances out of interest, showing the analyst more true anomalies in subsequent iterations.
(Meta–AAD), which learns a meta-policy with the aim of optimizing the number of discovered anomalies keeping the same budget , that is to say, the number of instances presented to the human for feedback.
Given a dataset = { 1, … , } ⊆ ℝ , at each iteration the policy selects an example to submit to the expert that will assert whether is actually an anomaly or not. The state of the policy is recorded in a vector ŷ ∈ R such that, for each ∈ {1, … , } , we have that the element is equal to −1, if the item has been submitted to the expert and reported as an anomaly, 1, if has been submitted to the expert and reported as normal, 0, if has not yet been submitted to the expert.
At the beginning of the policy, we have = 0, for each ∈ {1, … , } , and then at each iteration, the state of the item selected for the query is updated according to the expert feedback.
can be used to this aim. In particular, authors adopt Proximal Policy Optimization (PPO) [
computed. The instance with the highest probability is presented to the human.
A fundamental part of this process is the meta-features extraction. Formally, the aim is to define a function ∶ × y → R× , where is the number of meta-features, such that its image is as much as possible independent from the dataset. The framework allows flexible choices, in Table 1 are listed the main features adopted in literature. Among all these features an important role is played by the unsupervised anomaly detector D. Indeed, it is the only feature in the table that is computed before the training process and that is not updated after the expert’s feedback. Its main goal is to provide a bootstrap phase to the active process in the initial phase when the other features are not stable yet. As for the other meta-features they can be initialized at any arbitrary value for all the points, so that at the very first step of the active process the algorithm cannot discriminate on their basis.
set of = 6 meta-features: D (in particular they adopt the Isolation Forest algorithm [
that this fact may cause some issues in the query selection phase due to the specific distance distribution of the dataset. In order to relieve this dependence, it is introduced an innovative approach, called
on distances. Specifically, this set of meta-features includes
the adoption of the CFOF algorithm [
2. Meta–AAD–Light
matrix calculations involved in certain meta-features.
B1, A3 and N3 for a single item , the values of the distances of from all the other points in are needed, thus the cost is () and (
2) for the whole dataset. of Meta–AAD–Light are represented by D, A1, A4, N1, N4.
cost and is defined as follows:
B2: indicator asserting whether belongs to the -nearest neighbors of any known anomalous instance
The computation of the Meta–AAD–Light meta-features does not require computing the distances (and the associate rankings) among all the data points, but only the information about the distances between the points already classified as normal or anomalous and all the other points. In this way, the memory occupation goes from ( 2) for Meta–AAD and Meta–AAD–Rank to () for Meta–AAD–Light where is the number of queries and it is usually very smaller than the size of the dataset.
wine, from the ODDS repository [
We fix a budget of = 100 and we consider the following evaluation metrics, used also in [
• The Normalized AUC (N-AUC), that is the area under the curve of with varying normalized by the number of the total number of anomalies in the dataset, in formula 2 ∑=1 ′( ′ + 1) .
(2)
methods. In particular, we compute the of 2 emitted by exploiting the framework CodeCarbon
[
together with their number of samples and dimensions. Columns from 2 to 5 are associated with the comparison between Meta–AAD–Light and Meta–AAD and columns from 6 to 9 with the comparison between Meta–AAD–Light and Meta–AAD–Rank. Specifically, for each competitor and for each of the four above-mentioned metrics (namely, the number of anomalies, the precision, the normalizedAUC and the emitted 2), we compute the relative variation of Meta–AAD–Light with respect to as ( Meta–A A(D)–Light)−() , where ( Meta–AAD–Light) is the value of the metrics accomplished by
performances of Meta–AAD and Meta–AAD–Rank, for two datasets, namely pima and satimage-2, it is possible to observe a slight degradation in the results, and for the dataset speech we even outperform the other two methods. As for the emissions of 2, as predicted by the theoretical discussion,
the three datasets with the largest cardinality, where, in two cases (satellite and shuttle), we obtain the same performance in terms of accuracy while almost halving the 2 emissions, and in one case (satimage-2) we pay a small loss in accuracy to obtain a great benefit in terms of emission.
active anomaly detection. We prove that, diferently from the already existing sets of meta-features, the computation of Meta–AAD–Light requires constant time for a single item and, then, linear for the whole dataset. Experiments confirm that while maintaining good performance in terms of accuracy, the proposed method notably reduces the 2 emissions, thus decreasing the environmental impact of the whole approach.