A Novel Model of Working Set Selection for SMO Decomposition Methods

Zhendong Zhao, Lei Yuan, Yuxuan Wang, Forrest Sheng Bao, Shun-Yi Zhang, Yan-Fei SunICTAI 2007 · DOI

TL;DR

This paper introduces a novel working set selection strategy for Support Vector Machine (SVM) training, called Working Set Selection Without Reselection (WSS-WR). By preventing the re-selection of already optimized data points, WSS-WR significantly speeds up training and reduces the number of iterations compared to existing methods, particularly for large datasets.

What Problem Does This Paper Address?

Training Support Vector Machines (SVMs) often involves solving a complex quadratic optimization problem. Decomposition methods, like Sequential Minimal Optimization (SMO), break this down into smaller sub-problems by iteratively updating only a subset of variables (the "working set"). A crucial aspect of these methods is the "working set selection" strategy, which determines which variables to update in each iteration. Inefficient working set selection can lead to slow convergence, especially for difficult problems or large datasets. Existing methods, while effective, can suffer from redundant computations due to re-selecting variables that have already been optimized. This paper aims to address this by proposing a more efficient working set selection mechanism that avoids such re-selections.

Methods

The core contribution of this paper is the Working Set Selection Without Reselection (WSS-WR) model. This method builds upon existing SMO decomposition techniques, specifically incorporating second-order information as used in WSS 3. The novelty lies in its approach to managing the set of data points. WSS-WR maintains three sets of indices:

  • T: The set of all selected and optimized indices.
  • C: The set of available indices that have never been selected.
  • B: The working set selected in the current iteration.

Once a working set $B = \{i, j\}$ is selected and optimized, both indices $i$ and $j$ are moved from the available set $C$ to the optimized set $T$. This ensures that each data point is selected and optimized at most once. The selection of the working set $B$ itself leverages a strategy similar to WSS 3, which considers second-order information to identify potentially violating pairs.

Datasets

The paper evaluates its proposed method on a variety of datasets, including:

  • Small datasets (around 1,000 samples): ala, wla, australian, splice, breast-cancer, diabetes, fourclass, german.numer, heart, mpg, mg.
  • Large classification datasets: splice (from Delve archive), german.numer, heart, australian (from Statlog collection), fourclass, diabetes, breast-cancer, mpg (from UCI machine learning repository), ala, a9a, wla, w8a (compiled from UCI "adult" dataset), and IJCNN1 (from IJCNN 2001 challenge).

The paper also mentions using datasets from the LIBSVM library and the Delve archive.

Key Insights and Ideas

  • The "reselection" problem: The authors observe that in existing SMO methods, some data points are repeatedly selected for optimization, while others are never touched. This reselection is identified as a potential source of inefficiency.
  • "Once optimized, never re-optimized": The core idea of WSS-WR is to eliminate reselection by ensuring that once a data point's corresponding $\alpha$ value has been optimized, it is moved to a "permanently optimized" set and is no longer considered for future working set selections.
  • Efficiency gains for large datasets: The WSS-WR method shows particular promise for large-scale problems, especially when memory for caching is limited, as its performance is less affected by cache size compared to WSS 3.
  • Shrinking technique's limited impact: For WSS-WR, the benefits of the "shrinking" technique (a common optimization in SVM training) are found to be less pronounced, suggesting that the WSS-WR's inherent efficiency might reduce the need for such optimizations.

Key Results

  • Significant reduction in iterations and time: Experiments demonstrate that WSS-WR consistently outperforms WSS 3 in terms of both the number of iterations and the total training time across various kernels (RBF, Linear, Polynomial, Sigmoid) and datasets.
  • Accuracy is comparable: While WSS-WR is faster, the paper reports that the cross-validation accuracy of WSS-WR is comparable to, and sometimes even slightly better than, WSS 3. The difference in accuracy is generally very small (less than 0.026).
  • Robustness to cache size: Unlike WSS 3, the training time of WSS-WR does not significantly increase when the cache size is reduced from 100MB to 100KB, making it more suitable for memory-constrained scenarios.
  • Convergence: The convergence graphs show that WSS-WR reaches the optimum faster and terminates sooner than WSS 3, which may continue to iterate with minimal progress.

Limitations and Future Work

  • Theoretical convergence proof: While empirical results are strong, the paper mentions that a theoretical study on the convergence of WSS-WR is a future research direction.
  • Generalizability of ratio observations: The paper notes that the observed relationships between different ratio values (e.g., ratio5 < ratio4 < ratio3 < ratio2 < ratio1) might not be universally valid across all datasets.
  • Further improvements: The authors suggest that continually improving the WSS-WR model is an ongoing area of research.

Summary updated

BibTeX
@inproceedings{zhao2007novel,
  author = {Zhendong Zhao and Lei Yuan and Yuxuan Wang and Forrest Sheng Bao and Shun-Yi Zhang and Yan-Fei Sun},
  title = {{A Novel Model of Working Set Selection for SMO Decomposition Methods}},
  booktitle = {ICTAI},
  year = {2007},
  doi = {10.1109/ictai.2007.99},
}
Figure