SVM(三)从软间隔到核函数

在 SVM(一) 和 SVM(二) 中，从 感知机 到 SVM损失函数 再到拉格朗日对偶式， 个人认为还是较为清楚的说了 硬间隔线性可分SVM ，但是现实世界中往往并不是完美的，在实际环境中接触到的数据即便是线性可分也往往是找不到硬间隔的，还有线性不可分的情况，那么此时应该怎么办，SVM如何解决这种问题，本次SVM的最后一部分就来说一说这些问题

软间隔线性可分SVM

首先依旧是给定数据集 $D={(x^{(1)}, y^{(1)}), (x^{(2)},y^{(2)}),\cdots,(x^{(N)}, y^{(N)})}$ ，其中 $x^{(i)}\in R^n$，$y^{(i)}\in {-1, +1}$，$i = 1,2...,N$ ，前面的问题中前提是数据一定得是线性可分 的，我们这里也假定数据是线性可分的，但是硬间隔不存在，也就是说 一些噪声或者叫异常点在间隔中干扰了硬间隔，导致找不到一个传统意义上的硬间隔。

此时既然仍然是线性可分的，那就还是可以在数据中画出一个超平面尽最大限度的分好正负例，且能找到最大间隔，只不过间隔是有“误差”的，换句话就是说，此时允许一定的“误差”落在间隔中，这种间隔就叫做软间隔

从图中可以清楚的看出来，相较于硬间隔，软间隔允许有 错分数据 在间隔内，此时在数学上达到这种效果的方法就是给每一个样本点一个 松弛变量 $\xi$ ，且和最大间隔 $\frac{1}{2}||\theta||^2$ 之间加一个 惩罚参数来控制二者的“权重” $C$ ，比如 $C=+\infty$ 时其实就相当于不允许有任何误差，也就容易过拟合，所以软、硬间隔线性可分SVM二者的损失函数是类似的，主要差别即在 松弛变量 这部分，定义软间隔线性可分SVM损失函数为

$$ \begin{equation} \begin{aligned} \mathop{min}_{\theta}\space&\frac{1}{2}||\theta||^2+C\sum_{i=1}^{N}{\xi^{(i)}}\\ s.t. \space&y^{(i)}(\theta^Tx^{(i)}+b)+\xi^{(i)}\geq1，&i=1,2,...,N\\ &\xi^{(i)}\geq0， &i=1,2,...,N \end{aligned} \end{equation}\\ $$

然后依然是构造拉格朗日函数，但是注意此时约束为 两个不等式 ，所以需要 $\alpha,\beta$ 两个拉格朗日乘子向量

$$ \begin{equation} \begin{aligned} \mathop{min}_{\theta,b,\xi}\mathop{max}_{\alpha,\beta}L(\theta,b,\alpha,\beta,\xi)= &\frac{1}{2}||\theta||^2+C\sum_{i=1}^{N}{\xi^{(i)}}\\ &+\sum_{i=1}^{N}{\alpha^{i}}(1-y^{(i)}(\theta^Tx^{(i)}+b)-\xi^{(i)})\\ &+\sum_{i=1}^{N}{\beta^{(i)}\xi^{(i)}}\\ =&\mathop{max}_{\alpha,\beta}\mathop{min}_{\theta,b,\xi}L(\theta,b,\alpha,\beta,\xi) \end{aligned} \end{equation}\\ $$

然后根据对偶问题进行计算，分别对 $\theta,b,\xi$ 求导等于 $0$ 求极小

$$ \begin{equation} \begin{aligned} \frac{\partial L}{\partial \theta}&= \theta-\sum_{i=1}^{N}{\alpha^{(i)}y^{(i)}x^{(i)}}&=0\\ \frac{\partial L}{\partial b} &=-\sum_{i=1}^{N}{\alpha^{(i)}y^{(i)}}&=0\\ \frac{\partial L}{\partial \xi^{(i)}}&=C-\alpha^{(i)}-\beta^{(i)}&=0 \end{aligned} \end{equation}\\ $$

整合公式即可得出， 不要忘记拉格朗日乘子的约束

$$ \begin{aligned} &\theta=\sum_{i=1}^{N}{\alpha^{(i)}y^{(i)}x^{(i)}}\\ &\sum_{i=1}^{N}{\alpha^{(i)}y^{(i)}}=0\\ &C-\alpha^{(i)}-\beta^{(i)}=0\\ &\alpha^{(i)}\geq0\\ &\beta^{(i)}\geq0 \end{aligned}\\ $$

然后将 $\theta$ 带入原始问题的拉格朗日函数中，此处与硬间隔一致，所以推导过程就不赘述了，可以参考 SVM(二)拉格朗日对偶式，得到

$$ \mathop{min}_{\theta,b,\xi}L(\theta,b,\alpha,\beta,\xi)=\sum_{i=1}^{N}{\alpha^{(i)}}-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha^{(i)}\alpha^{(j)}y^{(i)}y^{(j)}x^{(i)}x^{(j)}}\\ $$

再对 $\alpha$ 求 $L$的极大即是对偶问题了，这里先考虑相较于硬间隔SVM来说多出来的约束条件 $C-\alpha^{(i)}-\beta^{(i)}=0$ ，和 $\alpha^{(i)}\geq0，\beta^{(i)}\geq0$ ，可以约掉 $\beta$ ，即是$0\leq\alpha^{(i)}\leq C$ ，所以对偶问题描述成

$$ \begin{equation} \begin{aligned} \mathop{min}_{\alpha}\space &\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha^{(i)}\alpha^{(j)}y^{(i)}y^{(j)}x^{(i)}x^{(j)}}-\sum_{i=1}^{N}{\alpha^{(i)}}\\ s.t. \space& \sum_{i=1}^{N}{\alpha^{(i)}y^{(i)}=0}\\ &0\leq\alpha^{(i)}\leq C，i=1,2,...,N \end{aligned} \end{equation}\\ $$

从对偶问题的形式也可以看出来，相较于硬间隔SVM来说，只是对拉格朗日乘子的上限做了限制，上限就是 $C$

核方法

软间隔线性可分依然是线性可分，假如真实的数据是线性不可分的情况SVM能不能处理，怎么处理？比如说数据分布如下图(左)，这时候是数据线性不可分，但是在可视化图中是能够很清楚的知道这些数据应该怎么划分，这里超平面应该是一个圆，但是我们不能完全依赖数据可视化，超过3维肉眼就很难看出来了，这时候的一个思路是经过一个特殊的转化(下图 $\phi(x)$ )，把这些数据变成线性可分的(下图右)，那么就可以利用线性可分SVM来处理了，核方法就是这么处理的。其实核方法不是只在SVM中出现，核方法是一个纯粹的数学方法，其解决的问题就是 数据映射到高维空间中计算量过于复杂 的问题

根据线性可分SVM中推导的公式来看，最终的目标函数只是与 $x^{(i)},x^{(j)}$ 的内积有关，然后对于线性不可分的数据定义某种线性变化

$$ x\rightarrow \phi(x)\\ $$

把 $x$ 映射到高维空间中，目的是 为了让在低维空间中线性不可分的数据在映射后的高位空间中线性可分，映射后的内积就是 $<\phi(x^{(i)}),\phi(x^{(j)})>$ ，有了这个映射就可以在映射后的高维空间中做SVM的事情，但是这个不叫核方法。到这里其实仔细想一下就会发现一个问题，这个映射是要做“升维”的事儿，那么维度爆炸甚至是无穷维时怎么办，计算量会特别大，解决这个问题的方法才是核方法，具体的做法是在原始空间中找到一个函数 $\kappa$ ，使得

$$ \kappa(x^{(i)},x^{(j)})=<\phi(x^{(i)}),\phi(x^{(j)})>\\ $$

这样一来根本就不用去计算 $\phi(x)$ 了甚至不需要知道 $\phi$ 是怎么映射的就解决了维度爆炸带来的计算性能下降的问题，找到的这个函数 $\kappa$ 就叫做核函数。常用的核函数主要为以下3类

线性核，实际上就是没有做变换 $\kappa(x_1, x_2) = <x_1, x_2>$
高斯核，使用较为广泛，能够把原始特征映射到无穷维，也叫做径向基函数(Radial Basic Function，简称RBF) $\kappa(x_1, x_2) = exp(-\frac{||x_1-x_2||_2^2}{2\sigma^2})$
多项式核 $\kappa(x_1, x_2) = (<x_1, x_2>+R)^d$

这里拿多项式核举个例子，取 $R=0，d=2$ ，假设这里的 $x，y$ 是一个2维向量

$$ \begin{equation} \begin{aligned} \kappa(x,y) &= (<x, y>)^2\\ &=(x_1y_1+x_2y_2)^2\\\ &=x_1^2y_1^2+2x_1y_1x_2y_2+x_2^2y_2^2\\ &=<(x_1^2,\sqrt2x_1x_2,x_2^2),(y_1^2,\sqrt2y_1y_2,y_2^2) >\\ &=<\phi(x),\phi(y)> \end{aligned} \end{equation}\\ $$

可以看出来，核函数 $\kappa$ 可以避免在高维空间中做内积这种复杂的运算是因为核函数巧妙的避免了映射之后再做内积，而是直接给替代了，想对应的SVM的原始问题、对偶问题、超平面模型都会有所变化，即是将内积转变为其核函数

$$ x^{(i)}\cdot x^{(j)}\rightarrow \kappa(x^{(i)}, x^{(j)})\\ $$

软间隔对偶问题

$$ \begin{equation} \begin{aligned} \mathop{min}_{\alpha}\space &\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha^{(i)}\alpha^{(j)}y^{(i)}y^{(j)}\kappa(x^{(i)},x^{(j)})}-\sum_{i=1}^{N}{\alpha^{(i)}}\\ s.t. \space& \sum_{i=1}^{N}{\alpha^{(i)}y^{(i)}=0}\\ &0\leq\alpha^{(i)}\leq C，i=1,2,...,N \end{aligned} \end{equation}\\ $$

超平面模型

$$ f(x)=sign(\sum_{i=1}^{N}{\lambda^{*(i)}y^{(i)}\kappa(x\cdot x^{(i)})+b^*})\\ $$

总结

经过 SVM(一)从感知机到SVM损失函数 和 SVM(二)拉格朗日对偶式 和本文，对SVM做了简单的介绍，其实还有一些内容没有整理，比如求解对偶问题的 SMO算法(类似坐标轴下降的一种算法) ，还有 支持向量回归等等，这部分留给后面处理。当然SVM并不可能是万能的，也是有一定使用场景的

优点：

较适合解决高维特征的分类回归问题，因为SVM主要求解的是对偶问题，经过对偶问题之后高维度就转化成了样本量相关的问题
通过核方法来能够解决线性不可分问题

缺点：

还是因为对偶问题会把高维度转化成样本量相关的问题的原因，SVM并不适用于特别大的数据集
核函数的选择更像是玄学，并没有完备的理论依据来证明什么核函数适用于什么情况，所以往往需要尝试，利用交叉验证来选取更合适的核函数
较依赖好的特征工程，特别是缺失值

最后感谢李航老师的《统计学习方法第二版》，对我个人理解SVM有很大帮助。

😛

软间隔线性可分SVM

核方法

总结

about me