2.3 SVM算法原理

学习目标

• 知道SVM中线性可分支持向量机
• 知道SVM中目标函数的推导过程
• 了解朗格朗日乘子法、对偶问题
• 知道SVM中目标函数的求解过程

1 定义输入数据

假设给定一个特征空间上的训练集为：

其中，$(x_i,y_i)$称为样本点。

• $x_i$为第i个实例（样本），

• $y_i$为$x_i$的标记：

  • 当$y_i=1$时，$x_i$为正例
  • 当$y_i=-1$时，$x_i$为负例

至于为什么正负用（-1，1）表示呢？

其实这里没有太多原理，就是一个标记，你也可以用(2，-3)来标记。只是为了方便，$y_i/y_j=y_i*y_j$的过程中刚好可以相等，便于之后的计算。）

2 线性可分支持向量机

给定了上面提出的线性可分训练数据集，通过间隔最大化得到分离超平面为 :$y(x)=w^T\Phi(x)+b$

相应的分类决策函数为： $f(x)=sign(w^T\Phi(x)+b)$

以上决策函数就称为线性可分支持向量机。

这里解释一下$\Phi(x)$这个东东。

这是某个确定的特征空间转换函数，它的作用是将x映射到更高的维度，它有一个以后我们经常会见到的专有称号”核函数“。

比如我们看到的特征有2个：

$x1,x2$,组成最先见到的线性函数可以是$w_1x_1+w_2x_2$.

但也许这两个特征并不能很好地描述数据，于是我们进行维度的转化，变成了$w_1x_1+w_2x_2+w_3x_1x_2+w_4x_1^2+w_5x_2^2$.

于是我们多了三个特征。而这个就是笼统地描述x的映射的。

最简单直接的就是：$\Phi(x)=x$

以上就是线性可分支持向量机的模型表达式。我们要去求出这样一个模型，或者说这样一个超平面y(x),它能够最优地分离两个集合。

其实也就是我们要去求一组参数（w,b),使其构建的超平面函数能够最优地分离两个集合。

如下就是一个最优超平面：

又比如说这样：

阴影部分是一个“过渡带”，“过渡带”的边界是集合中离超平面最近的样本点落在的地方。

3 SVM的计算过程与算法步骤

3.1 推导目标函数

我们知道了支持向量机是个什么东西了。现在我们要去寻找这个支持向量机，也就是寻找一个最优的超平面。

于是我们要建立一个目标函数。那么如何建立呢？

再来看一下我们的超平面表达式： $y(x)=w^T\Phi(x)+b$

为了方便我们让：$\Phi(x)=x$

则在样本空间中，划分超平面可通过如下线性方程来描述：$w^Tx+b=0$

• 我们知道为法向量，决定了超平面的方向；

• b为位移项，决定了超平面和原点之间的距离。

• 显然，划分超平面可被法向量w和位移b确定，我们把其记为（w,b）.

样本空间中任意点x到超平面（w,b）的距离可写成

假设超平面（w, b）能将训练样本正确分类，即对于$(x_i, y_i)\in D$，

• 若$y_i=+1$，则有$w^Tx_i+b>0$;
• 若$y_i=-1$，则有$w^Tx_i+b<0$;

令

如图所示，距离超平面最近的几个训练样本点使上式等号成立，他们被称为“支持向量"，

两个异类支持向量到超平面的距离之和为:；

它被称为“”间隔“”。

欲找到具有最大间隔的划分超平面，也就是要找到能满足下式中约束的参数w和b，使得$\gamma$最大。

即：

显然，为了最大化间隔，仅需要最大化，这等价于最小化。于是上式可以重写为：

这就是支持向量机的基本型。

拓展：什么是$||w||$?

链接：向量与矩阵的范数

3.2 目标函数的求解

到这一步，终于把目标函数给建立起来了。

那么下一步自然是去求目标函数的最优值.

因为目标函数带有一个约束条件，所以我们可以用拉格朗日乘子法求解。

3.2.1 朗格朗日乘子法

啥是拉格朗日乘子法呢？

拉格朗日乘子法 (Lagrange multipliers)是一种寻找多元函数在一组约束下的极值的方法.

通过引入拉格朗日乘子，可将有 d 个变量与 k 个约束条件的最优化问题转化为具有 d + k 个变量的无约束优化问题求解。

朗格朗日乘子法举例复习

经过朗格朗日乘子法，我们可以把目标函数转换为：

其中，上式后半部分：

走到这一步，这个目标函数还是不能开始求解，现在我们的问题是极小极大值问题

3.2.2 对偶问题

我们要将其转换为对偶问题，变成极大极小值问题：

从 变为：

参考资料：https://wenku.baidu.com/view/7bf945361b37f111f18583d049649b6649d70975.html

如何获取对偶函数？

• 首先我们对原目标函数的w和b分别求导：
  • 原目标函数：
  • 对w求偏导：
  • 对b求偏导：

• 然后将以上w和b的求导函数重新代入原目标函数的w和b中，得到的就是原函数的对偶函数：

• 这个对偶函数其实求的是：中的$minL(w,b)$部分（因为对w,b求了偏导）。

• 于是现在要求的是这个函数的极大值max(a),写成公式就是：

• 好了，现在我们只需要对上式求出极大值$\alpha$，然后将$\alpha$代入w求偏导的那个公式：

• 从而求出w.

• 将w代入超平面的表达式，计算b值；

• 现在的w,b就是我们要寻找的最优超平面的参数。

3.2.3 整体流程确定

我们用数学表达式来说明上面的过程：

• 1）首先是求的极大值。即：

注意有两个约束条件。

• 对目标函数添加符号，转换成求极小值：

• 2）计算上面式子的极值求出$\alpha^*$;

• 3）将$\alpha^*$代入，计算w,b

• 4）求得超平面：

• 5）求得分类决策函数：

4 举例

给定3个数据点：正例点$x1=(3,3),x2=(4,3)$,负例点$x3=(1,1)$,求线性可分支持向量机。 三个点画出来：

1) 首先确定目标函数

2) 求得目标函数的极值

• 原式：
• 把数据代入：
• 由于：

• 化简可得：

• 对$\alpha_1,\alpha_2$ 求偏导并令其为0，易知$s(\alpha_1,\alpha_2)$在点（1.5， -1）处取极值。

• 而该点不满足条件$\alpha_2>=0$,所以，最小值在边界上达到。

  • 当$\alpha_1=0$时，最小值$s(0,\frac{2}{13})=-\frac{2}{13}=-0.1538$
  • 当$\alpha_2=0$时，最小值$s(\frac{1}{4},0)=-\frac{1}{4}=-0.25$

• 于是，$s(\alpha_1,\alpha_2)$在$\alpha_1=0, \alpha_2=0$时达到最小，此时：

  • $\alpha_3 = \alpha_1+\alpha_2 = \frac{1}{4}$

3) 将求得的极值代入从而求得最优参数w,b

• $\alpha_1 = \alpha_3 = \frac{1}{4}$对应的点$x_1,x_3$就是支持向量机
• 代入公式：
  • 将$\alpha$结果代入求解：
  • 
  • 平面方程为：$0.5x_1+0.5x_2-2=0$

4) 因此得到分离超平面为

• $0.5x_1+0.5x_2-2=0$

5) 得到分离决策函数为：

• $f(x)=sign(0.5x_1+0.5x_2-2)$

ps:参考的另一种计算方式： https://blog.csdn.net/zhizhjiaodelaoshu/article/details/97112073

3 小结

• SVM中目标函数

  • 

• SVM中目标函数的求解过程

  • 1）首先是求的极大值。即：

  

  注意有两个约束条件。

  • 对目标函数添加符号，转换成求极小值：

  

  • 2）计算上面式子的极值求出$\alpha^*$;

  • 3）将$\alpha^*$代入，计算w,b

  

  • 4）求得超平面：

  

  • 5）求得分类决策函数：