持续创作,加速成长!这是我参与「掘金日新计划 · 10 月更文挑战」的第15天,点击查看活动详情
核方法相关的概念有三个Kernel Method(从思想角度)、Kernel Trick(从计算角度)、Kernel Function
核方法可以用于非线性带来的高维转换(从模型角度),对偶表示带来内积(从优化角度)
有时分类数据是完全不可分的,例如异或问题,即数据集为
{((0,0),0),((1,1),0),((1,0),1),((0,1),1)}
left{((0,0),0),((1,1),0),((1,0),1),((0,1),1)right}
显然异或问题中的数据不是线性可分的,但我们可以将数据映射到高位空间来实现线性可分,因此我们需要寻找一个非线性的ϕ(x)phi(x)将低维空间的数据xx映射到成高维空间的数据zz,从而实现新的数据集{(z,y)}left{(z,y)right}线性可分
Cover Theonem:高维比低维更易线性可分
ϕ(x)phi(x)可以是
x=(x1,x2)→ϕ(x)z=(x1,x2,(x1−x2)2)
x=(x_{1},x_{2})overset{phi(x)}{rightarrow }z=(x_{1},x_{2},(x_{1}-x_{2})^{2})
显然在新的空间中,新数据可以实现线性可分
在硬间隔SVM中我们将求解问题转化为凸优化问题
{min ω,b12ωTωs.t.yi(ωTxi+b)≥1,i=1,2,⋯ ,N
left{begin{aligned}&mathop{text{min }}limits_{omega,b} frac{1}{2}omega^{T}omega\&s.t.y_{i}(omega^{T}x_{i}+b)geq 1,i=1,2,cdots,Nend{aligned}right.
进而转化为其对偶问题
{min λ12∑i=1N∑j=1Nλiλjyiyjxixj−∑i=1Nλis.t.λi≥0,∑i=1Nλiyi=0
left{begin{aligned}&mathop{text{min }}limits_{lambda} frac{1}{2}sumlimits_{i=1}^{N}sumlimits_{j=1}^{N}lambda_{i}lambda_{j}y_{i}y_{j}x_{i}x_{j}-sumlimits_{i=1}^{N}lambda_{i}\
&s.t.lambda_{i}geq 0,sumlimits_{i=1}^{N}lambda_{i}y_{i}=0end{aligned}right.
如果我们把这里的原数据映射到高维空间实现线性可分,则问题转化为
{min λ12∑i=1N∑j=1Nλiλjyiyjϕ(xi)Tϕ(xj)−∑i=1Nλis.t.λi≥0,∑i=1Nλiyi=0
left{begin{aligned}&mathop{text{min }}limits_{lambda} frac{1}{2}sumlimits_{i=1}^{N}sumlimits_{j=1}^{N}lambda_{i}lambda_{j}y_{i}y_{j}phi(x_{i})^{T}phi(x_{j})-sumlimits_{i=1}^{N}lambda_{i}\
&s.t.lambda_{i}geq 0,sumlimits_{i=1}^{N}lambda_{i}y_{i}=0end{aligned}right.
然而,如果我们将xx代入ϕ(x)phi(x),然后计算点积ϕ(xi)Tϕ(xj)phi(x_{i})^{T}phi(x_{j}),这个计算量是很大的,因此我们引出核函数
核函数的定义为
∀x,x′∈X,∃ϕ:x↦zs.t.K(x,x′)=ϕT(x)ϕ(x)=<ϕ(x),ϕ(x′)>
begin{gathered}
forall x,x’ in X,exists phi:x mapsto z\
s.t.K(x,x’)=phi^{T}(x)phi(x)=left<phi(x),phi(x’)right>
end{gathered}
这里是直接求出ϕ(xi)Tϕ(xj)phi(x_{i})^{T}phi(x_{j}),不需要先求ϕ(x)phi(x),再求ϕ(xi)Tϕ(xj)phi(x_{i})^{T}phi(x_{j})
这里关于核函数的定义先看看就行,后面会有更精确的定义
例如一个核函数可以定义为K(x,x′)=exp(−(x−x′)22σ2)begin{aligned} K(x,x’)=text{exp}left(- frac{(x-x’)^{2}}{2sigma^{2}}right)end{aligned}
这里只要知道x,x′x,x’直接代入就能求出对应的ϕ(xi)Tϕ(xj)phi(x_{i})^{T}phi(x_{j})
关于线性可分、允许一点点错误、严格非线性三种问题解决方法
线性可分 | 一点点错误 | 严格非线性 |
---|---|---|
PLA | Pocket Algerithm | ϕ(x)phi(x)+PLA |
Hard-Margin SVM | Soft-Margin SVM | ϕ(x)phi(x)+Hard-Margin SVM |