机器学习笔记—支持向量机（2）

发表: 2017-05-08 浏览: 1477

机器学习

第一次看 Andrew Ng 的支持向量机讲义时，没看懂核概念，后来想可能是因为讲义从映射函数 Φ(x) 到核函数 K(x,z) 跳得太快了吧。

在讲线性回归时，使用房屋面积来预测价格，房屋面积是 x，我们考虑过使用 x、x2、x3 来回归得到一个三次函数。使 Φ 为映射函数，此处为

x 向量只有一个元素，该映射也即

把训练数据集 {(x(i),y(i));i=1,...,m} 映射为 {(Φ(x(i)),y(i));i=1,...,m}，也就是说，通过映射，我们生成了一个新的数据集，跟老数据集一一对应，每个数据的维度要多一些。

现在我们可以针对这个新的数据集计算最优间隔分类器。在映射之前的原始最优间隔分类器为：

当 wTx+b 大于 0 时，预测 y 为 1。

映射之后的最优间隔分类器为：

把之前的 x 都换成 Φ(x) 就对了。x 与 x 之间的内积变成 Φ(x) 和 Φ(x) 之间的内积。

我们定义核函数为映射后特征向量的内积：

也可以表示成：

所以，映射后的最优间隔分类器也可表示为：

给定映射函数 Φ，可以很容易通过计算 Φ(x) 和 Φ(z) 的内积来得到 K(x,z)，但有趣的是，K(x,z) 通常很容易计算，反倒是 Φ(x) 计算起来很费劲，可能是因为高维度向量，在这种情况下，直接在 Φ 映射后的空间里使用核函数 K(x,z)，而不显式使用 Φ(x)，是效率比较高的。我们来看几个例子。

假设 x,z∈Rn，考虑

也可写作：

由此，可以看到 K(x,z)=Φ(x)TΦ(z)，设 n=3，可得：

也即映射：

注意到，计算高维 Φ(x) 的时间复杂度为 O(n2)，而 K(x,z) 为 O(n2)。

再来看个例子：

设 n=3，映射函数 Φ 为：

参数 c 控制着 xi 和 xixj 之间的相对权重。

再推而广之，K(x,z)=(xTz+d) 对应的映射 Φ 的特征空间为 C(n+d,d) ，如果不管这个 O(nd) 维空间，计算 K(x,z) 只需要 O(n) 时间，所以在我们从不需要在高维特征空间中表示特征向量。

给定一个函数 K，如何知道它是不是一个有效的核，也就是说，存在一个特征映射 Φ，使得对于所有的 x、z，有 K(x,z)=Φ(x)TΦ(x)。

假定 K 是一个有效的核，映射函数为 Φ。现在，考虑一个有限训练集 {x(1),...,x(m)}，设 K 是一个 m*m 的矩阵，其中 Kij=K(x(i),y(j))。这个矩阵称作核矩阵。

因为 Kij=K(x(i),y(j))=Φ(x(i))TΦ(y(j))=Φ(x)Φ(y)=K(x(j),y(i))=Kji，所以，K 必定是对称的。

更进一步，使 Φk(x)表示向量 Φ(x) 的第 k 个坐标。设 y 为任意向量，有

因为 z 是任意向量，所以 K 是半正定矩阵。

所以，我们证明了如果 K 是个有效核（即关联了一些特征映射 Φ），那么核矩阵 K∈Rm*m 是对称半正定的。事实上，这不仅是个必要条件，也是个充分条件，K 也被称为 Mercer 核。

定理(Mercer)：给定 K：Rn×Rn—>R，K 是一个有效（Mercer）核，它的充分必要条件是，对于 {x(1),...,x(m)},(m<∞)，相应的核矩阵是对称半正定的。

之前介绍的 SVM 的求导是假定数据是线性可分的，当把数据通过 Φ 映射到高维特征空间后，增加了数据可分的可能性，但我们不能保证一定可分。有些情况下，就不清楚找到的超平面是不是我们需要的，因为它容易受异常点的影响。例如，下面左图是一个最优间隔分类器，当左上角区域添加一个异常点时，它导致分类边界有一个明显的偏移，最终的分类器的间隔就小得多。