SVM （四） 软间隔和正则化
线性分类SVM面临的问题
在前面的讨论中，我们一直假定训练样本在样本空间中是线性可分的，存在一个超平面能够把不同类的样本完全划分开。然而，在现实任务中往往是很难找到合适的核函数将训练样本“完全划分”。即使找到了某个核函数刚好将训练集在特征空间中线性可分，但是这种情况也有可能是过拟合造成的。由于噪声值的出现，超平面会有很大的倾斜，会得到一个间隔非常小的超平面，如下图所示。
线性分类SVM软间隔最大化
对于上述情况，我们如果仍然希望右图还是虚线的情况（因为这种情况虽然目前分的很好，但是考虑到未来随着数据的增多，最理想的情况仍然是虚线），那我们该怎么办呢？这时我们必须引入“软间隔”概念。左图要求所有的样本必须划分正确，这称之为“硬间隔”。而“软间隔”允许SVM在一些样本上出错，即允许某些样本不满足约束:
\begin{equation}
y_i (W^T x_i + b) \geq 1
\end{equation}
\begin{equation}
\begin{split}
& min \ \frac{1}{2}W^TW \\
s.t. \ &y_i (W x_i + b) \geq 1, \ i = 1,...,m
\end{split}
\end{equation}
在引入软间隔理论后，我们的优化目标就变成了下面的形式：
\begin{equation}
\begin{split}
& min \ \frac{1}{2}W^TW + C \sum_{i=1}^m \xi_i\\
s.t. \ & y_i (W x_i + b) \geq 1 - \xi_i, \ i = 1,...,m\\
& \xi_i \geq 0,\ i=1,...,m
\end{split}
\end{equation}
这里 \(C > 0\)为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数， \(C\)越大，对于误分类的惩罚越大，反之越小。也就是说我们希望目标函数尽量小，误分类的点尽可能的少。\(C\)是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。这个目标函数的优化和SVM线性可分的优化方式类似，下面我们来看看如何对线性分类SVM的软间隔最大化进行学习。
和线性可分SVM的优化方式类似，首先我们将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题，如下：
\begin{equation}
\begin{split}
L(w , b , \xi , \alpha , \mu) = \frac{1}{2}||W||^2 + C \sum_{i=1}^{m} \xi_i - \sum_{i=1}^m \alpha_i [y_i (W^T x_i +b) - 1 + \xi_i] - \sum_{i=1}^m \mu_i \xi_i
\end{split}
\end{equation}
其中, \(\mu_i \geq 0,\ \alpha_i, \geq 0\)。
也就是说，我们现在优化的目标函数是：
\begin{equation}
\underbrace{min}_{ W,b,\xi }\ \underbrace{max}_{ \alpha_i \geq 0, \mu_i \geq 0 } \ L(W, b, \alpha, \xi, \mu)
\end{equation}
这个优化目标也满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解，如下：
\begin{equation}
\underbrace{max}_{\alpha_i \geq 0, \mu_i \geq 0,} \ \underbrace{min}_{w,b,\xi}\ L(w,b,\alpha, \xi,\mu)
\end{equation}
我们可以先求优化函数对于 \(W\)，\(b\)，\(\xi\)的极小值，再求拉格朗日乘子\(\alpha\)，\(\mu\)的极大值。
首先我们来求优化函数对于\(W\)，\(b\)，\(\xi\)的极小值，这个可以通过求偏导数求得：
$$
\frac{\partial L}{\partial W} = 0 \ \Rightarrow W = \sum\limits_{i=1}^{m}\alpha_iy_ix_i
$$
$$
\frac{\partial L}{\partial b} = 0 \ \Rightarrow \sum\limits_{i=1}^{m}\alpha_iy_i = 0
$$
$$
\frac{\partial L}{\partial \xi} = 0 \ \Rightarrow \alpha_i + \mu_i = C
$$
这样我们可以利用上面三个式子去消除\(W\)，\(b\)了。
\begin{equation}
\begin{split}
L(W,b,\xi,\alpha,\mu)
& = \frac{1}{2}||W||_2^2 +C\sum_{i=1}^{m}\xi_i - \sum_{i=1}^{m}\alpha_i[y_i(w^Tx_i + b) - 1 + \xi_i] - \sum_{i=1}^{m}\mu_i\xi_i \\
&= \frac{1}{2}||W||_2^2 - \sum_{i=1}^{m}\alpha_i[y_i(W^Tx_i + b) - 1 + \xi_i] + \sum_{i=1}^{m}\alpha_i\xi_i \\
& = \frac{1}{2}||W||_2^2 - \sum_{i=1}^{m}\alpha_i[y_i(W^Tx_i + b) - 1] \\
& = \frac{1}{2}W^TW-\sum_{i=1}^{m}\alpha_iy_iW^Tx_i - \sum_{i=1}^{m}\alpha_iy_ib + \sum_{i=1}^{m}\alpha_i \\
& = \frac{1}{2}W^T\sum_{i=1}^{m}\alpha_iy_ix_i -\sum_{i=1}^{m}\alpha_iy_iW^Tx_i - \sum_{i=1}^{m}\alpha_iy_ib + \sum_{i=1}^{m}\alpha_i \\
& = \frac{1}{2}W^T\sum_{i=1}^{m}\alpha_iy_ix_i - W^T\sum_{i=1}^{m}\alpha_iy_ix_i - \sum_{i=1}^{m}\alpha_iy_ib + \sum_{i=1}^{m}\alpha_i \\
& = - \frac{1}{2}W^T\sum_{i=1}^{m}\alpha_iy_ix_i - \sum_{i=1}^{m}\alpha_iy_ib + \sum_{i=1}^{m}\alpha_i \\& = - \frac{1}{2}W^T\sum_{i=1}^{m}\alpha_iy_ix_i - b\sum_{i=1}^{m}\alpha_iy_i + \sum_{i=1}^{m}\alpha_i \\
& = -\frac{1}{2}(\sum_{i=1}^{m}\alpha_iy_ix_i)^T(\sum_{i=1}^{m}\alpha_iy_ix_i) - b\sum_{i=1}^{m}\alpha_iy_i + \sum_{i=1}^{m}\alpha_i \\
& = -\frac{1}{2}\sum_{i=1}^{m}\alpha_iy_ix_i^T\sum_{i=1}^{m}\alpha_iy_ix_i - b\sum_{i=1}^{m}\alpha_iy_i + \sum_{i=1}^{m}\alpha_i \\
& = -\frac{1}{2}\sum_{i=1}^{m}\alpha_iy_ix_i^T\sum_{i=1}^{m}\alpha_iy_ix_i + \sum_{i=1}^{m}\alpha_i \\
& = -\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum_{i=1}^{m}\alpha_i \\
& = \sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j
\end{split}
\end{equation}
仔细观察可以发现，这个式子和我们上一篇线性可分SVM的一样。唯一不一样的就是约束条件。现在看看我们的优化目标的数学形式：
\begin{equation}
\begin{split}
max \sum_{i=1}^m \alpha_i - &\frac{1}{2} \sum_{i=1, j=1}^m \alpha_i \alpha_j y_i y_j x_i^T x_j \\
s.t. \ &\sum_{i=1}^m \alpha_i y_i = 0 \\
&\alpha_i + \mu_i = C \\
&\alpha_i \geq 0 \ (i=1,2,...,m) \\
&\mu_i \geq 0 \ (i=1,2,...,m)
\end{split}
\end{equation}
这就是软间隔最大化时线性可分SVM的优化目标形式，和硬间隔最大化的SVM线性可分相比，我们仅仅是多了一个约束条件 \(0 \leq \alpha_i \leq C\)，我们依然可以通过SMO算法来求解上式极小化时的对应向量\(\alpha\)，继而求出\(W\)和\(b\)。
软间隔最大化时的支持向量
在软间隔最大化时，我们对每个样本 \((x_i,y_i)\)引入了松弛变量\(\xi_i\)。我们从下图来研究软间隔最大化时支持向量的情况，第\(i\)个点到对应类别支持向量的距离为\(\frac{\xi_i}{||W||_2}\)。根据软间隔最大化时KKT条件中对偶互补条件\(\alpha_i(y_i(W^T x_i + b)-1 + \xi_i)\ = 0\)，我们有：
1. 如果\(\alpha_i = 0\)，那么\(y_i(W^T x_i + b) -1 \geq 0\)，即样本在支持向量上或者被正确的分类。如图中远离支持向量的点。2. 如果\(0 < \alpha_i < C\)，那么\(\xi_i = 0,\ y_i(W^T + b) - 1 = 0\)，即点在支持向量上。如图中的虚线支持向量上的点。
3. 如果\(\alpha_i = C\)，说明这是一个异常点，此时需要检查\(\xi_i\)
(a) 如果 \(0 \leq \xi_i < 1\)，那么点被正确分类，但是却在超平面和自己类别的支持向量之间。如图中的样本2和4。
(b) 如果 \(\xi_i = 1\)，那么点在分离超平面上，无法被正确分类。
(c) 如果 \(\xi_i > 1\)，那么点在超平面的另一侧，也就是说，这个点不能够被正常分类。如图中的样本1和3。
以上就是引入软间隔的SVM的一些理解，希望大家能够理解这一技术。其实软间隔相当于正则化的过程，可以有效地防止训练过程中模型过拟合，从而更好地进行分类工作。