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