A New Decomposition Method for Support Vector Machines with Polynomial Convergence
Support vector machines (SVMs) are an important classifier which is widely used in pattern classification and machine learning. Recently large-scale classification problems in real world have attracted much attention where decomposition methods play an important role in solving SVMs.Although several decomposition algorithms have been applied in practice and proven to be convergent, the convergence speed is not easy to obtain which is important to analysis of different algorithms. The newly proposed algorithms based on rate certifying pair/set give us light to get the convergence speed in theory,but they suffer from high computational cost either due to more iterations to reach a tolerance of solution or to complexity in working set selection.A new simple decomposition algorithm based on a new philosophy is proposed in this paper. It has been proven that the working set selected by the new algorithm is a rate certifying set.Furthermore, compared with existing algorithms based on rate certifying pair/set, our algorithm provides a very good feature in combination of lower computational complexity in working set selection and faster convergence.
Support vector machines decomposition method convergence pattern recognition
Hong Qiao Yan-Guo Wang Bo Zhang
the Institute of Automation, Chinese Academy of Sciences, Beijing, China 100080 the Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing, China 100080
国际会议
厦门
英文
131-134
2006-07-27（万方平台首次上网日期，不代表论文的发表时间）