|
首先假设样本线性可分,此时的目标是求解最优分类面。
样本需满足的条件公式为y*(wx+b)>=δ,y取值为{-1,1},分别表示正负样本。
优化的目标函数为max δ ,也就是使得样本距离最大的分类面。
如果w不做约束,则对于任何x,只要w线性增长,则δ可取更大的值;而w线性变化,不会影响分类面形状。因此约束||w||=1。
也就是要求||w||=1条件下的max δ最优化问题。但此时w的解空间是在一个圆周上的点,函数非凸,无法逼近到最优解上。
因此将最优化问题进行转化,变为max δ/||w||,同时约束条件为所有的样本:y*(wx+b)>=δ。
上面的表述,其实是最优化问题的一般性表述,设置一个优化目标,然后添加各种约束条件。
然后对这个优化目标做了转化,设δ=1,则max δ/||w|| 问题等价于 min ||w||。约束条件为y*(wx+b)>=δ。
此时||w||虽然是个圆形区域,圆形区域是非凸的。但由于有约束条件的存在,每个约束条件都是一个分割面,这些分割面将圆形区域切分为凸型区域。然后就可以在这个凸函数上求解最优化函数了。可以使用梯度下降法,也可以使用一些现成的软件。
拉普拉斯算子:
如果只是等于0的约束,则分别使参数的导数为0,就能求到最优解。
公式表示为:L(w, β)=f(w)+∑β*h(w)。其中f(w)为最优化目标函数,h(w)为约束条件,每个w都使得h(w)=0.
更一般的情况,拉普拉斯算子可表示为:L(w, α, β)=f(w)+∑α*g(w)+∑β*h(w)。其中g(w)<=0。是一种新的不等式约束条件。
令θp(α, β)=max(α>=0, β) L(w, α, β),其中α,β为变量,并且α>=0,。则当 L(w, α, β) 满足约束条件时,θp(w)=f(w);不满足约束条件时,θp(w)=∞。
此时:min(w) f(w)=min(w) θp(w)。
此处引入对偶问题(dual problem)
令θd(α, β)=min L(w, α, β),d*=max(α>=0, β) min(w) L(w, α, β)
则一般情况下,d*<=p*。在大多数的实际应用中,可认为d*=p*。此时原始问题和对偶问题有相同的解。可利用对偶问题来求解原始问题。
KKT互补条件
在求解对偶问题时,会用到KKT互补条件。KKT条件共有5个,分别是:
δ L(w, α, β) / δ w = 0。也就是对w求偏导为0。
δ L(w, α, β) / δ β = 0。也就是对β求偏导为0。
α*g(w)=0。
g(w)<=0。
α>=0。
通常情况下α*g(w)=0,意味着α≠0等价于g(w)=0。
回到原始的目标,min f(w) = min (1/2)*(||w||)^2, s.t. gi(w*xi+b)>=1
转变为 g(w, b) = -gi(w*xi+b)+1<=0,
利用KKT条件中的第3个,α>0 => g(w, b) = 0. 这个式子意味着g(w, b)=0的样本xi距离分类面的距离为1,这些样本为支撑样本(support vector)。
求解原始的最优分类面问题,min L(w, b, α) = (1/2)*(||w||)^2 - ∑α*(gi(w*xi+b)-1)
对偶问题 θd(α) = min(w, b) L(w, b, α)
求解对偶问题,也就是让δ L(w, b, α)/ δ w = 0,δ L(w, b, α)/ δ b = 0
这里的解为 δ L(w, b, α)/ δ w = w - ∑αi*yi*xi = 0.
上式等价于 w = ∑αi*yi*xi ,也就是说w是样本x的线性组合。
δ L(w, b, α)/ δ b = -∑yi*αi = 0
将解出的w带入原始的式子,L=∑αi-(1/2)*∑(i)∑(j)yi*yj*αi*αj*<xi, xj>=W(α)
此时的对偶问题为 max W(α), st. αi>=0, ∑yi*xi=0
求解max W(α), 也可以使用偏导等于0的方法。
当求出α之后,就可以求出w,之后就可以求出b。
b = (max(yi=-1) (w*xi)+min(yi=1) (w*xi))/2
整个求解过程为先根据对偶问题,求出w的α表达式,然后根据对偶问题求出α,进而带入w表达式求出w,最后求出b。
关于最有间隔分类器的另一种表述为:
w = ∑αi*yi*xi
预测函数h(x)=g(w*x+b)
w*x+b=∑αi*yi*<xi,x>+b
也就是说预测函数可以被表示为新输入的样本与训练样本的内积之和。
一些心得:
1、学习笔记很重要,可以把重要的概念知识点串起来
2、算法的整体逻辑要理清,要明白重要的求解步骤
3、有一些概念或者关键步骤,老师可能会跳过,利用笔记可以详细思考下背后的原理
4、一节75分钟的课程,前后陆续看了4、5天,在中文翻译和笔记的帮助下,才算学懂。对于复杂的知识不能求快,笨鸟慢飞
|
|