SVM(线性模型)数学推导
作者:zihuanqiu
学习路线:先线性二分类解释清楚,再加入核方法扩展至非线性二分类
几个重要的概念
-
训练样本集
(xi,yi),其中xi为n维列向量,表示n维特征;yi为标签,当yi=+1时为正样本,yi=−1时为负样本。
则训练样本集为:D={(x1,y1),(x2,y2),⋯,(xm,ym)},y∈{−1,+1}
-
什么叫超平面
如上图,若在二维空间内(两个特征),若数据为线性可分,则可以用一条直线将正负样本区分开来(2分类问题);若在三维空间则为一个平面;三维空间以上无法想象统称为超平面。
但上图中区分正负样本肯定又不止一种划分方法,何者为最优?最优者才叫做SVM的超平面。
最优的判断标准则是,若对数据样本加以扰动(可以理解为采样样本总有误差),那么SVM超平面具有最佳的鲁棒性。从几何上来看,在上图中,若将超平面左右平移,直至触碰到最近的样本,那么这个被界定的范围记为d,则SVM的超平面是有最大d的那个超平面。
-
什么叫支持向量
SVM超平面左右平移最先触碰到的为支持向量
-
超平面的方程
wTx+b=0
其中:w和x都是n×1的列向量,n是特征维数。b为标量;w还是超平面的法向量,b控制了超平面到原点的距离。确定了w和b,超平面就被完全确定了。
那么在超平面上方数据wTx+b>0;在超平面下方数据wTx+b<0;
-
wTx+b=0与ζwTx+ζb=0表示的是同一个超平面
如:4x+4y=0 和 x+y=0 是同一个平面,4x+4y=4 和 x+y=1也是同一个平面
-
线性可分数据集的定义
在数据集{(xi,yi)}i=1∼m中,∃(w,b),使得对于∀i=1∼m,有:
{若yi=+1,则wTxi+b>0若yi=−1,则wTxi+b<0
即正样本全部分到上方,负样本全部分到下方
等价于 yi(wTxi+b)>0
-
点到平面距离公式
点(x0,y0)到平面w1x+w2y+b=0的距离表示为:
d=w12+w22∣w1x0+w2y0+b∣
则样本点到超平面的距离表示为:
d=∥w∥∣∣wTxi+b∣∣
-
若假设支持向量过超平面的平行线为wTx+b=1和wTx+b=−1(如上图所示),那么可求得
支持向量到超平面的距离为:
d=∥w∥1
那么超平面左右平移被限制的范围(即两个异类支持向量到超平面的距离之和)为:
Υ=∥w∥2
Υ被称为SVM的“间隔”(margin)
为什么可以假设支持向量过超平面的平行线为wTx+b=1和wTx+b=−1呢?正如上面第5点所述,由于W和b可以整体缩放倍数,超平面不变。那么总可以通过ζ⋅(w,b)→(w′,b′),使∣∣wTx+b∣∣=1。归一化的操作为我们带来便利
求解超平面转化为下列优化问题
在限制条件 yi(wTxi+b)⩾1,i=1∼m 下,最小化 21∥w∥2 的问题
即:
w,bmin21∥w∥2s.t.yi(wTxi+b)⩾1,i=1∼m
最大化Υ=∥w∥2等价于最小化21∥w∥2,而限制条件yi(wTxi+b)⩾1,i=1∼m表示求解超平面的前提条件是所有样本都被正确分类的情况下
这样就把支持向量机的求解转化为凸优化问题中的二次规划问题
二次规划(Quadratic Programming)
- 目标函数(Objective Function)为二次项
- 限制条件为一次项
要么无解,要么只有一个极值
SVM(非线性模型)数学推导
若数据集非线性可分,那么线性SVM的优化问题会变得无解。通过加入正则项,可以使SVM应用于非线性可分的数据集。
改写优化目标函数和限制条件
w,bmin21∥w∥2+Ci=1∑mξis.t.{yi(wTxi+b)⩾1−ξiξi⩾0,i=1∼m(1)
其中:ξi称为松弛变量(Slack Variable),∑i=1mξi称为正则项
若ξi足够大,则限制条件可以被轻易满足(即为限制条件加入了容忍度)。但ξi又不能太大,那么限制条件就失去了意义。因此在优化目标函数里需要添加ξi,并用一个超参数C来权衡最小化21∥w∥2与最小化∑i=1mξi之间的关系
低维到高维的映射
改写优化目标函数和限制条件后的SVM可以应用于非线性可分的数据集中。但是这样的SVM仍然是在试图寻找一条直线将正负样本划分,在某些情况下这仍然不够好,例如:
不同于其他机器学习算法,SVM试图通过高维映射,使低维空间的线性不可分问题变成高维空间中的线性可分问题,从而在高维空间中画出超平面对数据集进行划分。
我们定义高维映射φ(x):
xφφ(x)
其中x是低维向量,而φ(x)为高维向量
那么SVM的优化条件变为:
w,bmin21∥w∥2+Ci=1∑mξis.t.{yi(wTφ(xi)+b)⩾1−ξiξi⩾0,i=1∼m
此时w的维度也升高了,与φ(x)的维度相同
例子:
对于这么一个异或问题,我们有:
x1=[00]∈C1,x2=[11]∈C1,x3=[10]∈C2,x4=[01]∈C2
定义映射关系:
x=[ab]φφ(x)=⎣⎢⎢⎢⎢⎡a2b2abab⎦⎥⎥⎥⎥⎤
则升维后的样本为
φ(x1)=⎣⎢⎢⎢⎢⎡00000⎦⎥⎥⎥⎥⎤∈C1,φ(x2)=⎣⎢⎢⎢⎢⎡11111⎦⎥⎥⎥⎥⎤∈C1,φ(x3)=⎣⎢⎢⎢⎢⎡10100⎦⎥⎥⎥⎥⎤∈C2,φ(x4)=⎣⎢⎢⎢⎢⎡01010⎦⎥⎥⎥⎥⎤∈C2
求得w为:
w=⎣⎢⎢⎢⎢⎡−1−1−1−16⎦⎥⎥⎥⎥⎤,b=1
则
y1y2y3y4=wTx1+b=1>0=wTx2+b=3>0=wTx3+b=−1<0=wTx4+b=−1<0
可见的确通过升维,在高维空间划分了超平面,实现了非线性可分数据的分类问题。
核函数
可以证明:若升的维度越高,则数据集越有可能在高维空间被线性划分。可以猜想,若φ(x)为无限维度,则必定可以在无限高维空间划分任意数据集。但这样,会使得w也变为无限维度,使优化问题(1)变得不可解(因为w是代求参数)。
定理:我们可以不知道无限维映射φ(x)的显式表达,我们只要知道一个核函数(Kernel Function)
K(x1,x2)=φ(x1)T⋅φ(x2)
则(1)这个优化式仍然可解。
常用核函数:
-
高斯核
K(x1,x2)=e−2σ2∥x1−x2∥2
-
多项式核
K(x1,x2)=(x1Tx2+1)d
我们知道核K(x1,x2)的表达式,且知道K(x1,x2)可以表示为φ(x1)Tφ(x2),并且φ(x)是无限维的(不需要知道φ(x)的显示表达)。
K(x1,x2)能写成φ(x1)Tφ(x2)的充要条件为(Mercer’s Theorem):
- K(x1,x2)=K(x2,x1)(交换性)
- ∀Ci,xi(i=1∼N),有∑i=1N∑j=1NCiCjK(x1,x2)⩾0成立(半正定性)
原问题和对偶问题
现在我们要在只知道K(x1,x2)不知道φ(x)的情况下,解优化问题(1),因此我们需要一些理论知识铺垫。
这是优化理论的内容,用到就学一下吧
原问题(Prime Problem):
最小化:
f(ω)
限制条件:
gi(ω)⩽0(i=1∼K)hi(ω)=0(i=1∼M)
则其对偶问题(Dual Problem)为:
最大化:
Θ(α,β)=forallωinf{L(ω,α,β)}
限制条件:
α⩾0
其中L(ω,α,β)为:
L(ω,α,β)=f(ω)+i=1∑Kαigi(ω)+i=1∑Mβihi(ω)=f(ω)+αTg(ω)+βTh(ω)
forallωinf的意思是,在所有ω取值上取得的最小值
原问题和对偶问题的关系:如果ω∗是原问题的解,而α∗,β∗是对偶问题的解,则有:
f(ω∗)⩾θ(α∗,β∗)
proof:
θ(α∗,β∗)=forallωinf{L(ω,α∗,β∗)}⩽L(ω∗,α∗,β∗)=f(ω∗)+i=1∑Kαi∗gi(ω∗)+i=1∑Mβi∗hi(ω∗)⩽f(ω∗)
因为其中α∗⩾0, gi(ω∗)⩽0,hi(ω∗)=0
强对偶定理
若f(ω)为凸函数,且g(ω)=Aω+b,h(ω)=Cω+d,则优化问题的原问题与对偶问题间距为0,即:
f(ω∗)=θ(α∗,β∗)
再观察上面的proof过程,可以立即得出:
对 ∀i=1∼K,有αi∗=0 或者 gi(ω∗)=0
以上称为KKT条件
将SVM原问题转化为对偶问题
核函数SVM优化目标可以改写为(为了使形式上靠近优化理论,将ξi⩾0→ξi⩽0)
最小化:
w,bmin21∥w∥2+Ci=1∑mξi→w,bmin21∥w∥2−Ci=1∑mξi
限制条件:
yi(wTφ(xi)+b)⩾1−ξiξi⩾0→yi(wTφ(xi)+b)⩾1+ξi→1+ξi−yi(wTφ(xi)+b)⩽0→ξi⩽0
1. 原问题 |
1.核函数SVM原问题 |
最小化: f(ω) |
最小化: 21∥w∥2−C∑i=1mξi |
限制条件: gi(ω)⩽0(i=1∼K)hi(ω)=0(i=1∼M) |
限制条件: 1+ξi−yi(wTφ(xi)+b)⩽0ξi⩽0 |
从限制条件可知,左边的不等式限制条件gi(ω)⩽0对应右边的1+ξi−yi(wTφ(xi)+b)⩽0和ξi⩽0;而没有等式限制条。
优化目标函数f(ω)对应21∥w∥2+C∑i=1mξi
左边只有一个变量ω,而右边对应有三个变量ω,ξi,b
因此可以推导出核函数SVM的对偶问题:
2. 对偶问题 |
2. 核函数SVM对偶问题 |
最大化: Θ(α,β)=forallωinf{L(ω,α,β)} |
最大化: Θ(α,β)=forall(ω,ξi,b)inf{21∥w∥2−Ci=1∑mξi+i=1∑mαi(1+ξi−yi(wTφ(xi)+b))+i=1∑mβiξi} |
限制条件: αi⩾0(i=1∼K) |
限制条件: αi⩾0,βi⩾0(i=1∼m) |
L(ω,α,β)=f(ω)+∑i=1Kαigi(ω)+∑i=1Mβihi(ω) |
|
注意,由于SVM中的不等式限制条件有αi和βi两个,因此实际上左边的αi对应右边的αi和βi
现在我们来求解下式的具体表达式
Θ(α,β)=forall(ω,ξi,b)inf{L(ω,ξ,b)}=forall(ω,ξ,b)inf{21∥w∥2−Ci=1∑mξi+i=1∑mαi(1+ξi−yi(wTφ(xi)+b))+i=1∑mβiξi}
forall(ω,ξi,b)inf表示求关于(ω,ξi,b)的最小值,即求∂ω∂L(ω,ξi,b),∂ξi∂L(ω,ξi,b),∂b∂L(ω,ξi,b),并使他们等于零:
∂ω∂L(ω,ξi,b)=0→ω=i=1∑mαiyiφ(xi)∂ξi∂L(ω,ξi,b)=0→αi+βi=C∂b∂L(ω,ξi,b)=0→i=1∑mαiyi=0(2)
其中用到矩阵求导参考矩阵论,这里给出结果
若f(ω)=21∥ω∥2,则∂ω∂f(ω)=ω
若f(ω)=ωTx,则∂ω∂f(ω)=x
将(2)带入Θ(α,β),得到:
Θ(α)=i=1∑mαi−21i=1∑mj=1∑mαiαjyiyjK(xi,xj)
这时,通过把原问题转换为对偶问题,得到了核函数的表示形式!
将(2)带入限制条件αi⩾0,βi⩾0(i=1∼m)得到:
0⩽αi⩽C∑i=1mαiyi=0
于是我们求得了核函数SVM的优化对偶问题
核函数SVM对偶问题 |
最大化:Θ(α)=∑i=1mαi−21∑i=1m∑j=1mαiαjyiyjK(xi,xj) |
限制条件:0⩽αi⩽C∑i=1mαiyi=0 |
于是只有一个参数待求解:α,通常可以使用SMO算法
在测试流程中,我们可以有如下判断:
{若wTφ(xi)+b>0,则yi=+1若wTφ(xi)+b<0,则yi=−1
在(2)中,我们知道有ω=∑i=1mαiyiφ(xi),则:
wTφ(xi)=j=1∑m[αiyiφ(xj)]Tφ(xi)=j=1∑mαiyiφ(xj)Tφ(xi)=j=1∑mαiyiK(xi,xj)(3)
只剩下b待求解。确定了b,则核函数SVM训练完成
b的求解需要用到KKT条件,
3. KKT条件 |
3. SVM的KKT条件 |
∀i=1∼K, αi∗=0 或者 gi(ω∗)=0 |
∀i=1∼m, 1. αi=0 或者 1+ξi−yi(wTφ(xi)+b)=0 2. βi=0或者ξi=0 |
取一个0<αi<C⇒βi=C−αi>0,此时有:
βi=0αi=0⇒ξi=0⇒1+ξi−yi(wTφ(xi)+b)=0⇒1−yi(wTφ(xi)+b)=0
带入(3),得到:
b=yi1−wTφ(xi)=yi1−yiwTφ(xi)=yi1−yi∑j=1mαiyiK(xi,xj)
以上就是核函数SVM原问题转换为对偶问题,并用对偶问题训练SVM(求出αi和b的过程)的推导过程
核函数SVM算法总结
SVM算法
-
训练流程:
-
输入(xi,yi)i=1∼m
-
解优化问题:
最大化:Θ(α)=∑i=1mαi−21∑i=1m∑j=1mαiαjyiyjK(xi,xj)
限制条件:0⩽αi⩽C,∑i=1mαiyi=0
求解b:找一个0<αi<C,可以算得b=yi1−yi∑j=1mαiyiK(xi,xj)
-
测试流程
- 输入测试样本x
{若∑j=1mαiyiK(xi,xj)+b>0,则yi=+1若∑j=1mαiyiK(xi,xj)+b<0,则yi=−1
通过转换为对偶问题,我们可以看到上面没有出现φ(x),而待求解的参数只有αi和b
SVM处理多分类问题
上面都在说如何用SVM处理二分类问题,那么怎么样用SVM处理多分类问题呢?
我们有一下三种方法:
-
改造优化的目标函数和限制条件,使之能处理多分类问题。
这种方法通常效果一般,SVM专为二分类而生
-
一类VS其他类
例子:
若有C1,C2,C3三类,则可以设计三个SVM
SVM1:(C1,C2)VS(C3)
SVM2:(C1,C3)VS(C2)
SVM3:(C2,C3)VS(C1)
若y1=+1,y2=+1,y3=−1,则 显然为第一类
若y1=+1,y2=−1,y3=−1,在看看SVM1和SVM2的wTφ(xi)+b哪一个负的比较多就判断为哪一个
-
一类VS另一类
例子:
若有C1,C2,C3三类,则可以设计三个SVM
SVM1:(C1)VS(C2)
SVM2:(C1)VS(C3)
SVM3:(C2)VS(C3)
若y1=+1,y2=+1,y3=−1,则 显然为第一类(C1被投了两票,C3被投了一票)
对于n分类问题:
用一类VS其他类我们需要用n个SVM;
用一类VS另一类我们需要用2n(n−1)个SVM。
根据经验,用一类VS另一类的效果最佳,但同时也是最复杂的。