5.3.1 原始优化问题

5.3.1 原始优化问题

This leads to the following general optimization problem defining SVMs in the non-separable case where the parameter $C\ge 0$ determines the trade-off between margin-maximization (or minimization of $\parallel \mathbf{w}{\parallel }^2$ ) and the minimization of the slack penalty $\sum _{i=1}^m{\xi }_i^p$ :

$$\underset{\mathbf{w},b,\xi }{\min }\frac{1}{2}\parallel \mathbf{w}{\parallel }^2+C\sum _{i=1}^m{\xi }_i^p\text{\hspace{1em}(5.24)}$$ $$\text{subject to}{y}_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)\ge 1-{\xi }_i\wedge {\xi }_i\ge 0,i\in \left[m\right]\text{,}$$

where $\xi ={\left({\xi }_1,\dots ,{\xi }_m\right)}^{\top }$ . The parameter $C$ is typically determined via $n$ -fold cross-validation (see section 4.5).

As in the separable case, (5.24) is a convex optimization problem since the constraints are affine and thus convex and since the objective function is convex for any $p\ge 1$ . In particular, $\xi \mapsto \sum _{i=1}^m{\xi }_i^p=\parallel \xi {\parallel }_p^p$ is convex in view of the convexity of the norm $\parallel \cdot {\parallel }_p$ .

There are many possible choices for $p$ leading to more or less aggressive penaliza-tions of the slack terms (see exercise 5.1). The choices $p=1$ and $p=2$ lead to the most straightforward solutions and analyses. The loss functions associated with $p=1$ and $p=2$ are called the hinge loss and the quadratic hinge loss, respectively. Figure 5.5 shows the plots of these loss functions as well as that of the standard zero-one loss function. Both hinge losses are convex upper bounds on the zero-one loss, thus making them well suited for optimization. In what follows, the analysis is presented in the case of the hinge loss $\left(p=1\right)$ , which is the most widely used loss function for SVMs.

Figure 5.5

Both the hinge loss and the quadratic hinge loss provide convex upper bounds on the binary zero-one loss.