CS229：12-SVM（三）核函数

在 SVM(二)中，我们看到了如下的表示形式：

$$W(\alpha)=\sum_{i=1}\alpha_i-\frac{1}{2}\sum_{i=1}\sum_{j=1}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)$$

这里，内积$(x_i \cdot x_j)$就是最简单的核函数的形式。一般核函数会被写成$\langle x^{(i)}, x^{(j)} \rangle$的形式。

有时候，我们会将一些特征转换到高维空间上，就像我们在之前的过拟合&局部加权回归中提到的，比如特征$x$表示的是房屋面积，我们需要预测房子是否会在 6 个月内被卖出，我们有时候会将这个特征映射成如下的形式：

$$x \rightarrow \begin{bmatrix} x \\\ x^2 \\\ x^3 \\\ x^4 \end{bmatrix} = \phi(x)$$

原先的特征的内积形式$\langle x^{(i)}, x^{(j)} \rangle$会被写成$\langle \phi(x^{(i)}), \phi(x^{(j)}) \rangle$，而且往往$\phi(x)$会有很高的维度。因为在很多情况下，计算$\phi(x)$会有很高的代价，或者表示$\phi(x)$需要很高的代价，但是光是计算内核则可能代价较小。

比如：假如有两个输入：$x, z \in \Bbb R^n$，核函数被定义为：

$$\begin{align} k(x, z) = (x^T z)^2 &= (\sum_{i=1}^nx_iz_i)(\sum_{j=1}^nx_jz_j) \\\ &=\sum_{i=1}^n\sum_{j=1}^n(x_ix_j)(z_iz_j) \\\ &= \phi(x)^T\phi(z) \end{align}$$

假如需要表示成高维向量，那么$\phi(x)$是一个$n \times n$维的向量，如果$n = 3$：

$$\phi(x) = \begin{bmatrix} x_1x_1 \\\ x_1x_2 \\\ x_1x_3 \\\ x_2x_1 \\\ \vdots \\\ x_3x_3 \end{bmatrix}$$

所以，计算$\phi(x)$的时间复杂度就达到了$O(n^2)$，而计算核函数仅仅需要计算$x^Tz$，复杂度为$O(n)$。

接下去我们为这个核函数增加常数项：

$$k(x,z)=(x^Tz+c)^2$$

那么：

$$\phi(x) = \begin{bmatrix} x_1x_1 \\\ x_1x_2 \\\ x_1x_3 \\\ x_2x_1 \\\ \vdots \\\ x_3x_3 \\\ \sqrt{2c}x_1 \\\ \sqrt{2c}x_2 \\\ \sqrt{2c}x_3 \\\ c \end{bmatrix}$$

更一般的：

$$k(x, z)=(x^Tz+c)^d$$

有了核函数，即可替换 SVM 中的内积$\langle x^{(i)}, x^{(j)} \rangle$，比如常用的高斯核：

$$k(x,z)=\exp(-\frac{||x-z||^2}{2\sigma^2})$$

有了核函数，相当于把数据从原始空间转换到了高位空间，很多数据，在一维空间往往是线性不可分的，但是到了高维空间会变成可分的：

核函数的合法性

如何判断一个核函数是合法的呢？判断依据是：是否存在函数$\phi$，使得$k(x,z)$能够被写成$\langle \phi(x), \phi(z) \rangle$。

定理：如果核函数合法，那么其对应的核矩阵（kernel matrix）是半正定的。

核矩阵指的是矩阵$K \in \Bbb R^{m\times m}$，其中$K_{ij}=k(x^{(i)}, x^{(j)})$。半正定的意思是，对于任意向量$z$，都存在$z^TKz \geq 0$，证明如下：

$$\begin{align} z^TKz &= \sum_i\sum_jz_iK_{ij}z_j \\\ &= \sum_i\sum_jz_i\phi_(x^{(i)})^T\phi_(x^{(j)})z_j \\\ &= \sum_i\sum_jz_i\cdot \sum_k\phi_(x^{(i)})_k\underbrace{\phi_(x^{(j)})_k}_{向量第k项} \cdot z_j \\\ &= \sum_k\sum_i\sum_jz_i\cdot \phi_(x^{(i)})_k\phi_(x^{(j)})_k \cdot z_j \\\ &= \sum_k(\sum_iz_i\phi(x^{(i)}))^2 \geq 0 \end{align}$$

事实上，上面的定理的逆命题也一样成立，总结起来：

Merce 定理：给定核函数$k(x, z)$，那么$k(x, z)$合法（也即$\exists \phi, k(x,z)=\phi(x)^T\phi(z)$），当且仅当，对所有的$\lbrace x^{(1)}, \ldots, x^{(m)} \rbrace$，核矩阵$K \in \Bbb R^{m\times m}$是一个对称的半正定矩阵。