Abstract
This paper describes a methodology for detecting anomalies from sequentially observed and potentially noisy data. The proposed approach consists of two main elements: (1) filtering, or assigning a belief or likelihood to each successive measurement based upon our ability to predict it from previous noisy observations, and (2) hedging, or flagging potential anomalies by comparing the current belief against a time-varying and data-adaptive threshold. The threshold is adjusted based on the available feedback from an end user. Our algorithms, which combine universal prediction with recent work on online convex programming, do not require computing posterior distributions given all current observations and involve simple primal-dual parameter updates. At the heart of the proposed approach lie exponential-family models which can be used in a wide variety of contexts and applications, and which yield methods that achieve sublinear per-round regret against both static and slowly varying product distributions with marginals drawn from the same exponential family. Moreover, the regret against static distributions coincides with the minimax value of the corresponding online strongly convex game. We also prove bounds on the number of mistakes made during the hedging step relative to the best offline choice of the threshold with access to all estimated beliefs and feedback signals. We validate the theory on synthetic data drawn from a time-varying distribution over binary vectors of high dimensionality, as well as on the Enron email dataset.
Introduction
Detecting anomalies in sequential data streams—such as network traffic, sensor readings, or email logs—is a fundamental challenge in modern data science. Real-world data is rarely independent and identically distributed (i.i.d.); instead, underlying generative processes evolve over time or may be subject to adversarial manipulation. Furthermore, observations are frequently corrupted by noise, complicating the distinction between true anomalies and measurement errors.
A standard approach involves assigning a "likelihood" to each new observation and flagging it as an anomaly if it falls below a threshold. However, static thresholds often lead to excessive false alarms. While human feedback can refine these thresholds, labeling every data point is prohibitively expensive. This paper introduces FHTAGN (Filtering and Hedging for Time-varying Anomaly recoGNition), a framework that dynamically learns both the underlying data distribution and an optimal anomaly threshold using noisy data and limited human feedback.
Methodology: Filtering and Hedging
The FHTAGN framework decomposes the anomaly detection problem into two sequential steps, both formulated as Online Convex Programming (OCP) problems.
1. Filtering (Belief Assignment)
The algorithm sequentially assigns a probability density to the next "clean" system state based on past noisy observations. By modeling data using exponential families and employing an unbiased estimator of the sufficient statistic, the system performs gradient descent on the log-loss without requiring access to clean data.
2. Hedging (Dynamic Thresholding)
Instead of a fixed threshold, FHTAGN utilizes a time-varying threshold updated via projected subgradient descent. The threshold is only adjusted when the system receives ground-truth feedback following a mistake. Both steps are solved using Mirror Descent, a generic strategy for OCP that provides strong theoretical guarantees.
To minimize human effort, the hedging step supports two limited-feedback regimes:
- Label-efficient (Forecaster-driven): The algorithm requests a label only when it is uncertain, based on the proximity of the current likelihood to the threshold.
- Arbitrary feedback: The system adapts to feedback provided at random intervals by the user.
Experimental Results
The authors validated FHTAGN on both synthetic and real-world datasets:
- Synthetic Data: A 500-dimensional temporally-evolving Bernoulli product density corrupted by 10% noise. FHTAGN outperformed the best static threshold chosen in hindsight, committing only 30 total errors compared to 44 for the baseline.
- Enron Email Dataset: Analyzing communication patterns over 902 days, FHTAGN reduced errors from 143 (static baseline) to 73. Remarkably, it achieved this while requesting human feedback only ~10% of the time. The detected anomalies aligned with major historical events, such as the California energy crisis and Enron's financial collapse.
Key Insights and Conclusion
The core innovation of FHTAGN is its unified OCP framework. By casting statistical filtering and threshold hedging as OCP games, the system avoids complex posterior distribution computations, requiring only the current observation and previous state for updates. Furthermore, noise resilience is built-in; as long as an unbiased estimator of the sufficient statistic exists, the framework converges as if learning from clean data.
The primary limitation is the computational cost of the log partition function for complex exponential families. Future work will explore "pseudo-likelihoods" to extend this approach to high-dimensional, complex distributions where exact computation is intractable.
Summary updated