6 支持向量机

#SVM #HingeLoss #Kernel #RBF #SMO #KKT #Dual #LagrangeMethod

1 线性可分支持向量机硬间隔最大化

1.1 线性可分支持向量机

对于一个线性可分的二分类问题, 感知机用一个超平面分割空间中的点, 以误分类最小为策略寻找超平面, 解可以有多个; 但是线性可分支持向量机用间隔最大化求出最优的分离超平面, 解只有一个. 这样的意义是, 对于即是最难区分的点 (最靠近分离超平面的点), 也有足够高的置信度将它成功分类.

线性可分支持向量机

给定线性可分的训练数据集, 通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为 $\begin{matrix} (1.1) & ω^{*} \cdot x + b^{*} = 0 \end{matrix}$ 以及对应的决策函数 $\begin{matrix} (1.2) & f (x) = sgn (ω^{*} \cdot x + b^{*}) \end{matrix}$ 称为线性可分支持向量机.

1.2 函数间隔几何间隔

为了表示点距离超平面的远近, 引入函数间隔.

函数间隔

给定 $T = {(x_{i}, y_{i}), 1 \leq i \leq N}, (ω, b)$ , $y_{i} \in {+ 1, - 1}$ . 定义 $(ω, b)$ 和样本点 $(x_{i}, y_{i})$ 的函数间隔为 $\begin{matrix} (1.3) & {\hat{γ}}_{i} = y_{i} (ω \cdot x_{i} + b), \end{matrix}$ 定义 $(ω, b)$ 和 $T$ 的函数间隔为 $\begin{matrix} (1.4) & \hat{γ} = min_{i = 1, \dots, N} {\hat{γ}}_{i} . \end{matrix}$

如果等比例地将 $(ω, b)$ 变为 $(2 ω, 2 b)$ , 则超平面不变, 但函数间隔发生了改变. 为了解决这一点, 可以加入限制 (如 $| | ω | | = 1$ ). 这样约束条件下的间隔称为几何间隔. 也即, 几何间隔的定义式为 $\begin{matrix} (1.5) & γ = min_{i = 1, \dots, N} y_{i} (\frac{ω}{| | ω | |} \cdot x_{i} + \frac{b}{| | ω | |}) = \frac{\hat{γ}}{| | ω | |} . \end{matrix}$

1.3 间隔最大化

1.3.1 最大间隔分离超平面

为了寻找几何间隔最大化, 考察如下的优化问题 $\begin{aligned} max_{ω, b} & γ \\ s . t . & y_{i} (\frac{ω}{| | ω | |} \cdot x_{i} + \frac{b}{| | ω | |}) \geq γ, i = 1, \dots, N . \end{aligned}$
(要求几何间隔至少是 $γ$ , 也即有足够的置信度, 并寻找这样的置信度的最大值.) 问题等价于为 $\begin{aligned} max_{ω, b} & \frac{\hat{γ}}{| | ω | |} \\ s . t . & y_{i} (ω \cdot x_{i} + b) \geq \hat{γ} \end{aligned}$
需要指出, $\hat{γ}$ 的取值不影响问题的解, 因为随时可以用 $(ω, b) \to (λ ω, λ b)$ 来调整 $\hat{γ}$ , 且不会改变问题本身. 因此, 取 $\hat{γ} = 1$ 即可. 由注意到最大化 $1 / | | ω | |$ 与最小化 $| | ω | |^{2} / 2$ 等价, 因此将问题转化为凸二次规划问题

\begin{aligned} min_{ω, b} & \frac{1}{2} | | ω | |^{2} \\ (1.6) & s . t . & y_{i} (ω \cdot x_{i} + b) - 1 \geq 0. \end{aligned}

线性可分支持向量机-最大间隔法

输入线性可分数据集 $T$ , $Y = {- 1, + 1}$
输出最大间隔分离超平面, 分离决策函数

求解优化问题 (1.6), 得到最优解 $ω^{*}, b^{*}$ .
由此得到超平面 $ω^{*} \cdot x + b^{*} = 0$ 和分离决策函数 $f (x) = sgn (ω^{*} \cdot x + b^{*})$ .

1.3.2 最大间隔分离超平面的存在唯一性

最大间隔分离超平面的存在唯一性

若 $T$ 线性可分, 则完全正确分类的最大间隔分离超平面存在且唯一.

1.3.3 支持向量间隔边界

将与分离超平面距离最近的样本点实例称为支持向量. 对于支持向量, 需要使这里的约束条件成立, 也即 $y_{i} (ω \cdot x_{i} + b) - 1 = 0$ . 也即, 对 $y_{i} = + 1$ 的正例点, 支持向量在 $H_{1} : ω \cdot x + b = 1$ 上; 对 $y_{i} = - 1$ 的负例点, 在 $H_{2} : ω \cdot x + b = - 1$ 上.
因此, 在超平面的附近由 $H_{1}, H_{2}$ 形成了一条条带, 没有样本点在其中. 将 $H_{1}, H_{2}$ 的距离 $\frac{2}{| | ω | |}$ 称为间隔, $H_{1}, H_{2}$ 称为间隔边界.
可以注意到, 间隔的位置只会随着支持向量而改变, 与其他实例点无关. 支持向量机由很少的重要的训练样本确定.

1.4 学习的对偶算法

对偶问题的好处是更容易求解, 和更容易推广到非线性分类问题.
首先构建 Lagrange 函数

\begin{matrix} (1.7) & L (ω, b, α) = \frac{1}{2} | | ω | |^{2} - \sum_{i = 1}^{N} α_{i} y_{i} (ω \cdot x_{i} + b) + \sum_{i = 1}^{N} α_{i}, \end{matrix}

其中 $α = (α_{1}, \dots, α_{N})^{T}$ . 对偶问题为极大极小问题 $max_{α} min_{ω, b} L (ω, b, α) .$

求 $min_{ω, b} L (ω, b, α)$ . 令 ${\begin{aligned} \nabla_{ω} L (ω, b, α) = ω - \sum_{i = 1}^{N} α_{i} y_{i} x_{i} = 0, \\ \nabla_{b} L (ω, b, α) = - \sum_{i = 1}^{N} α_{i} y_{i} = 0 \end{aligned} \Rightarrow {\begin{aligned} ω = \sum_{i = 1}^{N} α_{i} y_{i} x_{i}, \\ \sum_{i = 1}^{N} α_{i} y_{i} = 0. \end{aligned}$
回代入 (1.7), 得

\begin{aligned} L (ω, b, α) = & \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j}) \\ - \sum_{i = 1}^{N} α_{i} y_{i} [(\sum_{j = 1}^{N} α_{j} y_{j} x_{j}) \cdot x_{i} + b] + \sum_{i = 1}^{N} α_{i} \\ = & - \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j}) + \sum_{i = 1}^{N} α_{i} . \end{aligned}

(黄色项与前面合并, 绿色项为 $0$ .)

求 $max_{α} min_{ω, b} L (ω, b, α)$ . 等价于

\begin{aligned} max_{α} & - \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j}) + \sum_{i = 1}^{N} α_{i} \\ s . t . & \sum_{i = 1}^{N} α_{i} y_{i} = 0, \\ α_{i} \geq 0, i = 1, \dots, N \end{aligned}

等价于

\begin{aligned} min_{α} & \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j}) - \sum_{i = 1}^{N} α_{i} \\ s . t . & \sum_{i = 1}^{N} α_{i} y_{i} = 0, \\ (1.8) & α_{i} \geq 0, i = 1, \dots, N \end{aligned}

线性可分支持向量机学习算法

输入线性可分 $T$
输出分离超平面, 决策函数

求解 (1.8), 得到最优解 $α^{*} = (α_{1}^{*}, \dots, α_{N}^{*})^{T}$ ;
计算 $ω^{*} = \sum_{i = 1}^{N} α_{i}^{*} y_{i} x_{i}$ , 选择 $α^{*}$ 的一个正分量 $α_{j}^{*} > 0$ (即寻找支持向量). 计算 $b^{*} = y_{j} - \sum_{i = 1}^{N} α_{i}^{*} y_{i} (x_{i} \cdot x_{j})$ ;
得到超平面 $ω^{*} \cdot x + b^{*} = 0$ 和分离决策函数 $f (x) = sgn (ω^{*} \cdot x + b^{*})$ .

满足 (1.8) 、 $α_{i}^{*} > 0$ 的样本点的实例 $x_{i}$ 可以作为支持向量的另一等价定义. 事实上, 由 KKT条件知 $α_{i}^{*} [y_{i} (ω^{*} \cdot x_{i} + b^{*}) - 1] = 0 \Rightarrow ω^{*} \cdot x_{i} + b^{*} = \pm 1.$

2 线性支持向量机软间隔最大化

2.1 线性支持向量机

如何求解线性不可分问题? 需要把硬间隔变成软间隔.
给定 $T$ 设定同上, 但不是线性可分的. 引入松弛变量 $ξ_{i} \geq 0$ , 将约束条件变为 $y_{i} (ω \cdot x_{i} + b) \geq 1 - ξ_{i} .$
但是, 不允许 $ξ$ 无限制的小, 因此需要支付代价 $C ξ_{i}$ ( $C$ 称为惩罚参数), 目标函数为 $\begin{matrix} (2.1) & \frac{1}{2} | | ω | |^{2} + C \sum_{i = 1}^{N} ξ_{i} . \end{matrix}$
目标函数的意义是使最小间隔尽可能大(对应 $ω$ 尽可能小, 参见 (1.6)), 误分类点个数尽可能小. 因此等价于如下凸二次规划

\begin{aligned} min_{ω, b, ξ} & \frac{1}{2} | | ω | |^{2} + C \sum_{i = 1}^{N} ξ_{i}, \\ s . t . & y_{i} (ω \cdot x_{i} + b) \geq 1 - ξ_{i}, i = 1, \dots, N, \\ (2.2) & ξ_{i} \geq 0, i = 1, \dots, N . \end{aligned}

线性支持向量机

输入线性不可分的 $T$
输出最大软间隔分离超平面, 分离决策函数
求解 (2.2), 得到分离超平面 $ω^{*} \cdot x + b^{*} = 0$ 和 $f (x) = sgn (ω^{*} \cdot x + b^{*})$ .

2.2 学习的对偶算法

(2.2) 的 Lagrange 函数为 $L (ω, b, ξ, α, μ) = \frac{1}{2} | | ω | |^{2} + C \sum_{i = 1}^{N} ξ_{i} - \sum_{i = 1}^{N} α_{i} [y_{i} (ω \cdot x_{i} + b) - 1 + ξ_{i}] - \sum_{i = 1}^{N} μ_{i} ξ_{i},$
其中 $α_{i} \geq 0, μ_{i} \geq 0$ . 考虑极大极小问题 $max_{α, μ} min_{ω, b, ξ} L (ω, b, ξ, α, μ)$ .

内层: 令 $\begin{aligned} \nabla_{ω} L (ω, b, ξ, α, μ) & = ω - \sum_{i = 1}^{N} α_{i} y_{i} x_{i} = 0, \\ \nabla_{b} L (ω, b, ξ, α, μ) & = - \sum_{i = 1}^{N} α_{i} y_{i} = 0, \\ \nabla_{ξ_{i}} L (ω, b, ξ, α, μ) & = C - α_{i}, μ_{i} = 0, \end{aligned}$
得 $ω = \sum_{i = 1}^{N} α_{i} y_{i} x_{i}, \sum_{i = 1}^{N} α_{i} y_{i} = 0, C - α_{i} - μ_{i} = 0.$
回代得 $min_{ω, b, ξ} L (ω, b, ξ, α, μ) = - \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j}) + \sum_{i = 1}^{N} α_{i} .$
外层对偶问题即为

\begin{aligned} min_{α} & \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j}) - \sum_{i = 1}^{N} α_{i}, \\ s . t . & \sum_{i = 1}^{N} α_{i} y_{i} = 0, \\ C - α_{i} - μ_{i} = 0, \\ α_{i}, μ_{i} \geq 0, i = 1, \dots, N, \end{aligned}

消去 $μ_{i}$ , 就得到了

\begin{aligned} min_{α} & \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j}) - \sum_{i = 1}^{N} α_{i}, \\ s . t . & \sum_{i = 1}^{N} α_{i} y_{i} = 0, \\ (2.3) & 0 \leq α_{i} \leq C, i = 1, \dots, N . \end{aligned}

定理 2.1

设 $α^{*} = (α_{1}^{*}, \dots, α_{N}^{*})^{T}$ 是对偶问题 (2.3) 的解, 若存在 $α^{*}$ 的分量 $α_{j}^{*}, 0 < α_{j}^{*} < C$ , 则原始问题 (2.2) 的解 $ω^{*}, b^{*}$ 由下式求得: $\begin{matrix} (2.4) & ω^{*} = \sum_{i = 1}^{N} α_{i}^{*} y_{i} x_{i}, b^{*} = y_{j} - \sum_{i = 1}^{N} y_{i} α_{i}^{*} (x_{i} \cdot x_{j}) . \end{matrix}$

证明

原始问题的解满足 KKT条件, 代入整理后得到结论.

线性支持向量机学习算法

输入 $T$
输出分离超平面和分类决策函数

选择惩罚参数 $C > 0$ , 求解 (2.3), 得到最优解 $α^{*} = (α_{1}^{*}, \dots, α_{N}^{*})^{T}$ ;
由定理2.1 得到 $ω^{*}, b^{*}$ ;
求得分离超平面 $ω^{*} \cdot x + b^{*} = 0$ 和分离决策函数 $f (x) = sgn (ω^{*} \cdot x + b^{*})$ .

2.3 支持向量

此时相应的, 也有 (软间隔的) 支持向量.

	$α_{i}^{*} < C$	$α_{i}^{*} = C$
$ξ_{i} = 0$	间隔边界	--
$0 < ξ_{i} < 1$	--	分类正确, 在间隔边界与分离超平面之间
$ξ_{i} = 1$	--	在分离超平面上
$ξ_{i} > 1$	--	分类错误, 在误分类一侧

2.4 合页损失函数

定义 $L (y (ω \cdot x + b)) = [1 - y (ω \cdot x + b)]_{+} = max {y (ω \cdot x + b), 0}$ 为 合页损失函数 (hinge loss function).
线性支持向量机除了依据软间隔最大化寻找分离超平面的解释之外, 还可以用最小化目标函数 $\sum_{i = 1}^{N} [1 - y_{i} (ω \cdot x_{i} + b)]_{+} + λ | | ω | |^{2}$ 来解释. 这里的第一项是经验损失. 也即正确分类时确信度 $y_{i} (ω \cdot x_{i} + b) > 0$ , 损失为 $0$ . 第二项是正则化项.

定理 2.2

原始优化问题 (2.2) 等价于优化问题 $\begin{matrix} (2.5) & min_{ω, b} \sum_{i = 1}^{N} [1 - y_{i} (ω \cdot x_{i} + b)]_{+} + λ | | ω | |^{2} . \end{matrix}$

证明

将 (2.2) 改写为 2.5. 令 $ξ_{i} = [1 - y_{i} (ω \cdot x_{i} + b)]_{+} \geq 0.$ 我们把 (2.2) 再写一遍 $\begin{aligned} (0) & min_{ω, b, ξ} & \frac{1}{2} | | ω | |^{2} + C \sum_{i = 1}^{N} ξ_{i}, \\ (1) & s . t . & y_{i} (ω \cdot x_{i} + b) \geq 1 - ξ_{i}, i = 1, \dots, N, \\ (2) & ξ_{i} \geq 0, i = 1, \dots, N, \end{aligned}$ 这样 $ξ_{i}$ 满足 (2). 下面只需说明它满足 (1). 当 $1 - y_{i} (ω \cdot x_{i} + b) > 0$ , 则 $y_{i} (ω \cdot x_{i} + b) = 1 - ξ_{i}$ ; 当 $1 - y_{i} (ω \cdot x_{i} + b) \leq 0$ 时, 有 $ξ_{i} = 0 \geq 1 - y_{i} (ω \cdot x_{i} + b)$ . 因此再令 $C = \frac{1}{2 λ}$ , (0) 就等价于 $min_{ω, b} \frac{1}{C} (\frac{1}{2} | | ω | |^{2} + C \sum_{i = 1}^{N} ξ_{i}),$ 因此与 (2.5) 等价; 反之亦然.

Pasted image 20241123001141.png|300
合页损失函数和 0-1 损失函数图像如上所示. 它可以看作 0-1 损失函数的上界, 在光滑性方面做出了优化.

3 非线性支持向量机核函数

3.1 核技巧

3.1.1 非线性分类问题

如果一个二分类数据集 $T$ 需要用 $R^{n}$ 的超曲面来划分, 则称为非线性可分问题.
目标是使用一个非线性变换, 将非线性问题转化为线性问题.

例如, 超曲面是一个椭圆. 设原空间 $X \subset R^{2}, x = (x^{(1)}, x^{(2)})^{T} \in X$ ; 新空间 $Z \subset R^{2}, z = (z^{(1)}, z^{(2)})^{T} \subset Z$ . 定义映射 $z = ϕ (x) = ((x^{(1)})^{2}, (x^{(2)})^{2})^{T} .$
经过变换, 原空间的椭圆 $ω_{1} (x^{(1)})^{2} + ω_{2} (x^{(2)})^{2} + b = 0$ 变换为新空间的直线 $ω_{1} z^{(1)} + ω_{2} z^{(2)} + b = 0$ . 因此问题的关键在于映射的寻找.

3.1.2 核函数的定义

核函数

设 $X \subset R^{n}$ 是输入空间, $H$ 是特征空间. 如果存在 $ϕ (x) : X \to H$ , 使得所有的 $x, z \in X$ , 函数 $K (x, z)$ 满足条件 $\begin{matrix} (3.1) & K (x, z) = ϕ (x) \cdot ϕ (z), \end{matrix}$
则称 $K (x, z)$ 为核函数, $ϕ (x)$ 为映射函数. 这里的乘积表示内积.

核技巧的想法是, 只考虑 $K (x, z)$ , 而不去显式地定义 $ϕ$ .
对于给定的核函数 $K (x, z)$ , $H, ϕ$ 并不一定唯一.

设

X = R^{2}

K (x, z) = (x \cdot z)^{2}

, 找出

H, ϕ : R^{2} \to H

取 $H = R^{3}$ , 则 $(x \cdot z)^{2} = (x^{(1)} z^{(1)} + x^{(2)} z^{(2)})^{2},$ 可取映射 $ϕ (x) = ((x^{(1)})^{2}, \sqrt{2} x^{(1)} x^{(2)}, (x^{(2)})^{2})^{T} .$
取 $H = R^{3}$ , 可取 $ϕ (x) = \frac{\sqrt{2}}{2} ((x^{(1)})^{2} - (x^{(2)})^{2}, 2 x^{(1)} x^{(2)}, (x^{(1)})^{2} + (x^{(2)})^{2})^{T} .$
取 $H = R^{4}$ , 可取 $ϕ (x) = ((x^{(1)})^{2}, x^{(1)} x^{(2)}, x^{(1)} x^{(2)}, (x^{(2)})^{2}) .$

3.1.3 核技巧在支持向量机中的应用

用核函数 $K (x_{i}, x_{j}) = ϕ (x_{i}) \cdot ϕ (x_{j})$ 来代替对偶问题 (2.3) 的损失函数:

W (α) = \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} K (x_{i}, x_{j}) - \sum_{i = 1}^{N} α_{i} .

对于分类决策函数, 由决策函数和 (2.4), 得

f (x) = sgn (\sum_{i = 1}^{N_{s}} a_{i}^{*} y_{i} K (x_{i}, x) + b^{*}) .

在变换 $ϕ$ 下的新定义空间中学习线性支持向量机.

3.2 正定核

通常所说的核函数指正定核函数. 我们关心满足怎样的条件, 函数 $K (x, z)$ 可以用 $ϕ$ 拆分, 以便是核函数. 首先给出结论

定理 3.1 (正定核的充要条件)

$K : X \times X \to R$ 是对称函数, 则 $K (x, z)$ 是正定核函数的充分必要条件是 $\forall x_{i} \in X, 1 \leq i \leq m$ , Gram 矩阵 $K = [K (x_{i}, x_{j})]_{m \times m}$ 是半正定矩阵.

这样我们可以给出正定核的等价定义(所以"正定"得名于此)

正定核的等价定义

$X \subset R^{n}$ , $K (x, z)$ 是定义在 $X \times X$ 上的对称函数. 如果 $\forall x_{i} \in X$ , $K (x, z)$ 的 Gram 矩阵半正定, 则 $K (x, z)$ 是正定核.

在实际应用中, 很难证明: 任意给定有限的 ${x_{1}, \dots, x_{m}}$ 都有 $K$ 是半正定的.

3.3 常用核函数

关于核函数可以参见这个概率论笔记.

3.3.1 Polynomial Kernel Function

K (x, z) = (x \cdot z + 1)^{p}, $ $ 对 应 分 类 决 策 函 数 为 $ $ f (x) = sgn (\sum_{i = 1}^{N_{s}} a_{i}^{*} y_{i} (x_{i} \cdot x + 1)^{p} + b^{*}) .

3.3.2 Gaussian Kernel Function (RBF)

K (x, z) = \exp (- \frac{| | x - z | |^{2}}{2 σ^{2}}) .

3.3.3 String Kernel Function

3.4 非线性支持向量机

只需利用核技巧进行替换, 就可以得到非线性支持向量机.

非线性支持向量机

从非线性分类训练集, 通过核函数和软间隔最大化或者凸二次规划(2.3), 学习得到分类决策函数 $\begin{matrix} (3.2) & f (x) = sgn (\sum_{i = 1}^{N} α_{i}^{*} y_{i} K (x, x_{i}) + b^{*}) \end{matrix}$ 的模型成为非线性支持向量机.

然后总结一下学习算法

非线性支持向量机学习算法

输入 $T$
输出分类决策函数

选取适当的 $K (x, z)$ 和参数 $C$ , 构造 $\begin{aligned} min_{α} & \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} K (x_{i}, x_{j}) - \sum_{i = 1}^{N} α_{i}, \\ s . t . & \sum_{i = 1}^{N} α_{i} y_{i} = 0, \\ (3.3) & 0 \leq α_{i} \leq C, i = 1, \dots, N . \end{aligned}$ (在 (2.3) 的基础上简单修改) 得到最优解 $α^{*} = (α_{1}^{*}, \dots, α_{N}^{*})^{T}$ .
选择 $α^{*}$ 的一个正分量 $0 < α_{j}^{*} < C$ , 计算 $b^{*} = y_{j} - \sum_{i = 1}^{N} α_{i}^{*} y_{i} K (x_{i}, x_{j}) .$
构造决策函数 (3.2).

4 序列最小最优化算法

SMO 算法

输入 $T$ ; 精度 $ε$ .
输出近似解 $\hat{α}$ .

选取初值 $α^{(0)} = 0$ , 令 $k = 0$ .
选取优化变量 $α_{1}^{(k)}, α_{2}^{(k)}$ , 解析求解两个变量的最优化问题 $\begin{aligned} min_{α_{1}, α_{2}} W (α_{1}, α_{2}) = & \frac{1}{2} K_{11} α_{1}^{2} + \frac{1}{2} K_{22} α_{2}^{2} + y_{1} y_{2} K_{12} α_{1} α_{2} - \\ (α_{1} + α_{2}) + y_{1} α_{1} \sum_{i = 3}^{N} y_{i} α_{i} K_{i 1} + y_{2} α_{2} \sum_{i = 3}^{N} y_{i} α_{i} K_{i 2}, \\ s . t . α_{1} y_{1} + α_{2} y_{2} = & - \sum_{i = 3}^{N} y_{i} α_{i} = ς, \\ 0 \leq α_{i} \leq C, i = 1, 2, \end{aligned}$ 得到最优解 $α_{1}^{(k + 1)}, α_{2}^{(k + 1)}$ , 更新 $α = α^{(k + 1)}$ .
若在精度 $ε$ 范围内满足停机条件 $\begin{aligned} \sum_{i = 1}^{N} α_{i} y_{i} & = 0, 0 \leq α_{i} \leq C, 1 \leq i \leq N, \\ y_{i} \cdot g (x_{i}) & {\begin{aligned} \geq 1, α_{i} = 0, \\ = 1, 0 < α_{i} < C, \\ \leq 1, α_{i} = C, \end{aligned} \end{aligned}$ 其中 $g (x_{i}) = \sum_{j = 1}^{N} α_{j} y_{j} K (x_{j}, x_{i}) + b,$ 则转到 4; 否则 $k = k + 1$ , 转到 2.
$\hat{α} = α^{(k + 1)}$ .