1. 线性可分支持向量机

1.1 训练集: T={(x1,y1),(x2,y2),...,(xN,yn=N)},xi∈Rn,yi∈{−1,1}

1.2 如果存在 Rn 中的超平面能将 T 中的正例点和负例点分开, 我们就说T是线性可分的, 或者说T是线性可分训练集

1.3 给定线性可分训练集 T , 通过间隔最大化策略或求解等价的凸二次优化问题得到的分离超平面w⋅x b=0以及相应的决策函数

f(x)=sign(w⋅x+b) 被称为 线性可分支持向量机, 其中 x,w∈Rn,b∈R

1.4 设 (w,b) 是 T 上的分离超平面, 定义T到分离超平面的距离为 T 中距离分离超平面最近的点到(w,b)的距离, 称为 (w,b) 关于 T 的几何间隔, 记为γ. 由定义可知, 必有

γ=|w⋅xi+b||w|=yi(w⋅xi+b)|w| , 并且满足上述等式的点至少有一对 xi,xj 且 yi∗yj=−1 .

1.5 所谓的间隔最大化策略就是寻找 (w,b) 使 γ 达到最大, 为此可表述为一个最优化问题:

maxw,b  γs.t.yi(w⋅xi+b)|w|≥γ,i=1,2,...,N

评论: 遗憾的是, 这个问题并不是一个凸优化问题, 为了使用凸优化的理论, 我们需要把(1.5)转化成凸优化问题.

1.6现在设

γ^=|w|γ 原问题转化为: maxw,b  γ^|w|s.t.  yi(w⋅xi+b)≥γ^,i=1,2,...,N 注意到 γ^ 的取值不会影响原问题的解(生成的分离超平面是一样的), 因此我们取 γ^=1 于是问题变为: maxw,b    1|w|s.t.    yi(w⋅xi+b)≥1,i=1,2,...,N .为了使用凸优化理论, 我们需要将原问题转化为最小化问题, 且目标函数变为凸函数. 这可以通过使用 w2 代替 1|w| 成为新的目标函数完美解决, 此时原问题转化为标准的凸优化问题形式: maxw,b  12w2s.t.  yi(w⋅xi+b)−1≥0,i=1,2,...,N 这里使用系数 12 有两个原因: 一方面是为了求偏导数方便, 另一方面, 考虑到最小几何间隔必在一对正负例点上同时取得(1.4), 因此我们的目标函数从一开始就可以使用 2γ 代替, 这个系数 2 最终会变为目标函数上的12.

评论: 至此, 我们已经可以求解线性可分支持向量机了.但是传统的凸优化方法用在支持向量机的求解问题上显得太慢, 我们有专门针对求解支持向量机的最优化理论, 即KKT条件和SMO算法. 为了使用这些理论, 我们需要利用拉格朗日对偶性理论, 将原问题做进一步变换.

1.7 引入拉格朗日乘子:

α∈Rn,αi≥0 构造 拉格朗日函数: L(w,b,α)=12w2−Σαiyi(w⋅xi+b)+Σαi , 由此构建的下列最优化问题称为原问题的 拉格朗日对偶问题: maxα minw,b L(w,b,α) . 拉格朗日对偶性理论向我们保证: (1)如果原问题有解, 那么对偶问题也有解 (2)设对偶问题的解为 w∗,b∗,α∗ , 则 w∗,b∗ 是原问题的最优解.

1.8 化简(化简过程的公式太难写了, 有空再说吧)对偶问题, 我们得到标准的支持向量机专用的凸二次优化问题:

minα  12ΣiΣjαiαjyiyj(xi⋅xj)−Σαis.t.  Σαiyi=0αi≥0,i=1,2,...,N 使用SMO算法可以解出 a∗ , 再由KKT条件, 可以得到原问题的最优解: w∗=Σα∗iyixib∗=yj−Σα∗iyi(xi⋅xj),α∗j>0

1.9 上述学习算法叫做最大间隔学习算法, 即利用间隔最大化策略, 构造凸优化问题, 然后通过求解凸优化问题得到原始问题最优解的算法.

1.10 如果我们利用对偶性求解原始问题, 那么对应于 αi>0 的点 xi 称为支持向量. 注意到, 对于非支持向量, αi=0 , 即它不会向凸优化问题的求解提供任何约束, 因此支持向量机的解完全取决于支持向量.

2 线性支持向量机

评论: 训练集 T 并不总是线性可分的, 对于不能线性可分的训练集, 我们也可以学习到一个支持向量机.

2.1 对于非线性可分训练集, 通过软间隔最大化策略或求解等价的最优化问题得到的分离超平面(w,b)以及决策函数 f(x)=sign(w⋅x+b) 称为线性支持向量机

2.2 回忆在线性可分的情况下, 我们有凸优化问题:

maxw,b  12w2s.t.  yi(w⋅xi+b)≥1,i=1,2,...,N 在非线性可分的情况下, 约束条件并不是总能被满足, 因此我们减弱约束条件为: yi(w⋅xi+b)≥1−ξi,ξi≥0 , 我们将尽量使用满足约束的最小的 ξi , 为此, 为每个 ξi 支付一个代价, 这里我们选用最简单的代价函数 Cξi , C 被称为惩罚系数, 于是, 线性支持向量机的原始问题可以表述为:maxw,b  12w2 CΣξis.t.  yi(w⋅xi b)−1 ξi≥0,i=1,2,...,Nξi≥0

评论 至此, 已经可以用借助凸优化理论求解线性支持向量机了. 但是为了用上SMO算法和KKT条件以获得更高的学习效率, 我们往往将原始问题转化为其拉格朗日对偶问题来求解.

2.3 为了构建拉格朗日对偶问题, 我们引入两个拉格朗日乘子:

α,β∈Rn,  αi≥0,βi≥0 , 构造拉格朗日函数: L(w,b,ξ,α,β)=12w2+CΣξi−Σαi[yi(w⋅xi+b)−1+ξi]−Σβiξi , 由此得到拉格朗日对偶问题: maxα,βminw,b,ξ  L(w,b,ξ,α,β)s.t.αi,βi≥0 . 拉格朗日对偶性理论向我们保证: (1) 如果原问题有解, 则对偶问题必有解 (2) 设对偶问题的解为 α∗,β∗,w∗,b∗,ξ∗ , 则原始问题的解为 w∗,b∗,ξ∗

注意 这里不引入约束条件 yi(w⋅xi+b)≥1−ξi 和 ξi≥0 ,因为它们已经通过拉格朗日乘子 α,β ”集成”到了 L 中.

2.4 化简对偶问题, 得到对偶问题的标准凸二次规划形式:minα,β  12ΣiΣjαiαjyiyj(xi⋅xj)−Σαis.t.  0≤αi≤CΣαiyi=0. 使用SMO算法得到解 α∗,β∗ , 再由KKT条件得到原始问题的解:

w∗=Σα∗iyixib∗=yj−Σα∗iyi(xi⋅xj),  0<α∗j<C

2.5 LSVM的对偶问题等价于问题:

minw,b  Σ[1−yi(w⋅xi+b)]++λw2 , 其中 [1−y(w⋅x+b)]+ 被称为 合页损失函数.

2.6 对应于 αi>0 的点被称为支持向量, 支持向量有4类:

间隔边界上的支持向量: 0<αi<C 间隔边间以内被正确分类的支持向量: αi=C,0<ξi<1 分离超平面上的支持向量: αi=C,ξi=1 误分类的支持向量: αi=C,ξi>1

评论 当 0<αi<C 时, 有 0<βi<C . 由KKT对偶互补条件(不等约束与其系数之积为0), 我们知道必有 ξi=0

疑问 为什么当 αi=C 时, ξi 一定不为0呢?

3. 非线性支持向量机

3.1 设

K:Rn×Rn→R , 若有 ϕ:Rn→H 满足 K(x,y)=ϕ(x)ϕ(y) , 则 K 是Rn上的 核函数.

3.2 K 是Rn上的和函数当且仅当

∀x1,x2,...,xm∈Rn  [K(xi,xj)](m×m)是半正定阵,  1≤i,j≤m

3.2 对于非线性可分数据集, 我们利用核函数和最大间隔策略, 或者求解等价的凸二次规划问题, 得到的分离超平面 (w,b) 以及相应的分类决策函数 f(x)=sign(w⋅x+b) 叫做非线性支持向量机.

3.3 非线性支持向量机的原始问题为:

maxw,b  12w2+CΣξis.t.  yi(w⋅xi+b)−1+ξi≥0,i=1,2,...,Nξi≥0 ,对偶问题为 maxα,βminw,b,ξ  L(w,b,ξ,α,β)s.t.αi,βi≥0 ,对偶凸二次优化问题为 minα,β  12ΣiΣjαiαjyiyjK(xi,xj)−Σαis.t.  0≤αi≤CΣαiyi=0 , 解为 w∗=Σα∗iyixib∗=yj−Σα∗iyiK(xi,xj),  0<α∗j<C

3.4 常见的核函数有:

线性核: x⋅y 多项式核: (x⋅y+1)p 高斯核(高斯径向基函数RBF): e−(x−y)22σ2 sigmoid核: tanh(x⋅y+1)

评论 高斯核函数将 Rn 映射到了无限维的希尔伯特空间, 它的值域为 [0,1) , 可以用来衡量变量相似度. 在大多数情况下, RBF具有最好的性能.