Fast Incremental SVDD Learning Algorithm with the Gaussian Kernel

Hansi Jiang, Haoyu Wang, Wenhao Hu, Deovrat Kakde, Arin ChaudhuriAAAI 2019 · DOI

Abstract

Support Vector Data Description (SVDD) is a robust method for one-class classification and outlier detection. However, traditional batch and incremental SVDD algorithms often struggle with the computational demands of large-scale streaming data. This paper introduces FISVDD (Fast Incremental SVDD), an algorithm that leverages the unique geometric properties of the Gaussian kernel to achieve significant speedups. By utilizing efficient matrix inverse updates and focusing only on current support vectors, FISVDD reduces per-iteration complexity to $O(k^2)$, where $k$ is the number of support vectors. Experimental results on benchmark datasets demonstrate that FISVDD achieves orders-of-magnitude faster processing times than standard incremental methods while maintaining nearly identical outlier detection accuracy.

Introduction

In the era of big data, identifying anomalies in high-volume streams is a critical challenge. Support Vector Data Description (SVDD) addresses this by defining a hypersphere boundary around "normal" data points in a high-dimensional feature space. While effective, SVDD's computational cost becomes prohibitive as datasets grow. Traditional incremental SVDD methods attempt to maintain global optimality by tracking all data points to satisfy Karush-Kuhn-Tucker (KKT) conditions, leading to high memory consumption and slow update cycles. FISVDD addresses these limitations by simplifying the optimization problem through the specific properties of the Gaussian kernel.

Methodology: The FISVDD Algorithm

The efficiency of FISVDD is built upon two theoretical pillars:

1. The Equidistance Property

The authors demonstrate that when a Gaussian kernel is employed, all support vectors on the boundary of the SVDD hypersphere are equidistant from the center in the feature space. This property allows the complex optimization problem to be recast as a linear system: $A\alpha = e$, where $A$ is the kernel matrix of the support vectors and $\alpha$ represents the Lagrange multipliers.

2. Efficient Matrix Updates

Rather than re-solving the system from scratch, FISVDD employs rank-1 updates (expanding) and downdates (shrinking) to the inverse of the kernel matrix.

  • Expansion: When a new data point falls outside the current boundary, it becomes a support vector. The matrix inverse is updated using the Schur complement.
  • Shrinking: If the addition of a new point causes an existing support vector to move inside the boundary (becoming an interior point), it is removed, and the matrix inverse is downdated accordingly.

By focusing exclusively on the $k$ support vectors, the algorithm maintains a per-iteration complexity of $O(k^2)$, making it highly suitable for real-time streaming applications.

Experimental Evaluation

The performance of FISVDD was evaluated against the standard Incremental SVM (Inc. SVM) using four real-world datasets: Shuttle, Mammography, Forest Cover (CoverType), and SMTP (KDD Cup 99).

Accuracy and Stability

A primary concern with fast incremental methods is the potential loss of accuracy. However, as shown in Figure 1, the F1 scores for FISVDD and Inc. SVM are virtually indistinguishable across all datasets, confirming that the algorithmic simplifications do not compromise detection quality.

F1 scores of FISVDD and Inc. SVM across four benchmark datasets as the number of streaming data points increases.

Computational Efficiency

The most significant advantage of FISVDD is its speed. On the Shuttle dataset, FISVDD completed the task in 251 seconds, compared to 22,923 seconds for the baseline—a speedup of nearly 90x. On the larger CoverType dataset, the improvement was even more pronounced, reducing processing time from over 3.5 hours to just 19 seconds.

Discussion and Limitations

While FISVDD offers dramatic performance gains, its theoretical simplifications are tied to the properties of the Gaussian kernel. While the Gaussian kernel is widely used in SVDD, the algorithm's current form may not generalize to other kernel types without modification. Additionally, like all SVDD-based methods, performance remains sensitive to the choice of the Gaussian bandwidth parameter ($\sigma$).

Conclusion

FISVDD represents a significant advancement in incremental learning for anomaly detection. By exploiting kernel-specific geometry and efficient matrix manipulations, it provides a scalable solution for processing massive data streams without sacrificing the predictive power of the SVDD model.

Summary updated

BibTeX
@inproceedings{jiang2019fast,
  author = {Hansi Jiang and Haoyu Wang and Wenhao Hu and Deovrat Kakde and Arin Chaudhuri},
  title = {{Fast Incremental SVDD Learning Algorithm with the Gaussian Kernel}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33013991},
}
Figure