本文主要是讲解核(Kernel)的基础内容，可以为SVM的核部分做补充。
本系列会出多篇文章，一步一步地更深入理解Kernel。这一篇，只理解基础的核函数，可以结合我之前的SVM文章支持向量机SVM 系列(3)——核函数(Kernel Function)一起学习。
机器学习的目的是训练一个模型，输入样本$x^{(i)}$ 预测对应的$y^{(i)}$ 。许多线性参数模型(比如线性回归或者SVM)，都是根据$w$来将$x^{(i)}$映射到$y^{(i)}$。通常，为了模型的效果更好，在训练前会对输入$x^{(i)}$进行一些处理，这个处理过程叫做叫做特征工程。
其中一种特征工程的方法，叫做多项式变换(polynomial transformation)。为了区分原始的$x^{(i)}$与新的特征， 通常称原始的$x^{(i)}$ 为输入属性(input attributes),而将转换后的特征称为输入特征(input features)(人们通常把原始的输入属性也叫做输入特征，其实都没有错)，其实这是一种映射关系。
通常用$\phi$ 来表示这种特征的映射。比如，对特征$x$进行4维多项式变换，就是：
$$ \phi(x)=\left[ \begin{aligned}& x\\ & x^2\\ & x^3\\ &x^4 \end{aligned}\right] $$
所以，模型输入就不再是$x$，而是映射后的$\phi(x)$。
核方法(Kernel Method)相关的计算(比如Support Vector Machine)，通常涉及到特征间的内积的计算，比如$\langle\phi(x),\phi(z)\rangle$。为了方便，我们定义一个对应的核(Kernel)，具体如下：
$$ k(x,z)=\phi(x)^T\phi(z) $$
通常情况下，对这个$k(x,z)$ 的计算非常容易，计算复杂度很低，甚至即便 $\phi(x)$ 本身维度极高时也很容易。
核函数细节
构造合法的核函数，有两种方法：
第一种，选择一个特征空间进行映射$\phi(x)$，再利用这个映射找到对应的核。比如，一维空间的核函数的定义如下：
$$ k(x,x\prime)=\phi(x)^T\phi(x\prime)=\sum\limits_{i=1}^M\phi_i(x)\phi_i(x\prime) $$
其中的$\phi_i(x)$是基函数。下图中展示了从对应的基函数集合构造函数的例子(摘自《PRML》)，它是$x$的函数$x\prime$用红色的叉表示，从左到右分别是：多项式基函数，高斯基函数，sigmoid基函数：
第二种方法，则是直接构造核函数。这种方法必须确定核函数是合法的，它必须是对于某个特征空间的标量积。比如下面的核函数：
$$ k(x,z)=(x^T,z)^2 $$
如果取$x=(x_1,x_2)$的特征情况，那么展开它得到 的结果是：
$$ \begin{aligned} k(x,z)&=(x^T,z)^2=(x_1,z_1+x_2z_2)\\ &=x_1^2z_1^2+2x_1z_1x_2z_2+x_2^2z_2^2\\ &=(x_1^2,\sqrt 2x_1x_2,x^2_2)(z_1^2,\sqrt 2z_1z_2,z^2_2)^T\\ &=\phi(x)^T\phi(z)\\ \end{aligned} $$
可以看出，这个特征映射包括了所有的二阶项。核函数$k(x,x\prime)$合法$\Leftrightarrow$ 由$k(x_i,y_i)$组成的Gram矩阵$K$在任何情况下都是半正定(positive semi-definite)的。注意，半正定矩阵与元素全部非负的矩阵是不同的。
给定一个合法的核$k_1(x,x\prime)$与$k_2(x,x\prime)$，下面的核也必定是合法的：
$$ \begin{aligned} k(x,x\prime)&= ck_1(x,x\prime)\\ k(x,x\prime)&= f(x)k_1(x,x\prime)f(x\prime)\\ k(x,x\prime)&= q(k_1(x,x\prime))\\ k(x,x\prime)&= \exp(k_1(x,x\prime))\\ k(x,x\prime)&= k_1(x,x\prime)+k_2(x,x\prime)\\ k(x,x\prime)&= k_1(x,x\prime)k_2(x,x\prime)\\ k(x,x\prime)&= k_3(\phi(x),\phi(x\prime))\\ k(x,x\prime)&= x^TAx\prime\\ k(x,x\prime)&= k_a(x_a,x_a\prime)+k_b(x_b,x_b\prime)\\ k(x,x\prime)&= k_a(x_a,x_a\prime)k_b(x_b,x_b\prime)\\ \end{aligned} $$
其中$c>0$是一个常数，$f(\cdot)$是任意函数，$q(\cdot)$是一个系数非负的多项式，$\phi(x)$是一个从$x$到$R^M$的函数，$k_3$是$R^M$中的一个合法核，$A$是一个对称半正定矩阵，$x_a,x_b$是变量，而且$x=(x_a,x_b)$。$k_a,k_b$是各自空间的合法的核函数。
基于以上的内容，我们就可以构造核了。可以看到简单的多项式核$k(x,x\prime)=(x^Tx\prime)^2$包含二次项，如果考虑更具一般性的核$k(x,x\prime)=(x^Tx\prime+c)^2$,其中$c>0$，那么对应的$phi(x)$就同时包含常数、线性项(一次项)和二次项！往下推，如果$k(x,x\prime)=(x^Tx\prime+c)^M$，那么它就包含所有的$M$阶的单项式！
另一个常见的核是高斯核(Gaussian Kernel)：
$$ k(x,x\prime)=\exp\Big(-\frac{\|x-x\prime\|^2}{2\sigma^2}\Big) $$
它可不是代表概率密度哈，之所以用高斯核，是因为高斯核对应的特征向量有无限维数，你没有看错，就是无限维。
高斯核是合法的，因为把平方项展开，可以得到：
$$ k(x,x\prime)=\exp(-x^2)\exp(-(x\prime)^2)\exp(2xx\prime) $$
对最后一个$\exp$进行泰勒展开，得到：
$$ k(x,x\prime)=exp(-x^2)exp(-(x\prime)^2)\Big(\sum\limits_{i=0}^\infty \frac{(2xx\prime)^i}{i!} \Big) $$
将有$x$的项放在一起，有$x\prime$项放在另外一边，那么可以得出
$$ k(x,x\prime)=\sum\limits_{i=0}^\infty \bigg(exp(-x^2)\frac{\sqrt{2^i}}{\sqrt{i!}}{x^i} \bigg)\bigg(exp(-(x\prime)^2)\frac{\sqrt{2^i}}{\sqrt{i!}}{(x\prime)^i}\bigg) $$
最终可以得到
$$ \phi(x)=\exp(-x^2)\cdot (1,\sqrt{\frac{2}{1!}}x,\sqrt{\frac{2^2}{2!}}x^2,...) $$
高斯核不光可以使用欧几里得距离，我们可以把$k(x,x\prime)=\exp\Big(-\frac{\|x-x\prime\|^2}{2\sigma^2}\Big)$中的核用一个非线性核替换，于是：
$$ k(x,x\prime)=\exp\Bigg\{-\frac{1}{\sigma^2}(k(x,x)+k(x\prime,x\prime),2k(x,x\prime)) \Bigg\} $$
核的思想还可以用在符号化的输入上，而不仅仅局限在基于实数的向量。甚至可以用在图片、集合、字符串、文本文档等等。比如$A_1$与$A_2$是两个集合，那么核函数的一个最简单的选择可以是：
$$ k(A_1,A_2)=2^{|A_1\cap A_2|} $$
这是一个合法的核，可以证明它是特征空间的一个内积。
关于核的内容还有很多，此系列会出后续文章，不过可能会需要一段时间，因为本人目前对核的理解还不够深。