Safe and Efficient Screening For Sparse Support Vector Machine

Assume that X E Him" is a data set containing 71 samples, X: (x1, . . . Let w*()\) be the optimal solution of Eq. (1) All the features With nonzero values in "w" (A) are called active The Lagrangian multiplier [1] of the problem defined in Eq. (1) is: The Eq. (2) can be reformulated as: Since the problem defined in Eq. (1) is convex and the optimal value of the In the preceding equation i'j: ij, and Y is a diagonal matrix and YM: When the input is given, it can be obtained in a closed form. The Ll--regularized L2--Loss SVM in Eq. (1) can be rewritten in an uncon-- Eq. (22) shows that the necessary condition for a feature f to be active in the To bound value of 0Tf' 7 we need to first construct a closed convex set K that We first study how to construct the convex set K. In the following, we construct a closed convex set K based on Eq. (19) and The proof of this proposition can be found in [2]. Let 01 and 02 be the optimal solutions of the problem defined in Eq. (19) for Assume that /\1 A2, and 01 is known. In the preceding equations, 01, A1, and /\2 are known. Figure 1 shows an example of the K in a two dimensional space. And K is indicated by the shaded area. It is indicated by the shaded area. Besides the n dimensional hyperball defined in Eq. (32), it is possible to By applying Proposition 6.1 to the objective function defined in Eq. (33) for 01, Let t::--: Z 0. By substituting 0: 02 and 0: 01 into Eq. Eq. (35)7 respectively, and then combining the two obtained equations7 the As the value of t change from 0 to 007 Eq. (36) generates a series of hyperball. Eq. (36) reaches it minimum when, The theorem can be proved by minimizing the 7" defined in Eq. (36).