1 低维映射到高维解决线性不可分问题

常常我们碰到的一些分类问题，是线性不可分的，例如下图这样：

对于这样的情况，通过之前的学习，我们了解到可以通过多项式回归结合逻辑回归的方式得到想要的结果：

为什么增加了高阶多项式之后，这样的分类问题就能够解决呢？

我们来举一个简单的例子，例如我们的数据是一维的：

我们没有办法使用一根直线将数据区分开来，因为不管怎么分，都会出现错误分类的情况：

如果原来的数据是 x ，我们给它增加一个维度 x²，从一维变成二维，数据就变成了这样：

我们可以用 y = x 这么一条直线将两者区分开来，这里设置 x² 为 y 轴。

回到一维中，其实就是这样的一条曲线 x² - x = 0：

多项式回归通过将数据从低维映射到高维，将原本线性不可分的情况变成了线性可分的情况。

2 利用核函数降低运算复杂度

不过使用多项式回归，随着维度的增加，会存在一个问题，那就是计算量会以几何级数增加。

而下面说到的核函数（Kernel Function）有助于解决这一个问题。

所谓的核函数，其实是一种计算的技巧，所以又被称为 Kernel Trick 。

如果 φ(x) 是 x 在高维的映射，那么我们定义核函数为：

为了方便演示，我们进行简单的假设。

假设 x 为一个 特征维度为 2 的向量：

假设 x 的映射 φ(x) 为：

那么我们对核函数的计算过程，是这样的：

类似的，如果特征维度为 n ，映射的阶数为 d，那我们可以得到的结果是：

你会发现先将特征映射到高维，然后在高维计算内积，和直接计算特征内积，然后进行高阶运算，两者的结果是一样的。

不同之处就在于，前者运算的时间复杂度是O(n^d)，而后者是O(n)。

3 是否核函数的判定

映射必须要满足一定的条件，我们才能进行这样的公式变换。就拿上面的推导为例，如果映射是

两者的计算结果是不相等的。

但问题是，寻找映射 φ(x) ，然后进行推导计算非常麻烦。

那对于核函数的判定，还有没有别的办法呢？

根据Mercer定理，任何半正定的函数都可以作为核函数。

例如对于上面所说的函数：

有 m 个训练样本 { x⁽¹⁾，x⁽²⁾，x⁽³⁾，… ，x^(m) } ，我们可以将任意的两个 x⁽ⁱ⁾ 和 x^(j) 代入到函数中得到：

i 和 j 都可以从 1 到 m，计算到的函数矩阵 K 是一个 m × m 的矩阵。

如果该函数的矩阵 K 是半正定的，那么该函数就是核函数。

根据向量的运算规则 A^TB = B^TA ，我们可以推导得到：

也就是该函数矩阵 K 是一个对称矩阵。

特征维度为 n ，我们用 φ_k(x) 代表映射函数 φ(x) 第 k 维的属性值。

那么对于任意 m × 1 的向量 z 来说，可以进行如下推导：

所以该函数矩阵 K 是一个半正定的矩阵。

综合来看，矩阵 K 是对称半正定的，满足Mercer定理，所以这个函数是核函数。

Mercer定理不是核函数必要条件，只是一个充分条件，也就是说还有不满足Mercer定理的函数也可以是核函数。

4 常用的核函数

核函数有很多，最常用的是高斯核函数：

高斯核函数可以将原始的特征空间映射到无穷维的特征空间。

对于样本 { x⁽¹⁾，x⁽²⁾，x⁽³⁾，… ，x^(m) } ，l 的取值是所有的 x 。

高斯核函数计算的是每一个 x^(j) ，和所有的 l⁽ⁱ⁾ 之间的距离关系：

上图中突起的点代表着就是 l⁽ⁱ⁾ 的位置，而 x^(j) 在图中落点的高度，就是核函数的值。

如果 x^(j) 与 l⁽ⁱ⁾ 距离很近，那么 || x^(j) - l⁽ⁱ⁾ ||² ≈ 0，核函数的值为 1；如果 x^(j) 与 l⁽ⁱ⁾ 距离很远，那么 || x^(j) - l⁽ⁱ⁾ ||² >> 0，核函数的值为 0 。

同样距离下，核函数变化的敏感度，可以通过 σ 来控制。

σ 越小，同样距离下核函数的结果就越小：

σ 越大，同样距离下核函数的结果就越大：

如果 σ 选择过小，可以将任意数据映射得线性可分，进而导致过度拟合。

如果 σ 选择过大，相当于一个低维度的空间，容易欠拟合。

文章转载自公众号：止一之路