1. 接上节的小尾巴

上节说道：对线性可分数据集，对偶最优化方法非常完美。有理论支撑，有实际可操作的凸优化解法。但是现实中，线性可分数据集很难找到，有噪声和特异点的存在，使得不能线性可分。于是需要把这个方法推广到一般上来。即本节的《线性SVM》。

数据集线性不可分情况下，样本点中肯定有些不能满足约束。于是修改硬间隔最大化，搞一个软间隔最大化：兼顾大多数点的情况下，给某些点走个后门，使得问题可以被解决。

通常，我们认为世界还是基本美好的。基于这个原则，我们主观上认为：训练集中存在一些特异点，去掉后剩下大部分还是线性可分的。

这些特异点，不能满足函数间隔大于等于1的约束条件。于是对每个样本，我们引入一个松弛变量 ξ≥0，将约束条件改为：

因为松弛变量 ξ≥0 ，所以函数间隔大于等于1的条件变松了，当 ξ=0.5 时，就是大于等于0.5了。

但是天下没有免费的午餐。对每个松弛变量 ξi ，计算一个代价，则目标函数变成：

原先我们目标是最小化 12||w||2，则可使得间隔尽量大。现在约束加了松弛变量。间隔越大，则那些特异点中误分类的越多，为保持约束，则松弛变量将越大，导致目标函数将变大。前后两项是相反的。（类似于模型误差+正则化损失。模型越复杂，误差越小，但正则化越大）

即我们的目标：前项尽量小，保证间隔尽量大些；同时后项尽量也小，要小就得让间隔小些，让误分类点少些。

按下葫芦浮起瓢。二者需要做一个平衡。为此引入一个惩罚参数 C，表示越照顾谁。C值越大，表示最大化间隔赠加一点，误分类点的惩罚将陡增。不能忍受误分类点的出现，只好牺牲原则开后门；C值越小，表示误分类点的影响越小，我们可多优先考虑最大化间隔。

线性SVM的基本问题/原始问题

注意：w解存在且唯一，但b不唯一。为何？因为线性可分中，α>0 对应的支撑向量都在边界上。w全部用上。算b时，乘子大于0还对应着一些走后门的向量。导致求解b时有多种可能，形成一个取值区间。

2. 线性SVM的对偶问题

同样的，可以将上述的原始问题转化为对偶问题。先给结论：

线性SVM的基本问题/原始问题

对应的线性SVM的对偶问题

从形式上看，于线性可分数据集的区别在于约束条件的不同。

如何推导？类似于上节。

写出原始问题的拉格朗日函数：

根据拉格朗日对偶性，原始问题的对偶问题是拉格朗日函数的极大极小问题。首先求L对（w,b）的极小，则有：

解得：

将其代入拉格朗日函数有：

再对上式求 α 的极大，即得到对偶问题：

将约束条件的后两项消去 μ ，即得到 0≤αi≤C 。

从对偶问题的解到原始问题的解

设求得对偶问题的最优解为 α∗=(α∗1,α∗2,...α∗N) ，存在分量 0<α∗j<C ，则原始问题的最优解可这样求：

上述结论和线性可分SVM相同。其得到是经过证明的：因原始问题是凸二次规划问题，其解满足KKT条件，所以可按照KKT条件展开，得到上述结果。

3. 线性SVM的支撑向量

算法：线性SVM的学习算法

• 构造并求解凸二次规划问题，求出最优解。和线性可分唯一不同在于约束条件中0≤αi≤C。
• 根据KKT条件计算（w,b）。w是大于0的乘子全上。b则是选择一个大于0的上。因线性可分中大于0的全部是边界上的支撑向量，b唯一。此处支撑向量广义了，b不唯一。
• 求得超平面为（w,b），分类决策函数为sign（w,b）。

在此，原始问题的解不唯一。b有多种选择。实际可取平均值。

乘子大于0的样本点的实例，称为支撑向量，其可见下图分布：

支撑向量构成：

• ξi=0 ，位于间隔边界H1和H2上。α∗i<C
• 0<ξi<1 ，位于间隔边界和分离超平面之间。α∗i=C
• ξi=1 ，位于分离超平面上。α∗i=C
• ξi>1 ，位于分离超平面误分一侧。α∗i=C

这段话仅是从数学公式上解释了各种情况下值的情况。

4. 如何解释拉格朗日乘子？

李老师在感知机一节中，提到过对偶问题的直观解释。

感知机的优化问题为：

求导有：

根据梯度下降法：

引入学习率（0-1之间）：

直观解释：当一个实例点被误分类，即位于分离超平面的错误一侧时，调整（w,b），使得超平面向误分类点一侧移动，减少该误分类点到超平面的距离。直至超平面超过该分类点使其正确。

对偶形式的角度看：

对误分类点通过：

逐步修改（w,b），假设修改 n 次，则（w,b）关于该点的增量分别是 αiyixi 和 αiyi 。αi=niη 。则最终学习到的（w,b）可表示为：

当η=1时，表示第i个实例点由于误分类而移动更新的次数。实例点更新次数越多，意味着它距离超平面越近，越难正确分类，对学习结果影响越大。

那你想想：这不就串起来了么？我们前面说，乘子大于0的对应着支撑向量。因为是支撑向量，距离平面最近，对学习结果影响最大，移动次数当然最多，其乘子自然大于0。而那些没有影响的点，本来就不需要移动，所以对应乘子自然为0了。

道理：线性可分SVM中，乘子对应着改点被分类正确所需要移动的花费。那些边缘上的点最难分，需要花费最大，乘子均大于0，这些点被称为支撑向量。而那些远离边缘的不需要花费，因此乘子为0，在确定超平面时不起作用。

那么，如何和线性SVM中的 C 对应起来？暂时没有想明白。（上面截图周老师的话仅是从数学上大小知道为何这样，但没有想到如何直观解释）

0904补充：

线性可分时，a≥0，其等价于 ∞≥a≥0，其在有限次内必可以全部分对（误分类次数是有上界的）。线性时， C≥a≥0，能分类对的在有限次肯定可以分对（< C），达到C时还不能分对的，则是那些徘徊在边界的，即它们此时全部作为支撑向量了。当C趋近于正无穷时，则优化目标无穷大，则必须要所有点都符合要求，此时就成了线性可分的情况。C越大，误分类惩罚越大，要求尽可能将点分对；同时C越大，可容纳移动次数上限增大，又有一些可分类对的。