soft-margin支持向量机
在求解支持向量机参数的二次规划中，约束条件要求所有点被正确分类的叫hard-margin支持向量机。这类支持向量机过拟合原因：（1）特征转换功能太强；（2）坚持所有点都被正确分类。
可以通过放宽条件，容忍部分噪声（容许这部分噪声数据分类错误），使得支持向量机具有更好的泛化性能。
对于pocket PLA，目标函数为 \[ \min\limits_{b,\mathbf w}\sum_{n=1}^N\left[\left[y_n\neq\mbox{sign}\left(\mathbf w^T\mathbf z_n+b\right)\right]\right]， \] 结合线性支持向量机，可以得到容忍错分的优化模型 \[ \begin{aligned} \min\limits_{b,\mathbf w}&\quad\frac{1}{2}\mathbf w^T\mathbf w + C\sum_{n=1}^N\left[\left[y_n\neq\mbox{sign}\left(\mathbf w^T\mathbf z_n+b\right)\right]\right]\\ \mbox{s.t.}&\quad y_n\left(\mathbf w^T\mathbf z_n+b\right)\geq 1-\infty\cdot\left[\left[y_n\neq\mbox{sign}\left(\mathbf w^T\mathbf z_n+b\right)\right]\right]， \end{aligned} \] $C$是调节最大边界和噪声容忍度的参数。但是，上述模型不是QP，并且不能区别分类错误时误差的大小，进一步降模型变为soft-margin支持向量机 \begin{equation} \begin{aligned} \min\limits_{b,\mathbf w,\boldsymbol\xi}&\quad\frac{1}{2}\mathbf w^T\mathbf w + C\sum_{n=1}^N\xi_n\\ \mbox{s.t.}&\quad y_n\left(\mathbf w^T\mathbf z_n+b\right)\geq 1-\xi_n\\ &\quad\xi_n\geq 0 \mbox{ for all }n， \end{aligned} \label{eq:soft-margin-primal-svm} \end{equation} 该QP模型有$\tilde d+1+N$个变量和$2N$个约束条件，也被称为基于$\ell_1$损失的soft-margin。如果采用$\xi_n^2$，则被称为基于$\ell_2$损失的soft-margin \begin{equation*} \begin{aligned} \min\limits_{b,\mathbf w,\boldsymbol\xi}&\quad\frac{1}{2}\mathbf w^T\mathbf w + C\sum_{n=1}^N\xi_n^2\\ \mbox{s.t.}&\quad y_n\left(\mathbf w^T\mathbf z_n+b\right)\geq 1-\xi_n， \end{aligned} \end{equation*} 此时不再需要约束条件$\xi_n\geq 0$。
$C$是调节最大边界和边界容忍度的参数，$\xi_n$是容忍误差的大小，如上图所示。$C$越小，对最大边界要求越高；$C$越大，能容忍的边界误差越小。
对偶soft-margin支持向量机
soft-margin支持向量机的拉格朗日函数为 \[ \begin{aligned} \mathcal L(b,\mathbf w,\boldsymbol\alpha, \boldsymbol\beta)= &{1\over 2}\mathbf w^T\mathbf w + C\sum_{n=1}^N\xi_n\\ &+\sum_{n=1}^N\alpha_n\left(1-\xi_n-y_n\left(\mathbf w^T\mathbf z_n+b\right)\right)+\sum_{n=1}^N\beta_n\left(-\xi_n\right)， \end{aligned} \] 根据${\partial\mathcal L\over\partial\xi_n}=0$可得$C-\alpha_n-\beta_n=0$，利用化解拉格朗日对偶问题相同的方法可得 \begin{equation} \begin{aligned} \min\limits_{\boldsymbol\alpha}&\quad\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N\alpha_n\alpha_my_ny_m\mathbf z_n^T\mathbf z_m-\sum_{n=1}^N\alpha_n \\ \mbox{subject to}&\quad\sum_{n=1}^Ny_n\alpha_n=0\\ &\quad 0\leq\alpha_n\leq C,\mbox{ for }n=1,2,\ldots,N \\ \mbox{implicitly}&\quad \mathbf w=\sum_{n=1}^N\alpha_ny_n\mathbf z_n\\ &\quad\beta_n=C-\alpha_n,\mbox{ for }n=1,2,\ldots,N， \end{aligned} \label{eq:qp-soft-margin-dual-svm} \end{equation} 与hard-margin对偶支持向量机不同的地方只是$\alpha_n$多了一个上界$C$，这是$N$个变量$2N+1$个约束条件的QP。$\alpha_n$的约束界也可以表示为矩阵形式 \begin{equation} \mathbf 0_N\leq \mathbf I_N\boldsymbol\alpha \leq C\cdot \mathbf 1_N。 \end{equation}
核soft-margin支持向量机
soft-margin是实际中广泛应用的支持向量机。
soft-margin的支持向量机与hard-margin的支持向量机基本相同，$\alpha_n$上界$C$的限制，导致$b$的计算不同。
利用complementary slackness条件可得 \begin{equation} \begin{aligned} \alpha_n\left(1-\xi_n-y_n\left(\mathbf w^T\mathbf z_n+b\right)\right)=&0\\ \left(C-\alpha_n\right)\xi_n=&0， \end{aligned} \label{eq:soft-margin-complementary-slackness} \end{equation} 当$\alpha_s>0$时，$b=y_s-y_s\xi_s-\mathbf w^T\mathbf z_s$；当$\alpha_s<C$时，$\xi_s=0$。满足$0<\alpha_s<C$的点称为自由支持向量$\left(\mathbf x_s, y_s\right)$，利用这些点容易得到 \begin{equation} b=y_s-\sum\limits_{SV}\alpha_ny_nK\left(\mathbf x_n, \mathbf x_s\right)。 \end{equation} 在极少数情况下，不存在自由支持向量，$b$通过不等式限定，只要满足KKT条件的取值都是合理的$b$。
上图展示了soft-margin高斯核支持向量机的效果，灰色的区域表示最大分类间隔。从图中可以看出，$C$越大，对误差的容忍越弱，越容易导致过拟合。
$\alpha_n$的物理含义
通过公式\eqref{eq:soft-margin-complementary-slackness}可知，$\alpha_n$将数据点分为如上图所示的3种类型：
- 当$\alpha_n=0$时，非支持向量，$\xi_n=0$，位于边界之外，极少数可能在边界上；
- 当$0<\alpha_n<C$时，自由（free）支持向量$\square$，$\xi_n=0$，位于边界上，用于计算$b$；
- 当$\alpha_n=C$时，有界（bounded）支持向量$\triangle$，$\xi_n=1-y_n\left(\mathbf w^T\mathbf z_n+b\right)$，落在边界内，可能正确分类也可能分错，极少数可能在边界上。
模型选择
上图左是soft-margin高斯核支持向量机的分类效果，横轴是$C$的变化，纵轴是$\gamma$的变化。由于$E_{cv}(C,\gamma)$不光滑，通常的模型选择方法是通过$C$和$\gamma$的数据网格，利用交叉验证的方法选择合适的模型，上图中所示，选择了左下角的模型。
交叉验证中，将数据分为$N$份的验证称为leave-one-out交叉验证，它的误差上界是 \begin{equation} E_{loocv}\leq\frac{\#SV}{N}， \label{eq:eloocv-upper-bound} \end{equation} $\#SV$表示支持向量的个数。可以通过支持向量的个数进行模型选择。由于支持向量个数的函数也是非光滑的，难以优化，也采取利用$C$和$\gamma$的数据网格，多次计算后做选择。
由于\eqref{eq:eloocv-upper-bound}也只是给出了$E_{loocv}$的上界，通常用于当$E_{cv}$计算量很大时模型的安全检查，剔除那些支持向量过多的危险模型，然后再在剩余模型中进一步做交叉验证选择合适的模型。
