Abstract
This paper addresses the computational challenge of hyperparameter tuning in One-Class Support Vector Machines (1-SVMs). We present an algorithm that computes the entire regularization path—the set of all solutions for every possible value of the regularization parameter $\lambda$. By demonstrating that the Lagrange multipliers follow a piecewise-linear path, we can trace the model's evolution through a series of "boundary events" where data points enter or leave the decision boundary. Experimental results on several UCI datasets show that this approach is significantly faster than traditional alpha seeding, providing a continuous solution space for more precise model selection.
Introduction
One-Class SVMs (1-SVMs) are widely used for novelty detection and density estimation, aiming to identify a boundary that encloses the majority of a dataset. A critical challenge in deploying these models is the selection of the regularization parameter (often denoted as $\lambda$ or $\nu$), which controls the trade-off between the volume of the enclosed region and the number of outliers. Traditionally, finding the optimal parameter requires "model selection," a process involving solving the SVM optimization problem repeatedly over a grid of values. This iterative approach is computationally expensive, particularly for large-scale applications.
Methodology: Exploiting Piecewise Linearity
The core contribution of this work is the adaptation of the regularization path concept to the $\nu$-1-SVM framework. The key mathematical insight is that the Lagrange multipliers ($\alpha_i$)—the dual variables in the SVM optimization—behave in a piecewise-linear fashion as the parameter $\lambda$ changes.
Instead of re-solving the quadratic program (QP) for every new $\lambda$, the algorithm tracks three sets of data points: those inside the boundary, those outside (outliers), and the "elbow set" of points exactly on the decision boundary. By solving a small system of linear equations, the algorithm determines the exact $\lambda$ value at which a point migrates between these sets. This allows the solver to "jump" from one boundary event to the next, tracing the entire solution space in a single continuous sweep.
Experimental Results
The proposed regularization path method was evaluated against the standard "alpha seeding" heuristic using four datasets from the UCI Machine Learning Repository: Credit, Pima, Yeast-cyt, and Spamdata.
As shown in the results table, the regularization path approach consistently outperforms alpha seeding. On the Credit dataset, the speedup is particularly dramatic, reaching up to 25 times faster than the heuristic alternative. Even on larger datasets like Spamdata, the path method remains more than twice as fast. Beyond raw speed, the regularization path provides a significant advantage in granularity: it yields the exact solution for every possible $\lambda$ in the range, whereas grid search only provides discrete samples.
Conclusion
The regularization path algorithm offers a robust and efficient alternative to traditional hyperparameter tuning for One-Class SVMs. By replacing repetitive QP solves with linear updates, it provides a complete view of the model's sensitivity to regularization. Future work includes extending this technique to streaming data for real-time change detection and exploring its application in multiclass problems with rejection options.
Summary updated