SVM系列（二）：核方法概述---正定核以及核技巧

1.核函数概述

在机器学习之逻辑回归（Logistics Regression）中，我们考虑了这样一个问题：

考虑一个简单的二分类问题，有 两个特征，两个特征值都为0 or 1为C2，否则为C1。在逻辑回归中，输入某一个样本的两个特征值 ，与各自的权重 相乘，也就是求inner product，最后加上一个bias，得到z，再将z用Sigmoid函数处理，最后与0.5进行比较，就可以判断属于哪一个类别。但是我们将两个特征映射到一个二维坐标系上，发现根本不可能找到一条直线将两类样本完全分开。这种限制与数据量无关，是逻辑回归自己本身的限制。

鉴于上面这种情况，就需要用到Teature Transformation，即特征转换。用特征转换处理后，使得我们能够用一条直线将C1和C2，也就是下面的红点和蓝点分开。图里面的处理方法是：定义新的 ， 为点到(0,0)的距离， 为到点(1,1)的距离。处理后如下图所示：

这时候我们发现，就能够找到一条直线将两类点分开，但在实际应用中，我们往往不能够找到比较好的特征变换的方法。

上面这种其实还是只是二维到二维的转换，实际上我们可以是二维到三维的转换，比如下面这种情况：

同样形状与颜色的点代表同一类别。观察上图我们发现，在二维平面上，我们不可能找到一条直线恰好可以将两类样本点分开，但假设我们做如下处理：

这样我们就将二维的点变换到了三维，这个时候我们再看看分布情况：

这个时候两个蓝点在一个平面上，两个红点在另一个平面上，在它们之间很容易找到一个超平面来使得它们分开。

上面啰嗦了一大堆，总结一下就是：当我们在低维空间对样本数据处理时，我们发现用线性的模型无法处理。于是我们便把低维数据引入到高维中，这样就可以用线性的模型去处理。

2.正定核

我们所说的核函数大部分都是正定核。在下面的探讨中，输入空间为 ， 。

2.1定义

正定核的定义有两种：

•对于 ，若存在一个函数 ，使得 ，则称 为正定核函数•对于 ，如果 满足对称性以及正定性，则我们也称 为正定核函数

对第一条定义的说明：我们要将低维样本映射到高维，则我们需要一个映射函数，如果我们能够找到一个 函数，使得我们定义的 恰好是两个高维样本 的内积，则 就是一个正定核函数。但上面我们也说了，这个映射函数很不好找。

为啥一定要是内积？因为内积恰恰是数据挖掘中非常重要的一种计算方式，数据挖掘的很多方法都是借助内积来完成的，所以核函数具有强大的功能。

对第二条定义的说明：

•所谓对称性，是指 。•所谓正定性：对低维空间中任意N个样本 ，其对应的Gram矩阵是半正定的。什么是Gram矩阵？我们令K表示那N个样本的Gram矩阵：

该矩阵是一个N X N的矩阵，比如（1，1）这个位置就是 什么是半正定？我们任取一个N维的列向量 ，如果满足：

则说明这个N X N的矩阵K是一个半正定的矩阵。

2.2证明

我们一再强调，映射函数 不好找。 那么我们该怎么定义一个正定核？瞎猜吗？显然不是，我们可以根据第二个定义来构造。因此我们需要证明一二两个定义是互通的。

将一二两个定义结合起来就是：

Gram矩阵半正定且K满足对称性。

下面我们将证明这个结论。先看从左到右，假设已知了 ，因为是求内积，所以对称性是显而易见的。那么我们怎么推导出Gram矩阵半正定呢？根据半正定的定义：

因此正推可以实现。反推暂时不太会。。后期补上。

因此上述两个定义是相通的。在定义一中，我们得找到一个 ，这个通常不好找。而在定义二中，我们只需要自己定义一个函数K，然后取任意N个样本，联合K求它们的Gram矩阵，只要该矩阵满足半正定性质，那么我们定义的函数K就是一个正定核函数。

3.核技巧

 什么是核技巧？在SVM的推导中，我们看到：

注：上述 只是为了便于区分才这样写，实际上是 。我们令：

于是有：

所谓核技巧，就是指我们可以直接计算 （这个K是已知的，根据定义二可以构造），而不需要真正的去找一个 （通常是很难找的）。也就是说，我们并不关心低维到高维的映射 是什么样子的，我们只需要构造一个函数K，使得该函数可以表示为映射后空间里数据的内积，这样就可以了。

4.常见的核函数

伟大的前人已经帮我们定义好了很多的核函数，常见的有：