r表示离平面最近的点的几何间隔,且所有点到平面的几何间隔均大于r。
max r
s.t. y(wx/|w|+b/|w|)>r :这里涉及点到平面的距离,可参考博客:https://www.cnblogs.com/hahaah/p/15078806.html
目的是找到点到平面最大的距离,从而确定平面位置。从这个角度不易优化参数对现有目标函数进行修改。
考虑几何间隔和函数间隔之间的关系:
设r1为函数间隔所以原式为:
max r1/|w|
s.t. y(wx+b)>r1
因为wx+b和2wx+2b,平面的位置并没有改动。对函数间隔进行限定规定其为1。所以原式为:
max 1/|w|
s.t. y(wx+b)>1
将其转化为凸二次规划问题进而能用对偶问题求解
min 1/2|w|*|w|
s.t. y(wx+b)>1
满足凸二次规划的条件,就可以用拉格朗日函数并转化为对偶问题进行求解。
变为拉格朗日函数:
1/2*|w|*|w|+λ*y(wx+b)-1 λ就是选择x是否满足条件,如果不满足不等式w为无穷大,最选择w让目标函数最小。参考博客:
因为满足KKT条件可以先对w求极值,再转变为对λ求极值。
就变为对w求导:
w=λyx
对b求导:
λyx总和为0
将w带入拉格朗日函数,在λyx总和为0的约束下。用smo算法对目标函数进行约束。
smo算法
选择一个参数违反KKT条件最严重的:实际上伪代码是遍历所有遍历违反KKT条件就更新。
第二个参数:在非0的参数中选择让其变化最大的,如果没有在非0参数中随机选择,都不满足条件在所有参数中随机选择。
选择好后用解析式对其更新。