Abstract
The decomposition method is currently one of the major methods for solving support vector machines. An important issue of this method is the selection of working sets. In this paper through the design of decomposition methods for bound-constrained SVM formulations we demonstrate that the working set selection is not a trivial task. Then from the experimental analysis we propose a simple selection of the working set which leads to faster convergences for difficult cases. Numerical experiments on different types of problems are conducted to demonstrate the viability of the proposed method.
Introduction
Training Support Vector Machines (SVMs) on large-scale datasets presents a significant computational challenge. At the core of SVM training is a Quadratic Programming (QP) problem involving an $l \times l$ matrix, where $l$ is the number of training samples. For modern datasets with tens of thousands of points, this matrix is often too large to fit in memory, necessitating the use of decomposition methods. These methods iteratively solve smaller sub-problems by selecting a small "working set" of variables to optimize while keeping others fixed.
The Working Set Selection Problem
A critical factor in the efficiency of decomposition methods is the strategy used to select the working set. Standard approaches, such as those implemented in $SVM^{light}$, typically select variables that most significantly violate the Karush-Kuhn-Tucker (KKT) optimality conditions. However, Hsu and Lin (2002) demonstrate that these traditional strategies can struggle, particularly when the penalty parameter $C$ is large, leading to slow convergence and "zig-zagging" behavior.
The "Free Variable" Bottleneck
The authors identify the number of "free variables"—those not at the boundaries 0 or $C$—as a primary bottleneck for convergence. When too many variables remain free, the algorithm struggles to find the global optimum efficiently because it only observes a small slice of the problem at a time.
To address this, the paper proposes a novel selection strategy that doesn't just focus on KKT violators but also selects variables that are "most satisfied" among the free variables. This approach forces variables to hit their bounds more quickly, effectively "shrinking" the complexity of the remaining optimization problem.
Experimental Results and Implementation
The proposed method was implemented in a tool called BSVM and benchmarked against 16 datasets from the Statlog and UCI repositories. The authors also introduced a simplified SVM formulation by adding a $\frac{1}{2}b^2$ term to the primal objective, which removes the linear equality constraint and simplifies the dual problem into a purely bound-constrained one.
Key findings include:
- Significant Speedups: On the "Heart" dataset, a naive selection strategy required 590 iterations, whereas the proposed strategy reached the same optimum in only 50 iterations.
- Efficiency at Scale: BSVM proved particularly effective in "difficult" scenarios with high $C$ values. For instance, on the "Adult4" dataset with an RBF kernel ($C=1000$), BSVM converged in 276 seconds, compared to over 1,700 seconds for $SVM^{light}$ without its shrinking heuristic.
- Model Accuracy: The simplified formulation with the $b^2/2$ term maintained nearly identical generalization accuracy to standard SVMs across all test sets.
Conclusion and Future Work
Hsu and Lin's work highlights that working set selection is a non-trivial task that deeply impacts SVM training efficiency. By prioritizing the reduction of free variables, their method offers a robust alternative for large-scale optimization. Future work involves integrating "shrinking" heuristics—temporarily removing variables likely to remain at bounds—to further enhance performance, and adapting the strategy for problems with more complex linear constraints.
Summary updated