Source-linked AI summary
Toward Supervised Anomaly Detection
Nico Goernitz, Marius Micha Kloft, Konrad Rieck, Ulf Brefeld
TL;DR
Anomaly detection needs labeled guidance without losing its unsupervised focus because supervised-derived methods can miss novel anomalies. The paper develops SSAD with convex optimization properties and active labeling, then reports stronger accuracy using limited labels in network intrusion detection.
Problem
Novel anomaly classes and differing training and test distributions make supervised-derived semi-supervised methods inappropriate for detecting previously unseen anomalies.
Method
The paper develops SSAD from the unsupervised paradigm, incorporates labeled data, provides a convex equivalent under mild assumptions, and adds active learning for labeling.
Results
SSAD achieves higher detection accuracy than baseline approaches in network intrusion detection while requiring only a handful of labeled instances to boost performance.
Takeaways & Limitations
The methodology is robust when baseline performance deteriorates due to obfuscation techniques and can exploit limited labeled data in costly labeling settings.
Takeaways & Limitations
The convex model has an intuitive interpretation only for normalized kernels.
Abstract
from arXiv · showhide
Anomaly detection is being regarded as an unsupervised learning task as anomalies stem from adversarial or unlikely events with unknown distributions. However, the predictive performance of purely unsupervised anomaly detection often fails to match the required detection rates in many tasks and there exists a need for labeled data to guide the model generation. Our first contribution shows that classical semi-supervised approaches, originating from a supervised classifier, are inappropriate and hardly detect new and unknown anomalies. We argue that semi-supervised anomaly detection needs to ground on the unsupervised learning paradigm and devise a novel algorithm that meets this requirement. Although being intrinsically non-convex, we further show that the optimization problem has a convex equivalent under relatively mild assumptions. Additionally, we propose an active learning strategy to automatically filter candidates for labeling. In an empirical study on network intrusion detection data, we observe that the proposed learning methodology requires much less labeled data than the state-of-the-art, while achieving higher detection accuracies.
1. Introduction
The paper argues that anomaly detection must accommodate labeled guidance while remaining grounded in unsupervised data characterization, because novel anomalies can arise from changed test distributions. It proposes SSAD and evaluates this distinction through controlled experiments and a broader methodology.
- Anomaly detection models normal data, scores deviations from that model, and flags instances exceeding a predefined threshold.
- Network intrusion detection needs anomaly detection because signature-based techniques protect against known attacks but fail on novel threats.
- Novel anomaly classes and differing training and test distributions make supervised-derived semi-supervised methods likely to miss previously unseen anomalies.
- In a controlled experiment, supervised and semi-supervised methods excelled when training and test distributions matched but became fragile when novel anomaly clusters appeared at test time.
- SSAD is derived from the unsupervised paradigm, incorporates labeled data, extends SVDD, and has a convex equivalent under relatively mild assumptions.
- The paper additionally proposes an active learning strategy to guide labeling and evaluates the methodology on real-world network intrusion scenarios.
2. Related Work
Related work spans supervised, unsupervised, and semi-supervised approaches, but many methods assume shared training and test distributions or incur difficult optimization problems. The paper extends this literature with a broader, mathematically grounded SSAD framework and expanded empirical comparisons.
- Semi-supervised learning provides a framework for learning from partially labeled data, often using a cluster assumption about nearby points and shared labels.
- Fully supervised anomaly detection methods commonly ignore unlabeled data while learning classifiers that separate innocuous data from attacks.
- SVDD learns a hypersphere enclosing most data, treating points outside it as anomalous, whereas one-class SVM separates data from the origin with a maximum-margin hyperplane.
- Existing unsupervised-derived semi-supervised methods include approaches with false-positive control, graph regularization, and SVDDneg, but some require test instances during training or face non-convex optimization.
- Many related methods assume training and test sets are drawn from the same distribution.
- This article extends prior work with a mathematically sound framework, arbitrary convex loss functions, dual representations, and comparisons against more baseline approaches.
3. Semi-supervised Anomaly Detection
The paper extends the unsupervised SVDD paradigm to incorporate labeled nominal and anomalous examples, then reformulates the resulting method for optimization. Under unit-norm feature representations, the intrinsically non-convex problem has an equivalent convex formulation with strong duality.
- Problem and model: Anomaly detection models normal data with a concise description so that deviating observations receive high anomaly scores.The SVDD represents normality with a hypersphere and scores instances by their distance from its center.
- Semi-supervised formulation: The proposed semi-supervised method generalizes SVDD by processing unlabeled examples together with labeled nominal and anomalous observations.Nominal labeled examples are required inside the hypersphere, whereas anomalies are encouraged to lie outside it.
- Semi-supervised formulation: Including negatively labeled data makes the direct optimization problem non-convex, so the paper instead uses a primal unconstrained formulation with explicit loss functions.The hinge loss recovers the original formulation, while smooth losses support differentiable optimization methods.
- Convex formulation: Under unit-norm feature representations, the non-convex optimization problem can be converted into an equivalent convex problem using Lagrangian duality and Fenchel-Legendre conjugates.The assumption is satisfied by kernels such as RBF kernels, and the derivation applies to convex loss functions.
- Convex formulation: Strong duality holds for the primal and dual optimization problems, although the convex model has an intuitive interpretation only for normalized kernels.For wider kernel classes, the paper resorts to the more general non-convex formulation.
4. Active Learning for Semi-supervised Anomaly Detection
The paper uses active learning to select informative anomaly-detection examples for expert labeling and repeatedly retrains the semi-supervised model. Its combined strategy balances boundary uncertainty with exploration of potentially anomalous, rarely labeled regions.
- Motivation and procedure: Active learning selects unlabeled instances whose labels are expected to produce the largest improvement in a retrained model.The strategy addresses settings where domain experts can label only a small fraction of very large training sets.
- Motivation and procedure: The method alternates between selecting candidates, obtaining expert labels, augmenting the training set, and retraining until the required performance is reached.Several points may be queried before each model update in practical implementations.
- Active learning strategies: The margin strategy queries points closest to the decision hypersphere, focusing on low-confidence borderline decisions.This is the anomaly-detection analogue of the supervised support vector machine margin strategy.
- Active learning strategies: The cluster strategy explores unknown feature-space regions by querying points in rarely labeled areas using an adjacency structure such as a k-nearest-neighbor graph.It is intended to identify novel anomaly classes in non-stationary outlier settings.
- Active learning strategies: The combined strategy queries points near the hypersphere boundary that also lie in potentially anomalous clusters, avoiding the limitations of either strategy alone.With no labeled points, the combined strategy reduces to the margin strategy.
5. Illustration of Proposed Learning Paradigm
Controlled experiments show that supervised-derived methods struggle with previously unseen anomaly clusters, whereas unsupervised-derived semi-supervised methods incorporate labels effectively and achieve stronger performance.
- Controlled experiment: Supervised-derived SVM and LDS methods perform poorly when test data contains novel outlier clusters, remaining below unsupervised SVDD across labeling ratios.The experiment compares these methods with SVDD, SVDDneg, and SSAD under differing labeled-to-unlabeled ratios.
- Solution geometry: With 25% labeled data, SSAD achieves perfect separation in the semi-supervised scenario, while the unsupervised solution mistakenly treats outliers as normal.
- Execution time: SSAD, SVDDneg, and SVDD have similar execution-time behavior, while SVM is fastest because it ignores unlabeled examples and LDS performs worst.
- Conclusion: The experiments conclude that unsupervised-derived semi-supervised methods outperform competitors by incorporating label information without relying on the supervised learning paradigm.
6. Real-World Network Intrusion Detection
The intrusion-detection evaluation uses sparse n-gram representations of real and cloaked HTTP attacks. SSAD improves detection over baselines, while active learning substantially reduces the labeling required for near-perfect separation.
- Representation: 3-grams map HTTP payloads into a sparse vector space, enabling representation of novel attack patterns without defining relevant strings in advance.The implicit feature set contains all possible strings of length n, while sparsity limits the nonzero features in each payload.
- Data: 145,069 normal HTTP connections and 27 Metasploit attack classes form the experimental data, including buffer overflows, code injections, tunnels, and cross-site scripting.
- Detection performance: For regular attacks, all methods detect malicious traffic equally well, with no significant difference between classifiers.
- Detection performance: 70% AUC is reached by unsupervised SVDD on cloaked attacks, while SSAD almost perfectly separates normal and cloaked traffic with 15% randomly labeled data.SVDDneg gains about 5% from incorporating cloaked attack information, whereas SSAD uses all labeled data and outperforms both baselines.
- Active learning: 3% labeled data is sufficient for SSAD to attain almost perfect separation with active learning, compared with 25% under random labeling.The active-learning strategy selects borderline and low-confidence points and significantly reduces manual labeling effort.
- Active learning: The combined active-learning strategy detects malicious traffic much faster than the margin-based strategy.Figure 10 compares detected outliers under combined, margin-based, and random sampling strategies.
- Threshold adaptation: Active learning also calibrates anomaly-detector thresholds: with small labeled samples, it finds a reasonable radius while random sampling and vanilla SVDD fail.The random strategy and vanilla SVDD reach false-positive rates of 0.5 and 1, respectively, in the reported threshold experiment.
7. Conclusion
The paper develops semi-supervised anomaly detection from an unsupervised paradigm, including an active learning strategy for selecting informative labels. Experiments show robust performance and accuracy gains from using limited labeled data, while motivating several extensions.
- SSAD generalizes support vector data description to incorporate prior and expert knowledge through labeled data.
- The proposed active learning strategy queries points near the hypersphere boundary that are likely to represent novel outlier categories.
- SSAD remains robust when baseline performance deteriorates because of obfuscation techniques in network intrusion detection.
- Only a handful of labeled instances are necessary to boost performance, which is useful when expert labeling is costly.
- Possible extensions include sparsity-inducing regularization, structured or non-isotropic norms, and multi-task formulations with multiple labels.
Appendix A. Analysis of SVDDneg
The appendix identifies non-convexity and duality gaps in SVDDneg under negatively labeled examples, then establishes equivalence with a convex one-class SVM formulation under translation-invariant kernels.
- Previously published SVDDneg-type methods can have duality gaps because their dual-space optimization may originate from a non-convex problem.
- SVDDneg treats unlabeled data as nominal and constrains labeled outliers outside the normality sphere, producing a two-class formulation.
- Figure 12 plots negative training-point percentage against primal and dual objective values to illustrate the duality gap.
- With more negative examples, the duality gap and the difference between objective values generally increase, although the gap need not be monotonic.
- For translation-invariant kernels satisfying k(x_i, x_i) = s, the non-convex SVDDneg dual has the same solution as the corresponding convex one-class SVM dual.
Appendix B. A Representer Theorem for SSAD
The appendix establishes that a representer theorem applies to the non-expanded SSAD objective, allowing its center to be represented using labeled and unlabeled examples.
- The section examines applicability of the representer theorem to semi-supervised anomaly detection.
- Under the stated reproducing-kernel Hilbert-space conditions, an optimizer can be expressed using finitely many coefficients associated with the inputs.
- The representer theorem applies to the non-expanded SSAD objective.
- Expanding the center in terms of labeled and unlabeled examples enables recovery of the primal variables R, γ, and c after optimization.
Appendix C. Computing the Gradients for Eq. (5)
The appendix derives gradients for the unconstrained SSAD objective so that a gradient-based solver can optimize its primal and kernelized representations.
- The gradient derivation supports implementation of a gradient-based solver for the unconstrained SSAD problem.
- The derivation uses the Huber loss and first computes gradients with respect to the primal variables R and c.
- Partial gradients for labeled examples are computed with respect to R, γ, and c before resolving the full objective gradient.
- For kernel functions, the center c is expanded using the representer theorem.
- The chain rule yields gradients with respect to the kernel expansion coefficients α_i/j.