SPARSEML Procedure

PROC SPARSEML uses a linear kernel to compute the support vector machine (SVM) learning classifiers for the binary pattern recognition problem. SVM is a powerful tool for finding robust classifiers; see Vapnik (1995); Burges (1998); Hsieh et al. (2008). Given a data set and the corresponding labels , the traditional SVM fitting model can be formulated as

where determine the classifier and , for each data point i, measures the error based on hinge loss that penalizes the misclassified points according to their distance from the corresponding classification margin.

The preceding model is called the L1-SVM model because the errors are penalized using the L1 norm. Similarly, the L2-SVM model can be formulated as

You can select these models by setting the parameters (using the REGL1= option) and (using the REGL2 option), respectively. If you specify the REGL1= option, then the L1-SVM model is used. If you specify the REGL2= option, then the L2-SVM model is used. If neither option is specified, then the L1-SVM model with a default penalty value (10) is assumed.

For performance purposes, the related dual problem would be solved. The following reformulates the L1-SVM model to produce the dual problem,

where the classifier would be recovered by

The algorithm that is used to solve the dual problem is referred to as the coordinate descent algorithm. It works on updating each coordinate by finding the that minimizes , where is the ith column of the identity matrix. This is equivalent to solving a one-dimensional problem,

which is a quadratic that can easily be minimized. Defining , which is referred to as the gradient, would show whether a certain coordinate is suitable to be updated. Especially given the box constraint, the projected gradient (PG) would help determine suitable coordinates by setting

thus updating each coordinate at a time. The randomized coordinate descent algorithm is suitable for large-scale sparse SVM models.