4 核技巧
针对线性不可分问题，不存在一个能正确划分两类样本的超平面，怎么办？
将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。
设样本 \boldsymbol{x} 映射后的向量为 \phi(\boldsymbol{x})，则划分超平面对应为 \boldsymbol{w}^{\top} \phi(\boldsymbol{x})+b=0。
重写原问题
\min _{\boldsymbol{w}} \frac{\|\boldsymbol{w}\|^2}{2}
s.t. y_i\left(\boldsymbol{w}^{\top} \phi\left(\boldsymbol{x}_i\right)+b\right) \geq 1, i=1,2, \ldots, m
重写对偶问题
\begin{gathered}
\max _{\boldsymbol{\alpha}} g(\boldsymbol{\alpha})=\sum_{i=1}^m \alpha_i-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \phi\left(\boldsymbol{x}_i\right)^{\top} \phi\left(\boldsymbol{x}_j\right) \\
\text { s.t. } \boldsymbol{\alpha} \geqslant 0 \text { and } \sum_{i=1}^m \alpha_i y_i=0
\end{gathered}
重写预测函数
y=\boldsymbol{x}^{\top} \boldsymbol{w}+b=\sum_i^m \alpha_i^{\star} y_i \phi(\boldsymbol{x})^{\top} \phi\left(\boldsymbol{x}_i\right)+b^{\star}
可以看到 \phi 仅以内积 \phi^T(x)\phi(x) 的形式出现。\phi(x)的维数可能很高甚至无穷维，通过计算 \phi(x) 直接计算内积通常是困难的，但是我们可以设想有一个函数 \kappa(x_i,x_j)=\phi^T(x_i)\phi(x_j)，这样就不用求解 \phi，直接带入这个函数就可以求得内积的值。这个函数就称之为核函数。
现在的问题是：
- 核函数是否存在？
- 什么样的函数可以作为核函数？
对于这两个问题，我们有 Mercer 定理：
令 \mathcal{X} 为输入空间， \kappa(\cdot, \cdot) 是定义在 \mathcal{X} \times \mathcal{X} 上的对称函数，则 \kappa 是核函数当且仅当对于任意数据集 D=\left\{\boldsymbol{x}_1, \cdots, \boldsymbol{x}_m\right\} ，核矩阵 K 总是半正定的
K=\left[\begin{array}{ccc}
\kappa\left(\boldsymbol{x}_1, \boldsymbol{x}_1\right) & \cdots & \kappa\left(\boldsymbol{x}_1, \boldsymbol{x}_m\right) \\
\vdots & \ddots & \vdots \\
\kappa\left(\boldsymbol{x}_m, \boldsymbol{x}_1\right) & \cdots & \kappa\left(\boldsymbol{x}_m, \boldsymbol{x}_m\right)
\end{array}\right]
这说明，只要一个对称函数对应的 K 是半正定的，其就能作为核函数使用。
至此我们只知道哪些函数可以作为核函数，但是不知道某个核函数的选择是否是合适的，所以这才是 SVM 的最大变数。经验来看，常用的核函数如下：
\begin{array}{lll}
\hline \text { 名称 } & \text { 表达式 } & \text { 参数 } \\
\hline \text { 线性核 } & \kappa\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right)=\boldsymbol{x}_i^{\top} \boldsymbol{x}_j & \\
\text { 多项式核 } & \kappa\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right)=\left(\boldsymbol{x}_i^{\top} \boldsymbol{x}_j\right)^d & d \geq 1 \text { 为多项式的次数 } \\
\text { 高斯核 } & \kappa\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_i-\boldsymbol{x}_j\right\|^2}{2 \delta^2}\right) & \delta>0 \text { 为高斯核的带宽(width) } \\
\text { 拉普拉斯核 } & \kappa\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_i-\boldsymbol{x}_j\right\|}{\delta}\right) & \delta>0 \\
\text { Sigmoid核 } & \kappa\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right)=\tanh \left(\beta \boldsymbol{x}_i^{\top} \boldsymbol{x}_j+\theta\right) & \beta>0, \theta<0 \\
\hline
\end{array}
函数组合也可得到一些核函数：
- 核函数线性组合 \gamma_1 \kappa_1+\gamma_2 \kappa_2
- 核函数直积 \kappa_1 \otimes \kappa_2(\boldsymbol{x}, \mathrm{z})=\kappa_1(\boldsymbol{x}, \mathbf{z}) \otimes \kappa_1(\boldsymbol{x}, \mathbf{z})
- 核函数生成 \kappa'=g(\boldsymbol{x}) \kappa(\boldsymbol{x}, \mathbf{z}) g(\mathbf{z})