Single Directional SMO Algorithm for Least Squares Support Vector Machines

Xigao Shao, Kun Wu, Bifeng LiaoComputational 2013 · DOI

TL;DR

This paper introduces a new "Single Directional SMO" (SD-SMO) algorithm for training Least Squares Support Vector Machines (LS-SVMs). SD-SMO improves training speed by optimizing only one Lagrange multiplier at a time in a specific direction, leading to fewer iterations and faster convergence without sacrificing classification accuracy.

What Problem Does This Paper Address?

Training Support Vector Machines (SVMs), and their variant Least Squares Support Vector Machines (LS-SVMs), can be computationally expensive, especially for large datasets. LS-SVMs, while offering a more efficient solution than traditional SVMs by solving linear equations instead of quadratic programs, still rely on decomposition methods like Sequential Minimal Optimization (SMO) for efficient training. A critical component of SMO is "working set selection," which determines which parameters to update in each iteration. Existing SMO methods can be slow due to repeated selections of updating patterns and the number of training cycles. This paper aims to accelerate LS-SVM training by proposing a novel working set selection strategy within the SMO framework.

Methods

The core innovation is the Single Directional SMO (SD-SMO) algorithm. Unlike traditional SMO which might update multiple parameters or select pairs of parameters, SD-SMO focuses on optimizing a single Lagrange multiplier ($\alpha_i$) at each step. This optimization is performed in a "single direction" that is adaptively chosen to ensure the convergence of the optimality conditions.

Key aspects of the SD-SMO method include:

  • Adaptive Objective Function: An adaptive objective function is selected to guide the optimization.
  • Single Directional Steps: The algorithm takes steps in a single direction for the Lagrange multipliers, aiming to reduce the number of training cycles and kernel operations.
  • Convergence Proof: The paper provides a theoretical proof for the asymptotic convergence of the SD-SMO algorithm to the global optimal solution.
  • Termination Criterion: The algorithm uses a criterion based on the norm of the violation of KKT optimality conditions to determine when to stop.

Datasets

The paper evaluates SD-SMO on several benchmark datasets:

  • For comparison with First Order SMO: Banana, Image, Waveform, and Splice.
  • For comparison with Second Order SMO: Titanic, Heart, Breast Cancer, Thyroid, and Pima.
  • For scalability analysis: a8a and covtype.binary (with varying sizes).

The datasets used are standard in machine learning literature for evaluating classification algorithms.

Key Insights and Ideas

  • The Power of Single Direction: The paper demonstrates that by carefully selecting a single direction for updating Lagrange multipliers, significant speedups can be achieved without compromising accuracy. This challenges the intuition that updating multiple parameters or using more complex selection criteria is always necessary for efficiency.
  • Reduced Training Cycles: The "single directional" approach inherently reduces the number of "training cycles" (repeated patterns of updates), which is a known bottleneck in traditional SMO.
  • Scalability: The experiments suggest that SD-SMO scales well with increasing dataset sizes, maintaining linear scaling of iterations.
  • Balancing Speed and Accuracy: A key takeaway is that SD-SMO achieves a favorable balance, offering substantially faster training times compared to existing SMO variants while maintaining comparable classification accuracy.

Key Results

  • Faster Training: Experimental results show that SD-SMO is significantly faster than both first-order and second-order SMO algorithms. For instance, on the Image dataset, SD-SMO was up to ten times faster than first-order SMO.
  • Comparable Accuracy: The classification accuracy of SD-SMO is reported to be not largely different from existing methods, and in some cases, it is comparable or slightly better. For example, the Image dataset achieved an accuracy of 0.963 with SD-SMO, comparable to first-order SMO.
  • Reduced Iterations: SD-SMO requires fewer iterations to converge compared to traditional SMO methods, as evidenced in Table 4 for datasets like Titanic and Pima.
  • Linear Scaling: The algorithm exhibits linear scaling with respect to training set size for datasets like a8a and covtype.binary.

Limitations and Future Work

  • Not Discussed in the Paper: The paper does not explicitly detail limitations or suggest specific future work beyond the general implication that the method is effective and efficient. However, one could infer that further exploration into different kernel functions or more complex LS-SVM formulations might be potential avenues. The paper focuses on LS-SVMs without a bias term, so extending to include bias could be a future direction.

Summary updated

Abstract

Working set selection is a major step in decomposition methods for training least squares support vector machines (LS-SVMs). In this paper, a new technique for the selection of working set in sequential minimal optimization- (SMO-) type decomposition methods is proposed. By the new method, we can select a single direction to achieve the convergence of the optimality condition. A simple asymptotic convergence proof for the new algorithm is given. Experimental comparisons demonstrate that the classification accuracy of the new method is not largely different from the existing methods, but the training speed is faster than existing ones.
BibTeX
@inproceedings{shao2013single,
  author = {Xigao Shao and Kun Wu and Bifeng Liao},
  title = {{Single Directional SMO Algorithm for Least Squares Support Vector Machines}},
  booktitle = {Computational},
  year = {2013},
  doi = {10.1155/2013/968438},
}
Figure