支持向量机(Support Vector Machine, SVM)：最通常状况（非线性）公式推导

时间 2020-08-08 标签支持向量机 support vector machine svm 通常状况非线性公式推导

看博客或教材时，总以为推导写的太简单，因此这里本身推导一下支持向量机的公式。部分推导会写在纸上，贴图上来，由于太长了，用latex敲实在是麻烦，若是哪里看不清楚或者哪里有误，还望评论指出，我及时修改。会不断更新的。算法

目录安全

三种基本的SVM：函数

三者关系：优化

核技巧：spa

推导code

超平面blog

三种基本的SVM：

分类	使用场景	备注
线性可分SVM	数据彻底线性可分	最原始、最基本的SVM
线性SVM	数据大多线性可分	加入一个扰动 $\varepsilon _{i}$
非线性SVM	数据线性不可分	引入核函数，最通常状况

三者关系：

非线性SVM的核函数 $K(x,z)=x^{T} \cdot z$ ，其就简化成了线性SVM；

线性SVM的扰动 $\varepsilon _{i}$ 恒等于0时，其就简化成了线性可分SVM；

核技巧：

对于数据线性不可分状况，基本思路是引入映射函数 $\varphi (x)$ ，把数据映射到更高维空间，在更高维空间进行分类，核函数定义为 $K(x,z)=\varphi(x) \cdot \varphi (z)$ ，即两个向量在特征空间（映射后空间）的内积，这种定义内积却不直接定义映射函数 $\varphi (x)$ 的技巧即为核技巧。为什么这样定义，看后面推导你就会发现，全部用到映射函数 $\varphi (x)$ 的场景，全是内积。

推导

下面推导最通常状况下的SVM（含有核函数和扰动）。

输入：

数据 $(x_{i},y_{i})$ ，i=1,2……m

求解：

超平面 $w^{T}\varphi (x_{i})+b$ ，也就是求解 $w^{T}$ 和

输出：

$y=sign(w^{T}\varphi (x_{i})+b)$

超平面

证实wT是法向量

这里提到的超平面长这样 $w^{T}x+b=0$ ，我比较熟悉的平面长这样 $y=a^{T}x+b$ ，通过移项变成 $[a^{T},-1]\begin{bmatrix} x \\ y \end{bmatrix}+b=0$ ，因此 $w^{T}x+b=0$ 中的x已经包含了x，y，即特征空间的全部坐标值，咱们利用的是整个特征空间肯定点与平面的关系， $w^{T}x+b=0$ 中虽然叫作x，可是却包含了y。

证实向量指向的方向就是正实例的一侧

设 $\varphi (x_{1})$ 为 $w^{T}\varphi (x)+b=0$ 平面上的点，该平面把特征空间分红两侧， $\varphi (x_{2})$ 为向量 $w^{T}$ 指向一侧的点。

则 $w^{T}\varphi (x_{1})+b=0$ ，设 $w^{T}\varphi (x_{2})+b=a$

上述两式相减获得 $w^{T}(\varphi (x_{1})-\varphi (x_{2}))=-a$

因为 $w^{T}(\varphi (x_{1})-\varphi (x_{2}))<0$

因此 $w^{T}\varphi (x_{2})+b=a>0$ 。

下图以二维为例。

推导点到平面距离公式

定义函数间隔为 $y_{i}(w^{T}\varphi (x_{i})+b)$ ，不难看出这是一个相对距离，去掉了点到超平面的距离公式中的分母，只要该数据点的分类断定正确， $y_{i}(w^{T}\varphi (x_{i})+b)$ 与 $\left | w^{T}\varphi (x_{i})+b \right |$ 是等价的。

优化函数的构建

要引出带 $\varepsilon _{i}$ 的更通常状况的优化函数，咱们须要先讨论一种更简单的场景，若数据在通过 $\varphi (x)$ 映射后，在高维空间彻底线性可分，则利用函数间隔设置一个安全距离，该安全距离的值设为1，也就是支持向量（在彻底线性可分时，支持向量就是距离分割超平面函数间隔为1的数据点，也是离分割平面最近的点，没什么神秘，就是数据映射的点，超平面上的全部点，不特指训练集中的数据点）到超平面的函数间隔等于1，以下图：

其他点到分割超平面的函数间隔就大于1，即对全部数据点知足下式：

$y_{i}(w^{T}\varphi (x_{i})+b)\geqslant 1$

为什么不用几何间隔定义也很容易想清楚，几何间隔是个绝对的距离，数据多种多样，根本没法保证支持向量到分割平面的几何间隔等于1，但函数间隔这一相对距离就能够。

因为 $y_{i}=\pm 1$ ，故

$\left | w^{T}\varphi (x_{i}) \right +b|\geqslant 1$

此时，点到超平面距离

$l=\frac{\left | w^{T}\varphi (x_{i})+b \right |}{\left \| w^{T} \right \|}\geqslant \frac{1}{\left \| w^{T} \right \|}$

两边支持向量的间隔就是

$2l=\frac{2}{\left \| w^{T} \right \|}$
因此咱们获得了咱们要优化的目标函数便是 $\frac{2}{\left \| w^{T} \right \|}$ ，它越大，SVM安全距离越大，容错率越高，SVM越健壮。

$max~~\frac{2}{\left \| w^{T} \right \|}$

$s.t.~~y_{i}(w^{T}\varphi (x_{i})+b)\geqslant 1,i=1,2\dots m$

等价于

$min~~\frac{\left \| w^{T} \right \|}{2}$

$s.t.~~y_{i}(w^{T}\varphi (x_{i})+b)\geqslant 1,i=1,2\dots m$

此时咱们在进一步考虑，即便进行 $\varphi (x)$ 映射后，少部分数据在高维空间仍然线性不可分，但绝大部分 $\varphi (x_{i})$ 知足 $y_{i}(w^{T}\varphi (x_{i})+b)\geqslant 1$ ，这时咱们引入一个扰动 $\varepsilon _{i}(\varepsilon _{i}\geq 0)$ ，允许函数间隔不彻底知足大于等于1，即：

$y_{i}(w^{T}\varphi (x_{i})+b)\geqslant 1-\varepsilon _{i},i=1,2\dots m$

对应的优化函数也应改成：

$min~~\frac{\left \| w^{T} \right \|}{2}+C\sum_{i=1}^{m}\varepsilon _{i}$

$s.t.~~y_{i}(w^{T}\varphi (x_{i})+b)\geqslant 1-\varepsilon _{i},i=1,2\dots m$

$~~~~\varepsilon _{i}\geqslant 0$

C为正则化系数，需手动调节，直观来看，咱们优化的目标函数要求 $\left \| w^{T} \right \|$ 尽量的小，同时 $\varepsilon _{i}$ 也要尽量的小，即咱们容许扰动 $\varepsilon _{i}$ 的存在，但 $\varepsilon _{i}$ 越小越好，最好没有。

下面讨论含 $\varepsilon _{i}$ 这一通常状况。

含有不等式约束的优化

这一步用到了拉格朗日乘数法及其对偶问题，KKT条件。

利用拉格朗日乘数法，构造：

$\tiny L(w,b,\varepsilon _{i},\alpha _{i},\mu _{i})=\frac{1}{2}\left \| w^{T} \right \|+C\sum_{i=1}^{m}\varepsilon _{i}+\sum_{i=1}^{m}\alpha _{i}[1-\varepsilon _{i}-y_{i}(w^{T}\varphi (x_{i})+b)]+\sum_{i=1}^{m}\mu _{i}(-\varepsilon _{i})$

注意不等式约束化为小于等于0的标准结构。

求 $minL(w,b,\varepsilon _{i},\alpha _{i},\mu _{i})$ ，其原始问题为：

$\min_{w,b,\varepsilon _{i}} ~\max_{\alpha _{i},\mu _{i}}~ L(w,b,\varepsilon _{i},\alpha _{i},\mu _{i})$

对应对偶问题为：

$\max_{\alpha _{i},\mu _{i}}~\min_{w,b,\varepsilon _{i}} ~ L(w,b,\varepsilon _{i},\alpha _{i},\mu _{i})$

注意原始问题与 $minL(w,b,\varepsilon _{i},\alpha _{i},\mu _{i})$ 等价，同时这里知足原始问题与对偶问题等价的条件，因此对偶问题也与求 $minL(w,b,\varepsilon _{i},\alpha _{i},\mu _{i})$ 的优化问题等价，因此下面经过求解对偶问题来求解 $minL(w,b,\varepsilon _{i},\alpha _{i},\mu _{i})$ 。注意 $\left \| w^{T} \right \|=w^{T} \cdot w$

如今求 $minL(w,b,\varepsilon _{i},\alpha _{i},\mu _{i})$ 等价于求

这里写一下KKT条件有哪些：

9式10式中的两个乘子必有一个为0，同时根据9,10,11,12四个式子以及 $\alpha _{i}+\mu _{i}=C$ ，咱们能够获得以下推论：

$\alpha _{i}$ 的值	$\mu _{i}$ 的值	$\varepsilon _{i}$ 的值	$y_{i}(w^{T}\varphi (x_i)+b)$ 的值	$(x_{i},y_{i})$
=0	=C	=0	>1	在安全间隔外，数据十分安全，断定很准确
(0,C)	(0,C)	=0	=1	为支持向量
=C	=0	(0,1)	(0,1)	在安全间隔内，断定仍正确
=C	=0	=1	=0	在分割面上
=C	=0	>1	<0	被误判

SMO

SMO就是一种继续求解上面的优化问题的的启发式方法，主要包含两个过程，第一步找到两个要优化的 $\alpha_{1}$ 和 $\alpha_{2}$ ，固定剩余m-2个 $\alpha$ ；第二步经过优化算法优化 $\alpha_{1}$ 和 $\alpha_{2}$ 。不断迭代这两步，直到全部的 $\alpha$ 知足KKT条件。

$\alpha_{1}$ 的肯定为外层循环，选KKT条件被破坏最大的 $\alpha$ ，先遍历 $0<\alpha_{i}<C$ ，若是都不符合要求，遍历整个数据集。

$\alpha_{2}$ 的肯定为内层循环，此时 $\alpha_{1}$ 已经肯定，要选出使得 $L(w,b,\varepsilon _{i},\alpha _{i},\mu _{i})$ 降幅最大的 $\alpha$ ，若找不到合适的 $\alpha_{2}$ ，就换一个 $\alpha_{1}$ ，从新走外层循环。

假设 $\alpha_{1}$ 和 $\alpha_{2}$ 已经选出，下面的思路是，使用旧的 $\alpha_{1}^{old}$ 和 $\alpha_{2}^{old}$ 以及固定了的 $\alpha_{3} \dots \alpha_{m}$ ，找出新的 $\alpha_{1}^{new}$ 和 $\alpha_{2}^{new}$

因为 $\alpha_{3} \dots \alpha_{m}$ 已经固定，不妨令 $\alpha _{1}y_{1}+\alpha _{2}y_{2}=t$ ，t为定值（根据 $\sum_{i=1}^{m}\alpha _{i}y_{i}=0$ ，t是由 $\alpha_{3} \dots \alpha_{m}$ 以及 $y_{3} \dots y_{m}$ 肯定），下面把 $\alpha_{1}$ 和 $\alpha_{2}$ 筛出来，同时扔掉不含 $\alpha_{1}$ 和 $\alpha_{2}$ 的其他项（用直线画出，下一步自动去掉），时刻记着 $y_{i}^{2}=1$ 。

因为 $\alpha _{1}y_{1}+\alpha _{2}y_{2}=t$ ，因此 $\alpha _{1}y_{1}^{2}+\alpha _{2}y_{2}y_{1}=ty_{1}$ ，进一步获得 $\alpha _{1}=ty_{1}-\alpha _{2}y_{1}y_{2}$ ，带入上面的结果继续化简：

上式对 $\alpha _{2}$ 求偏导，令结果等于0，即

下面分状况讨论。

1. $k_{11}+k_{22}-2k_{12}>0$ 时，

设超平面为，即 $g(x)=w^{T}\varphi (x)+b=\sum_{i=1}^{m}\alpha _{i}y_{i}k(x,x_{i})+b$

进一步化简

咱们的目标是用旧的 $\alpha _{1}^{old}$ 和 $\alpha _{2}^{old}$ 更新出新的 $\alpha _{1}^{new}$ 和 $\alpha _{2}^{new}$ ，且 $\alpha _{1}^{old}y_{1}+\alpha _{2}^{old}y_{2}=t$ ， $\alpha _{1}^{new}y_{1}+\alpha _{2}^{new}y_{2}=t$ ，因为暂时未考虑用导数获得的 $\alpha _{2}^{new}$ 是否在做用域内，因此用 $\alpha _{2}^{new,unc}$ 来表示这一中间状态，把 $t=\alpha _{1}^{old}y_{1}+\alpha _{2}^{old}y_{2}$ 代入上式继续化简，

目前约束 $\alpha _{2}$ 的有以下不等式

接下来就要讨论 $\alpha _{2}$ 的做用域

2. $k_{11}+k_{22}-2k_{12}\leq 0$ 时

根据二次函数与一次函数图像， $\alpha _{2}^{new}$ 只可能在边界上出现，即上面讨论的L或H，代入计算两点计算L，取最小的那个就能够了

求出 $\alpha _{2}^{new}$ 以后， $\alpha _{1}^{new}$ 由下式计算求出：（牢记 $\alpha _{1}^{new}y_{1}+\alpha _{2}^{new}y_{2}=t$ ，且 $y_{i}^{2}=1$ ）

$\alpha _{1}^{new}=ty_{1}-\alpha _{2}^{new}y_{1}y_{2}=(\alpha _{1}^{old}y_{1}+\alpha _{2}^{old}y_{2})y_{1}-\alpha _{2}^{new}y_{1}y_{2}$

每一次更新 $\alpha _{1}$ 和 $\alpha _{2}$ ，还要同步更新超平面与 $E_{i}$

$g(x)=w^{T}\varphi (x)+b=\sum_{i=1}^{m}\alpha _{i}y_{i}k(x,x_{i})+b$

$E_{i}=g(x_{i})-y_{i}$

不难看出主要任务就是更新b，b的更新公式推导以下：

至此，全部推导大体讲解完毕，但愿没有把大家讲糊涂吧，我我的以为写得已经很详细了。