浏览本文须要的背景知识点：拉格朗日乘子法、KKT 条件、一丢丢编程常识

一、引言

  后面一节咱们介绍了一种分类算法——奢侈贝叶斯分类器算法，从概率分布的角度进行分类。上面咱们会花几节来介绍另一种在分类问题中有着重要位置的算法——反对向量机 ¹（Support Vector Machine/SVM）。

  SVM 从根底到简单能够分成三种别离为线性可分反对向量机（也就是硬距离反对向量机）、线性反对向量机（软距离反对向量机）、非线性反对向量机（核函数反对向量机），这一节先来介绍第一种最根底的算法——硬距离反对向量机算法（Hard-margin Support Vector Machine）。

二、模型介绍

原始模型

  先来看下图，展现了一组线性可分的数据集，其中红点示意 -1、蓝叉示意 1，能够看到将该数据集离开的直线有有限多条，那么如何抉择一条绝对适合的直线呢？如下图中的两条直线 A、B，直观上仿佛直线 A 比直线 B 更适宜作为决策边界，因为对于直线 B，离某些样本点过于近，尽管仍然能正确分类样本点，但当在该样本点左近预测时，会失去齐全不同的后果，仿佛不合乎直觉，其泛化能力更差一些，而反观直线 A，其更具备鲁棒性。

<center> 图 2 -1</center>

  依据下面的推断，咱们的指标为找到一条直线（多维时为超平面），使得任意样本点到该超平面的间隔的最小值最大。超平面表达式如下：

$$
w^Tx + b = 0
$$

<center> 式 2 -1</center>

  同时使得每个样本点都在正确的分类上面，即满足下式：

$$
\left\{\begin{array}{c}
w^{T} x_{i}+b>0 & y_{i}=+1 \\
w^{T} x_{i}+b<0 & y_{i}=-1
\end{array} \quad \Rightarrow \quad y_{i}\left(w^{T} x_{i}+b\right)>0\right.
$$

<center> 式 2 -2</center>

  察看下图，能够将问题转化为找到两个超平面 A、C，使得两个超平面之间的间隔最大，同时每个样本点分类正确。

<center> 图 2 -2</center>

  无妨假如超平面 A 为 wx + b = 1，超平面 B 为 wx + b = -1（因为 w、b 都能够成比例缩放，所以必然能够找到对应的值使得上式成立），同时分类正确的条件如下：

$$
\left\{\begin{array}{c}
w^{T} x_{i}+b>0 & y_{i}=+1 \\
w^{T} x_{i}+b<0 & y_{i}=-1
\end{array} \quad \Rightarrow \quad y_{i}\left(w^{T} x_{i}+b\right) \ge 1\right.
$$

<center> 式 2 -3</center>

  任意一点到超平面 wx + b = 0 的间隔为（推导见四）：

$$
d = \frac{\mid w^Tx + b \mid}{\mid w \mid}
$$

<center> 式 2 -4</center>

  由上式可知超平面 A：wx + b = 1，超平面 B：wx + b = -1 之间的间距为（推导见四）：

$$
\text{margin} = \frac{2}{\mid w \mid}
$$

<center> 式 2 -5</center>

  那么问题转化为了如下模式：

$$
\begin{array}{c}
\underset{w, b}{\max} \frac{2}{\mid w \mid} \\
\text {s.t.} \quad y_{i}\left(w^{T} x_{i}+b\right) \geq 1 \quad i=1,2, \cdots, N
\end{array}
$$

<center> 式 2 -6</center>

  对向量的取模操作能够转化为向量内积的模式，同时取倒数，将最大值问题变成求最小值的问题，失去最初的模型如下：

$$
\begin{array}{c}
\underset{w, b}{\max} \frac{1}{2} w^Tw \\
\text {s.t.} \quad y_{i}\left(w^{T} x_{i}+b\right) \geq 1 \quad i=1,2, \cdots, N
\end{array}
$$

<center> 式 2 -7</center>

对偶模型

  对原模型用拉格朗日乘子法转换一下：

（1）应用拉格朗日乘子法，即在前面加上 N 个拉格朗日乘子的条件，失去对应的拉格朗日函数

（2）拉格朗日函数对 w 求偏导数并令其为零

（3）失去 w 的解析解

（4）拉格朗日函数对 b 求偏导数并令其为零

（5）失去新的条件

$$
\begin{aligned}
L(w, b, \lambda) &=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right) & (1)\\
\frac{\partial L}{\partial w} &=w-\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}=0 & (2)\\
w &=\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i} & (3)\\
\frac{\partial L}{\partial b} &=-\sum_{i=1}^{N} \lambda_{i} y_{i}=0& (4) \\
\sum_{i=1}^{N} \lambda_{i} y_{i} &=0 & (5)
\end{aligned}
$$

<center> 式 2 -8</center>

  将下面 w、b 的解析解带回到拉格朗日函数：

（1）拉格朗日函数

（2）开展括号

（3）察看（2）式最初一项，必然为零，再带入 w 的解析解

（4）化简整顿失去

$$
\begin{aligned}
L(w, b, \lambda) &=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right) & (1)\\
L(\lambda) &=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}-\sum_{i=1}^{N} \lambda_{i} y_{i} w^{T} x_{i}-\sum_{i=1}^{N} \lambda_{i} y_{i} b & (2)\\
&=\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}+\sum_{i=1}^{N} \lambda_{i}-\sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j} & (3)\\
&=\sum_{i=1}^{N}-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j} & (4)
\end{aligned}
$$

<center> 式 2 -9</center>

（1）原始问题

（2）应用拉格朗日乘子法转换

（3）转换为对偶问题，要想使得原始问题与对偶问题等价，须要引入 KKT 条件

（4）带入拉格朗日函数

$$
\begin{aligned}
& \min _{w, b} \frac{1}{2} w^{T} w \quad \text {s.t.} y\left(w^{T} x+b\right) \geq 1 & (1)\\
\Rightarrow & \min _{w, b} \max _{\lambda} L(w, b, \lambda) \quad \text {s.t.} \lambda \geq 0 & (2)\\
\Rightarrow & \max _{\lambda} \min _{w, b} L(w, b, \lambda) \quad \text {s.t.} \lambda \geq 0 & (3)\\
\Rightarrow & \max _{\lambda} L(\lambda) \quad \text {s.t.} \lambda \geq 0 & (4)
\end{aligned}
$$

<center> 式 2 -10</center>

KKT（Karush-Kuhn-Tucker）条件 ²

  后面在推导原始问题的对偶问题中，使得两个问题等价的条件被称为 KKT 条件（Karush–Kuhn–Tucker conditions）。

  对偶问题需满足的 KKT 条件如下：

$$
\left\{\begin{aligned}
\nabla_{w, b} L(w, b, \lambda) &=0 \\
\lambda_{i} & \geq 0 \\
y_{i}\left(w^{T} x_{i}+b\right)-1 & \geq 0 \\
\lambda_{i}\left(y_{i}\left(w^{T} x_{i}+b\right)-1\right) &=0
\end{aligned}\right.
$$

<center> 式 2 -11</center>

  由下面 KKT 条件能够看出，对于任意一个样本点，其 λ = 0 或者 y(wx + b) = 1，为前者时，其对最初的函数后果没有影响，即咱们能够疏忽这些样本点。当为后者时，该样本点在两个最大距离超平面内（图 2 - 2 中的虚线），被称为反对向量，这也是反对向量机名字的由来，最初的模型只与这些反对向量无关。

  通过使用拉格朗日乘子法后，失去了原模型的拉格朗日对偶模型并且须要满足如上所示的 KKT 条件：

$$
\begin{aligned}
& \underset{\lambda}{\max} \sum_{i=1}^{N} \lambda_{i}-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j} \\
\text {s.t.} & \sum_{i=1}^{N} \lambda_{i} y_{i}=0 \quad \lambda_{i} \geq 0 \quad i=1,2, \cdots, N
\end{aligned}
$$

<center> 式 2 -12</center>

三、算法步骤

  由下面的模型能够看出这是一个二次布局问题 ³（Quadratic programming），可能通过一些非凡的办法来求解，例如内点法（Interior Point）等等，前面有机会再来介绍求解办法。上面介绍一种专门用于反对向量机优化问题的算法——序列最小优化算法 ⁴（Sequential minimal optimization/SMO）。

  SMO 算法的思路在笔者看来有点相似后面讲到的坐标降落算法，既然须要优化的参数过多，那就一次优化一个。在 SMO 中则是一次抉择两个待优化变量，其余的当作常量，求解下面的对偶问题的极值，更新变量直至收敛。

算法推导

  留神这里的下标 a、b 即为下面形容的两个待优化变量的下标值，其中下标 b 与偏移量 b 不是同一个值，这里没有适合的字母示意了，所以用了 a、b，切勿与偏移量 b 混同

  定义一些符号来不便表述，为前面推导做筹备：

（1）两个样本点的点积用 K_ab 来示意，前面一节会介绍 SVM 中的一个很重要的特色——核函数，这里的 K 即代表的 Kernal

（2）用核函数来示意决策边界

（3）、（4）用 v_a 来示意去除了下标为 a、b 的样本点和偏移量

$$
\begin{aligned}
K_{a b} &=x_{a}^{T} x_{b} & (1)\\
f\left(x_{a}\right) &=w^{T} x_{a}+b \\
&=\sum_{i=0}^{N} \lambda_{i} y_{i} x_{i}^{T} x_{a}+b \\
&=\sum_{i=0}^{N} \lambda_{i} y_{i} K_{i a}+b & (2)\\
v_{a} &=f\left(x_{a}\right)-\lambda_{a} y_{a} K_{a a}-\lambda_{b} y_{b} K_{a b}-b & (3)\\
v_{b} &=f\left(x_{b}\right)-\lambda_{a} y_{a} K_{a b}-\lambda_{b} y_{b} K_{b b}-b & (4)
\end{aligned}
$$

<center> 式 3 -1</center>

  计算表达式，为前面推导做筹备：

（1）计算上面表达式

（2）带入 f(x)

（3）化简消去偏移量 b

（4）将括号开展

（5）移项后失去只蕴含 λ_a 的后果

（6）同上失去只蕴含 λ_b 的后果

$$
\begin{aligned}
\lambda_{a} y_{a} v_{a} &=\lambda_{a} y_{a}\left(f\left(x_{a}\right)-\lambda_{a} y_{a} K_{a a}-\lambda_{b} y_{b} K_{a b}-b\right) & (1)\\
&=\lambda_{a} y_{a}\left(\sum_{i=0}^{N} \lambda_{i} y_{i} K_{i a}+b-\lambda_{a} y_{a} K_{a a}-\lambda_{b} y_{b} K_{a b}-b\right) & (2)\\
&=\lambda_{a} y_{a}\left(\sum_{i=0}^{N} \lambda_{i} y_{i} K_{i a}-\lambda_{a} y_{a} K_{a a}-\lambda_{b} y_{b} K_{a b}\right) & (3)\\
&=\sum_{i=0}^{N} \lambda_{i} \lambda_{a} y_{i} y_{a} K_{i a}-\lambda_{a} \lambda_{a} y_{a} y_{a} K_{a a}-\lambda_{a} \lambda_{b} y_{a} y_{b} K_{a b} & (4)\\
\sum_{i=0}^{N} \lambda_{i} \lambda_{a} y_{i} y_{a} K_{i a} &=\lambda_{a} y_{a} v_{a}+\lambda_{a} \lambda_{a} y_{a} y_{a} K_{a a}+\lambda_{a} \lambda_{b} y_{a} y_{b} K_{a b} & (5)\\
\sum_{i=0}^{N} \lambda_{i} \lambda_{b} y_{i} y_{b} K_{i b} &=\lambda_{b} y_{b} v_{b}+\lambda_{a} \lambda_{b} y_{a} y_{b} K_{a b}+\lambda_{b} \lambda_{b} y_{b} y_{b} K_{b b} & (6)
\end{aligned}
$$

<center> 式 3 -2</center>

  将多个变量的问题转换为两个变量的问题：

（1）原拉格朗日函数

（2）将下面的后果带入函数中，因为只有下标为 a、b 的两个变量，只须要解决蕴含这两个变量的项、其余的项对立用常数 C 来示意

$$
\begin{aligned}
L(\lambda) &=\sum_{i=0}^{N} \lambda_{i}-\frac{1}{2} \sum_{i=0}^{N} \sum_{j=0}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j} & (1)\\
L\left(\lambda_{a}, \lambda_{b}\right) &=\lambda_{a}+\lambda_{b}-\frac{1}{2} \lambda_{a}^{2} K_{a a}-\frac{1}{2} \lambda_{b}^{2} K_{b b}-\lambda_{a} \lambda_{b} y_{a} y_{b} K_{a b}-\lambda_{a} y_{a} v_{a}-\lambda_{b} y_{b} v_{b}-C & (2)
\end{aligned}
$$

<center> 式 3 -3</center>

  定义符号为前面的推导做筹备：

（1）原问题的条件

（2）只解决下标为 a、b 的两个变量，其余用常量 c 示意（留神这里为 c，切勿与式 3 - 3 中的 C 混同）

（3）移项后两边同时乘以 y_a

（4）、（5）定义符号简化书写

（6）带入符号后 λ_a 的表达式

$$
\begin{aligned}
\sum_{i=0}^{N} \lambda_{i} y_{i} &=0 & (1)\\
\lambda_{a} y_{a}+\lambda_{b} y_{b} &=c & (2)\\
\lambda_{a} &=c y_{a}-\lambda_{b} y_{a} y_{b} & (3)\\
\gamma &=c y_{a} & (4)\\
s &=y_{a} y_{b} & (5)\\
\lambda_{a} &=\gamma-\lambda_{b} s & (6)
\end{aligned}
$$

<center> 式 3 -4</center>

  将两个变量的问题转换为单变量的问题：

（1）将下面失去的 λ_a 的表达式带入拉格朗日函数，失去只有 λ_b 为变量的函数

（2）拉格朗日函数对 λ_b 求偏导数

（3）留神到 s 的平方必然为 1，化简后失去

（4）合并同类项，整顿后失去

（5）另偏导数为零，求得 λ_b 的解

（6）合并同类项，整顿后失去

$$
\begin{aligned}
L\left(\lambda_{b}\right) &=\gamma-\lambda_{b} s+\lambda_{b}-\frac{1}{2}\left(\gamma-\lambda_{b} s\right)^{2} K_{a a}-\frac{1}{2} \lambda_{b}^{2} K_{b b}-\left(\gamma-\lambda_{b} s\right) \lambda_{b} s K_{a b}-\left(\gamma-\lambda_{b} s\right) y_{a} v_{a}-\lambda_{b} y_{b} v_{b}-C & (1)\\
\frac{\partial L}{\partial \lambda_{b}} &=-s+1+s \gamma K_{a a}-s^{2} K_{a a} \lambda_{b}-K_{b b} \lambda_{b}-s \gamma K_{a b}+2 s^{2} K_{a b} \lambda_{b}+y_{a} s v_{a}-y_{b} v_{b} & (2)\\
&=-s+1+s \gamma K_{a a}-K_{a a} \lambda_{b}-K_{b b} \lambda_{b}-s \gamma K_{a b}+2 K_{a b} \lambda_{b}+y_{b} v_{a}-y_{b} v_{b} & (3)\\
&=\left(2 K_{a b}-K_{a a}-K_{b b}\right) \lambda_{b}-s+1+s \gamma K_{a a}-s \gamma K_{a b}+y_{b} v_{a}-y_{b} v_{b}=0 & (4)\\
\lambda_{b} &=\frac{1-s+s \gamma K_{a a}-s \gamma K_{a b}+y_{b} v_{a}-y_{b} v_{b}}{K_{a a}+K_{b b}-2 K_{a b}} & (5)\\
&=\frac{y_{b}\left(y_{b}-y_{a}+y_{a} \gamma\left(K_{a a}-K_{a b}\right)+v_{a}-v_{b}\right)}{K_{a a}+K_{b b}-2 K_{a b}} & (6)
\end{aligned}
$$

<center> 式 3 -5</center>

  推导变量 λ_b 的更新公式：

（1）γ 的表达式

（2）带入 γ

（3）开展括号并带入 v

（4）合并同类项

（5）化简

（6）预测值与理论值之差记为 E

（7）分母示意为 K

（8）带入 E、K 后失去 λ_b 变量的更新公式

$$
\begin{aligned}
\gamma &=\lambda_{a}^{\text {old}}+y_{a} y_{b} \lambda_{b}^{\text {old}} & (1) \\
\lambda_{b}^{\text {new}} &=\frac{y_{b}\left(y_{b}-y_{a}+y_{a}\left(\lambda_{a}^{\text {old}}+y_{a} y_{b} \lambda_{b}^{\text {old}}\right)\left(K_{a a}-K_{a b}\right)+v_{a}-v_{b}\right)}{K_{a a}+K_{b b}-2 K_{a b}} & (2) \\
&=\frac{y_{b}\left(y_{b}-y_{a}+y_{a} \lambda_{a}^{\text {old}} K_{a a}+y_{b} \lambda_{b}^{\text {old}} K_{a a}-y_{a} \lambda_{a}^{\text {old}} K_{a b}-y_{b} \lambda_{b}^{\text {old}} K_{a b}+f\left(x_{a}\right)-y_{a} \lambda_{a} K_{a a}-y_{b} \lambda_{b} K_{a b}-b-f\left(x_{b}\right)+y_{a} \lambda_{a} K_{a b}+y_{b} \lambda_{b} K_{b b}+b\right)}{K_{a a}+K_{b b}-2 K_{a b}} & (3) \\
&=\frac{y_{b}\left(y_{b}-y_{a}+y_{b} \lambda_{b}^{\text {old}}\left(K_{a a}+K_{b b}-2 K_{a b}\right)+f\left(x_{a}\right)-f\left(x_{b}\right)\right)}{K_{a a}+K_{b b}-2 K_{a b}} & (4) \\
&=\lambda_{b}^{\text {old}}+\frac{y_{b}\left(f\left(x_{a}\right)-y_{a}-\left(f\left(x_{b}\right)-y_{b}\right)\right)}{K_{a a}+K_{b b}-2 K_{a b}} & (5) \\
E &=f(x)-y & (6) \\
K &=K_{a a}+K_{b b}-2 K_{a b} & (7) \\
\lambda_{b}^{\text {new}} &=\lambda_{b}^{\text {old}}+\frac{y_{b}\left(E_{a}-E_{b}\right)}{K} & (8)
\end{aligned}
$$

<center> 式 3 -6</center>

  推导变量 λ_a 的更新公式：

（1）由式 3 - 4 中的（2）式，更新前更新后该条件不变

（2）两边同时乘以 y_a 后移项

（3）合并同类项

$$
\begin{aligned}
y_{a} \lambda_{a}^{\text {new}}+y_{b} \lambda_{b}^{\text {new}} &=c=y_{a} \lambda_{a}^{\text {old}}+y_{b} \lambda_{b}^{\text {old}} & (1)\\
\lambda_{a}^{\text {new}} &=\lambda_{a}^{\text {old}}+y_{a} y_{b} \lambda_{b}^{\text {old}}-y_{a} y_{b} \lambda_{b}^{\text {new}} & (2)\\
&=\lambda_{a}^{\text {old}}+y_{a} y_{b}\left(\lambda_{b}^{\text {old}}-\lambda_{b}^{\text {new}}\right) & (3)
\end{aligned}
$$

<center> 式 3 -7</center>

  变量 λ_b 的限度条件：

（1）、（2）所有 λ 都须要大于等于零

（3）分状况探讨 λ_b 的限度条件

（4）综合（1）式失去最终变量 λ_b 的限度条件

$$
\begin{aligned}
&\lambda_{b}^{\text {new}} \geq 0 & (1)\\
&\lambda_{a}^{\text {new}}=\lambda_{a}^{\text {old}}+y_{a} y_{b}\left(\lambda_{b}^{\text {old}}-\lambda_{b}^{\text {new}}\right) \geq 0 & (2)\\
&\Rightarrow \left\{\begin{aligned}
\lambda_{b}^{\text {new}} \leq \lambda_{a}^{\text {old}}+\lambda_{b}^{\text {old}}, \quad y_{a} y_{b}=+1 \\
\lambda_{b}^{\text {new}} \geq \lambda_{b}^{\text {old}}-\lambda_{a}^{\text {old}}, \quad y_{a} y_{b}=-1
\end{aligned}\right. & (3)\\
&\Rightarrow \left\{\begin{aligned}
0 \leq \lambda_{b}^{\text {new}} \leq \lambda_{a}^{\text {old}}+\lambda_{b}^{\text {old}}, \quad y_{a} y_{b}=+1 \\
\max \left(0, \lambda_{b}^{\text {old}}-\lambda_{a}^{\text {old}}\right) \leq \lambda_{b}^{\text {new}} \leq+\infty, \quad y_{a} y_{b}=-1
\end{aligned}\right. & (4)
\end{aligned}
$$

<center> 式 3 -8</center>

  偏移量 b 的计算：

（1）定义汇合 S 为所有 λ 大于零的元素，即所有反对向量点对应的拉格朗日乘子

（2）偏移量 b 的计算公式即 y – wx，选取任意一个反对向量点进行计算

（3）更具鲁棒性的做法为计算所有反对向量点的后果取平均值

$$
\begin{aligned}
S &=\left\{i \mid \lambda_{i}>0, i=1,2, \cdots, N\right\} & (1)\\
b &=y_{s}-w^{T} x_{s} \quad(s \in S) & (2)\\
b &=\frac{1}{|S|} \sum_{s \in S}\left(y_{s}-\sum_{i \in S} \lambda_{i} y_{i} x_{i}^{T} x_{s}\right) & (3)
\end{aligned}
$$

<center> 式 3 -9</center>

算法具体步骤

1、初始化拉格朗日乘子向量、权重向量、偏移量

2、初始化误差向量

3、选取两个待优化的拉格朗日乘子参数

4、依照式 3 - 6 中的（8）式更新 λ_b

5、查看 λ_b 的上下界，超过上界取上界，低于下界则取下界

6、依照式 3 - 7 中的（3）式更新 λ_a

7、从新计算偏移量 b、权重向量 w 和误差向量 E

8、反复 3～7 直至所有拉格朗日乘子满足 KKT 条件或者代价函数没有显著的变动

待优化参数的抉择

  依据 John C. Platt 的论文《Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines》⁵，给出了一个启发式的抉择参数办法：第一个参数抉择不满足 KKT 条件的拉格朗日乘子参数，第二个参数则抉择使得|E_a – E_b|最大的拉格朗日乘子参数。

四、原理证实

任一点到超平面的间隔

  假如 x_0 为任意点，x_t 为 x_0 到超平面 wx + b = 0 的投影：

（1）x_0x_t 示意 x_0 到 x_t 的向量，w 为超平面的法向量，其方向与 x_0x_t 统一，所以夹角为零

（2）cos 0 = 1

（3）计算两个向量的内积，将 x_0x_t 写成向量差的模式

（4）开展括号

（5）因为 x_t 是超平面上的点，所以 wx + b = 0

（6）化简失去

（7）由（2）式与（6）式得

（8）求得任一点到超平面的间隔

$$
\begin{aligned}
\left|w \cdot x_{0} x_{t}\right| &=|| w|\cdot| x_{0} x_{t}\left|\cdot \cos 0^{\circ}\right| & (1)\\
&=|w| \cdot\left|x_{0} x_{t}\right| & (2)\\
w \cdot x_{0} x_{t} &=w \cdot\left(x_{0}-x_{t}\right) & (3)\\
&=w \cdot x_{0}-w \cdot x_{t} & (4)\\
&=w \cdot x_{0}-(-b) & (5)\\
&=w \cdot x_{0}+b & (6)\\
\left|w \cdot x_{0}+b\right| &=|w| \cdot\left|x_{0} x_{t}\right| & (7)\\
\left|x_{0} x_{t}\right| &=\frac{\left|w \cdot x_{0}+b\right|}{|w|} & (8)
\end{aligned}
$$

<center> 式 4 -1</center>

  |x_0x_t|即为点到超平面的间隔，既得证。

两个超平面的间距

  两个平行的超平面之间的间隔等于点到两个超平面的间隔之差的绝对值。依据式 2 -3 的限度条件，上面分两种状况探讨：

（1）当 wx + b 大于等于 1 时，其外部的绝对值能够去掉

（2）化简后失去后果

（3）当 wx + b 小于等于 -1 时，其外部的绝对值能够去掉

（4）化简后失去后果

$$
\begin{aligned}
\left|\frac{\left|w^{T} x+b+1\right|}{|w|}-\frac{\left|w^{T} x+b-1\right|}{|w|}\right| &=\left|\frac{w^{T} x+b+1}{|w|}-\frac{w^{T} x+b-1}{|w|}\right| & (1)\\
&=\frac{2}{|w|} & (2)\\
\left|\frac{\left|w^{T} x+b+1\right|}{|w|}-\frac{\left|w^{T} x+b-1\right|}{|w|}\right| &=\left|\frac{-w^{T} x-b-1}{|w|}-\frac{-w^{T} x-b+1}{|w|}\right| & (3)\\
&=\frac{2}{|w|} & (4)
\end{aligned}
$$

<center> 式 4 -2</center>

  综合下面两种状况失去两个超平面的间隔公式，既得证。

五、代码实现

应用 Python 实现

import numpy as np

class SMO:
    """
    硬距离反对向量机
    序列最小优化算法实现（Sequential minimal optimization/SMO）"""

    def __init__(self, X, y):
        # 训练样本特色矩阵（N * p）self.X = X
        # 训练样本标签向量（N * 1）self.y = y
        # 拉格朗日乘子向量（N * 1）self.alpha = np.zeros(X.shape[0])
        # 误差向量，默认为负的标签向量（N * 1）self.errors = -y
        # 偏移量 
        self.b = 0
        # 权重向量（p * 1）self.w = np.zeros(X.shape[1])
        # 代价值
        self.cost = -np.inf

    def fit(self, tol = 1e-6):
        """
        算法来自 John C. Platt 的论文
        https://www.microsoft.com/en-us/research/uploads/prod/1998/04/sequential-minimal-optimization.pdf
        """
        # 更新变动次数
        numChanged = 0
        # 是否查看全副
        examineAll = True
        while numChanged > 0 or examineAll:
            numChanged = 0
            if examineAll:
                for idx in range(X.shape[0]):
                    numChanged += self.update(idx)
            else:
                for idx in range(X.shape[0]):
                    if self.alpha[idx] <= 0:
                        continue
                    numChanged += self.update(idx)
            if examineAll:
                examineAll = False
            elif numChanged == 0:
                examineAll = True
            # 计算代价值
            cost = self.calcCost()
            # 当代价值的变动小于答应的范畴时完结算法
            if cost - self.cost <= tol:
                break
            self.cost = cost

    def update(self, idx):
        """对下标为 idx 的拉格朗日乘子进行更新"""
        X = self.X
        y = self.y
        alpha = self.alpha
        # 查看以后拉格朗日乘子是否满足 KKT 条件，满足条件则间接返回 0
        if self.checkKKT(idx):
            return 0
        if len(alpha[(alpha != 0)]) > 1:
            # 依照|E1 - E2|最大的准则寻找第二个待优化的拉格朗日乘子的下标
            jdx = self.selectJdx(idx)
            # 对下标为 idx、jdx 的拉格朗日乘子进行更新，当胜利更新时间接返回 1
            if self.updateAlpha(idx, jdx):
                return 1
        # 当未更新胜利时，遍历不为零的拉格朗日乘子进行更新
        for jdx in range(X.shape[0]):
            if alpha[jdx] == 0:
                continue
            # 对下标为 idx、jdx 的拉格朗日乘子进行更新，当胜利更新时间接返回 1
            if self.updateAlpha(idx, jdx):
                return 1
        # 当仍然没有没有更新胜利时，遍历为零的拉格朗日乘子进行更新
        for jdx in range(X.shape[0]):
            if alpha[jdx] != 0:
                continue
            # 对下标为 idx、jdx 的拉格朗日乘子进行更新，当胜利更新时间接返回 1
            if self.updateAlpha(idx, jdx):
                return 1
        # 仍然没有更新时返回 0
        return 0

    def selectJdx(self, idx):
        """寻找第二个待优化的拉格朗日乘子的下标"""
        errors = self.errors
        if errors[idx] > 0:
            # 当误差项大于零时，抉择误差向量中最小值的下标
            return np.argmin(errors)
        elif errors[idx] < 0:
            # 当误差项小于零时，抉择误差向量中最大值的下标
            return np.argmax(errors)
        else:
            # 当误差项等于零时，抉择误差向量中最大值和最小值的绝对值最大的下标
            minJdx = np.argmin(errors)
            maxJdx = np.argmax(errors)
            if max(np.abs(errors[minJdx]), np.abs(errors[maxJdx])) - errors[minJdx]:
                return minJdx
            else:
                return maxJdx

    def calcB(self):
        """
        计算偏移量
        别离计算每一个拉格朗日乘子不为零对应的偏移量后取其平均值
        """
        X = self.X
        y = self.y
        alpha = self.alpha
        alpha_gt = alpha[alpha > 0]
        # 拉格朗日乘子向量中不为零的数量
        alpha_gt_len = len(alpha_gt)
        # 全副为零时间接返回 0
        if alpha_gt_len == 0:
            return 0
        # b = y - Wx，具体算法请参考文章中的阐明
        X_gt = X[alpha > 0]
        y_gt = y[alpha > 0]
        alpha_gt_y = np.array(np.multiply(alpha_gt, y_gt)).reshape(-1, 1)
        s = np.sum(np.multiply(alpha_gt_y, X_gt), axis=0)
        return np.sum(y_gt - X_gt.dot(s)) / alpha_gt_len

    def calcCost(self):
        """
        计算代价值
        依照文章中的算法计算即可
        """
        X = self.X
        y = self.y
        alpha = self.alpha
        cost = 0
        for idx in range(X.shape[0]):
            for jdx in range(X.shape[0]):
                cost = cost + (y[idx] * y[jdx] * X[idx].dot(X[jdx]) * alpha[idx] * alpha[jdx])
        return np.sum(alpha) - cost / 2

    def checkKKT(self, idx):
        """
        查看下标为 idx 的拉格朗日乘子是否满足 KKT 条件
        1. alpha >= 0
        2. y * f(x) - 1 >= 0
        3. alpha * (y * f(x) - 1) = 0
        """
        y = self.y
        errors = self.errors
        alpha = self.alpha
        r = errors[idx] * y[idx]
        if (alpha[idx] > 0 and r == 0) or (alpha[idx] == 0 and r >= 0):
            return True
        return False

    def calcE(self):
        """
        计算误差向量
        E = f(x) - y
        """
        X = self.X
        y = self.y
        alpha = self.alpha
        alpha_y = np.array(np.multiply(alpha, y)).reshape(-1, 1)
        errors = X.dot(X.T).dot(alpha_y).T[0] + b - y
        return errors

    def calcU(self, idx, jdx):
        """
        计算拉格朗日乘子上界，使两个待优化的拉格朗日乘子同时大于等于 0
        依照文章中的算法计算即可
        """
        y = self.y
        alpha = self.alpha
        if y[idx] * y[jdx] == 1:
            return 0
        else:
            return max(0.0, alpha[jdx] - alpha[idx])

    def calcV(self, idx, jdx):
        """
        计算拉格朗日乘子下界，使两个待优化的拉格朗日乘子同时大于等于 0
        依照文章中的算法计算即可
        """
        y = self.y
        alpha = self.alpha
        if y[idx] * y[jdx] == 1:
            return alpha[jdx] + alpha[idx]
        else:
            return np.inf

    def updateAlpha(self, idx, jdx):
        """
        对下标为 idx、jdx 的拉格朗日乘子进行更新
        依照文章中的算法计算即可
        """
        if idx == jdx:
            return False
        X = self.X
        y = self.y
        alpha = self.alpha
        errors = self.errors
        # idx 的误差项
        Ei = errors[idx]
        # jdx 的误差项
        Ej = errors[jdx]
        Kii = X[idx].dot(X[idx])
        Kjj = X[jdx].dot(X[jdx])
        Kij = X[idx].dot(X[jdx])
        # 计算 K
        K = Kii + Kjj - 2 * Kij
        oldAlphaIdx = alpha[idx]
        oldAlphaJdx = alpha[jdx]
        # 计算 jdx 的新拉格朗日乘子
        newAlphaJdx = oldAlphaJdx + y[jdx] * (Ei - Ej) / K
        U = self.calcU(idx, jdx)
        V = self.calcV(idx, jdx)
        if newAlphaJdx < U:
            # 当新值超过上界时，批改其为上界
            newAlphaJdx = U
        if newAlphaJdx > V:
            # 当新值低于下界时，批改其为下界
            newAlphaJdx = V
        if oldAlphaJdx == newAlphaJdx:
            # 当新值与旧值相等时，判断为未更新，间接返回
            return False
        # 计算 idx 的新拉格朗日乘子
        newAlphaIdx = oldAlphaIdx + y[idx] * y[jdx] * (oldAlphaJdx - newAlphaJdx)
        # 从新计算偏移量
        self.b = self.calcB()
        # 更新权重向量
        self.w = self.w + y[idx] * (newAlphaIdx - oldAlphaIdx) * X[idx] + y[jdx] * (newAlphaJdx - oldAlphaJdx) * X[jdx]
        # 更新拉格朗日乘子向量
        alpha[idx] = newAlphaIdx
        alpha[jdx] = newAlphaJdx
        # 从新计算误差向量
        self.errors = self.calcE()
        return True

smo = SMO(X, y)
smo.fit()
print("w", smo.w, "b", smo.b)

六、第三方库实现

scikit-learn⁶ 实现

from sklearn.svm import SVC

svc = SVC(kernel = "linear")
# 拟合数据
svc.fit(X, y)
# 权重系数
w = svc.coef_
# 截距
b = svc.intercept_
print("w", w, "b", b)

七、动画演示

  下图展现了一个线性可分的数据集，其中红色示意标签值为 -1 的样本点，蓝色代表标签值为 1 的样本点：

<center> 图 7 -1</center>

  下图展现了通过反对向量机拟合数据后的后果，其中浅红色的区域为预测值为 -1 的局部，浅蓝色的区域则为预测值为 1 的局部。两条虚线别离为 wx + b = 1 和 wx + b = -1，能够看到图中的反对向量一共有三个，散布在两条虚线上，合乎后面说的反对向量机的个性。

<center> 图 7 -2</center>

八、思维导图

<center> 图 8 -1</center>

九、参考文献

1. https://en.wikipedia.org/wiki…
2. https://en.wikipedia.org/wiki…
3. https://en.wikipedia.org/wiki…
4. https://en.wikipedia.org/wiki…
5. https://www.microsoft.com/en-…
6. https://scikit-learn.org/stab…

残缺演示请点击这里

注：本文力求精确并通俗易懂，但因为笔者也是初学者，程度无限，如文中存在谬误或脱漏之处，恳请读者通过留言的形式批评指正

本文首发于——AI 导图 ，欢送关注