核方法

• 核方法定义
• 核函数背景
• 正定核函数

核方法定义

定理：令$\mathbb H$H为核函数$\kappa$κ对应的再生希尔伯特空间，$||h||_\mathbb H$∣∣h∣∣H​表示$\mathbb H$H空间中关于$h$h的范数，对于任意单调递增函数$\Omega :[0,\infty] \mapsto \mathbb R$Ω:[0,∞]↦R和任意非负损失函数$L:\mathbb R \mapsto [0.\infty],$L:R↦[0.∞],优化问题$minF(h)=\Omega(||h||_{\mathbb H})+L(h(x_1),...,h(x_m))$minF(h)=Ω(∣∣h∣∣H​)+L(h(x1​),...,h(xm​))的解总是可以写成：
$h^*(x)=\sum_{i=1}^m\alpha_i\kappa(x,x_i)$h∗(x)=i=1∑m​αi​κ(x,xi​)
表示定理对损失函数没有限制，对于正则化项$\Omega$Ω仅要求单调递增，甚至不要求$\Omega$Ω是凸函数，这就意味着对于一般的损失函数和正则化项，优化问题的最优解$h^*(x)$h∗(x)都可以表示为核函数$\kappa(x,x_i)$κ(x,xi​)的线性组合。

核函数的厉害之处从以上皆是就可以看出。

核函数背景

和函数的重要思想：非线性带来高维转换、对偶表示带来内积。

非线性带来高维转换
从线性分类的角度来看：以PLA和SVM为例，我们处理线性可分和不可分的问题时通常是用以下方法：

算法	线性可分	不是严格线性可分	严格非线性
感知机算法	PLA	Pocket Algorithm	$\phi(x)+PLA$ϕ(x)+PLA
支持向量机	hard-margin SVM	soft-margin SVM	$\phi$ϕ+hard-margin SVM(kernel SVM)

对于严格非线性问题的方法：可以假设通过某种映射$X\mapsto Z$X↦Z将输入控件映射到一个特征空间$Z$Z，然后再$Z$Z中执行线性分类。这就是非线性带来高维转换

对偶表示带来内积
在SVM中我们知道，解决凸优化问题我们依靠的就是最大间隔分类，再通过拉格朗日对偶性见简化为另一种对偶形式，但是对偶形式优化问题里包含一个内积的概念，也就是
$\underset \lambda{max}\sum_{i=1}^N\lambda_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j$λmax​∑i=1N​λi​−21​∑i=1N​∑j=1N​λi​λj​yi​yj​xiT​xj​
$s.t.\space\space\lambda_i≥0,\space\sum_{i=1}^N\lambda_iy_i=0$s.t.  λi​≥0, ∑i=1N​λi​yi​=0
中的$x_i^Tx_j,$xiT​xj​,而我们在计算的过程中必须要求出来这个内积。
如果是非线性问题，还需要拓展到高维空间，将$x_i^Tx_j$xiT​xj​转换成$\phi(x_i)^T\phi(x_j)，$ϕ(xi​)Tϕ(xj​)，然而高维空间求出这个内积的可能性太小。
而核方法就可以很好的解决这个问题。

核函数定义：$\kappa(x,z)=\phi(x)^T\phi(z),$κ(x,z)=ϕ(x)Tϕ(z),其中$\phi:X \mapsto \mathbb H,\space x、z\subset X$ϕ:X↦H, x、z⊂X

正定核函数

定义:
$\kappa:X×X\mapsto \mathbb R,任意x,z\subset X,有\kappa(x,z)$κ:X×X↦R,任意x,z⊂X,有κ(x,z)
如果$存在\phi: X\mapsto \mathbb R\space\space s.t.\space\kappa(x,z)=&lt;\phi(x),\phi(z)&gt;$存在ϕ:X↦R  s.t. κ(x,z)=<ϕ(x),ϕ(z)>，那么称$\kappa(x,z)$κ(x,z)是正定核函数。

而核函数$\kappa(x,z)$κ(x,z)必须满足正定性和对称性。
对称性：$\kappa(x,z)=\kappa(z,x)$κ(x,z)=κ(z,x)
正定性：在$X$X中任取N个元素，对应的Gram matrix$:\kappa=[\kappa(x_i,x_j)]$:κ=[κ(xi​,xj​)]是半正定的。

关于正定核函数为什么满足对称性和半正定性，有兴趣的可以查阅相关书籍了解一下。