示意图
二分类问题描述
Data={(xi,yi)}i=1N,xi∈Rp,yi∈{−1,+1}
由于超平面ωTx+b有很多个,要找到最好的一个超平面,以得到最低的泛化误差(或测试误差、期望损失)。
hard-margin SVM判别模型,与概率无关:
f(ω)=sign(ωTx+b)={ωTx+b>0,f(ω)=1ωTx+b<0,f(ω)=−1
目标函数:
⎩⎪⎨⎪⎧max margin(ω,b)s.t. {ωTxi+b>0,yi=1ωTxi+b<0,yi=−1⇒yi(ωTxi+b)>0,i=1...,N
即,{max margin(ω,b)s.t. yi(ωTxi+b)>0,i=1,...,N
什么是margin?
答:一共有N个点到直线的距离,最小的那个就是margin。点到直线距离公式,
margin(ω,b)=ω,b,ximindistance(ω,b,xi)=ω,b,ximin∥ω∥1∣ωTxi+b∣
则上式写为:
{ω,bmaxω,b,ximin∥ω∥1∣ωTxi+b∣ =ω,bmaxximin∥ω∥1∣ωTxi+b∣=ω,bmax∥ω∥1ximinyi(ωTxi+b)⇐yi∈{−1,+1}s.t. yi(ωTxi+b)>0
yi(ωTxi+b)>0可以理解为:∃ γ>0,s.t. xi,yiminyi(ωTxi+b)=γ
γ的取值对式子(或超平面)是没有影响的,实际上就是对ω,b的缩放。
因此,令 γ=1。
则,ω,bmax∥ω∥1ximinyi(ωTxi+b)=ω,bmax∥ω∥1γ=ω,bmax∥ω∥1
则,上式可写为:
{ω,bmax∥ω∥1⇒ω,bmin∥ω∥=ω,bmin21ωTω 硬间隔;二次的、凸优化,可直接求解s.t. ximinyi(ωTxi+b)=1⇒yi(ωTxi+b)⩾1,i=1,...,N 有N个约束
则,(1){ω,bmin21ωTω s.t. yi(ωTxi+b)⩾1,i=1,...,N
开始求解
1. Primal problem:带ω,b约束的优化
(1){ω,bmin21ωTωs.t. yi(ωTxi+b)⩾1,for i=1,...,N1−yi(ωTxi+b)⩽0
2. 拉格朗日乘子法→对ω,b无约束的优化
L(ω,b,λ)=21ωTω+i=1∑Nλi(1−yi(ωTxi+b)), λi⩾0
(2){ω,bminλmaxL(ω,b,λ)s.t. λi⩾0
值得注意的是:1−yi(ωTxi+b)⩽0。为什么呢?
答:
直观上看,
如果1−yi(ωTxi+b)>0,则λmaxL=21ωTω+∞=∞
如果1−yi(ωTxi+b)⩽0,则λmaxL一定存在,λmaxL=21ωTω+0=21ωTω (λi→0)
则,ω,bminλmaxL(ω,b,λ)=ω,bmin(∞,21ωTω)=21ωTω
因此,1−yi(ωTxi+b)>0被丢弃了。
3. 转化为强对偶问题
(3){λmaxω,bminL(ω,b,λ)s.t. λi⩾0
什么是强、弱对偶?
答:凸优化二次问题满足强对偶关系。
(1)弱对偶关系为min maxL⩾max minL,对应理解为“尾凤⩾头鸡”,即凤尾优于鸡头、瘦死的骆驼比马大。
(2)强对偶关系,就是把⩾改为=。
4. 求解对偶问题:解拉格朗日方程ω,bminL(ω,b,λ)
L(ω,b,λ)=21ωTω+i=1∑Nλi(1−yi(ωTxi+b)), λi⩾0
(1) 求∂b∂L=0
∂b∂L=∂b∂[i=1∑Nλi−i=1∑Nλiyi(ωTxi+b)]=∂b∂[−i=1∑Nλiyib)]=−i=1∑Nλiyi=0
则,i=1∑Nλiyi=0
(2) 将i=1∑Nλiyi=0代入到L(ω,b,λ)中
L(ω,b,λ)=21ωTω+i=1∑Nλi−i=1∑Nλiyi(ωTxi+b)=21ωTω+i=1∑Nλi−i=1∑NλiyiωTxi+i=1∑Nλiyib=21ωTω+i=1∑Nλi−i=1∑NλiyiωTxi
(3) 求∂ω∂L=0
∂ω∂L=21⋅2⋅ω−i=1∑Nλiyixi=0
则,ω=i=1∑Nλiyixi
(4) 将ω=i=1∑Nλiyixi代入到L(ω,b,λ)中
L(ω,b,λ)=21(i=1∑Nλiyixi)T(i=1∑Nλiyixi)+i=1∑Nλi−i=1∑Nλiyi(j=1∑Nλjyjxj)Txi
注意:
∵λi∈R,yi∈{−1,1},xi∈Rp
∴(i=1∑Nλiyixi)T=i=1∑NλiyixiT
∴ωTω=(i∑NλiyixiT)⋅(j∑Nλjyjxj)=i∑Nj∑NλiλjyiyjxiTxj
同理,i=1∑Nλiyi(j=1∑Nλjyjxj)Txi=i=1∑Nλiyij=1∑NλjyjxjTxi=i∑Nj∑NλiλjyiyjxjTxi=i∑Nj∑NλiλjyiyjxiTxj⇐xiTxj=xjTxi∈R
发现上面两个结果一样!因此,可以约掉啦~
(i=1∑Nλiyixi)T(i=1∑Nλiyixi)=i=1∑Nλiyi(j=1∑Nλjyjxj)Txi=i∑Nj∑NλiλjyiyjxiTxj
L(ω,b,λ)=i=1∑Nλi−21i∑Nj∑NλiλjyiyjxiTxj即ω,bminL(ω,b,λ)
代入式(3)即,
(4)⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧λmaxi=1∑Nλi−21i=1∑Nj=1∑NλiλjyiyjxiTxj⇐λmaxω,bminL(ω,b,λ)s.t. λi⩾0,i=1∑Nλiyi=0
(5) 对偶问题的最终优化式
最优化问题常由min表示
(5)⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧λmin21i=1∑Nj=1∑NλiλjyiyjxiTxj−i=1∑Nλis.t. λi⩾0,i=1∑Nλiyi=0
5. KKT条件求解对偶问题
原问题和对偶问题具有强对偶关系充要条件满足KKT条件
拉格朗日方程(上面第2点):
L(ω,b,λ)=21ωTω+i=1∑Nλi(1−yi(ωTxi+b)), λi⩾0
KKT(Karush-Kuhn-Tucker)条件:
⎩⎪⎪⎪⎨⎪⎪⎪⎧∂ω∂L=0,∂b∂L=0,∂λ∂L=0λi⩾0⇒拉格朗日乘子法的要求1−yi(ωTxi+b)⩽0⇒上面第2点解释了λi(1−yi(ωTxi+b))=0⇒此时,L(ω,b,λ)=21ωTω,为最大值;松弛互补条件
松弛互补条件?
基于互补松弛型给出强对偶的一个必要条件——KKT条件,最后给出凸函数性KKT条件的充分必要性。
(1) 最优解ω∗=i=1∑Nλiyixi
就是之前(3)中∂ω∂L=0的结果。
(2) 最优解b∗=yk−i∑NλiyixiTxk
假设∃(xk,yk), s.t. 1−yk(ωTxk+b)=0,即(xk,yk)为支持向量,ωTxk+b∈{−1,1}。
由yk(ωTxk+b)=1∵yk=±1,yk2=1∴yk2(ωTxk+b)=yk∴ωTxk+b=yk∴b∗=yk−ωTxk=yk−(ω∗)Txk=yk−i=1∑Nλiyixi
(3) 根据w∗,b∗得出超平面w∗x+b∗
- f(x)=sign((w∗)Tx+b∗)
-
w∗=i=1∑Nλiyixi可看做是Data={(xi,yi)}i=1N,xi∈Rp,yi∈{−1,+1}的线性组合
-
λi只对支持向量才有意义,即1−yi(ωTxi+b)=0上的点,此时,λi⩾0;对于非支持向量不起作用,此时λi=0。