核方法与高维空间映射

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第15天，点击查看活动详情

核方法相关的概念有三个Kernel Method（从思想角度）、Kernel Trick（从计算角度）、Kernel Function

核方法可以用于非线性带来的高维转换（从模型角度），对偶表示带来内积（从优化角度）

有时分类数据是完全不可分的，例如异或问题，即数据集为

$$\left\{((0,0),0),((1,1),0),((1,0),1),((0,1),1)\right\}$$

显然异或问题中的数据不是线性可分的，但我们可以将数据映射到高位空间来实现线性可分，因此我们需要寻找一个非线性的$\varphi (x)$将低维空间的数据$x$映射到成高维空间的数据$z$，从而实现新的数据集$\left\{(z,y)\right\}$线性可分

Cover Theonem：高维比低维更易线性可分

$\varphi (x)$可以是

$$x=(x_1,x_2)\stackrel{\varphi (x)}{\to }z=(x_1,x_2,(x_1-x_2{)}^2)$$

显然在新的空间中，新数据可以实现线性可分

在硬间隔SVM中我们将求解问题转化为凸优化问题

$$\{\begin{array}{rl}& \underset{\omega ,b}{\min }\frac{1}{2}{\omega }^T\omega \\ & s.t.y_i({\omega }^T{x}_i+b)\ge 1,i=1,2,\cdots ,N\end{array}$$

进而转化为其对偶问题

{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 ​21​i=1∑N​j=1∑N​λi​λj​yi​yj​xi​xj​−i=1∑N​λi​s.t.λi​≥0,i=1∑N​λi​yi​=0​

如果我们把这里的原数据映射到高维空间实现线性可分，则问题转化为

{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.
⎩⎨⎧​​λmin ​21​i=1∑N​j=1∑N​λi​λj​yi​yj​ϕ(xi​)Tϕ(xj​)−i=1∑N​λi​s.t.λi​≥0,i=1∑N​λi​yi​=0​

然而，如果我们将$x$代入$\varphi (x)$，然后计算点积$\varphi (x_i{)}^T\varphi (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}
∀x,x′∈X,∃ϕ:x↦zs.t.K(x,x′)=ϕT(x)ϕ(x)=⟨ϕ(x),ϕ(x′)⟩​

这里是直接求出$\varphi (x_i{)}^T\varphi (x_j)$，不需要先求$\varphi (x)$，再求$\varphi (x_i{)}^T\varphi (x_j)$

这里关于核函数的定义先看看就行，后面会有更精确的定义

例如一个核函数可以定义为$\begin{array}{r}K(x,x^{\prime })=\text{exp}\left(-\frac{(x-x^{\prime }{)}^2}{2{\sigma }^2}\right)\end{array}$

这里只要知道$x,x^{\prime }$直接代入就能求出对应的$\varphi (x_i{)}^T\varphi (x_j)$

关于线性可分、允许一点点错误、严格非线性三种问题解决方法