Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2005-001 (March 14, 2005)

A Regularized Nonsmooth Newton Method for Multi-class Support Vector Machines
by Ping Zhong and Masao Fukushima

PostScript File

Multi-class classification is an important and on-going research subject in machine learning. Recently, the $\nu$-K-SVCR method was proposed by the authors for multi-class classification. Since many optimization problems have to be solved in multi-class classification, it is extremely important to develop an algorithm that can solve those optimization problems efficiently. In this paper, the optimization problem in the $\nu$-K-SVCR method is reformulated as an affine box constrained variational inequality problem with a positive semi-definite matrix, and a regularized version of the nonsmooth Newton method that uses the D-gap function as a merit function is applied to solve the resulting problems. The proposed algorithm fully exploits the typical feature of the $\nu$-K-SVCR method, which enables us to reduce the size of Newton equations significantly. This indicates that the algorithm can be implemented efficiently in practice. The preliminary numerical experiments on benchmark datasets show that the proposed method is considerably faster than the standard Matlab routine used in the original $\nu$-K-SVCR method.