回顾对偶支持向量机
当特征空间维数$\tilde d$很大时，计算$q_{n,m}=y_ny_m\mathbf z_n^T\mathbf z_m$是对偶支持向量机的求解瓶颈。
能否找到比$O(\tilde d)$快的方法计算$\mathbf z_n^T\mathbf z_m=\Phi(\mathbf x_n)^T\Phi(\mathbf x_m)$？能否将先特征转换再计算内积的两步合为一步呢？
核技巧
对于2阶多项式变换 \[ \Phi_2(\mathbf x)=\left(1, x_1,x_2,\ldots,x_d,x_1^2,x_1x_2,\ldots,x_1x_d,x_2x_1,x_2^2,\ldots,x_2x_d,\ldots,x_d^2\right)， \] 为了简化同时包含了$x_1x_2$和$x_2x_1$这样的项。变换之后$Z$空间的内积可以可直接通过$X$空间计算 \[ \Phi_2(\mathbf x)^T\Phi_2(\mathbf x’)=1+\left(\mathbf x^T\mathbf x’\right)+\left(\mathbf x^T\mathbf x’\right)^2。 \] 这种特征转换和内积合并的方法称之为核函数， \begin{equation*} K_{\Phi_2}\left(\mathbf x,\mathbf x’\right)=\Phi_2(\mathbf x)^T\Phi_2(\mathbf x’)。 \end{equation*} 利用核函数，可以简化对偶支持向量机的实现，二次项的系数为 \begin{equation} q_{n,m}=y_ny_m\mathbf z_n^T\mathbf z_m=y_ny_mK\left(\mathbf x_n,\mathbf x_m\right)， \end{equation} 利用支持向量$\left(\mathbf x_s, y_s\right)$计算偏移量 \begin{equation} \begin{aligned} b =&y_s-\mathbf w^T\mathbf z_s\\ =&y_s-\left(\sum_{n=1}^N\alpha_ny_n\mathbf z_n\right)^T\mathbf z_s\\ =&y_s-\sum_{n=1}^N\alpha_ny_nK\left(\mathbf x_n,\mathbf x_s\right) ， \end{aligned} \end{equation} 对于特定的输入$\mathbf x$，判别函数为 \begin{equation} \begin{aligned} g_{SVM}(\mathbf x) =&\mbox{sign}\left(\mathbf w^T\Phi(\mathbf x)+b\right)\\ =&\mbox{sign}\left(\sum_{n=1}^N\alpha_ny_nK\left(\mathbf x_n,\mathbf x\right)+b\right) 。 \end{aligned} \end{equation} 从上面的公式可以看出，计算不再依赖变换后的空间，只依赖原空间，$b$和判别函数只依赖原空间的支持向量，大大简化了计算。
多项式核
仿照2阶多项式核的定义，可以推导高阶多项式核的定义为 \begin{equation} K_Q(\mathbf x,\mathbf x’)=\left(\zeta + \gamma\mathbf x^T\mathbf x’\right)^Q\quad\zeta\geq 0,\gamma > 0。 \end{equation} 事实上，系数$\zeta$和$\gamma$的取值不会改变多项式所在的空间，这些系数会被$\mathbf w$所吞噬。但是，不同的系数会得到不同的支持向量和判别函数。选择不同的核，相当于改变了边界的定义。多项式核可以在几乎不增加计算量的情况下，得到复杂的判别界。支持向量机通过large-margin控制判别界的复杂度。
上图是2阶多项式核支持向量机的效果，不同系数下的支持向量和判别界不同。
当$\zeta=0,\gamma=1$时，多项式核就变为了线性核。线性核利用原始支持向量机就比较高效。因此，应当首先尝试线性核，当线性核不能满足要求时再尝试其它高阶核。
高斯核
对于1维数据的高斯核，利用Taylor展式可得 \begin{equation*} \begin{aligned} K(x,x’) =&\exp\left(-\left(x-x’\right)^2\right)\\ =&\exp\left(-x^2\right)\exp\left(-x’^2\right)\exp\left(2xx’\right)\\ =&\exp\left(-x^2\right)\exp\left(-x’^2\right)\sum_{i=0}^\infty\frac{\left(2xx’\right)^i}{i!}\\ =&\sum_{i=0}^\infty\exp\left(-x^2\right)\exp\left(-x’^2\right)\sqrt{\frac{2^i}{i!}}\sqrt{\frac{2^i}{i!}}x^ix’^i\\ =&\Phi(x)^T\Phi(x’)， \end{aligned} \end{equation*} 其中$\Phi(x)=\exp\left(-x^2\right)\cdot\left(1,\sqrt{\frac{2^1}{1!}}x,\sqrt{\frac{2^2}{2!}}x^2,\ldots\right)$，容易看出这是无穷维的特征变换。更一般的高斯核定义为 \begin{equation} K\left(\mathbf x,\mathbf x’\right)=\exp\left(-\gamma\left\lVert\mathbf x-\mathbf x’\right\rVert^2\right)\quad \gamma>0。 \end{equation} 高斯核也成为径向基函数（RBF，Radial Basis Function）核。基于高斯核的判别函数为 \begin{equation} g_{SVM}(\mathbf x)=\mbox{sign}\left(\sum_{SV}\alpha_ny_n\exp\left(-\gamma\left\lVert\mathbf x-\mathbf x_n\right\rVert^2\right)+b\right)， \label{eq:rbf-svm} \end{equation} 它是以支持向量为中心的高斯函数的线性组合，不再依赖$\mathbf w$，只依赖于支持向量和系数$\alpha_n$。
高斯核相当于进行了无限维的特征转换，可以得到复杂的判别界，泛化性能通过最大边界“保证”。
上图是不同系数的高斯核支持向量机的效果，$\gamma$越大，高斯函数越尖，越容易过拟合。当$\gamma\rightarrow\infty$时，$K_{lim}\left(\mathbf x,\mathbf x’\right)=[[\mathbf x＝\mathbf x’]]$，相当于严格判断是否与支持向量一致。
小结
各种核函数的比较如下表：
| 核函数 | 优势 | 局限性 |
|---|---|---|
| 线性核 | 计算快； 通过$\mathbf w$和支持向量容易解释 |
无法处理线性不可分数据 |
| 多项式核 | 可以通过次数$Q$控制复杂度 | 当$Q$很大时数值计算困难 （当$\left\lvert\zeta+\gamma\mathbf x^T\mathbf x’\right\rvert<1$时，$K(\mathbf x, \mathbf x’)\rightarrow 0$）； 3个参数难以选择 |
| 高斯核 | 强大； $K(\mathbf x, \mathbf x’)$有界； 1个参数容易选择； |
没有显示的$\mathbf w$供解读； 计算比线性核慢； 太强大导致容易过拟合 |
当采用多项式核时，如果$Q$较小，可以尝试直接利用特征变换和原始支持向量机，求解速度可能比核方法更快。
核是一种特殊的相似性度量，但是不是所有的相似性度量都可以作为核。有效的核必须满足Mercer条件（充要条件）：核函数矩阵 \begin{equation*} \begin{aligned} \mathbf K =&\begin{bmatrix} \Phi(\mathbf x_1)^T\Phi(\mathbf x_1) & \Phi(\mathbf x_1)^T\Phi(\mathbf x_2) &\ldots &\Phi(\mathbf x_1)^T\Phi(\mathbf x_N)\\ \Phi(\mathbf x_2)^T\Phi(\mathbf x_1) & \Phi(\mathbf x_2)^T\Phi(\mathbf x_2) &\ldots &\Phi(\mathbf x_2)^T\Phi(\mathbf x_N)\\ \ldots&\ldots&\ldots&\ldots\\ \Phi(\mathbf x_N)^T\Phi(\mathbf x_1) & \Phi(\mathbf x_N)^T\Phi(\mathbf x_2) &\ldots &\Phi(\mathbf x_N)^T\Phi(\mathbf x_N) \end{bmatrix}\\ =&\left[\mathbf z_1\quad\mathbf z_2\quad\ldots\quad\mathbf z_N\right]^T\left[\mathbf z_1\quad\mathbf z_2\quad\ldots\quad\mathbf z_N\right]\\ =&\mathbf Z\mathbf Z^T \end{aligned} \end{equation*} 必须是对称半正定。
若$K_1(\mathbf x,\mathbf x’)=\Phi_1(\mathbf x)^T\Phi_1(\mathbf x’)$和$K_2(\mathbf x,\mathbf x’)=\Phi_2(\mathbf x)^T\Phi_2(\mathbf x’)$是两个有效的核，那么下面生成的也是有效的核：
- $K(\mathbf x,\mathbf x’) = K_1(\mathbf x,\mathbf x’)\cdot K_2(\mathbf x,\mathbf x’)$；
- $K(\mathbf x,\mathbf x’) = K_1(\mathbf x,\mathbf x’)+K_2(\mathbf x,\mathbf x’)$；
- $K(\mathbf x,\mathbf x’) = (1-K_1(\mathbf x,\mathbf x’))^{-1},\quad 0<K_1(\mathbf x,\mathbf x’)<1$；
- $K(\mathbf x,\mathbf x’) = \alpha K_1(\mathbf x,\mathbf x’),\quad\alpha\in\mathbb R$。
