Support Vector Machine Models for Classification

Introduction

A support vector machine (SVM) is a quadratic programming (QP) model with training or learning algorithms. Developed by Vapnik (1995, 1998) and his coworkers, SVMs are used for classification, regression and function approximation. Because SVMs are QP models, this chapter discusses SVMs for classification from the mathematical programming (MP) perspective. SVMs are machine learning techniques because a SVM is usually trained, usually through numerical methods, to determine the values of the parameters in the classification function or discriminant functions.

As any other classification techniques, a SVM is used to construct a classification function or discriminant functions based on known values of the attributes or variables and known class memberships of the observations in a sample. The constructed classification function or discriminant functions are then used to evaluate the attribute values of any observation to obtain discriminant scores and to assign the observation into one of the classes. Many discriminant and classification techniques have been developed because no single technique always outperforms others under all situations (Johnson & Wichern, 1988). Statistical techniques, such as Fisher’s linear discriminant function (Fisher, 1936), Smith’s quadratic discriminant function (Smith, 1947) and logistic regression (Hand, 1981), have been standard tools for this purpose. More recently, other techniques, such as MP (Hand, 1981; Sun, 2010, 2011, 2014), neural networks (Stern, 1996) and classification trees (Breiman et al., 1984), have become alternative tools.

SVM (Vapnik, 1995, 1998) is a recent revolutionary development in classification analysis. Although they are modifications of the linear programming (LP) or mixed integer programming (MIP) models, they perform much better than their LP and MIP counterparts. Because they are QP models, they are also much more difficult to solve than their LP counterparts. Three concepts, classification margin maximization, dual formulation and kernels, are crucial in SVMs (Bredensteiner & Bennett, 1999). By minimizing the sum of classification errors and maximizing the classification margin at the same time in a QP model, SVMs construct discriminant functions with good generalization capabilities. Usually the dual formulation of the QP models is solved because the dual is usually easier to solve than the primal. By using inner product kernels in the dual formulations, SVMs can be built and nonlinear discriminant functions can be constructed in high dimensional feature spaces without carrying out the mappings from the input space to the high dimensional feature spaces. The size of the dual formulation is independent of the dimension of the input space and independent of the inner product kernels used.

However, most of the SVM research is for two-class classification although efforts have been made to extend the techniques to multi-class problems. Some of the approaches proposed in the literature for multi-class classification include the one-against-one approach (e.g., Friedman, 1996; Kreβel, 1999; Mayoraz & Alpaydin, 1999; Angulo et al., 2003), the one-against-all approach (e.g., Corte & Vapnik, 1995; Vapnik, 1995, 1998) and the one model formulation (e.g., Vapnik, 1995, 1998; Corte & Vapnik, 1995; Bredensteiner & Bennett, 1999; Weston & Watkins, 1999; Guermeur et al., 2000; Crammer & Singer, 2001; Guermeur, 2002; Lee et al., 2004; Sun, 2013). Examples of popular training software packages for SVMs include LIBSVM (Chang & Lin, 2011) and LIBLINEAR (Fan et al., 2008).