Advancements in Unsupervised Anomaly Detection

Anomaly Detection is about finding unexpected behaviors in data. These unexpected behaviors, or anomalies, can lead to serious issues like loss of important data, leaks in water systems, breakdowns in machinery, or failures in oil extraction. Identifying these anomalies quickly is crucial since they can lead to costs-either financial (like maintenance or fraud) or environmental (like pollution).

#The Challenge of User Trust

When using systems to detect anomalies, it's vital that users trust the results. However, getting reliable labels for these anomalies is often difficult. Anomalies may not follow clear patterns, which makes the task more complex. This is why many methods for anomaly detection operate without any labeled data, relying on unsupervised learning. Traditional methods set a boundary between what is considered normal and what is not, based on heuristics-rules based on intuition rather than hard data. Unfortunately, these rules can be hard to verify.

Due to these uncertainties, especially for data close to the decision boundary, users may feel unsure about the predictions made by the detection system. To improve user trust, one suggestion is to allow the system to reject cases where it isn't confident in its predictions. However, implementing this method introduces new challenges, particularly in determining how to evaluate confidence in predictions without having access to true labels for the anomalies.

#The Need for a Confidence Metric

The core idea of allowing a system to abstain from making predictions when it isn't confident is known as Learning To Reject. In this setup, the model can choose not to make predictions when it believes it could be wrong, thereby improving its performance on predictions it does make. However, this creates a situation where a person must step in to make decisions whenever the model chooses not to predict.

Currently, there are two types of rejection strategies used. The first is novelty rejection, where the model abstains when it encounters new or unusual data. The second is ambiguity rejection, which is when the model abstains when it doesn't feel certain about its prediction, particularly when facing data that is too close to the decision boundary. Since anomalies often don't fit into clear categories, novelty rejection isn't ideal for this situation, as the model would reject all anomalies.

On the other hand, current methods for ambiguity rejection require evaluating model performance on data where predictions are made, compared to data where predictions are withheld. This means the model must rely on labeled data, which isn't available in the context of anomaly detection.

#Proposal for a New Approach

This paper addresses this challenge by proposing a fresh approach that allows for ambiguity rejection in a completely unsupervised manner. The approach has three key contributions:

1. A thorough analysis of a Stability metric used for anomaly detection with properties that help in Learning to Reject.
2. The design of a rejection mechanism that doesn’t require labeled data while offering guarantees often desired in Learning to Reject methods.
3. An experimental evaluation showing that this new method outperforms previous approaches based on other unsupervised metrics.

#Understanding Anomaly Detection

In anomaly detection, the goal is to identify examples of anomalies in a given set of data. These examples are turned into scores, with higher scores suggesting that an example is more likely to be an anomaly. Because there are no labels to guide the process, a threshold is typically set to distinguish between normal and anomalous examples.

Without labels, the threshold is often set based on an expected proportion of anomalies in the dataset. This is known as the contamination factor, which is an estimate of how many examples in the dataset are anomalies.

#Learning to Reject

In the Learning to Reject framework, outputs are extended to include an option to abstain from predictions altogether. This involves learning a second model to determine when to abstain. A common way to accomplish this is by defining a confidence score and a rejection threshold.

When the model’s confidence in a prediction falls below this threshold, it opts to not make a prediction. The challenge here is to find the right threshold without labeled data.

#Confidence Metrics and Stability

Traditional metrics rely on quantifying how likely a prediction is correct, which requires labels. Instead, this approach suggests focusing on the concept of stability. Stability refers to how consistent the model's output is when there are slight changes to the training data. If slight changes lead to different outputs, the prediction is considered unstable.

A stability-based confidence metric can be used to express how stable the output is for a given example. If an example is stable, it means the prediction is not sensitive to small changes in the training data, while unstable predictions indicate that even minor changes could flip the predicted label.

#Key Findings from Theoretical Analysis

The new proposal highlights a limited number of cases where examples will receive low confidence scores. This is largely because many examples will fall into categories that the model can confidently identify, either as normal or anomalous. For example, normal data tends to cluster together, while anomalies are often isolated.

The method, called Rejecting via ExCeeD, calculates a stability-based confidence metric and rejects examples that fall below a specific threshold. This constant threshold allows for strong guarantees, including estimates of the proportion of rejections and upper bounds on expected costs.

#Setting the Rejection Threshold

The analysis indicates that examples with low confidence are those that are close to the model's decision boundary. Thus, the method suggests rejecting any examples that fall below the predetermined threshold. The tighter the threshold, the fewer examples will be rejected.

By increasing the number of training examples, the sensitivity to the decision boundary decreases, which means that more examples will receive a stable, high confidence score. Conversely, decreasing the tolerance for uncertainty leads to a broader area of potential rejections.

#Estimating and Bounding the Rejection Rate

Knowing the rejection rate is critical to understanding how many examples the model will abstain from making predictions on. It's a vital aspect of differentiating between different models. Therefore, a way to estimate the rejection rate is proposed, which converges towards the true rate as the size of the training set increases.

A simple estimator is provided to calculate the rejection rate based on the trained model's performance. Since the true distribution of the example scores is unknown, estimates are made based on available training scores.

#Expected Cost at Test Time

An important aspect of the Learning to Reject scenario is the costs associated with different outcomes. False positives, false negatives, and rejections each incur their associated costs. By estimating an expected cost per example, one can select between different models.

The proposed method includes upper bounds on costs for expected outcomes, ensuring that the model avoids high costs over time. By using the estimated rejection rate, the expected costs incurred can be kept within acceptable limits.

#Related Work in Anomaly Detection

While there isn't much existing work focusing on Learning to Reject in unsupervised anomaly detection, there are similar research areas. The first involves supervised methods, which can enhance models by using labels to optimize rejection thresholds based on model performance. The second includes self-supervised methods that generate pseudo-labels for training data, enabling traditional supervised learning.

Finally, optimizing unsupervised metrics is another category where researchers derive rejection thresholds from metrics that can be calculated without labels. These metrics focus on aspects like the consistency of predictions or model trustworthiness, helping to determine effective rejection thresholds.

#Experimental Setup

In the experiments, the new method is compared against several baselines across 34 publicly available datasets with various applications. Different methods are tested for their performance over numerous scenarios, including variations in the cost functions.

Different unsupervised anomaly detectors are employed, and the method is evaluated based on how it sets rejection thresholds compared to other approaches, while also considering computational efficiency.

#Results of Experiments

The results indicate that the new method often achieves lower costs compared to other baselines, performing particularly well in various scenarios. The method consistently ranks high across detectors and exhibits superior overall performance.

Statistical tests conducted during the research show that the new approach is significantly better than other methods across multiple detectors, thus demonstrating its effectiveness.

#Impact of Varying Cost Functions

Varying the costs associated with different outcomes provides insights into the method's flexibility. By adjusting these costs, it becomes clear how sensitive the method is to changes in its decision-making process.

Across different cases, the new method maintains its competitive edge and achieves lower average costs relative to the other baseline methods.

#Confirming Theoretical Results

The experiments also verify the theoretical guarantees outlined in the approach. Cost estimates remain below the predicted upper limits, and the rejection rates align closely with empirical findings across various datasets.

These outcomes enhance confidence in the method's theoretical predictions and practical applicability, solidifying its potential for real-world anomaly detection tasks.

#Conclusions and Limitations

In summary, the proposed method effectively addresses the challenges associated with Learning to Reject in unsupervised anomaly detection. By leveraging a stability metric, the proposal offers ways to set rejection thresholds without needing labeled data.

However, there are limitations to the method. Since it operates without labels, it presents a less nuanced view of performance, especially in cases where anomalies might have different costs. The presence of a positive rejection rate may also lead to a potentially higher cost for an otherwise accurate detector.

Future work could explore more tailored solutions that address varying costs or develop models that better adapt to real-world complexities in anomaly detection.