ML—核技巧

华电北风吹
天津大学认知计算与应用重点实验室
日期：2015/11/13

什么是核?
$x_i,x_j \in R^N$，模型中遇到的关于$x_i,x_j$的计算全部是$<x_i,x_j>$，若在N维中得不到想要的效果，就可以利用核函数，将原本是N维的内积运算映射到高维空间，甚至是无限维。
$K(x_i,x_j)=<\phi(x_i),\phi(x_j)> \tag{0}$

一、线性核函数
线性核函数计算公式为
$K(x_i,x_j)=x_i^Tx_j \tag{1-1}$
可以看出，线性核函数就是原始的内积运算，并没有提升到高维空间。

二、多项式核函数
多项式核函数计算公式为
$K(x_i,x_j)=(\gamma\times x_i^Tx_j+c)^d \tag{2-1}$
可以看一个简单的多项式核函数例子：
$K(x_i,x_j)=(x_i^Tx_j+c)^2$
$=\sum_{p,q=1}^{N}{(x_i^px_i^q)(x_j^px_j^q)}+\sum_{p=1}^{N}{(\sqrt{2c}x_i)(\sqrt{2c}x_j)}+c^2$
若N=3，可以得到(维度为10)
$\phi(x_i)=[x_i^{(1)}x_i^{(1)},x_i^{(1)}x_i^{(2)},x_i^{(1)}x_i^{(3)},x_i^{(2)}x_i^{(1)},x_i^{(2)}x_i^{(2)},x_i^{(2)}x_i^{(3)},x_i^{(3)}x_i^{(1)},x_i^{(3)}x_i^{(2)},x_i^{(3)}x_i^{(3)},\sqrt{2c}x_1,\sqrt{2c}x_2,\sqrt{2c}x_3,c]^T$
可以验证，映射后高维空间的维数是$C_{N+d}^d$。

三、径向基核函数(Radial Basis Function)
径向基核函数利用公式(3-1)对N维向量$x_i,x_j$的内积扩展到无限维向量$\phi(x_i),\phi(x_j)$的内积。
$K(x_i,x_j)=e^{-\gamma||x_i-x_j||^2} \tag{3-1}$
其中
$\phi(x)=e^{-\gamma x^2}[1,\sqrt{\frac{(2\gamma)}{1!}}x,\sqrt{\frac{(2\gamma)^2}{2!}}x^2,\sqrt{\frac{(2\gamma)^3}{3!}}x^3,...,\sqrt{\frac{(2\gamma)^k}{k!}}x^k,...]^T \tag{3-2}$
下面对此公式进行简要推导解释：
$e^{-\gamma||x_i-x_j||^2}$
$=e^{-\gamma x_i^2+2\gamma x_i^Tx_j-\gamma x_j^2}$
$=e^{-\gamma x_i^2-\gamma x_j^2}\times e^{2\gamma x_i^Tx_j}$
$=e^{-\gamma x_i^2-\gamma x_j^2}\times (1+2\gamma x_i^Tx_j+\frac{(2\gamma x_i^Tx_j)^2}{2!}+\frac{(2\gamma x_i^Tx_j)^3}{3!}+...+\frac{(2\gamma x_i^Tx_j)^k}{k!}+...)$
$=e^{-\gamma x_i^2-\gamma x_j^2}\times (1+\sqrt{2\gamma} x_i^T\sqrt{2\gamma}x_j+\sqrt{\frac{(2\gamma)^2}{2!}}(x_i^T)^2\sqrt{\frac{(2\gamma)^2}{2!}}x_j^2+\sqrt{\frac{(2\gamma)^3}{3!}}(x_i^T)^3\sqrt{\frac{(2\gamma)^3}{3!}}x_j^3+...+\sqrt{\frac{(2\gamma)^k }{k!}}(x_i^T)^k\sqrt{\frac{(2\gamma)^k }{k!}}x_j^k+...)$
$=e^{-\gamma x_i^2}\times [1+\sqrt{2\gamma} x_i^T+\sqrt{\frac{(2\gamma)^2}{2!}}(x_i^T)^2+\sqrt{\frac{(2\gamma)^3}{3!}}(x_i^T)^3+...+\sqrt{\frac{(2\gamma)^k }{k!}}(x_i^T)^k+...]$
$* e^{-\gamma x_j^2}\times [1+\sqrt{2\gamma}x_j+\sqrt{\frac{(2\gamma)^2}{2!}}x_j^2+\sqrt{\frac{(2\gamma)^3}{3!}}x_j^3+...+\sqrt{\frac{(2\gamma)^k }{k!}}x_j^k+...]$
$=\phi(x_i)^T\phi(x_j)$