Abstract
Most existing approaches to anomaly detection focus on statistical features of the data. However, in many cases, users are merely interested in a subset of the statistical outliers depending on the specific domain of interest, e.g., network attacks or financial fraud. The instruction from human experts is therefore indispensable in building predictive models in such applications. However, obtaining labels from human experts is time-consuming and expensive. Obtaining labels from nonexpert labelers are relatively easy and cost-effective. However, the labeling accuracy of a nonexpert is usually difficult to assess. Therefore, it remains open to leverage both the machine intelligence and the knowledge from labelers with diverse backgrounds to construct a machine learning model for domain-specific anomaly detection. To this end, this paper proposes a framework of tripartite active learning for interactive anomaly discovery in large datasets based on crowdsourced labels. This tripartite active learning method consists of two stages. In the first stage, an unsupervised learning algorithm is employed to extract statistical outliers from the dataset. We then develop an iterative algorithm consisting of two steps. The algorithm first evaluates and trains labelers based on gold instances provided by the expert labelers. Then, it assigns the most informative samples to its most confident labeler for relabeling and update the detector based on new labels.
Introduction
Standard anomaly detection algorithms excel at identifying statistical outliers—data points that deviate significantly from the norm. However, in practical applications like network security or financial fraud detection, not all statistical outliers are relevant. A sudden spike in network traffic might be a routine backup rather than a malicious intrusion. To bridge the gap between statistical significance and domain relevance, human expertise is required.
The challenge lies in the cost of expertise. High-level analysts are expensive and cannot be expected to label massive datasets. Crowdsourcing offers a cheaper alternative, but non-expert labels are often noisy and unreliable. This paper introduces TALC (Tripartite Active Learning from Crowds), a framework designed to integrate machine intelligence, expert knowledge, and crowdsourced labor to build accurate, domain-specific detectors efficiently.
The TALC Framework
The proposed system operates in two distinct stages to optimize both computational resources and human effort.
Stage I: Unsupervised Outlier Extraction
In the first stage, the system uses a Label Propagation with Random Sampling (LPRS) algorithm. This unsupervised step is designed to handle large datasets by identifying "medoid" instances—representative normal points—and filtering out the majority of the data. This reduces the search space to a manageable pool of potential anomalies, ensuring that human labelers only focus on the most suspicious candidates.
Stage II: The Tripartite Active Learning Loop
The core of the innovation is the interaction between three parties: the Machine, the Expert, and the Non-expert (Crowd).
- Evaluation and Training: Non-experts are not treated as static oracles. Instead, they are evaluated and trained using "gold instances"—samples previously labeled and explained by experts. When a non-expert mislabels a gold instance, the system provides the correct answer and the expert's reasoning, allowing the crowd to learn and improve over time.
- Informed Task Assignment: The machine identifies samples with the highest uncertainty. It then matches these samples to the most confident labeler based on their historical performance on similar gold instances.
- Optimization: To ensure robustness and prevent labeler fatigue, task assignment is formulated as a Linear Integer Programming problem, which the authors efficiently solve by mapping it to a Minimum Cost Network Flow problem.
Experimental Results
The TALC framework was evaluated across several diverse datasets, including medical data (Annthyroid), rare speech patterns (Speech), and network intrusion data (HTTP/KDD Cup 99).
Key findings include:
- Efficiency: TALC achieved the performance of an "ideal" detector (trained on perfectly labeled data) while requiring up to 90% fewer labels on datasets like
httpandannthyroid. - Convergence: The system typically reached peak performance within 12 iterations, demonstrating rapid learning.
- Robustness: By training labelers and using capacity constraints, TALC consistently outperformed baseline active learning methods that do not account for labeler noise or learning.
Conclusion
TALC represents a significant step forward in interactive anomaly detection. By leveraging a small set of expert-verified "gold instances" to filter and train a larger pool of non-expert labelers, the system provides a cost-effective way to build high-performance, domain-specific models. This tripartite approach ensures that machine intelligence is guided by human insight without the prohibitive costs usually associated with expert-led labeling.
Summary updated