Change point method: an exact line search method for SVMs

Predicting two groups from a set of predictor variables known as binary classification is not a new problem. Various different statistical approaches to binary classification are available in the literature, such as logistic regression, linear or quadratic discriminant analysis and neural networks. Another method which have recently become popular is called Support Vector Machines (SVMs) (Vapnik, 1999). This technique seems to perform better in terms of prediction quality compared to the alternatives mentioned. Its optimization problem is well defined and can be solved through a quadratic programming (Groenen et al., 2008). Moreover, the classification rule SVMs provide is relatively simple and can be immediately used with new samples. However, a disadvantage is that the nonlinear SVM interpretation in terms of predictor variables is not always possible and that the standard dual formulation of SVM may be difficult to comprehend (Groenen et al., 2008). This paper focuses on linear SVMs, specifically on the primal linear SVM problem. The primal formulation is used as it is easier to interpret, than a standard dual one. Groenen et al. (2008) formulates the SVM in terms of a loss function regularized by a penalty term. This formulation is called an SVM loss function with an absolute hinge error. Other researchers tackled similar SVM formulation using various methods. For example, Zhang (2004) and Bottou (2010) proposed a stochastic gradient descent method. In Collins et al. (2008) the exponential gradient search method is applied. In our paper we discuss an iterative majorization approach to minimizing the SVM loss function introduced by Groenen et al. (2008). Its advantage is that at each iteration of the algorithm we are guaranteed to decrease the loss value until convergence is reached. As the SVM loss function with an absolute hinge error is convex and coercive, iterative majorization converges to a global minimum after a sufficient number of iterations. The main focus of our paper is the development of an original line search method for optimizing the SVM loss function – the Change Point Method (CPM). The great advantage of the CPM is that it is exact. We also combine the CPM with different search directions (e.g. majorization, coordinate descent) in order to create an efficient optimization method for solving SVM problems. Finally, we compare the performance of different approaches testing them on the seven empirical data sets. The performance measures of interest are the computational efficiency and the loss value reached.