【南瓜书ML】(task5)支持向量机的数学推导（更新ing）

学习总结

SVM中的求解过程：

• 拉格朗日乘子法：把约束条件搞到目标函数里面去。
• KKT条件：把约束条件为不等式的，转变为约束条件为等式。
• 拉格朗日对偶：把不容易解决的问题，转变为容易解决的对偶问题。
• 核函数：把本来线性不可分的点，投射到更高维度上去，使其变得线性可分。

一、间隔与支持向量

支持向量机SVM是20世纪90年代在计算机界发展起来的一种分类算法，在许多问题中都被证明有较好的效果，被认为是适应性最广的算法之一。

支持向量机的基本原理：如上图，白色和蓝色的点各为一类，如果数据本身是线性可分的，让两类的点分开的超平面有很多，但现在我们的目标是找到一个【最大间隔超平面】，即该分割平面距离最近的观测点最远：

根据距离超平米那最近的点，只要同时缩放w和b可以得到：$w^T{x}_1+b=1$与$w^T{x}_2+b=-1$，因此：

$$\begin{array}{l}{w}^T{x}_1+b=1\\ w^T{x}_2+b=-1\\ \left(w^T{x}_1+b\right)-\left(w^T{x}_2+b\right)=2\\ w^T\left(x_1-x_2\right)=2\\ \begin{array}{l}{w}^T\left(x_1-x_2\right)=\Vert w{\Vert }_2{\Vert x_1-x_2\Vert }_2\cos \theta =2\\ {\Vert x_1-x_2\Vert }_2\cos \theta =\frac{2}{\Vert w{\Vert }_2}\end{array}\\ \begin{array}{l}{d}_1=d_2=\frac{{\Vert x_1-x_2\Vert }_2\cos \theta }{2}=\frac{\frac{2}{\Vert w{\Vert }_2}}{2}=\frac{1}{\Vert w{\Vert }_2}\\ d_1+d_2=\frac{2}{\Vert w{\Vert }_2}\end{array}\end{array}$$

由此可知道SVM模型的具体形式：
$$\begin{array}{rl}\underset{w,b}{\min }& \frac{1}{2}\Vert w{\Vert }^2\\ \text{ s.t. }& y^{(i)}\left(w^T{x}^{(i)}+b\right)\ge 1,i=1,\dots ,n\end{array}$$

几个概念：
（1）支持向量：距离超平面最近的几个训练样本满足下面条件。
假设超平面 $(w,b)$ 能将训练样本正确分类, 即对于 $\left(x_i,y_i\right)\in D$, 若 $y_i=+1$, 则有 $w^T{x}_i+$$b>0$, 若 $y_i=-1$, 则有 $w^T{x}_i+b<0$, 令：
$$\{\begin{array}{ll}{w}^T{x}_i+b⩾+1,& y_i=+1\\ w^T{x}_i+b⩽-1,& y_i=-1\end{array}$$

（2）间隔：两个异类支持向量超平面的距离之和 $\gamma =\frac{2}{\Vert w\Vert }$

（3）SVM的目标函数：找到最大间隔的划分超平面, 需要求解参数 $w$ 和 $b$ 使得 $\gamma$ 最大, 目标函数如下:
$$\begin{array}{lc}{\min }_{w,b}& \frac{1}{2}\Vert w{\Vert }^2\\ \text{ s.t. }& y_i\left(w^T{x}_i+b\right)⩾1,i=1,2,\dots ,m\end{array}$$

二、转为对偶问题后的求解

可以将上面SVM目标形式中的约束条件写为: $g_i(w)=-y^{(i)}\left(w^T{x}^{(i)}+b\right)+1\le 0$
可以将优化问题拉格朗日化
$$\mathcal{L}(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2-\sum _{i=1}^n{\alpha }_i\left[y^{(i)}\left(w^T{x}^{(i)}+b\right)-1\right]$$
因此：
$$\mathcal{L}(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2-\sum _{i=1}^n{\alpha }_i\left[y^{(i)}\left(w^T{x}^{(i)}+b\right)-1\right]$$欲构造 $dual$ 问题, 首先求拉格朗日化的问题中 $\mathrm{w}$ 和 $\mathrm{b}$ 的值, 对 $\mathrm{w}$ 求梯度, 令梯度为 0, 可求得 w:
对 b 求梯度, 令梯度为 0, 可得：
$$\frac{\partial }{\partial b}\mathcal{L}(w,b,\alpha )=\sum _{i=1}^n{\alpha }_i{y}^{(i)}=0$$

将 $\mathrm{w}$ 带入拉格朗日化的原问题可得
$$\begin{array}{l}\mathcal{L}(w,b,\alpha )={\sum }_{i=1}^n{\alpha }_i-\frac{1}{2}{\sum }_{i,j=1}^n{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_j{\left(x^{(i)}\right)}^T{x}^{(j)}-b{\sum }_{i=1}^n{\alpha }_i{y}^{(i)}\\ \mathcal{L}(w,b,\alpha )={\sum }_{i=1}^n{\alpha }_i-\frac{1}{2}{\sum }_{i,j=1}^n{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_j{\left(x^{(i)}\right)}^T{x}^{(j)}\end{array}$$
因此：
$$\begin{array}{rl}& \text{ 对拉格朗日化的原问题求最小值, 得到了 }\mathrm{w}\text{ , 现在可以构造 dual 问题 }\\ & \begin{array}{rl}\underset{\alpha }{\max }& W(\alpha )=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^n{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_j*x^{(i)},x^{(j)}*\\ \text{ s.t. }& {\alpha }_i\ge 0,i=1,\dots ,n\\ & \sum _{i=1}^n{\alpha }_i{y}^{(i)}=0\end{array}\\ & \text{ 可以推导出 b的值为: }{b}^{\ast }=-\frac{{\max }_{i:y^{(i)}=-1}{w}^{\ast T}{x}^{(i)}+{\min }_{i:y^{(i)}=1}{w}^{\ast T}{x}^{(i)}}{2}\\ & \begin{array}{r}\text{ SVM的决策子如下,值的符号为类别. }\\ w^{T}x+b={\left({\sum }_{i=1}^n{\alpha }_i{y}^{(i)}{x}^{(i)}\right)}^{T}x+b={\sum }_{i=1}^n{\alpha }_i{y}^{(i)}*x^{(i)},x*+b\end{array}\end{array}$$

Reference

[1] 陈希孺编著.概率论与数理统计[M].中国科学技术大学出版社,2009
[2] B 站视频教程：https://www.bilibili.com/video/BV1Mh411e7VU
[3] 线上南瓜书：https://datawhalechina.github.io/pumpkin-book/#/chapter1/chapter1
[4] 开源地址：https://github.com/datawhalechina/pumpkin-book
[5] 【数学基础】KKT条件
[6] 支持向量机SVM的通俗介绍
[7] SVM（三）：对偶问题最直白解释
[8] 对偶问题