Risk-Averse support vector classifier machine via moments penalization

Abstract

Support vector machine (SVM) has always been one of the most successful learning methods, with the idea of structural risk minimization which minimizes the upper bound of the generalization error. Recently, a tighter upper bound of the generalization error, related to the variance of loss, is proved as the empirical Bernstein bound. Based on this result, we propose a novel risk-averse support vector classifier machine (RA-SVCM), which can achieve a better generalization performance by considering the second order statistical information of loss function. It minimizes the empirical first- and second-moments of loss function, i.e., the mean and variance of loss function, to achieve the “right” bias-variance trade-off for general classes. The proposed method can be solved by the kernel reduced and Newton-type technique under certain conditions. Empirical studies show that the RA-SVCM achieves the best performance in comparison with other classical and state of art methods. The additional analysis shows that the proposed method is insensitive to the parameters, so abroad range of parameters lead to satisfactory performance. The proposed method is a general form of standard SVM, so it enriches the related studies of SVM.

Appendix A Proof of remark 1

Theorem 2

Under the condition of Theorem 1, the objective function $f_1({\varvec{\alpha }})$ in (24) is convex if

$$\begin{aligned} \frac{{{\lambda _1}}}{{{\lambda _2}}} \ge 2 \left(c + \frac{1}{p}\right). \end{aligned}$$

(A1)

Proof

Here, let ${g_i}({\varvec{\alpha }}) = \frac{1}{p}\log (1 + {e^{p{\varvec{r}_i}}}) = \max \{ {\varvec{r}_i},0\} + \frac{1}{p}\log (1 + {e^{ - p{|\varvec{r}_i |}}})$, the objective function of (24) can be written as

$$\begin{aligned} {f_1}(\varvec{\alpha } ) = {\lambda _1}\sum \limits _{i = 1}^m {{g_i}(\varvec{\alpha } )} + {\lambda _2}{g^\top }(\varvec{\alpha } )Qg(\varvec{\alpha } ) + \frac{1}{2}{\varvec{\alpha } ^\top }K\varvec{\alpha } \end{aligned}$$

(A2)

The Hessian matrix of $f_1(\varvec{\alpha })$ is:

$$\begin{aligned} {\nabla ^2}{f_1}(\varvec{\alpha } )= & {} {\lambda _1}\sum \limits _{i = 1}^m {{\nabla ^2}{g_i}(\varvec{\alpha } )} + 2{\lambda _2}\sum \limits _{i = 1}^m {{\varvec{\delta } _i}{\nabla ^2}{g_i}(\varvec{\alpha } )} \nonumber \\&+ 2{\lambda _2}\nabla g(\varvec{\alpha } )Q\nabla {g^\top }(\varvec{\alpha } ) + K\nonumber \\= & {} \sum \limits _{i = 1}^m {({\lambda _1} + 2{\lambda _2}{\varvec{\delta } _i}){\nabla ^2}} {g_i}(\varvec{\alpha } ) \nonumber \\&+ 2{\lambda _2}\nabla g(\varvec{\alpha } )Q\nabla {g^\top }(\varvec{\alpha } ) + K \end{aligned}$$

(A3)

where $Q=\varvec{I}-\frac{1}{m}\varvec{e}^\top \varvec{e}$, $\varvec{\sigma }=Qg(\varvec{\alpha })$, and

$$\begin{aligned} {\varvec{\delta } _i}= & {} {g_i}(\varvec{\alpha } ) - \frac{1}{m}\sum \limits _{i = 1}^m {{e^T}g(\varvec{\alpha } )} \nonumber \\= & {} \max \{ {\varvec{r}_i},0\} + \frac{1}{p}\log (1 + {e^{ - p{|\varvec{r}_i |}}}) - \frac{1}{m}\sum \limits _{j = 1}^m \max \{ {\varvec{r}_j},0\} \nonumber \\&+ \frac{1}{p}\log (1 + {e^{ - p{|\varvec{r}_j |}}}) \nonumber \\\ge & {} - \frac{1}{m}\sum \limits _{j = 1}^m {\max \{ {\varvec{r}_j},0\} - \frac{1}{{mp}}\sum \limits _{j = 1}^m {\log (1 + {e^{ - p{|\varvec{r}_j |}}})} } \nonumber \\\ge & {} - {c} - \frac{1}{{mp}}\sum \limits _{j = 1}^m {\log (1 + {e^{ - p(1+M)}})} \nonumber \\\ge & {} - {c} - \frac{{\log 2}}{p}\nonumber \\\ge & {} - {c} - \frac{1}{p}. \end{aligned}$$

(A4)

To prove that the objective function in Eq.(A2) is convex, it suffices to show that ${\nabla ^2}{f_1}(\varvec{\alpha } ) \succeq 0$ for every $\varvec{\alpha }$. It’s obvious that $2{\lambda _2}\nabla g(\varvec{\alpha } )Q\nabla {g^T}(\varvec{\alpha } ) + K\succeq 0$. That is, we need to prove that $\sum \nolimits _{i = 1}^m {({\lambda _1} + 2{\lambda _2}{\varvec{\delta } _i}){\nabla ^2}} {g_i}(\varvec{\alpha } ) \succeq 0$. Thus, let $\varvec{\mu }_i=\lambda _1+2\lambda _2 \varvec{\delta } _i$, then we need to prove $\varvec{\mu }_i\ge 0$, based on (A4), we get $\frac{{{\lambda _1}}}{{{\lambda _2}}} \ge 2(c + \frac{1}{p})$. That is, when $\frac{{{\lambda _1}}}{{{\lambda _2}}} \ge 2(c + \frac{1}{p})$, for each $\varvec{\alpha }\in R^m$, we have ${\nabla ^2}{f_1}(\varvec{\alpha } ) \succeq 0$. Therefore, the objective function $f_1(\varvec{\alpha })$ in (24) is convex. $\square$

It is obvious that the objective function in Eq.(25) is convex since ${\varphi _p}(r)$ and ${({\varphi _p}(r))^2}$ are convex functions. When $\frac{{{\lambda _1}}}{{{\lambda _2}}} \ge 2(c + \frac{1}{p})$, the solution of problem (24) obtained by algorithm 1 is globally optimal based on the Theorem 2. In fact, we have rarely encountered non-convergence in a large number of experiments. Of course we can also make a simple rule for selecting a optimal superparameter that satisfies the conditions given above.