支持向量机

问题提出

支持向量机的分类基本思想在给定的样本空间中寻找一个超平面将训练样本进行分割，而且能够对新样本也进行正确的分类。

如下图中，这样的超平面有许多个，如何选择才能使得效果较好。更直观的观察就是在两个类别之间，存在一定的间隔，如果这个间隔越大，是不是意味着两个类别能更好的区分？！

支持向量机（Support Vector Machine）

根据这个观察，那么如何来描绘这个间隔就是接下来的问题。就一个二维或者或者三维空间而言，间隔就是意味着距离，这是发生在两点、平行线、平行面之间。那么在下图中，我们很容易去选择两个平行线或者平行面来来描绘这个间隔，一个简单的办法就是将我们所要寻找的超平面进行平移，得到一组平行的平面，这是就会产生我们所说的间隔。

问题抽象

几个概念
定义（函数间隔）对于给定的训练数据集D和给定的超平面S(w,b)，定义超平面S关于样本点(x(i),y(i))的函数间隔为：

γ^(i) = y (i) (w x (i) + b)

那么可以定义超平面S关于训练数据集D的函数间隔为所有样本点中函数间隔的最小值，即：

γ^= min i = 1, 2, \dots, m γ^(i)

函数间隔在一定程度上可以表征分类预测的正确性和确信度（感知机使用的就是函数间隔），但选择分类超平面时，如果成比例的扩大参数那么函数间隔也会相应的增大，那么可以使用规范化的手段来限制这种变化，经过规范化的函数间隔称之为几何间隔。

定义（几何间隔）对于给定的训练集D和平面S(w,b)，定义的超平面S关于样本点(x(i),y(i))的几何间隔为：

γ (i) = 1 | | w | | y (i) (w x (i) + b)

定义超平面S关于训练数据集D的几何间隔为所有样本点到该超平面几何间隔中的最小值，即：

γ = min i = 1, 2, \dots, m γ (i)

基于以上的分析和定义，将问题描述如下：
假设给出样本的形式为X=(x1,x2,⋯,xd),每个样本对应一个类别Y=y。那么可以定义一个样本实例为(X,Y)=(x1,x2,⋯,xd,y)，现在有数据集D={(x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))},如果有一个新样本X′,如何确定其对应的类别Y′。

问题的数学理解
支持向量机寻找的是一个能将样本集进行线性分割的超平面。这样的超平面存在无数个，感知机就是寻找其中的任意一个；而支持向量机与之不同的是寻找的是几何间隔最大的一个，这样的满足条件的超平面具有唯一性。那么问题可以表示为带约束的最优化问题：

max w, b γ s . t . 1 | | w | | y (i) (w x (i) + b) \geq γ, i = 1, 2, \dots, m

依据几何间隔和函数间隔的关系：

γ (i) = γ^(i) | | w | | γ = γ^| | w | |

那么，问题可以转化为：

max w, b γ^| | w | | s . t . y (i) (w x (i) + b) \geq γ^, i = 1, 2, \dots, m

在上述的优化问题中，当超平面的参数同时变化时，函数间隔也同时变化，这种变化对优化问题中的目标函数和不等式约束没有影响，因此我们可以令γ^=1。那么上述优化问题可以等价地写成：

min w, b 12 | | w | | 2 s . t . y (i) (w x (i) + b) - 1 \geq 0, i = 1, 2, \dots, m

问题的几何解释
那么可以定义一个超平面：

W T x + b = 0 (1)

那么与该超平面平行的超平面为：

W T x + b = Δ (2)

理想的超平面将所有的样本分为两类，标记为正类和反类。那么两类中到各自距离分割超平面最近的样本所在的与分割超平面平行的超平面可以表示为：

W T x + b = Δ + (3) W T x + b = Δ - (4)

那么不妨令：

Δ + + Δ - = 0 (5) | Δ + | = | Δ - | = 1 (6)

那么可以得到两个平行面的距离 γ，称之为几何间隔。根据之前的分析，这个间隔越大，那么我们的超平面应该有更好的分类效果。

max W, b γ = 2 | | W | | s . t . {W T x (i) + b W T x (i) + b \geq 1, y (i) = 1 \leq - 1, y (i) = 1 (7)

上述问题等价于：

min W, b γ = 12 | | W | | 2 (8) s . t . y (i) (W T x (i) + b) \geq 1, i = 1, 2, \dots, m

这是带约束的最优化问题，想到使用Lagrange乘子法，在最优点满足KKT条件

问题解法

解决上述(8)的带约束的优化问题，构建Lagrange函数：

L (W, b, λ) = 12 | | W | | 2 - \sum i = 1 m λ i (y (i) (W T x (i) + b) - 1) (9)

那么(8)问题转化为：

min W, b 12 | | W | | 2 = min W, b max λ i \geq 0 L (W, b, λ) (10)

由KKT条件,在局部最优解处有：

⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ \partial L \partial W = 0 \partial L \partial b = 0 λ i (y (i) (W T x (i) + b) - 1) = 0 i = 1, 2, \dots, m λ i \geq 0 i = 1, 2, \dots, m (11)

那么：

\partial L \partial W = W - \sum i = 1 m λ i y (i) x (i) = 0 (12) \partial L \partial b = \sum i = 1 m λ i y (i) = 0 (13)

将(11)、(12)代入(9)得：

L (W, b, λ) = 12 | | W | | 2 - \sum i = 1 m λ i (y (i) (W T x (i) + b) - 1)) = 12 W T W - b \sum i = 1 m λ i y (i) + \sum i = 1 m λ i - \sum i = 1 m λ i y (i) W T x (i) = 12 (\sum i = 1 m λ i y (i) x (i)) T (\sum i = 1 m λ i y (i) x (i)) + \sum i = 1 m λ i - \sum i = 1 m λ i y (i) (\sum i = 1 m λ i y (i) x (i)) T x (i) = \sum i = 1 m λ i - 12 (\sum i = 1 m λ i y (i) x (i)) T (\sum i = 1 m λ i y (i) x (i))

L (W, b, λ) = \sum i = 1 m λ i - 12 \sum i = 1 m \sum j = 1 m λ i λ j y (i) y (j) (x (i)) T x (j)

那么，优化问题(8)转化为：

min W, b max λ i \geq 0 \sum i = 1 m λ i - 12 \sum i = 1 m \sum j = 1 m λ i λ j y (i) y (j) (x (i)) T x (j) s . t . ⎧ ⎩ ⎨ ⎪ ⎪ \sum i = 1 m λ i y (i) = 0 i = 1, 2, \dots, m λ i \geq 0 (14)

优化问题(14)的对偶问题为：

max λ i \geq 0 min W, b \sum i = 1 m λ i - 12 \sum i = 1 m \sum j = 1 m λ i λ j y (i) y (j) (x (i)) T x (j) s . t . ⎧ ⎩ ⎨ ⎪ ⎪ \sum i = 1 m λ i y (i) = 0 i = 1, 2, \dots, m λ i \geq 0 (15)

优化问题(15)中的目标函数与W,b无关，因此可以变为：

max λ i \geq 0 \sum i = 1 m λ i - 12 \sum i = 1 m \sum j = 1 m λ i λ j y (i) y (j) (x (i)) T x (j) s . t . ⎧ ⎩ ⎨ ⎪ ⎪ \sum i = 1 m λ i y (i) = 0 i = 1, 2, \dots, m λ i \geq 0 (16)

上述优化问题(16)是一个二次规划问题，可以使用通用的二次规划算法来解。SMO算法是解决该问题的一个高效算法。

序列最小优化算法(SMO)

坐标上升

考虑一个无约束的优化问题：

max α W (α 1, α 2, \dots, α m)

坐标上升法的基本思想是：除某个参数外，固定其余的参数；然后再为固定的参数维度上进行搜索，使得目标函数最大；更新未固定的参数，然后选择其他参数(Note:不是相邻的选择，参数维度是可以相同的！−−−−−−−−−−−−−−−−−−−−−−−−−−−−)重复上述操作，直到所有的目标函数收敛为止。

伪代码如下：

loopuntilconvergence{fori=1,2,⋯,m{αi:=argmaxα^iW(α1,⋯,αi−1,αi,⋯,αm−1,αm)}}

SMO

基本思想：按照坐标上升的做法，应该挑选一个变化的参数而固定其他参数，但是由于问题(16)是带约束的优化问题，被固定的参数可以由固定的参数根据约束∑mi=1λiy(i)=0推导出来。因此，此处选取两个参数λi,λj,然后固定其余参数，依据坐标上升法进行搜索。对于非固定的两个变量构建一个二次规划问题，这个子问题的解会使得原始问题的目标函数变小，更重要的是这个子问题可以有解析解！！！通过不断地求解子问题来达到求解原问题的目的。根据所述，整个SMO算法包含两个部分：求解两个变量的二次规划的解析方法和选择变量的启发式算法。

变量选择方法
两个变量的选择，其中至少有一个变量时违反KKT条件的（选择的目的）。

1、第一变量的选择
SMO中第一变量选择的过程称为外循环，选择违反KKT条件最严重（如何判断是否严重？）的样本点，并将其对应的变量作为第一个变量。对于最优解时所有样本点满足KKT条件：

λ i λ i = 0 \Rightarrow y (i) (w x (i)) > 1 > 0 \Rightarrow y (i) (w x (i)) = 1

检验在ϵ范围内进行,首先对λ>0对应的样本进行测试其是否满足KKT条件，如果都满足在扩大到整个训练集进行测试。

2、第2个变量的选择
第2个变量的选择称为内循环。第二个变量选择的标准是希望使目标函数能够有足够大的变化。如果不能有足够的变化那么需要放弃第2个变量重新选择，遍历支持向量点依次作为第2个变量进行尝试；如果仍不满足则可遍历整个训练集；再找不着可以重新寻找第1个变量。

子问题解析解法
//待研究//

问题变种：软间隔

之前的问题中，一直假设存在这样的超平面，可以完美的将两类安全的分开。然而实际中，这种理想情况往往很难有，有时候碰到间隔不明显的情况。解决问题的办法是：让支持向量机在边界地区允许判断失误——软间隔，可以容忍一定的噪声和outliers。

那么可以将优化问题(8)修改为：

min W, b, ξ 12 | | W | | 2 + C \sum i = 1 m ξ i (17) s . t . {y (i) (W T x (i) + b) \geq 1 - ξ i i = 1, 2, \dots, m ξ i \geq 0 i = 1, 2, \dots, m

解决上述(17)的带约束的优化问题，构建Lagrange函数：

L (W, b, λ, ϕ) = 12 | | W | | 2 - \sum i = 1 m λ i (y (i) (W T x (i) + b) - 1 + ξ i) - \sum i = 1 m ϕ i ξ i (18)

那么优化问题(17)转化为：

min W, b, ξ 12 | | W | | 2 = min W, b, ξ max λ i, ϕ i \geq 0 L (W, b, λ, ϕ) (19)

由KKT条件,在局部最优解处有：

⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ \partial L \partial W = 0 \partial L \partial b = 0 \partial L \partial ξ = 0 λ i (y (i) (W T x (i) + b) - 1 + ξ i) = 0 i = 1, 2, \dots, m ϕ i ξ i = 0 i = 1, 2, \dots, m λ i \geq 0 i = 1, 2, \dots, m ϕ i \geq 0 i = 1, 2, \dots, m (20)

那么：

\partial L \partial W = W - \sum i = 1 m λ i y (i) x (i) = 0 (21) \partial L \partial b = \sum i = 1 m λ i y (i) = 0 (22) \partial L \partial ξ = C - λ i - ϕ i = 0 (23)

将(21)、(22)代入(17)得：

L (W, b, λ, ξ) = \sum i = 1 m λ i - 12 \sum i = 1 m \sum j = 1 m λ i λ j y (i) y (j) (x (i)) T x (j)

那么，优化问题(17)转化为：

min W, b, ξ max λ i, ϕ i \geq 0 \sum i = 1 m λ i - 12 \sum i = 1 m \sum j = 1 m λ i λ j y (i) y (j) (x (i)) T x (j) s . t . ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ \sum i = 1 m λ i y (i) = 0 i = 1, 2, \dots, m C - λ i - ϕ i = 0 ϕ i \geq 0 λ i \geq 0 (24)

优化问题(24)的对偶问题为：

max λ i \geq 0 \sum i = 1 m λ i - 12 \sum i = 1 m \sum j = 1 m λ i λ j y (i) y (j) (x (i)) T x (j) s . t . ⎧ ⎩ ⎨ ⎪ ⎪ \sum i = 1 m λ i y (i) = 0 i = 1, 2, \dots, m 0 \leq λ i \leq C i = 1, 2, \dots, m (25)

观察式子(25)和之前的式子(16)，只是在参数λ上多了一个上界C。

问题变种：线性不可分

核函数

对于轻微的非线性(含有噪声或者异常点)，我们可以通过软间隔来解决。但是如果非线性非常严重，软间隔也不能很好解决的时候，该如何做呢？一种比较好的解决办法是将样本映射到高维空间。打个比方说,样本在二维是不可分的，但是在三维空间也许是可分的。假如能找到这样的映射，那么就可以在那个高维的空间中使用SVM，这样问题就得到了解决。

假设映射关系为：

x - \to - - - ϕ ϕ (x) (26)

根据式(1)和式(12)，我们可以得到所需要的分类器：

f (x) = (\sum i = 1 m λ i y (i) x (i)) T x + b = \sum i = 1 m λ i y (i) (x (i)) T x + b (27) = \sum i = 1 m λ i y (i) ⟨ x (i), x ⟩ + b

结合式子(26)、(27)可得在高维空间的SVM为：

f (x) = \sum i = 1 m λ i y (i) ⟨ ϕ (x (i)), ϕ (x) ⟩ + b (28)

如果观察这个式子，我们可以知道，需要找到一个映射ϕ和计算样本在映射后在高维空间的内积才能对样本进行分类。那么，有没有一种办法，可以直接跨过这两步，也就是直接在低维空间就可以得到高维空间的内积。如果有这样的方法，那就会简单很多！矩阵分析中为我们提供这种方法——核函数。

令X为输入空间，κ(⋅,⋅)是定义在X×X上的对称函数，则κ是核函数当且仅当对于任意数据D={x1,x2,⋯,xm}，核矩阵K总是半正定的。

K = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ κ (x 1, x 1) ⋮ κ (x i, x 1) ⋮ κ (x m, x 1) \dots ⋱ \dots ⋮ \dots κ (x 1, x j) ⋮ κ (x i, x j) ⋮ κ (x m, x j) \dots ⋱ \dots ⋱ \dots κ (x 1, x m) ⋮ κ (x i, x m) ⋮ κ (x m, x m) ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥

几种常见的核函数
多项式核：

κ (x i, x j) = (x T i x j) d d \geq 1

高斯核：

κ (x i, x j) = exp (- | | x i - x j | | 2 2 σ 2) σ > 0

拉普拉斯核：

κ (x i, x j) = exp (- | | x i - x j | | σ) σ > 0

Sigmoid核：

κ (x i, x j) = tanh (β x T i x j + θ) β > 0, θ < 0

References:
[1]斯坦福机器学习课程——SVM
[2]周志华:《机器学习》
[3]张薇:《最优化方法》
[4]支持向量机通俗导论
 [5]支持向量机（五）SMO算法
[6]李航：《统计学习方法》