Source-linked AI summary
Unsupervised Anomaly Detection via Variational Auto-Encoder for Seasonal KPIs in Web Applications
Haowen Xu, Wenxiao Chen, Nengwen Zhao, Zeyan Li, Jiahao Bu, Zhihan Li, Ying Liu, Youjian Zhao, Dan Pei, Yang Feng, Jie Chen, Zhaogang Wang, Honglin Qiao
TL;DR
Seasonal KPI anomaly detection is difficult because patterns and data quality vary while labels are scarce. The paper proposes Donut, an unsupervised VAE-based detector with specialized training and detection techniques, and reports best F-scores of 0.75 to 0.90 while providing a KDE interpretation of reconstruction.
Problem
Seasonal KPI anomaly detection must handle varied patterns and data quality with incomplete labels, while existing methods suffer from tuning, label dependence, performance, or theoretical limitations.
Method
Donut is an unsupervised VAE-based anomaly detector using Modified ELBO and Missing Data Injection during training and MCMC Imputation during detection.
Results
Donut’s best F-scores range from 0.75 to 0.90 for the studied KPIs and outperform state-of-the-art supervised and VAE-based anomaly detection algorithms.
Takeaways & Limitations
A KDE interpretation of reconstruction and the time-gradient analysis provide a theoretical explanation for Donut’s performance on seasonal KPIs.
Takeaways & Limitations
Choosing the latent dimension K is difficult in the totally unsupervised scenario and is left for future work.
Abstract
from arXiv · showhide
To ensure undisrupted business, large Internet companies need to closely monitor various KPIs (e.g., Page Views, number of online users, and number of orders) of its Web applications, to accurately detect anomalies and trigger timely troubleshooting/mitigation. However, anomaly detection for these seasonal KPIs with various patterns and data quality has been a great challenge, especially without labels. In this paper, we proposed Donut, an unsupervised anomaly detection algorithm based on VAE. Thanks to a few of our key techniques, Donut greatly outperforms a state-of-arts supervised ensemble approach and a baseline VAE approach, and its best F-scores range from 0.75 to 0.9 for the studied KPIs from a top global Internet company. We come up with a novel KDE interpretation of reconstruction for Donut, making it the first VAE-based anomaly detection algorithm with solid theoretical explanation.
1 INTRODUCTION
Monitoring seasonal Web-application KPIs is important for timely anomaly response, but varied patterns, data quality, and sparse labels make detection difficult. Donut addresses this gap with an unsupervised VAE-based method and reports strong performance with three specialized techniques.
- Seasonal KPIs such as Page Views, online users, and orders require anomaly detection to support timely troubleshooting and mitigation.
- Seasonal patterns arise from user behavior and schedules, while anomaly detection remains challenging across varied patterns and data quality without labels.
- Existing methods involve algorithm selection and parameter tuning, rely heavily on labels, perform unsatisfactorily, or lack theoretical foundations.
- Donut is an unsupervised anomaly detector based on a Variational Auto-Encoder that can operate without labels and use occasional labels when available.
- The Modified ELBO, Missing Data Injection, and MCMC Imputation techniques enable Donut to outperform supervised and VAE-based alternatives.
- Donut’s best F-scores range from 0.75 to 0.9 on the studied KPIs from a top global Internet company.
2 BACKGROUND AND PROBLEM
The paper studies seasonal KPIs with local variations, noise, anomalies, and incomplete labels, motivating an unsupervised deep-generative approach. It positions VAE as the starting point for a theoretically grounded detector that can use occasional labels.
- 2.1 Context and Anomaly Detection in General: Seasonal KPIs repeat at regular intervals but vary in shape across cycles because user behavior differs across days.
- 2.1 Context and Anomaly Detection in General: Anomalies are recorded points that violate normal patterns, whereas abnormal data include both anomalies and missing points.
- 2.1 Context and Anomaly Detection in General: Occasional anomaly labels are far too incomplete for typical supervised learning algorithms.
- 2.2 Previous Work: Supervised ensembles reduce detector-selection effort but depend on good labels and incur computational cost from running multiple traditional detectors.
- 2.2 Previous Work: Unsupervised methods learn normal regions in original or latent spaces and score observations by their distance from those regions.
- 2.2 Previous Work: Existing VAE-based detection was not designed for time series, performed poorly in the paper’s settings, and lacked theoretical support for its designs.
- 2.3 Problem Statement: The paper seeks an unsupervised deep-generative detector with solid theoretical explanation that can exploit occasionally available labels.
- 2.4 Background of Variational Auto-Encoder: A VAE models latent z and visible x, using a prior for z, a neural-network conditional distribution pθ(x|z), and an approximating posterior qϕ(z|x).
3 ARCHITECTURE
Donut combines a simple VAE architecture with modified training objectives and MCMC-based imputation to detect anomalies in seasonal KPI windows. Its design targets robust reconstruction of normal points despite anomalies and missing values.
- Architecture: Donut combines Modified ELBO and Missing Data Injection during training with MCMC Imputation during detection.
- Architecture: Sliding windows of length W convert KPI sequences into VAE input vectors because the VAE is not sequential.
- Architecture: Soft-plus layers plus ϵ keep Gaussian standard deviations positive and avoid numerical problems when local KPI variations are very small.
- Training: The re-parameterization trick rewrites z as z(ξ) = µ_z + ξ · σ_z, with one sample used for ELBO computation during training.
- Training: Modified ELBO excludes labeled anomalies and missing points from reconstruction contributions while scaling the prior contribution by the ratio of normal points.
- Training: Missing data injection randomly zeros normal points before each epoch, strengthening training to reconstruct normal values from abnormal windows.
4 EVALUATION
Donut is evaluated on three labeled KPI datasets using point-wise and segment-aware metrics, against supervised and VAE baselines. It achieves strong unsupervised performance while maintaining acceptable alert delays, with M-ELBO providing most of the improvement and K remaining an important tuning parameter.
- 4.1 Datasets: 18 business KPIs were collected at one-minute intervals, with datasets A, B, and C split into training, validation, and testing sets at 49%, 21%, and 30%.Operators labeled all anomalies in the three evaluation datasets, providing ground truth for evaluation.
- 4.2 Performance Metrics: Best F-score evaluates the best threshold-specific harmonic mean of precision and recall, while AUC summarizes performance across thresholds.The evaluation also reports average alert delay at the threshold yielding the best F-score.
- 4.2 Performance Metrics: 0.6 precision and 0.5 recall illustrate the modified segment-aware metric, which counts an anomaly segment as detected when any point crosses the threshold.The example uses a threshold of 0.5 and reports a one-minute alert delay for the first segment.
- 4.4 Overall Performance: Donut achieves best F-scores from 0.75 to 0.9 without labels and outperforms supervised Opprentice in all evaluated cases.With incomplete labels, Opprentice declines heavily on datasets A and B; labels generally improve Donut, although some 100% label results are slightly worse than 10%.
- 4.4 Overall Performance: Donut outperforms the VAE baseline by a large margin on datasets A and B, with the relative advantage largest on A, medium on B, and smallest on C.The paper attributes this pattern to differences in KPI smoothness and Donut’s handling of abnormal points within sliding windows.
- 4.5 Effects of Donut Techniques: M-ELBO contributes most of the improvement over the VAE baseline, while missing-data injection may require more training epochs and MCMC never harms performance.The authors recommend using all three techniques, while noting that choosing K remains difficult without a fully unsupervised selection method.
5 ANALYSIS
Donut interprets reconstruction through KDE: posterior samples identify a normal pattern, and likelihood kernels estimate how well the input follows it. Its training and detection techniques improve posterior quality, while anomaly density and latent-space optimization remain important limits.
- 5.1 KDE Interpretation: The reconstruction probability lacks a well-defined probabilistic interpretation, motivating Donut’s KDE interpretation for the reconstruction probability and algorithm.The posterior-weighted integral of pθ(x|z) is not itself a well-defined probability density.
- 5.3 Causes of Time Gradient: The time-gradient effect arises because contiguous, similarly shaped KPI windows map to nearby posterior distributions with small variance.The effect reflects transitions in window shape rather than explicit time information, since Donut consumes only the shape of x.
- 5.1 KDE Interpretation: Each posterior sample z supplies a kernel density estimator, whose likelihood indicates how well x follows the corresponding normal pattern.The posterior expectation aggregates these kernel scores for density estimation.
- 5.1 KDE Interpretation: Sampling from the prior may mix kernels for different patterns, potentially confusing density estimation for a particular x.The KDE interpretation therefore motivates posterior-conditioned sampling rather than prior sampling.
- 5.2 Find Good Posteriors for Abnormal x: M-ELBO trains Donut to reconstruct normal points within abnormal windows, missing-data injection amplifies this training effect, and MCMC iteratively improves detection posteriors.M-ELBO changes training, whereas MCMC improves detection by approaching better posteriors.
- 5.2 Find Good Posteriors for Abnormal x: Donut may still fail to find a good posterior when a testing window contains too many anomalies.For long-lasting anomalies, the paper states that correct scores in the first few minutes can be sufficient operationally.
- 5.3 Causes of Time Gradient: The three ELBO terms separate dissimilar shapes, constrain posterior distributions toward N(0, I), and expand posterior entropy within that restricted area.The reconstruction, prior, and entropy terms jointly shape the latent-space arrangement.
- 5.4 Sub-Optimal Equilibrium: Latent distributions can converge to a sub-optimal equilibrium that breaks the time gradient and downgrades detection performance.The paper describes overfitting after latent groups separate incorrectly, causing some testing windows to be recognized as another pattern.
6 DISCUSSION
Donut’s reconstruction is central to its anomaly-detection design, and its KDE interpretation may extend to other deep generative models. The discussion identifies broader sequence-similarity applications, while leaving latent-dimension selection and threshold choice unresolved.
- 6.1 Broader Implications: Dimension reduction can discard abnormal-point information, making reconstruction essential for Donut and potentially relevant to other dimension-reduction detectors.The paper specifically suggests reconstructed samples could reduce sensitivity to the number of principal components in PCA-based detection.
- 6.1 Broader Implications: KDE interpretation is the heart of Donut and may benefit other deep generative anomaly-detection models.M-ELBO, missing-data injection, and MCMC are described as applicable to other deep generative models because they improve posterior finding.
- 6.1 Broader Implications: The time-gradient effect may extend to other seasonal or periodical sequences whose similar windows map to neighboring posterior distributions.The paper suggests possible use beyond anomaly detection, including retrieving similar curves from a large database.
- 6.2 Future Work: Choosing the latent dimension K remains future work because its value affects under-fitting, posterior quality, and sub-optimal equilibria.The paper suspects larger K may reduce sub-optimal equilibria but states that more experiments and analysis are needed.
- 6.2 Future Work: The paper does not discuss how to choose the detection threshold, which remains difficult in the unsupervised scenario.Existing threshold-selection work may be applicable to Donut.
- 6.2 Future Work: A sequence-to-sequence RNN architecture could replace Donut’s fully connected layers to handle larger windows and cross-point correlations.This is presented as a possible extension rather than an evaluated result.
7 CONCLUSION
Donut is an unsupervised VAE-based detector for seasonal KPIs with local variations, achieving strong performance on studied KPIs. Its performance is supported by KDE-based theoretical analysis and the discovery of the time gradient effect.
- Donut’s best F-scores range from 0.75 to 0.90 for the studied KPIs.
- New techniques enable Donut to greatly outperform state-of-the-art supervised and VAE-based anomaly detection algorithms.
- KDE interpretation and the time gradient effect provide theoretical explanations for Donut’s performance.