支持向量机二：非线性问题与核技巧

传统的支持向量机模型通过一个超平面对于特征空间的分类，并不适用于非线性的分类问题。为了解决这一个问题，我们引入核技巧来解决这一问题。

核技巧

以一个二维空间为例 $\{x^{(1)}, x^{(2)}\}$ ，如果可以通过一个椭圆对于实例完成分类，我们可以通过一个线性变换 $z = f(x) = ((x^{(1)})^2, (x^{(2)})^2)$ 将椭圆变换为直线。在新空间中就有直线：

这样就将原本的非线性分类问题转化为了线性分类问题。

通过这个例子，对于一个非线性分类问题，可以通过一个变换将原空间映射为一个新的特征空间，转换为线性分类问题，这就是所谓核技巧的思想。我们首先引入核函数：

核函数

设 $\mathcal{X}$ 是输入空间（欧氏空间），设 $\mathcal{H}$ 为特征空间（希尔伯特空间），如果存在一个从 $\mathcal{X}$ 到 $\mathcal{H}$ 的映射 $\phi(x): \mathcal{X} \to \mathcal{H}$ ，对于所有的 $x, z \in \mathcal{X}$ ，函数 $K(x,z)$ 满足：

则称 $K(x, z)$ 为核函数

核技巧的应用

核技巧希望通过直接定义 $K(x,z)$ ，而不显示的定义 $\phi(x)$ 。可以简化我们在优化过程中的计算。

在原始的线性分类问题对偶问题中，目标函数为：

其中实例的内积可以使用核函数来代替，可以得到新的对偶问题的目标函数：

正定核

通过映射函数 $\phi(x)$ 可以直接构造核函数，但是反过来如何直接判断一个函数 $K(x,z)$ 是否是一个核函数。我们通常所说的核函数成为正定核函数，一个函数是正定核的充要条件是：

设 $K: \mathcal{X} \times \mathcal{X} \to \textbf{R}$ 是对称函数，则 $K(x, z)$ 为正定核函数的充要条件是对任意 $x_i \in \mathcal{X}, K(x, z)$ 对应分Gram矩阵是半正定矩阵。

常用核函数

多项式核函数

高斯核函数