Polynomial-time decomposition algorithms for support vector machines

作     者：Hush, D Scovel, C 

作者机构：Los Alamos Natl Lab Los Alamos NM 87545 USA 

出 版 物：《MACHINE LEARNING》 (机器学习)

年 卷 期：2003年第51卷第1期

页      面：51-71页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：U.S. Department of Energy, USDOE Los Alamos National Laboratory, LANL 

主　　题：support vector machines polynomial-time algorithms decomposition algorithms 

摘      要：This paper studies the convergence properties of a general class of decomposition algorithms for support vector machines (SVMs). We provide a model algorithm for decomposition, and prove necessary and sufficient conditions for stepwise improvement of this algorithm. We introduce a simple rate certifying condition and prove a polynomial-time bound on the rate of convergence of the model algorithm when it satisfies this condition. Although it is not clear that existing SVM algorithms satisfy this condition, we provide a version of the model algorithm that does. For this algorithm we show that when the slack multiplier C satisfies root1/2 less than or equal to Cless than or equal to mL, where m is the number of samples and L is a matrix norm, then it takes no more than 4LC(2)m(4)/epsilon iterations to drive the criterion to within epsilon of its optimum.