资料参考来源：

清华大学出版社 周志华 《机器学习》 第六章

清华大学出版社 李航 《统计学习方法》 第二章 感知机，第七章 支持向量机

第七讲：最优间隔分类器、拉格朗日对偶、支持向量机

cs229 lecture 3 support vector machine

对于线性可分的训练数据，硬间隔最大化线性支持向量机可以说是几乎完美的算法。但是在实际问题中，训练集往往都是线性不可分（线性不可分不等同于非线性）的，也即是说，总是会有噪声或者特异点对我们的数据集造成干扰，这个时候，我们就需要更一般的能够适应这种情况的算法。

软间隔最大化

线性支持向量机软间隔最大化的原始问题

为了应对线性不可分的状况，我们需要引入软间隔最大化来代替原来的硬间隔最大化。

假设我们有一个线性不可分的训练数据集$T=\{(x_1,y_1),...,(x_N,y_N)\}$，$x_i∈X=R^n$,$y_i∈Y=\{-1,+1\},i=1,..,N$

那么，在通常情况下，这个训练集中会有少部分的特异点（outlier），只有将这些特异点去除后的训练数据集才是线性可分的。

从一方面来看，这些特异点就是不满足函数间隔大于等于1的约束条件。为了解决这个问题，我们可以引入松弛变量$ε_i≥0$（实际上我们可以将这个变量看作是以函数间隔衡量的误差量）使函数间隔加上松弛变量大于等于1来控制这些样本点的间隔。这样，我们就可以得到新的约束条件：

在有了这个改动之后，我们还要相应的修改目标函数：对每个松弛变量$ε_i$支付一个代价$ε_i$，将目标函数由原来的$\frac{1}{2}\mid\mid w\mid\mid^2$改为：

（这个部分很像是正则化之后的结构风险函数，后面我们会做讨论）

C>0 称为称罚参数，一般来说由问题决定，C值越大对于误分类的惩罚就越大，C值小对误分类的惩罚就小。这个时候，最小化目标函数的含义就分为了两层：

一是为了让$\frac{1}{2}\mid\mid w\mid\mid^2$尽量小也即是说间隔尽量大；

二是为了让误分类点的个数尽量少。

C便是调和两者的系数。

加入了上面的内容后，我们可以得到线性不可分的训练数据集的线性支持向量机的学习问题，或说凸二次规划（convex quadratic programming）问题（原始问题）为：

因为这是一个凸二次规划问题，所以关于$(w,b,ε)$的解是存在的。可以证明，w的解是唯一的，但b的解不唯一，b的解存在于一个区间内。

我们假设这个问题的解是$w^*,b^*$，于是，我们可以得到分离超平面$w^*x+b^*=0$以及分类决策函数$f(x)=sign(w^*x+b^*)$，我们称这样的模型为训练样本线性不可分时的线性支持向量机，简称线性支持向量机。

显然线性支持向量机包含线性可分支持向量机。但由于现实中训练数据集往往是不可分的，所以线性支持向量机具有更广的适用性。

我们浓缩以下上面的内容，得到线性支持向量机的定义：

线性支持向量机的定义

对于给定的线性不可分的训练数据集，通过求解凸二次规划问题，即软间隔最大化问题：

得到的分离超平面

以及相应的分类决策函数

称为线性支持向量机。

对偶算法

对偶问题形式

线性不可分数据集的凸二次规划问题的对偶问题为：

下面我们对如何得到这个对偶问题进行推导：

首先，我们构建原始最优化问题的拉格朗日函数：

其中$α_i≥0，μ_i≥0$

对偶问题是拉格朗日函数的极大极小问题。

我们首先求$L(w,b,ε,α,μ)$对$w,b,ε$的极小值：

由此我们得到

将求得的式子代入到拉格朗日函数，得到：

再对$min_{w,b,ε}L(w,b,ε,α,μ)$求α的极大，便得到对偶问题

我们将这个问题中的式子做一些变换：首先用$C-α_i$代替$μ_i$，然后再利用$μ_i≥0$得到

我们再将对目标函数求极大转换为求极小，就可以得到我们在这个小节之初给出的对偶问题的形式了。

求解方法

定理

设$α^*=(α_1^*,α_2^*,...,α_N^*)^T$是上面给出的对偶问题的一个解若存在$α^*$的一个分量$α_j^*$，$0 < α_j^* < C$，则原始问题的解$w^*,b^*$可按下式求得：

下面我们给出证明：

证明：

因为原始问题是凸二次规划问题，因此它的解满足KKT条件：

等式$w^*=\sum^N_{i=1}α_i^*y_ix_i$很容易可以由第一条式子求得。又由式子$α_i^*(y_i(w^*x_i+b^*)-1+ε_i^*)=0$ 和 $μ_i^*ε^*_i=0$我们可以得到，若存在$α_j^*$，$0 < α^*_j < C$（对应支持向量），则$y_i(w^*x_i+b^*)-1=0$，再代入第一条式子，我们就可以得到$b^*$的表达式。

由此定理，我们最终可以得到分离超平面的表达式：

以及分类决策函数：

该决策函数便是线性支持向量机的对偶形式。

看起来似乎与前面线性可分支持向量机没有什么区别，但事实上，我们要注意，这里的$b^*$的取值是不唯一的。

下面我们给出线性支持向量机的具体算法。

线性支持向量机算法

输入：训练数据集$T=\{(x_1,y_1),...,(x_N,y_N)\}$，其中$x_i∈X=R^n$，$y_i∈Y=\{-1,+1\},i=1,2...,N$

输出：分离超平面和决策函数

步骤：

1.选择惩罚参数C > 0，构造并求解凸二次规划问题

求得最优解$α^*=(α^*_1,...,α^*_N)^T$

2.计算$w^*=\sum^N_{i=1}α_i^*y_ix_i$

选择$α^*$的一个分量$α^*_j$适合条件$0 < α^*_j < C$，计算

3.求得分离超平面

分类决策函数

在步骤2中，对任一适合条件$0 < a_j^* < C$的$a_j^*$，按照步骤2中求$b^*$的等式都可以求出$b^*$，但是由于原始问题对b的解是不唯一的，所以实际计算中我们可以取在所有符合条件的样本点上的平均值。

支持向量

在线性不可分的情况下，我们将对偶问题的解$α^*=(α^*_1,...,α^*_N)^T$中对应于$α^*_i > 0$的样本点$(x_i,y_i)$的样本$x_i$称为支持向量（软间隔的支持向量）。如图所示：

上图中，实线就是分离超平面，虚线表示间隔边界，$\frac{ε_i}{\mid\mid w\mid\mid}$就是样本$x_i$到间隔边界的距离。（因为$y_i(w^*x_i+b^*)+ε_i^*$为距离超平面的函数间隔加上松弛变量，而函数间隔$\hat{γ}$除以w的L2范数得到几何间隔，所以$\frac{ε_i}{\mid\mid w\mid\mid}$就是以函数间隔角度表示的松弛变量转换成几何间隔角度的松弛变量，也即是离间隔边界的距离）

根据KKT互补条件$α_i^*(y_i(w^*x_i+b^*)-1+ε_i^*)=0$ 我们可以得到样本点的位置：

1. α=0，则$(y_i(w^*x_i+b^*)-1+ε_i^*)≥0$，说明样本点被正确分类
2. α=C，说明这是一个支持向量上的特异点，需要检查$ε_i$:
   • 若$α_i^*=C,0 < ε_i < 1$，则分类正确，$x_i$在间隔边界与分离超平面之间。
   • 若$α_i^*=C,ε_i =1$,则$x_i$在分离超平面上
   • 若$α_i^*=C,ε_i > 1$，则$x_i$在分离超平面误分的一侧。
3. 若$α_i^* < C$则$ε_i = 0$，支持向量$x_i$恰好落在间隔边界上

由此我们得到软间隔的支持向量$x_i$分布在三个区域：

1. 间隔边界上
2. 间隔边界与分离超平面之间
3. 分离超平面误分一侧。

小结

不像上一章，本章的内容不多，我们不需要将整体的内容再做一次推导。所以我在这里仅仅是讨论一下算法优化中的一些细节。

先我们看回加入了松弛变量的原始问题：

我们在开头提到过这个问题的本身似乎是结构化风险最小化策略，$\frac{1}{2}\mid\mid w\mid\mid^2+C\sum^N_{i=1}ε_i$看起来就是结构化风险函数，但与我们常见的结构化风险函数不同，这个式子中的罚项$C$是加在经验风险上而不是正则化项上。

当然，我们可能会认为$\frac{1}{2}\mid\mid w\mid\mid^2$是经验风险项。但事实上，回顾硬间隔最大化一章，我们知道，$\frac{1}{2}\mid\mid w\mid\mid^2$仅是用于衡量“间隔”的函数，而非误差，因为在线性可分支持向量机的硬间隔最大化算法中我们考虑训练数据集是线性可分的，也即是说，一定有完美的超平面能够将训练数据集的正负类完全分开，换句话说，该模型在训练集上的误差为0 。而函数间隔能否衡量模型复杂度，我暂时没有找到相关资料。但何况，从另一方面来说，$ε$显然比起$\frac{1}{2}\mid\mid w\mid\mid^2$更像是用于衡量误差的项，只不过这个“误差”是针对“间隔边界”而言而不是针对分离超平面，而罚项$C$根据原文是用于“调和”两项之间的关系的系数，所以我更偏向于在模型正则化中，罚项不一定要加在正则化项上，如果这种说法成立的话，我们或许可以将这个问题看作是模型结构化风险最小化策略的一种。

下面关于合页损失函数的讨论，或许可以表示一些二者（原始最优化问题与结构风险最小化策略）之间的关系：

合页损失函数

对于线性支持向量机算法，我们还可以有另一种解释，就是最小化以下目标函数：

第一项是经验风险，第二项是正则化项。

第一项的函数为：

这个函数称为合页损失函数(hinge loss function)。下标”+”表示以下取正值的函数：

意思就是说，样本点$x_i$分对的时候损失函数的值为0，否则是$1-y_i(wx_i+b)$。但事实上，我们会发现有的样本点被正确分类，它的损失却不是0（如图7.5中的$x_4$）（或许是因为这个“损失”是相较间隔边界而言的，而不是分离超平面。）

由这个关系，我们可以得到定理

我们可以对这个定理做一点简单地证明：

首先我们将式子（7.63）中的$[1-y_i(wx_i+b)]_+$等价地看作$ε_i$，这样子我们就可以把这个问题转变成原始最优化问题（7.60）~（7.62）.

而且，因为$[1-y_i(wx_i+b)]_+≥0$，我们首先可以得到$ε_i≥0$，因此式子（7.62）成立。

然后，

• 当$1-y_i(wx_i+b) > 0$时，$1-y_i(wx_i+b)=[1-y_i(wx_i+b)]_+$，所以有$y_i(wx_i+b)=1-ε_i$；
• 当$1-y_i(wx_i+b) ≤ 0$时，就有$ε_i=0$.

因此，我们可以得到式子$y_i(wx_i+b)≥1-ε_i,i=1,...,N$ 成立。

代换后发现约束条件都满足，我们就可以将最优化问题写为：

假设$λ=\frac{1}{2C}$，则

因为$\frac{1}{C}$不影响我们优化，故可以去除，所以该问题与问题（7.60）等价。

书上提供了我们关于合页损失函数的图形：

横轴是函数间隔$y(wx+b)$，纵轴是损失。合页函数名字的由来是因为函数形状像一个合页（？）。

图中还标出了0-1损失函数（就是y=0和y=1那两条线），它是二分类问题的真正的损失函数（即仅有两值，分错（损失1）或者分对（损失0）），合页损失函数是0-1损失函数的上界（离散数学中，对一个集合M，如果集合中的任何数都不超过实数S，则称S为M的上界。这里的意思是假设0-1损失函数为f(x)，合页损失函数为g(x),对任意x,f(x)≤g(x)始终成立）。

由于0-1损失函数不是连续可导的，直接优化由它构成的目标函数往往会比较困难，因此我们时常会用其他损失函数来“代替”0-1损失函数进行优化。线性支持向量机就可以认为是优化由0-1损失函数的上界（合页损失函数）构成的目标函数。这时的上街函数又称为代理损失函数（surrogate loss function）

图中还有一条虚线，那表示感知机的损失函数$[-y_i(wx_i+b)]_+$。即样本点被正确分类时损失是0，否则是$-y_i(wx_i+b)$。与之相比，合页损失函数确保了样本点不仅要分类正确，还要确信度足够高的时候损失才能是0，换句话说，合页损失函数对学习有更高的要求。