参考资料:
周志华《机器学习》
吴恩达 斯坦福大学机器学习 CS229
问题由来：如何处理线性不可分的数据集？
如图所示，以“异或”问题为例，这四个样本点在二维平面上是线性不可分的，即找不到二维空间中的一条直线分隔开圈圈和叉叉。我们可以把低维特征空间中的样本点映射到更高维的特征空间中去，使之线性可分。如图所示，我们把原始的二维空间映射到一个合适的三维空间，就找到了一个合适的划分超平面，分隔开圈圈和叉叉，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。
如果在我们的algorithm中，我们的样本点向量全部是以向量内积$\langle x, z\rangle$的形式出现的，我们就可以把算法中所有的向量内积$\langle x, z\rangle$替换为核函数的形式$\langle \phi(x), \phi(z)\rangle$，其中$\phi$表示特征映射feature mapping
给定一个feature mapping：$\phi$，我们定义其对应的核函数Kernel为：
核函数有什么优良特性呢？
核函数本身容易计算，不需要显式地计算$\phi(x)$ 和 $\phi(z)$并计算它们的内积，计算$\phi(x)$的算法复杂度为$O\left(n^{2}\right)$，而直接计算$K(x, z)$算法复杂度只需$O(n)$！我们只需$O(n)$复杂度去计算核函数，却达到了feature mapping之后在高维特征空间中一样的效果！
有哪些常见的核函数呢？
| 名称 | 表达式 | 参数 |
|---|---|---|
| 线性核 | $\kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)=\boldsymbol{x}{i}^{\mathrm{T}} \boldsymbol{x}{j}$ | |
| 多项式核 | $\kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)=\left(\boldsymbol{x}{i}^{\mathrm{T}} \boldsymbol{x}{j}\right)^{d}$ | $d \geqslant 1$为多项式的次数，映射到$C_{n+d}^{n}$维，证明见下文 |
| 高斯核 | $\kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}{i}-\boldsymbol{x}{j}\right\|^{2}}{2 \sigma^{2}}\right)$ | $\sigma>0$ 为高斯核的带宽(width)，映射到无穷维 |
| 拉普拉斯核 | $\kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}{i}-\boldsymbol{x}{j}\right\|}{\sigma}\right)$ | $\sigma>0$ |
| Sigmoid核 | $\kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)=\tanh \left(\beta \boldsymbol{x}{i}^{\mathrm{T}} \boldsymbol{x}{j}+\theta\right)$ | tanh为双曲正切函数，$\beta>0, \theta<0$ |
多项式核映射到$C_{n+d}^{n}$维的证明：
若x=(x1,x2,….xn), $\phi(x)$包含了x分量所有小于等于d次组合，那么$\phi(x)$的维度便 等价于问题$(1+x1+x2+x3+….xn)^{d}$ 展开有多少项，这个问题的计算用隔板法可以推出是$C{n+d}^{n}$。
证明方法： (1^n0)(x1^n1)…..(xi^n1)…(xn^nn) 有多少个等价于： n0+n1+n2….+nn=d 有多少种组合法,其中ni大于等于0。 变形一下： (n0+1)+(n1+1)+(n2+1)+….(nn+1)=d+n+1. 换一下表示方式N0+N1+….Nn=d+n+1, 其中Ni大于等于1, 此时便可以用隔板法了。 d+n+1个球代表有d+n个可选位置，要分成n+1份，则需要放入n个板。所以就是d+n个位置放入n个板，$C{n+d}^{n}$
如何判断一个核函数是否是有效的核函数？
若已知合适映射$\phi(\cdot)$的具体形式，则可写出核函数$\kappa(\cdot, \cdot)$。但在现实中我们通常不知道$\phi(\cdot)$的具体形式，那么什么样的函数是有效的核函数呢？我们有如下定理：
Theorem（Mercer):
对于一个给定核函数$K: \mathbb{R}^{n} \times \mathbb{R}^{n} \mapsto \mathbb{R}$，如果K是一个有效的(Mercer)核，对任意m个样本点$\left{x^{(1)}, \ldots, x^{(m)}\right}$，其对应的kernel matrix是半正定的。这互为充要条件。
定义：Kernel matrix
对于m个样本点$\left{x^{(1)}, \ldots, x^{(m)}\right}$，我们有$m \times m$方阵，其$(i, j)$元为$K_{i j}=K\left(x^{(i)}, x^{(j)}\right)$。这个矩阵就叫Kernel Matrix