支持向量机的核函数

什么是核函数？核函数的作用是什么？怎么样把核函数和支持向量机结合起来？怎么样使用支持向量机来解决分类问题？怎么样在逻辑回归算法，支持向量机，神经网络这三个分类算法里选择使用哪个算法来解决实际问题？本文就是回答这些疑问的。

核函数

什么是核函数？核函数是特征转换函数。这是非常抽象的描述，这一节的内容就是为了理解这个抽象的概念的。

从多项式说起

多项式

时，我们预测出 $y=1$。上述公式只写了二阶多项式，我们可以写到更高阶的多项式来模拟复杂的分界线。我们改写一下上面的公式：

改写多项式

这里，$f_1=x_1, f_2 = x_2, f_3 = x_1 x_2, f_4 = x_1^2, f_5 = x_2^2 ...$ 。

那么问题来了，除了多项式外，有没有更好地途径把特征 $x_1, x_2$ 映射到特征 $f_1, f_2, f_3, f_4, f_5 ...$ 呢？

相似性函数

我们在二维坐标上选择三个标记点 $l^{(i)}$ ，针对一个训练样例 $x$，我们使用相似性函数来定义新的特征：

Similarity Function

如下图所示，当我们选择三个标记点 $l^{(1)}, l^{(2)}, l^{(3)}$ 时，针对一个只有两个特征的训练样例 $(x_1, x_2)$，通过我们的相似性函数映射后，我们将得到 $f_1, f_2, f_3$ 三个新特征。

高斯核函数

我们把上面的相似性函数称为高斯核函数，它的主要作用就是把输入特征映射到另外一组特征上。当 $x$ 离标记点 $l^{(i)}$ 很近的时候，这两个点间的距离接近于 0 ，故 $f_i$ 接近于 1 。当 $x$ 离标记点 $l^{(i)}$ 很远的时候，这两个点间的距离接近于无穷大，故 $f_i$ 接近于 0 。

理解相似性函数

假设我们选择了三个标识点 $l^{(1)}, l^{(2)}, l^{(3)}$ ，映射出三个新特征 $f_1, f_2, f_3$ ，那么当：

Paste_Image.png

时，我们预测为 1。假设我们训练出来的参数为 $\theta_0 = -0.5, \theta_1 = 1, \theta_2 = 1, \theta_3 = 0$ ，那么当某个测试样例点 $x$ 靠近 $l^{(1)}$ ，但远离 $l^{(2)}, l^{(3)}$ 时，我们可以得出：

Paste_Image.png

即我们把测试样例点 $x$ 归类到 $y=1$ 这个类别里。相同的道理，假设某个测试样例 $x$ 离三个标记点都很远，那么：

Paste_Image.png Similarity

针对训练样例，也满足上述核函数。由于我们选择 landmark 与训练样例重合，所以针对训练样例 $x^{(i)}$ 有 $f_i=1$ 。

计算预测值

假如我们已经算出了 $\theta$，那么当 $\theta^Tf >= 0$ 时，预测值为 1，反之为 0。

计算参数

根据 SVM 的成本函数，由于我们把 $f$ 代替 $x$ 作为新的特征，所以我们可以通过最小化下面的函数来计算得出参数 $\theta$

Cost Function

针对上述公式，实际上 $m=n$，因为 $f$ 是由训练数据集 $x^{(i)}$ 定义，即 $f$ 是一个 m 维的向量。

支持向量机算法的参数

1. C 值越大，越容易造成过拟合，即 lower bias, higher variance. 当 C 值越小，越容易造成欠拟合，即 higher bias, lower variance。
2. $\sigma^2$ 越大，高斯核函数的变化越平缓，会导致 higher bias, lower variance。当 $\sigma^2$ 越小，高斯核函数变化越快，会导致 lower bias, higher variance。

实践中的 SVM

一般情况下，我们使用 SVM 库 (liblinear, libsvm ...) 来求解 SVM 算法的参数 $\theta$，而不是自己去实现 SVM 算法。在使用这些库的时候，我们要做的步骤如下

• 选择参数 C
• 选择核函数
  • 可以支持空的核函数，即线性核函数 (linear kernel)。Predict "y = 1" if $\theta^Tx >= 0$。
  • 高斯核函数 $f_i = exp \left( - \frac{| x - l^{(i)} |^2}{2\sigma2} \right)$，这个时候需要选择合适的参数 $\sigma^2$。

在使用第三方算法的时候，一般需要我们提供核函数的实现。输入参数是 $x_1, x_2$，输出为新的特征值 $f_i$。另外一个需要注意的点是，如果使用高斯核函数，在实现核函数时，需要对参数进行缩放，以便加快算法收敛速度。

多类别的分类算法

这个和逻辑回归里介绍的 one-vs.-all 一样。可以先针对一个类别和其他类别做二元分类，逐个分类出所有的类别。这样我们得到一组参数。假如，我们有 K 个类别，那么我们最终将得到 $\theta^{(1)}, \theta^{(2)}, \theta^{(3)} ... \theta^{(K)}$ 个参数。

算法选择

逻辑回归和 SVM 都可以用来解决分类问题，他们适用的场景有些区别。

假设 n 是特征个数；m 是训练数据集的样例个数。一般可以按照下面的规则来选择算法。

如果 n 相对 m 来说比较大。比如 n = 10,000; m = 10 - 1000，如文本处理问题，这个时候使用逻辑回归或无核函数的 SVM 算法。
如果 n 比较小，m 中等大小。比如 n = 1 - 1000; m = 10 - 10,000。那么可以使用高斯核函数的 SVM 算法。
如果 n 比较小，m 比较大。比如 n = 1 - 1000; m = 50,000+ 。那么一般需要增加特征，并且使用逻辑回归或无核函数的 SVM 算法。

以上的所有情况都可以使用神经网络来解决。但训练神经网络的计算成本比较高。