[ML Notes] SVM:核函数

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)$ 也是核函数。