{'fraction_non_alphanumeric': 0.03145695364238411, 'fraction_numerical': 0.007893115663021717, 'mean_word_length': 4.880235453928005, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Little Help Makes a Big Difference: Leveraging Active Learning to Improve Unsupervised Time Series Anomaly Detection

Key Performance Indicators (KPI), which are essentially time series data, have been widely used to indicate the performance of telecom networks. Based on the given KPIs, a large set of anomaly detection algorithms have been deployed for detecting the unexpected network incidents. Generally, unsupervised anomaly detection algorithms gain more popularity than the supervised ones, due to the fact that labeling KPIs is extremely time- and resource-consuming, and error-prone. However, those unsupervised anomaly detection algorithms often suffer from excessive false alarms, especially in the presence of concept drifts resulting from network re-configurations or maintenance. To tackle this challenge and improve the overall performance of unsupervised anomaly detection algorithms, we propose to use active learning to introduce and benefit from the feedback of operators, who can verify the alarms (both false and true ones) and label the corresponding KPIs with reasonable effort. Specifically, we develop three query strategies to select the most informative and representative samples to label. We also develop an efficient method to update the weights of Isolation Forest and optimally adjust the decision threshold, so as to eventually improve the performance of detection model. The experiments with one public dataset and one proprietary dataset demonstrate that our active learning empowered anomaly detection pipeline could achieve performance gain, in terms of F1-score, more than 50% over the baseline algorithm. It also outperforms the existing active learning based methods by approximately 6%-10%, with significantly reduced budget (the ratio of samples to be labeled).


Introduction
Anomaly detection has always been one of the grand challenges, yet an essential capability, in building resilient computer and communication networks. Being able to detect anomalies will not only guarantee a timely warning of potential failures in the systems, but also ensure a quick remediation and error correction, which may save a lot of unnecessary expenses. As a matter of fact, Key Performances arXiv:2201.10323v1 [cs.LG] 25 Jan 2022 Indicators (KPIs), which are essentially time series data collected over time, have been widely used to assess the health status of networks and services. Any network failures or unexpected incidents can lead to the significant deviation of KPIs from their normal patterns. Therefore, KPI based anomaly detection algorithms aim at detecting those deviations with respect to the time series characteristics (e.g., seasonality, trend) or statistical features (e.g., min, max, mean). For example, the commonly seen anomalies include, but not limited to, spike, dip, continuous bursts, sudden or gradual trend change.
To date, many anomaly detection algorithms have been proposed, including both supervised and unsupervised ones. It is commonly recognized that the supervised anomaly detection algorithms perform better than the unsupervised ones if the labels are sufficiently provided. However, this assumption does not always hold true considering the fact that labeling tons of KPIs is extremely timeand effort-consuming and error-prone. Unsupervised ones are therefore preferred over the supervised ones in practice. One question naturally arising here is that, can we balance the trade-off between labeling effort and detection performance? In other words, human operators only pay a reasonable amount of effort to label the KPIs of interest (e.g., the ones lead to false positives), and then guide the algorithm towards a better detection behavior. This is particularly interesting considering the fact that unsupervised anomaly detection algorithms often suffer from excessive false alarms, especially in the presence of concept drifts potentially resulting from network routine updates or legitimate changes.
In fact, the aforementioned question has found some answers in the community [4,18], which share the relevant theoretical foundation with active learning. With the same question in mind, in this paper, we intend to present a new active learning based solution to improve the performance of an unsupervised anomaly detection algorithm. Specifically, our contributions are four-fold: (1) we develop three query strategies to obtain the most informative and representative positive samples for labeling; (2) we propose a light-weight model update strategy to efficiently derive more accurate anomaly scores and optimal decision threshold, solving the parameterization issue of unsupervised learning methods, and eventually contributing to the improved detection performance; (3) the proposed methods are systematically integrated into an unsupervised anomaly detection algorithm (Isolation Forest), clearly illustrating a feasible approach to introducing human operator's feedback into the closed-loop pipeline for improving its adaptability and performance; (4) a set of experiments with two different datasets are carried out for comparative studies with the state-of-the-art approaches, demonstrating the strong generalization capability of detecting various anomalies in different time series dataset.
The remainder of this paper is organized as follows. We firstly review the related work in Section 2 and introduce the unsupervised solution to time series anomaly detection problem in Section 3. Section 4 describes in detail our active learning solution with experimental results in Section 5. Section 6 finally concludes the paper.

Related Work
Supervised learning. Statistical models such as ARIMA [21] have been traditionally used to model the normal behaviors of time series by training on "clean" data. The deviation from the model forecast is then used as a measure of abnormality. However, directly thresholding this deviation is usually insufficient in real-world applications. Liu et al. [9] used statistical models for feature extraction and then a classifier such as Random Forest (RF) [2] to detect the anomalies. More recently, deep learning algorithms, such as LSTMs [12,11], have been introduced to work as feature extractors in supervised anomaly detection.
Unsupervised learning. There has been a growing interest in unsupervised methods for time series anomaly detection in order to overcome the lack of labeled data in real world scenarios. For example, Luminol [8], developed by LinkedIn, segments time-series into chunks and uses the frequency of similar chunks to calculate the anomaly scores. SPOT and DSPOT [16] use extreme value theory to model distribution tail in order to detect outliers in time series. Microsoft [13] uses spectral residual (SR) concept from signal processing to develop their SR-based anomaly detector. More recently, deep learning-based methods [12] have been also employed to detect anomalies in unsupervised settings. For example, DONUT [20] uses variational auto-encoder to detect anomalies from seasonal KPIs.
Active learning. There are two major active learning approaches for anomaly detection. The first approach, such as the one proposed in [5], usually solves a semi-supervised learning problem (SSAD) that uses both labeled and unlabeled points in its underlying formulation. When no labels are available, the models are first trained on unlabeled data in unsupervised settings. They are subsequently updated by incorporating labeled points from feedback into the learning problem. In [17], the authors used variants of SSAD model for benchmarking and found that there is no one-fit-all strategy for one-class active learning. Recently, Amazon developed NCAD based on deep semi-supervised learning [14] for time series anomaly detection [3].
The second approach to active anomaly detection is based on ensemble learning. The base learners are usually tree-based, such as Isolation Forest (iForest) [10], RS-Forest [19], or Robust Random Cut Forest (RRCF) [6]. They are firstly trained on unlabeled data and then be updated using labeled points from the feedback. The update can be in the form of adjusting the weights of trees [18], weights of trees' nodes [4] or trees' edges [15] in order to improve the performance of the base models on these labeled points.
For sample selection, the existing methods explored three strategies. Top anomalies implies the selection of points that have the maximum anomaly scores. Top diverse strategy, which is similar to the previous one, but requires the maximization of certain "diversity" measure in the group of selected points. Random strategy selects points randomly and is usually used as a baseline.

Unsupervised Anomaly Detection
Let X = (x 1 , x 2 , .., x n ) be a time series, which is a sequence indexed in time with x i ∈ R d . In this work, we focus on univariate time series data where d = 1. A time series anomaly detector usually takes X as input and outputs a sequence Y = (y 1 , y 2 , ..., y n ) of the same length, where y i = 1 if x i is anomalous or y i = 0 otherwise. An anomaly detection pipeline is usually composed of two main modules: feature extraction and anomaly detection model.

Features extraction.
A feature extractor projects the input sequence X = (x 1 , x 2 , .., x n ) into a feature space of dimension d f so that it becomes easier to distinguish anomalous points from normal ones. Each point x i ∈ X is then represented by a vector x i of size d f . In this work, we extract features in online mode and uses sliding windows of size w = 5. More specifically, for a given timestamp t, we calculate some measures from the window [x t−w , ..., x t−1 ] and subtract them from the current value x t . Among d f = 6 features used in this work and listed in Table 1, five of them are statistical features widely used in time series anomaly detection. The last one is the saliency map calculated from one-day-length subsequence [13]. Table 1. The 6 features used to represent each point in the feature space.

Feature Description max
Difference with maximum value on window of size w min Difference with minimum value on window of size w mean Difference with mean of window of size w naive Difference from the previous value linear residual Fit a linear model on a window of size w and compute the residual at the current point saliency map Spectral saliency at the current point Anomaly detection model. Similar to [4], we use iForest as the anomaly detection model because it is an unsupervised model being composed of trees and is much faster than RRCF. The initial iForest model is trained on the pool of unlabeled points. An ensemble of trees also facilitates the model update in active learning. Ensemble learning methods, especially the tree-based ones such as iForest, are well suited for active learning anomaly detection. This is because anomalies usually exhibit abnormal behaviors and their representations are mostly scattered in the feature space, which is in contrast to normal points whose representations form high density clusters. The separation boundaries between the representation of normal and abnormal points in the feature space are thus non-homogeneous, which can be well-represented by a properly trained iForest model. In addition, since iForest is widely used in outlier and anomaly detection, having a mechanism to enhance it using active learning would benefit the whole community.

Design assumptions
While there are different variants of active learning scenarios in the literature, our focus in this paper is on the pool-based active learning [7] only. Specifically, we assume that a (typically large) number of unlabeled data points, referred to as the unlabeled pool, is available and accessible to the learning process. An analyst or a domain expert is also available to provide a ground-truth label for any point in this pool upon request. The requests to domain expert are in "batch", consisting of all "interesting" points within the given budget. Figure 1 illustrates the active learning process that has three main components, (1) start with a fully unsupervised model; (2) select points according to the given budget and query strategy; (3) update the model based on domain expert's feedback. This process can be iterative, either upon a request, or is automatically triggered when the model performance gets worse than a certain threshold.
Our active learning pipeline is essentially inspired from [4] and [18]. They both use tree-based ensemble unsupervised models as the anomaly detectors. Wang et al. [18] handles the ensemble at the tree level, and the model update focuses on adjusting the weights of trees in the ensemble. Das et al. [4], on the other hand, works at the nodes of constituting trees and updates the model by adjusting node weights. These two approaches, however, have high complexity.
-Das et al. [4] uses iForest as the base model, which is relatively fast. However, its model updating process is computationally expensive since node-level features and scores for each point need to be computed, either in training or inference. In addition, it solves an underlying optimization problem in order to find the best node weights (NW), which can be too expensive for a model with a high number of nodes. -Wang et al. [18] employs a very fast and straightforward model update strategy which consists of adjusting tree weights according to the scores of anomalous points. It, however, uses a slightly modified version of RRCF as the base model. It's well known that RRCF is slow since it is designed for streaming context and the model auto-adjusts for each incoming stream value in order to adapt to the new data distribution.
In order to build a very fast and easy-to-deploy anomaly detector with active learning, we propose an active learning pipeline using iForest as the base model. iForest model is updated by adjusting the weights of its constituting and by seeking the best value for its "offset" parameter. The remaining of this section will describe in details different query and model update strategies we adopt in this work.

Query strategy
There exists a number of query methods in the literature, and they usually follow a common formulation. Given U the set of unlabeled points, b the given budget, and an interest function f : U → R used as a measure of "informativeness" or "utility" of requesting the label for each point x ∈ U, a query strategy aims at selecting The choice of a query strategy thus usually reduces to the choice of an interest function f . In this work, we use three query strategies for our active learning pipeline. Algorithm 1 presents how points are selected according to U, b, and f .
Set Q ← Q ∪ {x} end while return Q -Top anomalous selection (TA) (Figure 2(a)): Also called "greedy strategy" in the context of anomaly detection, it selects points that have the highest anomaly scores. Let UAD(x) be the anomaly score of x, the interest function corresponding is defined as f (x) = UAD(x). -Close to decision boundary selection (CTDB) (Figure 2(b)): Points that are the closest to the decision boundary of the anomaly detector are selected. The region near the decision boundary is expected to contain the most difficult points to classify. Mathematically, if we denote δ the threshold used to classify points, the interest function is defined as f (x) = −(UAD(x) − δ) 2 . -TA + CTDB (Figure 2 (c)): This is a combination of the two above strategies by using half of the budget for TA and the other half for CTDB. This combination gives more diversity in the selected samples and is expected to better update the unsupervised model.

Model update strategy
For model update, we rely on the anomaly scores obtained by the iForest model. After querying a set of points for their labels, the unsupervised iForest model can be updated using one of the following strategies: -Tree weights update (TW): iForest is a tree-based model and, in the original formulation of its scoring function, its trees contribute equally to the calculation of anomaly score for each input point. We adopt the strategy proposed in [18] to adjust the contributions or weights of iForest trees so that if a tree turns out to be more accurate in its anomaly scoring of anomalous queried points, it contributes more to the calculation of anomaly score. -Offset update (O): iForest has a critical hyperparameter called contamination ratio. It is used during training to determine, thanks to the percentile metric, the offset value, which will be used in inference to classify points as anomalous or nominal by thresholding their anomaly scores. In practice, this ratio is usually guessed based on application context, and it usually turns out to be very difficult to set it properly. We propose to "learn" this offset value based on the feedback for queried points. Finding the best offset from feedback can be done in various ways, such as a simple rule-based thresholding or training a classifier and then using its decision boundary as the learned offset. We have tested and found that the rule-based thresholding has performed better than a linear SVM. Algorithm 2 presents the procedure to calculate offset value from feedback. Intuition behind the two-step model update strategy: Figure 3 illustrates the impact of the above-stated model update strategies on the score distribution and offset of an iForest model. At the beginning, the score distributions of nominal and anomalous points produced by the unsupervised iForest model have a "large" overlap and the offset value is not properly set to "well" separate these two distributions (Figure 3(a)). By updating the weights of iForest trees, these two distributions are pushed further away from each other, causing anomalous and nominal samples to have higher and lower scores, respectively (Figure 3(b)). It should be noted that updating the weights of iForest trees has no impact on the offset of the iForest model. This offset value is further adjusted using Algorithm 2 so that it can better separate the two score distributions and, consequently, the adjusted iForest model can better distinguish anomalous points from nominal ones (Figure 3(c)). Experimental evidence for the impact of each model updating strategy is given in Section 5.3.

Experimental settings
Datasets: Our evaluation experiments are conducted on two datasets. The first one (AIOps) is public and is commonly used for performance evaluation of univariate time series anomaly detection algorithms. It is released by the AIOps2018 competition 3 and consists of 29 KPIs collected from some internet companies in China. In our experiments, we use the training and testing data from the Final subset of this dataset The second dataset (Huawei) is private and collected from Huawei production environment. It is composed of 8 univariate telecom core network KPIs from different network elements. Each KPI is split into two halves, the first for training and the second for testing. These two datasets contain KPIs with a wide range of time series characteristics and anomalous patterns. Anomalous points and segments are labeled by domain experts and annotated as positive points, whereas nominal ones are designated as negative a) b) c) d) Fig. 4. Some KPIs from AIOps ((a) and (b)) and Huawei ((c) and (d)) datasets. Anomalous points are marked using red color. points. Some KPIs from these two datasets are shown in Figure 4. Table 2 summarizes some statistics of the two datasets.
Metrics: For performance evaluation and comparison purpose, we adopt the evaluation protocol suggested by [22] and commonly used by the community. In this protocol, the F1-score is not calculated directly based on point-wise matching between the labels and detection results. A delay parameter k is introduced to adjust the detection results before F1-score calculation. According to human experts and for a contiguous anomaly segment, it is acceptable if the algorithm can detect and trigger an alert within a delay of k points. More precisely, we mark a segment of continuous anomalies as correctly detected if a point from this segment that is within k points from the segment's beginning is detected. In our experiments, the delay for both AIOps and Huawei datasets is k = 7, as recommended by the AIOps competition and used in other works.

Supervised and unsupervised anomaly detection
To demonstrate the effectiveness of our anomaly detection pipeline, we compare it with several SoTA anomaly detection methods in Table 3. In addition to Isolation Forest (iForest), we also use Random Forest (RF) and run our pipeline presented in Section 3 in a supervised setting in order to establish the performance upper bound when all points are labeled in our active anomaly detection (i.e., query budget = 100%). RF is selected because it is also a tree-based ensemble model. It can be seen that our best RF and iForest models achieve the best results among all supervised (sup.) and unsupervised (un.) methods, respectively. Thus, with a relatively simple and right set of features, combined with the right parameterization of popular supervised and unsupervised models, we can achieve the SoTA performance on benchmark datasets. This observation is valuable in a practical viewpoint, in which simple and explainable features and models are usually preferable over more complex ones. Also, the performance of iForest drops significantly when it uses, for example, an inappropriate value for its Table 3. Performance comparison with SoTA methods. Random Forest and iForest models are trained with features in Table 1. For iForest, the value in bracket is the contamination ratio: 0.01 (usually recommended), 0.03, and 0.007 (best value found by grid search on training data).

Model
Type contamination parameter, among others. We assume that this type of performance degradation due to parameterization also applies to all other methods. This issue, however, can be handled by active learning, as will be shown in the next section.
It should be noted that NCAD [3] does not strictly follow the adopted evaluation protocol. It uses a more relaxed one without a delay restriction, which is thus equivalent to the adopted protocol with k = ∞. SR-CNN is a semisupervised model that requires 65 million anomaly-free simulated points to train its CNN model for saliency map thresholding [13]. Finally, the gap in performance between RF and a "perfect" model can be explained partially by the lack of coherence in dataset labeling and by the limited representative and expressive power of the feature set and model.

Active anomaly detection
We evaluate our active anomaly detection pipeline on the two benchmark datasets and provide the results in Table 5.3. We are able to compare our approach with [4] using its open source implementation 4 . Since the implementation of [18] is not open, we've implemented it using an open source implementation of RRCF [1]. Our implementation turns out to be too slow due to the high complexity of RRCF. We couldn't obtain experimental results in a reasonable amount of time, and thus decided to not compare our method with [18] here.
In all experiments, iForest (0.03) presented in Section 5.2 is used as the baseline unsupervised model. Each value in Table 5.3 represents the F1-score obtained by using a unique combination of query strategy, model update strategy, and query budget. It can be seen that, even starting with a weak unsupervised model and using only 1% query budget, our active learning pipeline improves the performance by 56.51%, reaching 80.29% F1-score for AIOps dataset. Similarly, for Huawei dataset, the performance is improved by 75.14% and reaches 71.37% F1-score. This performance is better than the performance achieved by [4] and iForest (best) and is very close to the performance of RF (best) shown in Table  3. This clearly demonstrates the effectiveness of our active learning pipeline. Among query strategies, greedy selection (TA) outperforms random and CTDB. The random strategy does not really improve the performance. This is similar to the observations reported in previous works [4,18] and demonstrates the necessity of a good query strategy in an active learning pipeline. Among model update strategies, TW has almost no impact, regardless the amount of query budget. O and TW+O lead to the best improvement for AIOps and Huawei datasets, respectively. This demonstrates the importance of our proposed offset update (O) strategy. Finally, using our active learning approach, the required query budget to reach the best improvement is small compared to [4]. Our approach needs about 1% whereas [4] needs 25 − 50% of the training data.
In terms of computational complexity, our approach is about 14× and 6× faster than [4] on AIOps and Huawei datasets. This confirms the utility of our simple model update strategies, compared to the more complex ones used in [4].

Concluding Remarks
This paper proposed an efficient active learning based approach to systematically integrating the feedback and expert knowledge of network operators into unsupervised anomaly detection pipeline. In particular, we proposed three effective query strategies to assist operator in labeling those KPI samples that lead to alarms, including both true and false ones. A lightweight model update algorithm, which consists of updating the weights of trees and the adjustment of decision threshold in Isolation Forest model, has been also developed to improve the performance and efficiency. The experiments with two datasets have validated the performance advantages over baseline Isolation Forest and existing active learning based method in terms of detection performance and computational efficiency. Despite the claimed advantages, we believe sample query strategy and model update algorithm, as well as their integration with other unsupervised anomaly detection algorithms (e.g., RRCF), still have room to be further improved.