A study on SMO-type decomposition methods for support vector machines

被引：215
作者：
Chen, Pai-Hsuen [1 ]
Fan, Rong-En [1 ]
Lin, Chih-Jen [1 ]
机构：
[1] Natl Taiwan Univ, Dept Comp Sci, Taipei 106, Taiwan
来源：
IEEE TRANSACTIONS ON NEURAL NETWORKS | 2006年 / 17卷 / 04期
关键词：
decomposition method; sequential minimal optimization (SMO); support vector machine (SVM);
D O I：
10.1109/TNN.2006.875973
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Decomposition methods are currently one of the major methods for training support vector machines. They vary mainly according to different working set selections. Existing implementations and analysis usually consider some specific selection rules. This paper studies sequential minimal optimization type decomposition methods under a general and flexible way of choosing the two-element working set. The main results include: 1) a simple asymptotic convergence proof, 2) a general explanation of the shrinking and caching techniques, and 3) the linear convergence of the methods. Extensions to some support vector machine variants are also discussed.
引用
收藏
页码：893 / 908
页数：16
相关论文
共 28 条
  • [1] Boser B. E., 1992, Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, P144, DOI 10.1145/130385.130401
  • [2] The analysis of decomposition methods for support vector machines
    Chang, CC
    Hsu, CW
    Lin, CJ
    [J]. IEEE TRANSACTIONS ON NEURAL NETWORKS, 2000, 11 (04): : 1003 - 1008
  • [3] Training ν-support vector classifiers:: Theory and algorithms
    Chang, CC
    Lin, CJ
    [J]. NEURAL COMPUTATION, 2001, 13 (09) : 2119 - 2147
  • [4] LIBSVM: A Library for Support Vector Machines
    Chang, Chih-Chung
    Lin, Chih-Jen
    [J]. ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY, 2011, 2 (03)
  • [5] Cherkassky V, 1997, IEEE Trans Neural Netw, V8, P1564, DOI 10.1109/TNN.1997.641482
  • [6] CORTES C, 1995, MACH LEARN, V20, P273, DOI 10.1023/A:1022627411411
  • [7] CORTES C, 2003, P 16 ANN C LEARN THE, P41
  • [8] CRISP DJ, 2000, ADV NEURAL INF PROCE, V12
  • [9] Fan RE, 2005, J MACH LEARN RES, V6, P1889
  • [10] Polynomial-time decomposition algorithms for support vector machines
    Hush, D
    Scovel, C
    [J]. MACHINE LEARNING, 2003, 51 (01) : 51 - 71
123