二、核函数

上一节我们说到，在引入对偶问题与KKT条件以后，此时的w为

于是此时的模型从wx+b转换成了另一个形式：

以下的核函数，都是基于上面的式子来说的：

对于比较简单的样例，比如X = [x₁,x₂]只有两个特征，就可以用上一节的图中“圈与×”的点很方便的进行表示，也可以很方便的线性可分。
并且对于需要预测的 x的类别，我们就会计算每个支持向量机的样例x⁽ⁱ⁾与x之间的内积。
最终再与正负1进行比较。

以上都是线性可分时的情况。

那么线性不可分时怎么办呢？怎么把SVM应用到线性不可分的情况中呢？

比如下面举的例子中，X = [x₁²，x₂²，x₂]在二维坐标系中是线性不可分的，那应该怎么办呢？就根据特征构造一个映射函数Φ(X)，把特征映射到新的高维的坐标系中去，这样，这个特征点在新的高维的坐标系中就线性可分了，就可以用SVM进行分类了。
于是，此时模型中，需要计算的内积，就不再是x⁽ⁱ⁾与x了，而是二者的映射函数之间的内积了（因为只有这样，才能线性可分）：

但是这样，需要每次都实现计算一次映射函数，然后计算样例与需要预测的样例的映射函数之间的内积，十分麻烦并且会维度爆炸。
我们又发现，右边两个映射函数的结果，可以用一个x⁽ⁱ⁾与x的式子表示。而这个式子，只需要在低维度计算x⁽ⁱ⁾与x的式子，就可以达到同样的计算效果，即二者的wx+b的结果是一样一样的，那么肯定是后者好呀，后者就是核函数。

先总的概括三步，再分别细细的解释这三步

2.1 核函数总结：

• 1. 实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去，映射到高维空间后，相关特征便被分开了，也就达到了分类的目的；
• 2. 但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的(甚至会到无穷维，维度爆炸)。
• 3. 此时，核函数就隆重登场了，核函数绝就绝在它在低维上进行计算，但是和 采用第二步（映射到高维以后进行运算）计算得到的结果是相同的，效果也是一样的。（这句话是精髓，后面会解释。）
     但是，相比于第二步（映射到高维以后进行运算），核函数的优点就体现出来了：避免了直接在高维空间中的复杂运算，不需要显示的写出映射函数Φ（高维），大大降低了时间复杂度。

2.2 分步讲解以上三点

2.2.1 遇到线性不可分的情况

线性不可分数据

如上图，此时是线性不可分的。
如果用X₁和X₂来表示这个二维平面的两个坐标的话，这条二次曲线的实际方程是如下（加了少量噪声 生成得到的）：

从上式可以看出，此时关于X的多项式是有三个的：X₁²，X₂²，X₂。
原来的特征点，使用二维平面上的坐标表示的，即X = （X₁，X₂）。现在，我们试着“将样例特征映射到高维空间中去”，因为上式有三个多项式，所以三个特征就足够线性可分了（下面会解释）。
经过映射函数Φ(X)，我们得到了新的特征 X' = （X₁²，X₂²，X₂），此时用这三个特征来简历坐标系，那么上面的二维平面图会变成这个样子：

再旋转：

此时，数据是可以通过一个平面切分开来的，此时就可以用SVM分类了。

由上，可以得出结论，也即上面的总结1：当我们遇到线性不可分的样例时，我们的常用做法是把样例特征映射到高维空间中去，映射到高维空间后，相关特征便被分开了，也就达到了分类的目的。

2.2.2、维度爆炸的情况

首先，上面的线性不可分数据的图形是二次曲线中的特例，一般情况下，二次曲线的方程如下：

也就是说，此时关于特征X₁和X₂的多项式，变为了5个（原始空间的所有特征一阶和二阶的组合）。那么为了让这个曲线中的样例线性可分，根据 上一节的的想法，就需要将特征映射到一个5维空间中去。

这么看似乎没什么问题，但是！如果现在原始空间是3维呢？

• 如果映射原始空间的特征的二项式的组合（比如X₁X₁，X₁X₂共有3*3个） 那么就会得到一个9维空间；
• 如果映射到原始空间特征所有的一阶和二阶的组合，就会得到一个19维的空间。

假设现在原始空间有100个特征呢？
------------------------------------------------------------------------------------------------
可以看到，这个数目，是呈爆炸性增长的，这样下去

• 首先计算映射函数Φ(X)就十分困难了：考虑所有的特征组合
• 还会增加运算的复杂度：两个高维（比如10000或无穷）的向量相乘，耗费时间

------------------------------------------------------------------------------------------------

2.2.3、核函数的隆重登场

分两部分进行，先解释第一部分的这句话：在低维上进行计算，但是和 采用第二步（映射到高维以后进行运算）计算得到的结果是相同的，效果也是一样的。

再解释第二部分的这句话：避免了直接在高维空间中的复杂运算，大大降低了时间复杂度。

一、与‘’映射到高维以后进行计算‘’的效果相同的核函数

1.1 直观了解一下核函数

核函数的定义：计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数(Kernel Function)。

看不懂没关系，举几个核函数的例子先直观了解一下：

甚至把上式 中的数字1 去掉也是一个核函数。

1.2 不采用核函数的情况下，SVM的表达

如2.2.1小节，我们希望将得到的特征映射后的特征应用于SVM分类，而不是最初的特征。这样我们需要将判别模型中w^Tx+b公式中的内积从<x⁽ⁱ⁾,x>映射到<Φ(x⁽ⁱ⁾),Φ(x)>。其中x⁽ⁱ⁾是支持向量，x是需要判别的样本。

将核形式化定义，如果原始特征内积是<x,z>，映射后为<Φ(x),Φ(z)>，那么定义核（Kernel）为

至此，我们可以得出结论，如果要实现2.2.1小节的效果，只需计算出Φ(x)，然后计算Φ(x)^TΦ(z)即可。

然而，这种计算方式是非常低效的。
比如最初的特征是n维的，我们将其映射到n²维，然后再计算，这样为我们需要O(n²)的时间。
for i in range(n²)：
---- x_i*z_i（n²次）

1.3 采用核函数的情况下，有什么效果

上面讲到，单纯的先把特征映射到高维再计算内积的方式是十分耗时间的，那么能不能想办法，减少计算时间呢？

举个栗子：

假设x和z都是n维的

展开后，得

这个时候发现我们可以只计算原始特征x和z内积的平方（时间复杂度是O(n) 。。。for i in range（n）。。。），就等价与计算映射后特征的内积。

是不是很有意思？

也就是说，用不同的计算方法，取得了相同的结果。（一个映射到高维以后做内积，一个（核函数）直接在原来的低维空间中进行运算）。而这里的K(x,z)就是一个核函数。核函数的优越可见一斑。

现在看一下映射函数（n=3时），根据上面的公式，得到

说明，一个核函数只能对应着一个映射函数。上面的这个核函数只有选择上面的这个映射函数时，才能够等价。

再比如，另一个核函数

对应的映射函数（n=3时）是

更一般的，核函数

对应的映射后特征维度为

综上，就是前面所说的：

• 1、核函数在在低维上进行计算，但是和 采用第二步（映射到高维以后进行运算）计算得到的结果是相同的

• 2、因为最终计算的结果是相同的， 而判别模型就是求得内积的结果以后和1比较大小，所以最终用SVM判断的效果也是一样的。

• 3、但是，相比于第二步（映射到高维以后进行运算），核函数的优点就体现出来了：避免了直接在高维空间中的复杂运算，不需要显示的写出映射函数Φ（高维），大大降低了时间复杂度。

1.4 几个核函数

通常人们会从一些常用的核函数中选择（根据问题和数据的不同，选择不同的参数，实际上就是得到了不同的核函数），例如：

• 1、多项式核

上面所举的例子也就是多项式核，而且这个核所对应的映射实际上是可以写出来的，该空间的维度是C^d_m+d，其中m 是原始空间的维度。

• 2、高斯核

因为这个函数类似于高斯分布，所以称为高斯核函数，也叫做径向基函数(Radial Basis Function 简称RBF)。它能够把原始特征映射到无穷维。

不过，如果�σ选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果�σ选得很小，则可以将任意的数据映射为线性可分——当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数�σ，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。

如下所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间：

• 3、线性核

这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了(意思是说，咱们有的时候，写代码，或写公式的时候，只要写个模板或通用表达式，然后再代入不同的核，便可以了，于此，便在形式上统一了起来，不用再分别写一个线性的，和一个非线性的)。

即 ，不用再写一下线性的SVM，再写一个非线性的SVM了，只需要写同样的代码，前者用线性核，后者用别的核就行了。

2.3 使用核函数以后，怎么分类新来的样本呢？

只需要将原来的内积替换成核函数就行了。值的判别也是同1进行比较。

2.4 核函数的有效性判定

详细参考Jerrylead的第八小节 。

问题：给出了一个 函数K，我们能否认为K是一个有效的核函数，或者说，能够找到一个映射函数Φ，使得对于所有的x和z，都有

证明：
如果假设K是有效地核函数，那么根据核函数定义：

可见，矩阵K应该是个对称阵。让我们得出一个更强的结论，那么对于任意向量z，有

最后一步，是因为 i 和 j 是同属性的，相当于x^Tx。从这个公式我们可以看出，如果K是个有效的核函数，那么，在训练集上得到的核函数矩阵K应该是半正定的。

这样我们得到一个核函数的必要条件：

K是有效的核函数 ==> 核函数矩阵K是对称半正定的。

可幸的是，这个条件也是充分的，由Mercer定理来表达。

简而言之就是：
核函数矩阵K是对称半正定的K是有效的核函数 ==> K是有效的核函数

写在最后：核函数不仅仅用在SVM上，但凡在一个模型后算法中出现了了<x,z>，我们都可以常使用K(x,z)去替换，这可能能够很好地改善我们的算法。

三、规则化和不可分情况的处理

3.1、什么情况下才是不可分？

我们之前讨论过：

• 样例线性可分时可以直接使用SVM进行分类
• 当样例线性不可分时（比如同心圆的情况），使用核函数来将特征映射到高维，这样很可能就可分了。

然而，映射后我们也不能100%保证可分。如下图：

上图中，有‘背叛’点出现，那么映射到三维，四维以后，也不一定能保证可分。如果非要给映射到非常高的维度，也许最终可分了，但是可过拟合了。这也不是我们想要的结果。

那怎么办呢，我们需要将模型进行调整（加入松弛变量ξ），以保证在不可分的情况下，也能够尽可能地找出分隔超平面。

3.2 调整模型，使之能够容忍不好归类的因子-- 软间隔

3.2.1 之前的模型的缺点

之前讨论过的模型中，是想找到一个绝对正确的平面能够分类出所有的正负例，但是，这种太‘硬’的做法可能取得反效果。如下图所示：

可以看到一个离群点（可能是噪声）可以造成超平面的移动，间隔缩小，可见以前的模型对噪声非常敏感。
再有甚者，如果离群点在另外一个类中，如上上图所示，那么这时候就是线性不可分了。

3.3.2 调整模型，实现软间隔

为了避免上述情况的发生，我们应该允许一些点游离并在在模型中违背限制条件（限制条件：函数间隔必须大于1）。于是我们设计得到新的模型如下（也称软间隔）

原约束条件右边等于1，说明，必须必须大于1，不能接受背叛（x点出现在了圈点内）的情况。这种情况，有两个缺点，一是分隔超平面容易受离群点的影响，二是甚至不可分。

现在约束条件右边变成了1-ξ，且每个样例的ξ>=0，也就是说允许出现离群点了（函数间隔可以小于1了）。甚至当 ξ 足够大时，可能1-ξ<0，间隔变为负数，也就是说可以出现背叛点了。

但是，不能惯着那些不安分的点，所以在 目标函数后面加上Cξ（大于0），最小化目标函数的情况下，就是表明一种态度，最好不要出现这种情况，但是出现了我也能忍，但是我会尽力压制。所以被称为软间隔。

松弛变量ξ是为了纠正或约束少量“不安分”或脱离集体不好归类的因子。

3.3.3 修改以后的模型 的对偶形式：

模型加入松弛变量以后，拉格朗日公式（加入约束条件）也要修改如下：

按照我们在拉格朗日对偶中提到的求法，定义函数θ^p使之合理，再变成对偶问题θ^d，最里面的参数就变成了w、b和ξ。分别对w、b和ξ求 偏导，代入公式中就得到了min L。然后就是求max了。这里只写出最后结果如下：

此时我们发现没有了参数ξ，与之前的模型不同之处在于0<=α 变成了0<=α<=C。为什么会这样勒？

前面所说，为得到最小值，对w、b和ξ分别求偏导，并另之为0（这也是KKT的第一个条件）。得到

又因为松弛变量系数 r 是大于等于零的，所以有α<=C。于是得到约束条件的第一个式子。

------------------------------------------------------------------------------------
之前说过，当目标函数是凸规划问题的时候==>

x * 满足KKT条件 是 强对偶条件（对偶问题的解等于原问题的解）的充要条件。
即，若d* = p* <==> x * 满足KKT条件
------------------------------------------------------------------------------------

也就是说，只有当 x * 满足KKT条件时，才能有d* = p，化成对偶问题才有意义。那么此时，就要让上述的最优解 α 向量满足KKT条件.

其中第一条偏导数为零比较好解释。
由第三个条件 αigi=0 可以得到

α_i作为样例的系数，取不同的值 时，代表着不同的样例位置。比如之前问题中，α_i=0时，说明样例在间隔平面内部。α_i>0时，说明在间隔平面上，是支持向量。

这里也一样：
α_i=0时：

α_i=C时：

0<α_i<C时：

简单些就是：

注意：当ξ>0时，说明此时就出现‘不安分’的点了，因为此时约束条件--函数间隔小于1。

上图中

• 第一种情况，α_i=0，ξ=0，说明该样例点在界内，正常的点被正确分类。
• 第二种情况，0<α_i<C，ξ=0，说明α_i是支持向量，该样例点在边界上。
• 第三种情况，α_i<0，ξ>0，此时约束条件--函数间隔小于1，说明该样例点或者在两条边界之间，或者在错误的阵营中。

----------------------------------------------------------------------------------------------

至此，算是得到了软间隔的SVM的目标函数，并且此时的 α 向量满足KKT条件，是对偶问题的最优解，也是原问题的最优解

3.4、悬而未决的问题

不论是‘硬’间隔的目标函数，还是软间隔的目标函数，我们都得到了预测新来样例的方法：用判别模型wx+b和1比较。

后来通过引入对偶问题，我们发现，可以不用计算w，直接用α就可以进行判别。

所以呢，怎么求α？