title: 12. SVM（三）核函数 date: 2018-07-22 21:33:00 categories: SVM tags: [SVM, 核函数] mathjax: true

在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$的形式。

有时候，我们会将一些特征转换到高维空间上，就像我们在之前的3. 过拟合&局部加权回归中提到的，比如特征$x$表示的是房屋面积，我们需要预测房子是否会在6个月内被卖出，我们有时候会将这个特征映射成如下的形式： $$ x \rightarrow \begin{bmatrix} x \
x2 \
x3 \
x4 \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 Rn$，核函数被定义为： $$ \begin{align} k(x, z) = (xT 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(n2)$，而计算核函数仅仅需要计算$xTz$，复杂度为$O(n)$。

接下去我们为这个核函数增加常数项： $$ k(x,z)=(xTz+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)=(xTz+c)d $$

有了核函数，即可替换SVM中的内积$\langle x{(i)}, x{(j)} \rangle$，比如常用的高斯核： $$ k(x,z)=\exp(-\frac{||x-z||2}{2\sigma2}) $$ 有了核函数，相当于把数据从原始空间转换到了高位空间，很多数据，在一维空间往往是线性不可分的，但是到了高维空间会变成可分的：

核函数的合法性

如何判断一个核函数是合法的呢？判断依据是：是否存在函数$\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$，都存在$zTKz \geq 0$，证明如下： $$ \begin{align} zTKz &= \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}$是一个对称的半正定矩阵。