[ML Notes] SVM：核函数

Author: nex3z 2020-09-02

1. 一个例子

  假设 $\phi(\boldsymbol x)$ 是二阶多项式映射，将二维的样本空间映射到三维的特征空间，即

$$\phi(\boldsymbol x) = \phi\bigg( \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \bigg) = \begin{bmatrix} x_1^2 \\ \sqrt{2} x_1 x_2 \\ x_2^2 \end{bmatrix}$$

计算特征空间中两个向量的内积为

$$\begin{aligned} \phi(\boldsymbol a)^\mathrm{T} \phi(\boldsymbol b) &= \begin{bmatrix} a_1^2 \\ \sqrt{2} a_1 a_2 \\ a_2^2 \end{bmatrix}^\mathrm{T} \begin{bmatrix} b_1^2 \\ \sqrt{2} b_1 b_2 \\ b_2^2 \end{bmatrix} \\ &= a_1^2 b_1^2 + 2 a_1 a_2 b_1 b_2 + a_2^2 b_2^2 \\ &= (a_1 b_1 + a_2 b_2) ^ 2 \\ &= \bigg( \begin{bmatrix} a_1 \\ a_2 \end{bmatrix}^\mathrm{T} \begin{bmatrix} b_1\\ b_2 \end{bmatrix} \bigg)^2 \\ &= (\boldsymbol a^\mathrm{T} \boldsymbol b)^2 \end{aligned}$$

上式表明，可以通过原始样本空间二维向量的内积 $\boldsymbol a^\mathrm{T} \boldsymbol b$，来得到特征空间三维向量的内积 $\phi(\boldsymbol a)^\mathrm{T} \phi(\boldsymbol b)$，由此得到二阶多项式的核函数为

$$\mathcal{K}(\boldsymbol x_i, \boldsymbol x_j) = (\boldsymbol x_i^\mathrm{T} \boldsymbol x_j)^2 \tag{1}$$

  通过核函数，可以使用原始空间的内积来得到特征空间的内积，降低直接计算特征空间内积的计算量，甚至不需要知道特征空间 $\phi(\boldsymbol x)$ 的具体变换。

2. 核函数

  向上面的例子那样，如果已经知道了 $\phi(\boldsymbol x)$ 的具体形式，则可以得到核函数 $\mathcal{K}(\cdot , \cdot)$。但在实际场景中通常不会知道 $\phi(\boldsymbol x)$ 的具体形式，为了直接寻找合适的核函数，有如下定理。

  核函数　令 $\mathcal{X}$ 为输入空间，$\mathcal{K}(\cdot, \cdot)$ 是定义在 $\mathcal{X} \times \mathcal{X}$ 上的对称函数，则 $\mathcal{K}$ 是核函数当且仅当对于任意数据 $D = \{\boldsymbol x_1, \boldsymbol x_2, \dots, \boldsymbol x_m\}$，核矩阵（kernel matrix） $\boldsymbol K$ 总是半正定的

$$\boldsymbol K = \begin{bmatrix} \mathcal{K}(\boldsymbol x_1, \boldsymbol x_1) & \cdots & \mathcal{K}(\boldsymbol x_1, \boldsymbol x_j) & \cdots & \mathcal{K}(\boldsymbol x_1, \boldsymbol x_m) \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \mathcal{K}(\boldsymbol x_i, \boldsymbol x_1) & \cdots & \mathcal{K}(\boldsymbol x_i, \boldsymbol x_j) & \cdots & \mathcal{K}(\boldsymbol x_i, \boldsymbol x_m) \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \mathcal{K}(\boldsymbol x_m, \boldsymbol x_1) & \cdots & \mathcal{K}(\boldsymbol x_m, \boldsymbol x_j) & \cdots & \mathcal{K}(\boldsymbol x_m, \boldsymbol x_m) \end{bmatrix} \tag{2}$$

  对于一个半正定矩阵，总能找到一个与之对应的映射 $\phi$，即任何一个核函数都隐式定义了一个称为“再生核希尔伯特空间”（Reproducing Kernel Hilbert Space，RKHS）的特征空间。选择不同的核函数，就意味着选择了不同的特征空间。

3. 常用核函数

  常用的核函数有

• 线性核
  • 表达式：$\mathcal{K}(\boldsymbol x_i, \boldsymbol x_j) = \boldsymbol x_i^\mathrm{T} \boldsymbol x_j$
• 多项式核
  • 表达式：$\mathcal{K}(\boldsymbol x_i, \boldsymbol x_j) = (\boldsymbol x_i^\mathrm{T} \boldsymbol x_j)^d$
  • 参数：$d \geq 1$ 为多项式次数
• 高斯核
  • 表达式：$\mathcal{K}(\boldsymbol x_i, \boldsymbol x_j) = \exp (-\frac{||\boldsymbol x_i -\boldsymbol x_j||^2}{2\sigma^2})$
  • 参数：$\sigma \geq 0$ 为高斯核的带宽
• 拉普拉斯核：
  • 表达式：$\mathcal{K}(\boldsymbol x_i, \boldsymbol x_j) = \exp (-\frac{||\boldsymbol x_i -\boldsymbol x_j||}{\sigma})$
  • 参数：$\sigma \geq 0$
• Sigmoid 核
  • 表达式：$\mathcal{K}(\boldsymbol x_i, \boldsymbol x_j) = \tanh(\beta \boldsymbol x_i^\mathrm{T} \boldsymbol x_j + \theta)$
  • 参数：$\beta > 0$，$\theta < 0$

  通过对核函数进行适当的组合，也可以得到核函数，例如 若 $\mathcal{K}_1$ 和 $\mathcal{K}_2$ 为核函数，则

• 对于任意正数 $\gamma_1$、$\gamma_2$，其线性组合 $\gamma_1 \mathcal{K}_1 + \gamma_2 \mathcal{K}_2$ 也是核函数。
• 核函数的直积 $\mathcal{K}_1 \otimes \mathcal{K}_2 (\boldsymbol x, \boldsymbol z) = \mathcal{K}_1(\boldsymbol x, \boldsymbol z) \mathcal{K}_2(\boldsymbol x, \boldsymbol z)$ 也是核函数。
• 对于任意函数 $g(\boldsymbol x)$，$\mathcal{K}(\boldsymbol x, \boldsymbol z) = g(\boldsymbol x) \mathcal{K}_1(\boldsymbol x, \boldsymbol z) g(\boldsymbol z)$ 也是核函数。