SVM基本原理

：最小距离最大化

推导过程以二维空间为例

1 最大间隔模型

1.1 w^T*x+b=0表示方法

二维空间中一条直线的表示方法：Ax+By+C=0

将式中的x,y换成x1,x2，得到：Ax1+Bx2+C=0

转换成矩阵乘法的形式：
$(A,B)\binom{x_{1}}{x_{2}}+C=0$

设向量w =
$\binom{A}{B}$
，向量x =
$\binom{x_{1}}{x_{2}}$
，b = C，则有二维空间中一条直线可表示为
$w^{T}x+b=0$

(机器学习中的向量默认是列向量，要是想令w=(A,B)，方程写成wx+b=0也可以)

1.2 支持向量平面的表示

(支持向量平面：超平面平移到两个类别的支持向量，得到的两条直线，图像里的w^T*x+b=±1两条直线，没有找到这两个平面的名称，就先这样叫吧)

将直线进行平移，只改变Ax+By+C=0中的C，即
$w^{T}x+b=0$
中的b参数，超平面到两类支持向量的距离相同，则平移量相同

支持向量所在的平移直线为
$w^{T}x+b=m$
，对不同的数据样本m的数值是不相同的

为了计算方便，对数据进行归一化，将数据统一到同一个空间，等比例的缩放成±1

1.3 距离的表示

数学中点(x,y)到直线Ax+By+C=0的距离为：

$\frac{\ |Ax+By+C|}{\sqrt{A^{2}+B ^{2} }}$
(几何距离)

前面设了w =
$\binom{A}{B}$
，向量x =
$\binom{x_{1}}{x_{2}}$
，b = C，则||w|| =
${\sqrt{A^{2}+B ^{2} }}$
(向量的模)，|Ax+By+C| =
$|w^{T}x+b|$

则点到直线的距离可表示为：
$\frac{\ |w^{T}x+b|}{||w||}$
(函数距离)

1.3.1去掉绝对值

设图像中“+”一类为正例，即
$y_{i}$
= 1，
$w^{T}x_{i}+b\geqslant 1$
，“-”一类为负例，即
$y_{i}$
= -1，
$w^{T}x_{i}+b\leqslant -1$

对于每一个样本数据，满足：
$y_{i}(w^{T}x_{i}+b)\geq 1$

则当
$x_{i}$
为正例，
$|w^{T}x_{i}+b|=(w^{T}x_{i}+b)=y_{i}(w^{T}x_{i}+b)$

当
$x_{i}$
为负例，
$|w^{T}x_{i}+b|=-(w^{T}x_{i}+b)=y_{i}(w^{T}x_{i}+b)$

距离可表示为：
$\frac{\ y_{i}(w^{T}x_{i}+b)}{||w||}$

1.4 模型函数

最大间隔即max mariage(w，b)，对所有的样本又满足
$y_{i}(w^{T}x_{i}+b)\geqslant 1$

两类样本的间隔即样本中每个点到直线的最小距离，即
$mariage(w,b) =\min_{x_{i}} \frac{\ y_{i}(w^{T}x_{i}+b)}{||w||}$

间隔中的最小值是和
$x_{i}$
相关的，与w无关，则
$mariage(w,b) =\frac{1}{||w||}\min_{x_{i}}\ y_{i}(w^{T}x_{i}+b)=\frac{1}{||w||}$

再对间隔的表示形式做变换，
$\max_{w,b}\frac{1}{||w||} \Rightarrow \min_{w,b}{\frac{1 }{2}||w||^{2}}$

得到，模型函数为：
$\left\{\begin{matrix} \min_{w,b}{\frac{1 }{2}||w||^{2}} \\ s.t.y_{i}(w^{T}x_{i}+b)\geqslant 1 \end{matrix}\right.$

由于约束条件的标准形式是…≤0的形式，将约束条件移项，
$\left\{\begin{matrix} \min_{w,b}{\frac{1 }{2}||w||^{2}} \\ s.t. 1-y_{i}(w^{T}x_{i}+b)\leqslant 0 \end{matrix}.........(1)\right.$

2 对偶问题

求多元函数的极值，可借助高等数学中的拉格朗日函数。

令
$L(w,b,\lambda ) = \frac{1 }{2}||w||^{2}+\sum_{i=1}^{N}\lambda _{i}[1-y_{i}(w^{T}x_{i}+b)]$
，
$\lambda _{i}\geqslant 0$
，
$s.t. 1-y_{i}(w^{T}x_{i}+b)\leqslant 0$

结合上面的这些，可将模型函数转换成：

$\left\{\begin{matrix} \min_{w,b}{\frac{1 }{2}||w||^{2}} \\ s.t. 1-y_{i}(w^{T}x_{i}+b)\leqslant 0 \end{matrix}\right.$
$\Rightarrow$
$\left\{\begin{matrix} \min_{w,b}\max_{\lambda }L(w,b,\lambda )\\ s.t. \lambda _{i}\geqslant 0 \end{matrix}.....(2)\right.$

从对所求参数w,b有限制条件的极值，变成了无条件极值。

2.1 转换过程的解释

记
$\Delta =1-y_{i}(w^{T}x_{i}+b)$
，对于w和b的不同取值，
$\Delta$
要么＞0，要么≤0。

①如果
$\Delta$
＞0，
$L(w,b,\lambda )> 0$
，其最大值为正无穷

②如果
$\Delta$
≤ 0，
$L(w,b,\lambda )$
最大值在
$\Delta$
取0的时候取到，即
$\max_{\lambda }L(w,b,\lambda )=\frac{1 }{2}||w||^{2}$

则
$\min_{w,b}\max_{\lambda }L(w,b,\lambda ) = \min_{w,b}{(+\infty, \frac{1 }{2}||w||^{2}})=\min_{w,b}\frac{1 }{2}||w||^{2}$

相当于，新的函数
$\min_{w,b}\max_{\lambda }L(w,b,\lambda )$
去掉了
$\Delta$
＞0对应的w和b的取值情况，等价于，原函数
$\min_{w,b}\frac{1 }{2}||w||^{2}$
添加上限制条件
$1-y_{i}(w^{T}x_{i}+b)\leqslant 0$

2.2 转换成对偶形式

将模型函数(2)转换成对偶形式为：

$\left\{\begin{matrix} \max_{\lambda }\min_{w,b}L(w,b,\lambda )\\ s.t. \lambda _{i}\geqslant 0 \end{matrix}.....(3)\right.$

(对于任意一个表达式，对偶的转换满足：min max L ≥ max imn L(弱对偶)，凸优化中都是强对偶性，则min max L =max imn L)

2.2.1 为什么要转换成对偶形式

(1) 原问题是先求最大再求最小，对偶问题是先求最小再求最大，习惯上是先求最小再求最大。

(2) 原问题先求最大，确定了λ的值之后，还有两个w和b自由度，再求最小值的时候，需要对w和b分情况讨论；而对偶问题先求最小，确定了w和b的值，再求最大的时候只有λ一个自由度，不需要分情况讨论，更为简单。

2.3 求解w，b

转换成对偶问题之后，要先对拉格朗日函数求出w,b的值

2.3.1 对w求偏导

$L(w,b,\lambda ) = \frac{1 }{2}||w||^{2}+\sum_{i=1}^{N}\lambda _{i}[1-y_{i}(w^{T}x_{i}+b)]$
, 则
$\frac{\partial L}{\partial w} = w - \sum \lambda _{i}y_{i}x_{i}$

这里是对向量求偏导，可以去查一下向量求导公式

$\frac{1 }{2}||w||^{2} = \frac{1 }{2}w^{T}w$
，而
$\frac{\partial w^{T}w}{\partial w}\ = 2w$

$\frac{\partial \sum_{i=1}^{N}\lambda _{i}[1-y_{i}(w^{T}x_{i}+b)]}{\partial w}\ =-\frac{\partial \sum_{i=1}^{N}\lambda _{i}y_{i}w^{T}x_{i}}{\partial w}\ =-\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}$

令
$\frac{\partial L}{\partial w} =0$
得，
$w = \sum \lambda _{i}y_{i}x_{i}$

2.3.2 对b求偏导

$\frac{\partial L}{\partial b} =- \frac{\partial \sum \lambda _{i}y_{i}b}{\partial b}=-\sum \lambda _{i}y_{i}$

令
$\frac{\partial L}{\partial b} =0$
，得
$\sum \lambda _{i}y_{i} = 0$

2.3.3 代入拉格朗函数

$L(w,b,\lambda ) = \frac{1 }{2}||w||^{2}+\sum_{i=1}^{N}\lambda _{i}[1-y_{i}(w^{T}x_{i}+b)]$

$= \frac{1 }{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}[1-y_{i}(w^{T}x_{i}+b)]$

$= \frac{1 }{2}(\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i})^{T}(\sum_{j=1}^{N}\lambda _{j}y_{j}x_{j})+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}y_{i}(\sum_{j=1}^{N}\lambda _{j}y_{j}x_{j})^{T}x_{i}-\sum_{i=1}^{N}\lambda _{j}y_{i}b$

$= \frac{1 }{2}[\sum_{i=1}^{N}\lambda _{i}y_{i}(x_{i})^{T}](\sum_{j=1}^{N}\lambda _{j}y_{j}x_{j})+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}y_{i}[\sum_{j=1}^{N}\lambda _{j}y_{j}(x_{j})^{T}]x_{i}$

$= \frac{1 }{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}(x_{i})^{T}x_{j}+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}(x_{i})^{T}x_{j}$

$= -\frac{1 }{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}(x_{i})^{T}x_{j}+\sum_{i=1}^{N}\lambda _{i}$

则模型函数
$\left\{\begin{matrix} \max_{\lambda }\min_{w,b}L(w,b,\lambda )\\ s.t. \lambda _{i}\geqslant 0 \end{matrix}\right.$
转换成
$\left\{\begin{matrix} \max_{\lambda }-\frac{1 }{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}(x_{i})^{T}x_{j}+\sum_{i=1}^{N}\lambda _{i}\\ s.t. \lambda _{i}\geqslant 0\\ \sum \lambda _{i}y_{i} = 0\end{matrix}\right.$
或
$\left\{\begin{matrix} \min_{\lambda }\frac{1 }{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}(x_{i})^{T}x_{j}-\sum_{i=1}^{N}\lambda _{i}\\ s.t. \lambda _{i}\geqslant 0\\ \sum \lambda _{i}y_{i} = 0\end{matrix}\right.$

3 模型求解

原问题和对偶问题是强对偶
$\Leftrightarrow$
满足KKT条件

3.1 KKT条件形式

$\left\{\begin{matrix} \frac{\partial L}{\partial b} =0, \frac{\partial L}{\partial w} =0\\ \lambda _{i}[1-y_{i}(w^{T}x_{i}+b)]=0\\ \lambda _{i}\geqslant 0\\ 1-y_{i}(w^{T}x_{i}+b)\leqslant 0\end{matrix}\right.$

其中第二个表达式为互补松弛条件。

结合后三个表达式，当样本点在
$w^{T}x+b=\pm 1$
这两个超平面上的时候，
$\lambda _{i}$
才能够不为零；对于其他的样本点，
$\lambda _{i}$
的取值只能为0。即只有在
$w^{T}x+b=\pm 1$
这两个超平面上的样本点才对模型参数的取值有影响，其他的点则不影响模型参数，故，将这些样本点称为支持向量。