支持向量机 (Support Vector Machine)

作者: ZzzZBbbB | 来源:发表于2020-04-18 12:04 被阅读0次

SVM
SVM
支持向量机&&聚类
机器学习——libSVM（一）
SVM支持向量机
支持向量机SVM
核函数与支持向量机入门
18、SVM（支持向量机）
机器学习-----支持向量机
机器学习代码实现 SVM (5)

SVM俗语：

SVM有三宝：间隔、对偶、核技巧

SVM的由来

对于线性可分的问题，一般可以使用PLA得到解决，但是根据其原理可以得到，PLA只是负责得到一个线性可分的线/超平面，但是对于这根线/超平面，并不能保证最好。

所以对于线性可分数据来说，有无数条线/平面满足条件，但是最完美（最完美的意思表示在在新的数据上拟合效果最好）只有一条, 鲁棒性最好

margin：
the distance of hyperplane to its closest point
has at least 2 closest points (one is a positive point and one is a negative point)

总结一下
SVM = hyperplane + maximum margin

SVM关键词

监督学习，二分类器，学习策略：间隔最大化

SVM的目标函数

对于二维平面来说，通过一条直线 $y=ax+b$ 可以将平面分成两部分，一部分数据为正，一部分数据为负，由此进行拓展，对于 $d$ 维的 $x$ ，其超平面的方程为：
$w^{T} x+b=0$
与之超平面对应的分类模型为
$f(w,b) = sign(w^{T} x+b)$

首先明确一点 $w$ 垂直与所求的超平面：
证明：任意取超平面上的两点 $x_{1}$ , $x_{2}$ ，其构成向量 $x_{1}-x_{2}$
$w^{T} x_{1}+b=0$

$w^{T} x_{2}+b=0$

两个公式相减，得到 $w^{T} (x_{1}-x_{2})= 0$

为了后续方便计算和说明，这里做一个假设
$w^{T} x_{n}+b=1$ 其中 $x_{n}$ 为距离超平面最近的正类点

进一步说明： $w^{T} x_{n}+b$ 可以为任何值，但是由于已经确定了 $x_{n}$ 为距离超平面最近的正类点，所以即使结果为10或者为100或者任意大于1的值，只要对其进行归一化，并不会对其他的点有任何影响（主要就是强调一个相对的概念）。

1/||w||的由来.png

$w^{T} (x_{n}-x) = w^{T} (a+c) =w^{T} c = ||w||*||c||$

$||c|| = \frac{1}{\|\vec{w}\|}$

所以距离超平面最近的点与超平面的距离为 $\frac{1}{\|\vec{w}\|}$ ,也就是所谓的maximum margin的的表达，于是SVM的目标函数则找到了，即
$max \frac{1}{\|\vec{w}\|}$

SVM目标函数的转化

虽然找到了SVM的目标函数 $\frac{1}{\|\vec{w}\|}$ ，并且想要找到其的最大值，但是不要忘记一个假设前提， $w^{T} x_{n}+b=1$ , 其限制了与超平面最近的正类点，与其说是限制了与超平面最近的正类点，不如说是限制了所有的点，也就是说，除开最近的点 $w^{T} x_{n}+b=1$ ，其他点的得到的结果必须比1大，也就是目标函数扩展成：

（1）
$\max \frac{1}{\|\vec{w}\|}$

$s.t. \min |w^{T} x_{i}+b|=1 ,i = 1...N$ 其中N表示数据点的总数

我们对其进行进一步转化
（2）

$\min ||w||$

$s.t. \min |w^{T} x_{i}+b|=1 ,i = 1...N$

我们对第（2）中第二个限制进行分解，得到
(3)

$\min ||w||$

$\forall i , |w^{T} x_{i}+b| \geq1 ,i = 1...N$

这里需要解释一下（2）到（3）的过程，其实严格来说（2）的限制和（3）的限制其实不对等，因为（2）中说明是最近的点距离为1，但是（3）中说明的是所有点距离大于等于1，这里是对于（2）来说是一个充分不必要条件，唯一的风险就是所有的点都比1大，举个例子，比如说一共5个点，对于（2）的话距离的列表可能为[1,2,3,4,5]，对于（3）来说可能为[10,20,30,40,50]。

这里就需要重新回到我们之前提到的相对距离的概念了，这个结果10的得到其实是 $w^{T} x_{i}+b = 10$ ，所以只要将 $w$ 和 $b$ 的除以10，最近距离的点结果依旧是1，所以在这里的话（2）和（3）的限制是相等的。

对（3）进一步转化得到（4），这里还进行一步转化的原因是为了利用已有的凸优化理论，使用1/2是为了方便后续计算
（4）
$\min \frac{1}{2} w^{T} \cdot w$

$\forall i , |w^{T} x_{i}+b| \geq1 ,i = 1...N$

这里我们可以发现其实限制有N个， $|w^{T} x_{i}+b| \geq1$ 带上绝对值符号不利于后续的计算，所以对其进行分解，
当point为正类时， $w^{T} x_{i}+b \geq1$ ， $y_{i} = +1$
当point为正类时， $w^{T} x_{i}+b \leq1$ ， $y_{i} = -1$
所以限制转化为
$\forall i , y_{i} (w^{T} x_{i}+b) \geq1 ,i = 1...N$

这样目标函数求解问题得到的最终的完美形式：

$\min \frac{1}{2} w^{T} \cdot w$

$\forall i , y_{i} (w^{T} x_{i}+b) \geq1 ,i = 1...N$

优化问题求解（数学背景）

通过上述一系列的转化，可以发现，最终目标函数的求解本质上是一个线性规划的优化问题，其中给定的约束有 $N$ 个（ $N$ 个点，所以有 $N$ 个不等式），未知参数有 $d+1$ 个（ $d$ 个 $w$ 和 $1$ 个 $b$ )，目标函数是二次的。

拉格朗日乘子法

拉格朗日乘子法：有约束情况下求函数极值的方法,这里借助拉格朗日乘子法引出对偶问题
https://www.youtube.com/watch?v=lDehPPIgQpI
https://charlesliuyx.github.io/2017/09/20/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%B3%95%E5%92%8CKKT%E6%9D%A1%E4%BB%B6/

这里我们将原问题称为 $p1$ ,
$p1$ 的拉格朗日函数 $p2$ 为（更多信息参考上述链接，这里直接给出结论）：
$L(w, b, \lambda)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left[1-y_{i}\left(w^{T} x_{i}+b\right)\right]$

$\lambda_{i} \geq 0$

$1- y_{i}(w^{T} x_{i}+b) \leq 0$

最小化问题 $p1$ : $\min_{w, b} \frac{1}{2} w^{T} \cdot w$ 转化为 $p2:$ $\min _{w, b} \max _{\lambda} L(w, b ,\lambda)$
$p1$ 对 $w, b$ 的函数， $w,b$ 为自变量
$p2$ 首先以 $\lambda$ 为自变量求 $L$ 的最大值 $L1$ ，随后以 $w,b$ 为自变量求得到的 $L1$ 中的最小值，其本质上还是对 $w, b$ 的函数

使用拉格朗日乘子的好处：
将带约束的问题转化为无约束的问题，这里指的带约束是指对参数 $w,b$ 的限制条件

但是描述 $p2$ 的时候可以知道其实是带了 $1- y_{i}(w^{T} x_{i}+b) \leq 0$ ，这样子的话其实还是会有对参数 $w,b$ 的约束，其实这个约束可以舍去，因为函数 $L$ 天然的带有 $1- y_{i}(w^{T} x_{i}+b) \leq 0$ 约束

解释：https://www.youtube.com/watch?v=WeoASoHnTpc&list=PLOxMGJ_8X74Z1N3OcacUaCxiXaGNHtFw2&index=2

Lagrange的奇妙之处.png

对偶的引出

目标函数是二次，约束条件是线性，=> 凸二次规划问题 (QPP,Quadratic programming problem)，理想情况可以使用一些QP的套件直接进行求解得到答案，但是存在样本维度过高或者样本数很多，或者存在样本特征升维的一些情况，QP可能就不太能够直接求解，由此引入了对偶求解的概念。

由于将问题 $p1$ 转化成了 $p2$ ,为了求解的方便，可以将 $p2$ 转化为其对偶问题 $p3$

$p2: \min _{w, b} \max _{\lambda} L(w, b ,\lambda)$

$p3: \max _{\lambda} \min _{w, b} L(w, b ,\lambda)$

这里需要提及一个关于对偶问题的性质：
1.弱对偶性——对偶问题 $\leqslant$ 原问题
$\max \min L \leqslant \min \max L$

简单的来说就是小的里面最大的小不会比大的里面最小的大（鸡头<凤尾）
证明：
https://www.youtube.com/watch?v=bscvk5n_TsM&list=PLOxMGJ_8X74Z1N3OcacUaCxiXaGNHtFw2&index=5

2.强对偶性
$\max \min L = \min \max L$

凸二次函数优化问题 + 约束线性 ---> 满足强对偶关系

根据上述的定理可以发现通过这样一步的对偶问题转换，我们把本来需要求的以 $\lambda$ 为参数的 $L$ 的最大值后以以 $w,b$ 为参数的最小值(本质上未知数是 $w,b$ ) 转换成
以 $w,b$ 为参数的 $L$ 的最小值后以 $\lambda$ 为参数的最大值(本质上未知数是 $\lambda$ )