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}\)是一个对称的半正定矩阵。