Working Set Selection Using Second Order Information for Training Support Vector Machines

Rong-En Fan, Pai-Hsuen Chen, Chih-Jen LinJMLR 2005 · OpenReview

TL;DR

This paper introduces a novel working set selection strategy for training Support Vector Machines (SVMs) using second-order information, leading to faster convergence and reduced training times compared to existing methods. By leveraging the curvature of the objective function, the proposed method efficiently identifies crucial data points for updates, significantly improving performance, especially on large-scale datasets.

What Problem Does This Paper Address?

Training Support Vector Machines (SVMs) involves solving a large quadratic optimization problem. For massive datasets, directly solving this problem is computationally prohibitive. Decomposition methods, like Sequential Minimal Optimization (SMO), break down the problem by iteratively updating only a small subset of variables (the "working set"). The efficiency of these methods heavily relies on how this working set is chosen. Existing methods primarily use first-order information (gradients) to identify "violating pairs" of data points that violate optimality conditions. However, this can lead to slow convergence, especially for difficult problems. This paper aims to accelerate SVM training by developing a more effective working set selection strategy that utilizes second-order information, which captures the curvature of the objective function.

Methods

The core contribution is a new working set selection method, termed WSS 3. Unlike previous methods that rely solely on first-order information (gradients), WSS 3 incorporates second-order information (Hessian of the objective function). Specifically, it builds upon the idea of minimizing a second-order approximation of the objective function when updating the working set.

The paper proposes WSS 2, which heuristically selects one element of the working set based on the maximal violating pair (first-order information) and then searches for the second element by considering the second-order approximation of the objective function. WSS 3 further refines this by generalizing the selection to handle non-positive definite kernel matrices, which can arise with certain kernels like the sigmoid kernel.

The paper also discusses the theoretical underpinnings, including convergence properties and finite termination guarantees, for decomposition methods using these new selection strategies. It also explores the impact of maintaining feasibility in sub-problems and compares different approaches.

Datasets

The paper evaluates its proposed methods on a variety of datasets, categorized into:

  • Small problems: Around 1,000 samples, including ten binary classification and five regression problems. Specific datasets mentioned include image, splice, tree, diabetes, fourclass, german.numer, wla, abalone, cadata, cpusmall, space_ga, ala, a9a, w8a, covtype, breast-cancer, mg, and IJCNN1.
  • Large problems: More than 30,000 instances, specifically a9a, w8a, IJCNN1, and covtype.

The data preprocessing involves scaling attributes to [-1,1] for most datasets, with exceptions for those with binary values.

Key Insights and Ideas

  • Second-order information accelerates convergence: By considering the curvature of the objective function, the proposed working set selection method can more effectively identify the most impactful updates, leading to fewer iterations.
  • WSS 3 handles non-positive definite kernels: The generalization to WSS 3 is crucial for broader applicability, as certain kernels can lead to non-positive definite matrices, which standard methods might struggle with.
  • Trade-off between selection complexity and iteration count: While WSS 3's selection step is more computationally intensive than WSS 1, the significant reduction in iterations often leads to overall faster training times.
  • Shrinking and caching interactions: The effectiveness of shrinking and caching strategies can be influenced by the working set selection method. WSS 3 appears to integrate better with shrinking, leading to more aggressive pruning of variables.
  • Feasibility in sub-problems: The paper investigates whether enforcing feasibility during working set selection (using a more complex sub-problem) offers advantages. It concludes that for final iterations, the simpler approach (without explicit feasibility checks) is sufficient and faster.

Key Results

  • Significant reduction in iterations: Experiments show that WSS 3 consistently reduces the number of iterations compared to WSS 1, especially in the "parameter selection" phase where convergence can be slow. Reductions are often substantial, with ratios of iterations between WSS 3 and WSS 1 frequently below 1.
  • Faster training times: Despite a more complex selection step, WSS 3 generally leads to shorter training times. This speedup is more pronounced when using smaller cache sizes, suggesting its utility for large-scale problems where the kernel matrix cannot be fully stored.
  • Competitive performance with O(l^2) full checks: The paper demonstrates that WSS 2, an O(l) heuristic, achieves iteration ratios close to those of a full O(l^2) check, indicating its effectiveness in selecting near-optimal working sets.
  • WSS 3 integrated into LIBSVM: The proposed WSS 3 has been adopted into the popular LIBSVM software package, highlighting its practical impact.

Limitations and Future Work

  • Theoretical analysis of global performance: While the paper establishes theoretical properties for WSS 3, a deeper theoretical study on its global performance and convergence rates, especially compared to other methods, is suggested as a future research direction.
  • Feasibility of sub-problems: The paper explores the impact of maintaining feasibility in sub-problems. While it shows that the simpler approach is often faster, a definitive conclusion on whether enforcing feasibility could lead to better overall performance in all scenarios remains an open question.
  • Performance on extremely large datasets: While experiments cover large datasets, the performance on truly massive datasets where memory constraints are extreme could be further investigated.
  • Exploring other heuristics: The paper mentions that other heuristics for working set selection are possible and that the performance of WSS 2 is compared against a full check. Further exploration of alternative heuristic combinations could be beneficial.

Summary updated

Abstract

Working set selection is an important step in decomposition methods for training support vector machines (SVMs). This paper develops a new technique for working set selection in SMO-type decomposition methods. It uses second order information to achieve fast convergence. Theoretical properties such as linear convergence are established. Experiments demonstrate that the proposed method is faster than existing selection methods using first order information.
BibTeX
@article{fan2005working,
  author = {Rong-En Fan and Pai-Hsuen Chen and Chih-Jen Lin},
  title = {{Working Set Selection Using Second Order Information for Training Support Vector Machines}},
  journal = {J. Mach. Learn. Res.},
  year = {2005},
  url = {https://openreview.net/forum?id=A0FeQTHWVQ},
}
Figure