SVM基本原理:最小距离最大化
推导过程以二维空间为例
1 最大间隔模型
1.1 w^T*x+b=0表示方法
二维空间中一条直线的表示方法:Ax+By+C=0
将式中的x,y换成x1,x2,得到:Ax1+Bx2+C=0
转换成矩阵乘法的形式:
设向量w = ,向量x =
,b = C,则有二维空间中一条直线可表示为
(机器学习中的向量默认是列向量,要是想令w=(A,B),方程写成wx+b=0也可以)
1.2 支持向量平面的表示
(支持向量平面:超平面平移到两个类别的支持向量,得到的两条直线,图像里的w^T*x+b=±1两条直线,没有找到这两个平面的名称,就先这样叫吧)
将直线进行平移,只改变Ax+By+C=0中的C,即中的b参数,超平面到两类支持向量的距离相同,则平移量相同
支持向量所在的平移直线为,对不同的数据样本m的数值是不相同的
为了计算方便,对数据进行归一化,将数据统一到同一个空间,等比例的缩放成±1
1.3 距离的表示
数学中点(x,y)到直线Ax+By+C=0的距离为:(几何距离)
前面设了w = ,向量x =
,b = C,则||w|| =
(向量的模),|Ax+By+C| =
则点到直线的距离可表示为:(函数距离)
1.3.1去掉绝对值
设图像中“+”一类为正例,即 = 1,
,“-”一类为负例,即
= -1,
对于每一个样本数据,满足:
则当为正例,
当为负例,
距离可表示为:
1.4 模型函数
最大间隔即max mariage(w,b),对所有的样本又满足
两类样本的间隔即样本中每个点到直线的最小距离,即
间隔中的最小值是和相关的,与w无关,则
再对间隔的表示形式做变换,
得到,模型函数为:
由于约束条件的标准形式是...≤0的形式,将约束条件移项,
2 对偶问题
求多元函数的极值,可借助高等数学中的拉格朗日函数。
令 ,
,
结合上面的这些,可将模型函数转换成:
从对所求参数w,b有限制条件的极值,变成了无条件极值。
2.1 转换过程的解释
记,对于w和b的不同取值,
要么>0,要么≤0。
①如果>0,
,其最大值为正无穷
②如果 ≤ 0,
最大值在
取0的时候取到,即
则
相当于,新的函数去掉了
>0对应的w和b的取值情况,等价于,原函数
添加上限制条件
2.2 转换成对偶形式
将模型函数(2)转换成对偶形式为:
(对于任意一个表达式,对偶的转换满足: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求偏导
, 则
这里是对向量求偏导,可以去查一下向量求导公式
,而
令得,
2.3.2 对b求偏导
令,得
2.3.3 代入拉格朗函数
则模型函数转换成
或
3 模型求解
原问题和对偶问题是强对偶 满足KKT条件
3.1 KKT条件形式
其中第二个表达式为互补松弛条件。
结合后三个表达式,当样本点在这两个超平面上的时候,
才能够不为零;对于其他的样本点,
的取值只能为0。即只有在
这两个超平面上的样本点才对模型参数的取值有影响,其他的点则不影响模型参数,故,将这些样本点称为支持向量。
3.2 求解
w的值使用即可求得
对于参数b,取样本点,满足
,(即样本点在支持向量的超平面上),则
等式两边同乘,得到
,(由于
)
则
模型: