机器学习之支持向量机（Support Vector Machines, SVM）

前言： 学习笔记，记录下对于一些问题的记录和理解，复习和加深记忆用，挖坑补坑用。

参考：李航《统计学习方法》

基本内容

支持向量机是一种二类分类模型。学习策略是间隔最大化，可形式化为求解一个凸二次规划问题，或等价于最小化正则化的合页损失函数。

支持向量机从简至繁模型

线性可分支持向量机（硬间隔最大化）
线性支持向量机（软间隔最大化）
非线性支持向量机（核技巧+软间隔最大化）

从感知机模型到线性支持向量机

之前的博文参考：感知机模型

从感知机模型可知，当数据线性可分时，通过感知机学习算法，可以获得一个分离超平面，实现分类。但我们知道，在感知机模型中分离超平面的是不唯一的。那么怎么获得一个分离“效果最好”的超平面呢。

线性可分支持向量机解决了这个问题。它决定这一效果最好的超平面的方法是使得分类后的超平面的两侧的数据点与超平面的间隔最大。

对于间隔
- 函数间隔（会受放大倍数的影响，以至于对同一超平面可以有不同距离）
  $\hat \gamma_i=y_i(wx_i+b)$
- 几何间隔（归一化||w||，使之唯一确定）
  $\gamma_i = \frac{y_i}{||w||}(wx_i+b)=\frac{\hat \gamma_i}{||w||}$

因此就可以根据上面所述，在感知机模型的基础上，加上条件优化，使得几何间隔最大化。

得出线性支持向量机的约束最优化问题：
$\mathop{max}\limits_{w,b} \gamma \\ s.t. \ \ \ \frac{y_i}{||w||}(w x_i+b)\geq\gamma, \ \ \ i=1,2,...,N$
写作函数间隔形式：
$\mathop{max}\limits_{w,b} \frac{\hat \gamma}{||w||} \\ s.t. \ \ \ y_i(w x_i+b)\geq \hat \gamma, \ \ \ i=1,2,...,N$
也即：
$\mathop{max}\limits_{w,b} \frac{1}{||w||/\hat \gamma} \\ s.t. \ \ \ y_i(\frac{w}{\hat \gamma} x_i+\frac{b}{\hat \gamma})\geq 1, \ \ \ i=1,2,...,N$
等价于：
$\mathop{max}\limits_{w,b} \frac{1}{||w||} \\ s.t. \ \ \ y_i(w x_i+b)\geq 1, \ \ \ i=1,2,...,N$

线性可分支持向量机学习算法—硬间隔最大化

原始形式

(可参考感知机模型)

最优化问题求解 $w^* ，b^*$
$\mathop{min}\limits_{w,b} \ \frac{1}{2} ||w||^2 \\ s.t. \ \ \ y_i(w·x_i+b)-1 \geq 0, i=1,2,...,N$
结果
- 分离超平面
  $w^* x+b^* = 0$
- 决策函数
  $f(x)=sign(w^*x+b^*)$

对偶形式

对偶问题的转化推导
- 拉格朗日函数
$L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum\limits_{i=1}^N \alpha_i [y_i(w·x_i+b)-1]$
- 拉格朗日问题
$\mathop{min}_{w,b}\ \mathop{max}_\alpha L(w,b,\alpha)$
- 对偶问题
$\mathop{max}_\alpha \ \mathop{min}_{w,b}L(w,b,\alpha)$
- 求解
  
  对于 $\mathop{min}\limits_{w,b}L(w,b)$ :
  $\frac{\partial L(w,b)}{\partial w}=0\\ \frac{\partial L(w,b)}{b}=0$
  得到
  $w-\sum\limits_{i=1}^N \alpha_i y_i x_i = 0 \\ \sum\limits_{i=1}^N \alpha_i y_i = 0$
  拉格朗日函数变为
  $\begin{aligned} L(\alpha) &= \frac{1}{2}||w||^2 - \sum\limits_{i=1}^N \alpha_i [y_i(w·x_i+b)-1]\\ &=\frac{1}{2}||\sum\limits_{i=1}^N \alpha_i y_i x_i||^2-\sum\limits_{i=1}^N \alpha_i [y_i(||\sum\limits_{i=1}^N \alpha_i y_i x_i||·x_i+b)-1]\\ &=\frac{1}{2}\sum\limits_{j=1}^N \sum\limits_{i=1}^N \alpha_i \alpha_i y_i y_j (x_i·x_j)-\sum\limits_{i=1}^N\alpha_i y_i((\sum\limits_{j=1}^N\alpha_j y_j x_j)·x_i+b)+\sum\limits_{i=1}^N\alpha_i \\ &=-\frac{1}{2}\sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i·x_j)+\sum\limits_{i=1}^N \alpha_i \end{aligned}$ L(α)=21∣∣w∣∣2−i=1∑Nαi[yi(w⋅xi+b)−1]=21∣∣i=1∑Nαiyixi∣∣2−i=1∑Nαi[yi(∣∣i=1∑Nαiyixi∣∣⋅xi+b)−1]=21j=1∑Ni=1∑Nαiαiyiyj(xi⋅xj)−i=1∑Nαiyi((j=1∑Nαjyjxj)⋅xi+b)+i=1∑Nαi=−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+i=1∑Nαi
  对于极大化 $L(\alpha)$
  $\begin{aligned} \mathop{max}\limits_\alpha \ \ &L(\alpha) \ \ \ \Rightarrow \ \ \ -\mathop{min}\limits_\alpha L(\alpha)\\ \end{aligned}$
  因此等价的对偶问题为
  $\begin{aligned} \mathop{min}\limits_\alpha \ \ &\frac{1}{2}\sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i·x_j)-\sum\limits_{i=1}^N \alpha_i \\ s.t. \ \ &\sum\limits_{i=1}^N\alpha_i y_i = 0 \\ &\alpha_i \geq 0,\ \ i=1,2,...,N \end{aligned}$
一个定理（推导?）

若 $\alpha^*$ 是对偶问题的解，则有
$w^* = \sum\limits_{i=1}^N\alpha_i^* y_i x_i \\ b^* = y_j - \sum\limits_{i=1}^N\alpha_i^* y_i (x_i·y_j)$
对偶问题算法
- 构造上述对偶问题，得到 $\alpha^*$
- 根据 $\alpha^*$ ，按照定理计算出 $w^*，b^*$
- 最终结果
  
  分离超平面：
  $w^*·x + b^* = 0$
  分类决策函数：
  $f(x)=sign(w^*·x + b^*)$

线性支持向量机—软间隔最大化

以上是针对线性可分条件，对于一般的线性不可分情况不适用。

为了扩展到一般线性不可分情况下，使用软间隔最大化，即在函数间隔上加入松弛变量，对于松弛变量，在最优化问题上加入对于松弛变量的惩罚项，因此

原始形式

最优化问题

$\mathop{min}\limits_{w,b,\xi} \ \frac{1}{2} ||w||^2 + C \sum\limits_{i=1}^N \xi_i \\ s.t. \ \ \ y_i(w·x_i+b) \geq 1-\xi_i, i=1,2,...,N \\ \xi_i \geq 0,\ \ \ i=1,2,...,N$

结果
- 分离超平面
$w^*·x+b^*=0 \\$
- 分类决策函数
$f(x) = sign(w^*·x+b^*)$

对偶形式

最优化问题(推导过程同上)

$\begin{aligned}\mathop{min}\limits_\alpha \ \ &\frac{1}{2}\sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i·x_j)-\sum\limits_{i=1}^N \alpha_i \\s.t. \ \ &\sum\limits_{i=1}^N\alpha_i y_i = 0 \\&0 \leq \alpha_i \leq C,\ \ i=1,2,...,N\end{aligned}$

结果（求解过程使用SMO算法）
- 同理得到 $w^*, b^*$
$w^* = \sum\limits_{i=1}^N\alpha_i^* y_i x_i \\ b^* = y_j - \sum\limits_{i=1}^N\alpha_i^* y_i (x_i·y_j) \\$
- 分离超平面
$w^*·x+b^*=0$
- 分类决策函数
$f(x)=sign(w^*·x + b^*)$
引入对偶形式的好处：一方面可以高效率求解；另一方面方便引入核技巧

线性支持向量机—合页损失函数

上述线性支持向量机使用的学习策略是软间隔最大化，学习算法是凸二次规划。此外有个等价描述：最小化以下损失函数
$L(w,b) = \sum\limits_{i=1}^N[1-y_i(w·x_i+b)]_+ +\lambda||w||^2$
其中，合页损失函数：
$[z]_+ = \left\{ \begin{array}{ccc} z,\ \ \ z > 0 \\ z,\ \ \ z \leq 0 \end{array} \right.$
Q：为什么可以用此表示？

why？ （为什么可以用最小化该损失函数来学习线性支持向量机）

观察式子，很明显后面一项是正则化项，去掉不影响理解。前面部分，很明显是关于距离的表示。

先从最简单的模型理解，即对于感知机模型，可以使用类似的最小化损失函数
$L(w,b) = \sum\limits_{i=1}^N [-y_i(w·x_i+b)]_+$
$[-z]_+$ 表示的含义为，当为误分类点时，值为正；当为正确分类点时，值为0。因此对于最小化该损失函数，训练学习过程就是尽量使得所有点分类正确，得到损失函数最小值为 0。

再考虑去掉正则化项的合页损失函数
$L(w,b)=\sum\limits_{i=1}^N [1-y_i(w·x_i +b)]_+$
$[z]_+$ 表示的含义是，当样本点与分离超平面的函数距离大于1时（包含着正确分类的信息），值为0；当函数距离小于1或为负值（未正确分类）时，值为 $1-y_i(w·x_i+b)$ 。

先考虑线性可分情况，事实上，最小化上述损失函数，就等价于使所有样本点满足 $y_i(w·x_i+b)>0$ 即可，因为 $y_i(w·x_i+b)$ 为函数距离，随放大倍数而改变，因此只要满足 $y_i(w·x_i+b)>0$ ，就一定可以通过放大w,b确保 $y_i(w·x_i+b)>1$ ，从而确使损失函数最小化为0。这也侧面说明了函数间隔取 1 并不影响结果。

但很明显这样的 w,b 有无数个（不仅仅因为放大倍数的原因，刨去放大倍数，只要能使样本点正确分类的超平面对应的w,b都是满足条件的）。所以在线性可分的情况下，这是跟上面感知机模型最小化是等价的。

那么如何获得唯一的超平面呢，可通过加入正则化项来确使结果唯一。也即
$L(w,b) = \sum\limits_{i=1}^N[1-y_i(w·x_i+b)]_+ +\lambda||w||^2$
但此时有个问题，最小化此时的损失函数，等价于两种情况？（1. 全部正确分类 2.没有全部正确分类，但加入了更小的正则化项）。对于第一种情况比较好理解，对于第二种情况，理论上是不存在的（从下面问题等价可以知晓，但如何直观理解呢？**how?**换句话说，是否正则化项的加入都改变不了先满足前项最小的事实？应该是否）。这难以理解的一部分应该是因为前面 1 的原因，换句话说，加入正则项后貌似开始受 1 的影响了？

再考虑一般情况，即对于非严格的线性可分情况，其实理解过程与上相似。

值得注意的一点是：

于各种情况对损失函数最小化的贡献来说，正确分类第一，函数间隔小于1，次之，最后是误分类（函数间隔为负）。

因此最小化该损失函数，这样理解来说，似乎是我们想要的。

Q：为什么同软间隔最大化等价？

即证明
$\mathop{min}_{w,b}\ \sum\limits_{i=1}^N[1-y_i(w·x_i+b)]_+ +\lambda||w||^2$
等价于
$\mathop{min}\limits_{w,b,\xi} \ \frac{1}{2} ||w||^2 + C \sum\limits_{i=1}^N \xi_i （1）\\ s.t. \ \ \ y_i(w·x_i+b) \geq 1-\xi_i, i=1,2,...,N （2）\\ \xi_i \geq 0,\ \ \ i=1,2,...,N （3）$

证明：

令
$[1-y_i(w·x_i+b)]_+ = \xi_i$
得到条件（3）
$\xi_i\geq 0\ ，1-y_i(w·x_i+b)>0 \Rightarrow y_i(w·x_i+b)=1-\xi_i \\ \xi_i = 0\ ，1-y_i(w·x_i+b)\leq 0 \Rightarrow y_i(w·x_i+b)\geq 1-\xi_i$
等价条件（2）

最优化问题为
$\mathop{min}_{w,b} \ \ \sum\limits_{i=1}^N \xi_i + \lambda||w||^2$
令 $\lambda=\frac{1}{2C}$ 即可得到最优化问题（1）

反之，同理，因此等价。

非线性支持向量机—核函数

核函数的引入

下面是处理非线性的情况，很容易想到的思路是将线性不可分的数据通过某一个映射关系，映射为线性可分。而我们可以相信的是，对于线性不可分数据总在足够高维中存在着线性可分的超平面。而我们要做的就是找到这个映射。这是传统的思路。

以简单二维实例加以理解：

有如下训练数据，很明显该数据在二维情况下是线性不可分的。
机器学习之支持向量机（Support Vector Machines, SVM）

事实上以上数据是以圆 $(x_1-1)^2 + x_2^2 =1$ 为分界线，使用python生成的随机点。

为说明为题，便于理解，在已知事实的情况下，产生一个映射：
$z_1 = x_1^2,\ \ \ z_2=x_2^2, \ \ \ z_3=x_1$
那么，将以上训练数据点 $(x_1, x_2)$ 映射到三维空间 $(z_1, z_2, z_3)$ ，数据点分布使用python画出来为：

可以看出来，此时已经可以使用一个三维平面将其正确分类。在此三维空间中，数据点线性可分。超平面方程为 $z_1 + z_2 -2 z_1=0$ ，事实上，这与圆的方程是对应的。

当然，实际上，我们事先是不知道能够得到如此映射关系的。而且，对于上面圆（二次曲线）方程的更一般表示应该为：
$a_1x_1^2+a_1x_2^2+a_3x_1+a_4x_2+a_5x_1x_2+a_6=0$
也即对应的映射为 $R^2 \rightarrow R^5$ ：
$z_1=x_1^2,\ z_2=x_2^2,\ z_3=x_1,\ z_4=x_2,\ z_5=x_1x_2$
对应五维空间的线性方程为：
$a_1z_1+a_2z_2+a_3z_3+a_4z_4+a_5z_5+a_6=0$
当然，有些项是可以省略的。同样，这也只是针对于二次曲线的一般情况。

继续上面的例子中，假设我们已经得到了对应映射关系，那么针对线性可分情况下，使用线性可分支持向量机可以得到最优化问题：
$\mathop{min}\limits_\alpha \ \ \frac{1}{2}\sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_i \alpha_j y_i y_j(z_i·z_j)-\sum\limits_{i=1}^N \alpha_i$
这就是熟悉的支持向量机问题了，按照步骤求解即可。

所以总结一下，对于传统思路，就是先对数据进行高纬度线性可分映射，然后再使用线性支持向量机进行分类。
但这会存在问题：

映射关系的确定有点难计算，而且后续计算，还需要一步步地代入。
另外可以预想的是，会出现维度爆炸的情况，上述中我们仅仅映射到了三维，更一般情况下是五维，而这仅仅是在原始数据为二维的情况下的映射。当样本维度高时（通常情况就是如此），映射空间的维度将会是不可想象的爆炸多，会成指数型增长。势必会增加非常大的计算压力，而且当原始维度很高时，计算根本无法进行。

那么，如何解决上述问题，如何将其推广到更一般的情况呢？这就需要核函数了，发挥核技巧的强大作用了。

我们注意到，在上面传统思路求解的过程中，其实是不必要去关注具体的映射过程的。我们需要的就是得到上面的最优化问题就可以了，观察式子
$\mathop{min}\limits_\alpha \ \ \frac{1}{2}\sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_i \alpha_j y_i y_j(z_i·z_j)-\sum\limits_{i=1}^N \alpha_i$
其实，我们只需要知道 $z_i·z_j$ 的表达式就可以，而不必要先知道映射方程，然后在作内积（其实这样也是为了获得 $z_i·z_j$ 表达式而已）。

而 $z_i·z_j$ 就是核函数。具体定义参考书本。关于函数空间问题参考：机器学习基础补充知识

粗略说就是，若 $\phi(x)$ 为映射函数，那么核函数K(x, z)就是映射函数的内积，即
$K(x,z) = \phi(x)·\phi(z)$
核函数简化了内积运算，因为不再必要进行先一一映射再一一相乘的麻烦运算了，取而代之的是直接使用核函数带入计算即可，而且不必关注映射到高维线性可分的具体实现了（可理解为隐式映射）。一言蔽之，核函数跟映射没有关系，其只是用来对映射到高纬空间后的内积的直接运算。

核函数的选择

在理解核函数的引入后，可能会有个疑问，即是如何正好获得到核函数的？更确切说，怎么就能如此巧合地不加以分析计算映射关系，而直接得到核函数的表达式的？

那最初的例子作为理解，那么是如何在不了解映射关系的情况下得到核函数的。其实，答案很简单，就是一个非线性分类问题的核函数不是唯一的，不像最初例子给出的关系式那么完美，而是**通过经验和领域知识而直接选择既定的常用的核函数。这也是为什么选择核函数通常也需要验证其有效性。

常用核函数：

多项式核函数（polynomial kernel function）
$K(x,z) = (x·z+1)^p$
高斯核函数（Gaussian kernel function）
$K(x,z) = exp(-\frac{||x-z||^2}{2\sigma^2})$

注意：不同核函数肯定有不同作用和优缺点，到具体实践使用后和有所感悟时补充（!!!）。

非线性支持向量机算法

选择适当的核函数 K(x, z) 和参数 C
构造求解最优化问题

$\begin{aligned}\mathop{min}\limits_\alpha \ \ &\frac{1}{2}\sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_i \alpha_j y_i y_jK(x_i,x_j)-\sum\limits_{i=1}^N \alpha_i \\s.t. \ \ &\sum\limits_{i=1}^N\alpha_i y_i = 0 \\&0 \leq \alpha_i \leq C,\ \ i=1,2,...,N\end{aligned}$

结果（求解过程使用SMO算法）
- 得到$ w^, b^$
$w^*x = \sum\limits_{i=1}^N\alpha_i^* y_i K(x_i,x) \\b^* = y_j - \sum\limits_{i=1}^N\alpha_i^* y_i K(x_i,y_j) \\$
- 分离超平面
$w^*·x+b^*=0$
- 分类决策函数
$f(x)=sign(w^*·x + b^*)$

其他相关补充

序列最小最优化算法（sequential minimaloptimization， SMO）
Mercer定理
KKT条件

机器学习之支持向量机 （Support Vector Machines, SVM）