复现SMO算法：深入探索序列最小优化的分析方法【三、算法原理揭秘-1】

本文主要是介绍复现SMO算法：深入探索序列最小优化的分析方法【三、算法原理揭秘-1】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这篇深入探讨序列最小优化（SMO）算法的第一部分中，我们专注于算法核心的第一个组成部分——求解两个拉格朗日乘数的分析方法。我们将逐步展开详细的数学推导，明确如何从约束的确定到乘数的优化更新，直至找到最优解。在介绍这一复杂的过程时，我们将特别注意保持逻辑的清晰性和步骤的精确性，确保即使是初学者也能跟随每一个推导步骤。

一、求解两个拉格朗日乘数的分析方法

SMO算法的一个关键创新是将大型二次规划（QP）问题分解为只涉及两个拉格朗日乘数的最小可能QP问题。每一步中，算法选择两个拉格朗日乘数进行 联合优化 ，并且通过 分析方法 直接求解这两个乘数的最优值。

对于这两个乘数，首先需要确定它们的约束条件。这些约束包括：

• 边界约束：由于拉格朗日乘数必须非负，且受到参数 $C$ 的限制，即 $0\le {\alpha }_i\le C$。
• 等式约束：由于分类问题的目标函数约束，两个乘数必须满足 ${\alpha }_1{y}_1+{\alpha }_2{y}_2=\text{常数}$。

在确定约束后，SMO利用核函数 $K(x_i,x_j)$ 计算二次项的导数，通过设置导数为零求解最优化问题。求解过程中，如果 ${\alpha }_2$ 的更新超出了其界限，需要对其进行剪辑处理，以确保其仍然在允许的范围内。这种剪辑后的 ${\alpha }_2$ 值和相应的 ${\alpha }_1$ 值将决定当前的最优解。

---

让我们从头开始逐步推导出求解两个拉格朗日乘数的分析方法。

推导目标原始函数

我们的最初优化问题是：

$$\underset{\mathbf{w}}{\min }\frac{1}{2}||\mathbf{w}|{|}^2$$

这是在最小化权重向量 $\mathbf{w}$ 的欧几里得长度的平方，也可以被看作是最小化 $\mathbf{w}$ 的L2范数。这样的形式化问题有助于找到最大间隔超平面。约束条件是：

y i ( w T x i + b ) ≥ 1 , ∀ i ∈ { 1 , . . . , m } y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1, \quad \forall i \in \{1, ..., m\} yi​(wTxi​+b)≥1,∀i∈{1,...,m}

其中 $y_i$ 是第 ( i ) 个训练样本的标签，${\mathbf{x}}_i$ 是第 ( i ) 个训练样本，( b ) 是偏置项，$m$ 是训练样本的数量。

接着我们引入拉格朗日乘数 ${\alpha }_i$ 来构造拉格朗日函数 $L(\mathbf{w},b,\alpha )$ ，这个函数将原始问题转化为其对偶问题，从而可以通过最优化拉格朗日乘数而非 $\mathbf{w}$ 和 ( b ) 来求解。拉格朗日函数为：

$$L(\mathbf{w},b,\alpha )=\frac{1}{2}||\mathbf{w}|{|}^2+\sum _{i=1}^m{\alpha }_i\left(1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\right)$$

目标是最大化 $L$ 关于 $\alpha$ 的值，同时满足对于所有 ${\alpha }_i$ ，都有 ${\alpha }_i\ge 0$

拉格朗日函数 $L$ 的偏导数分别对 $\mathbf{w}$ 和 $b$ 为零时，给出了以下两个等式：

$$\mathbf{w}=\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i$$

$$0=\sum _{i=1}^m{\alpha }_i{y}_i$$

将 $\mathbf{w}$ 表达式代入拉格朗日函数 $L$ ，并且考虑到 $\sum {\alpha }_i{y}_i=0$ ，我们得到 $L$ 关于 $\alpha$ 的新表达式，这就是对偶问题的目标函数，我们只需要最大化这个目标函数就可以找到最优解。

我们将上面我们得到的$\mathbf{w}$和$0={\sum }_{i=1}^m{\alpha }_i{y}_i$带入原方程后得到：

将 $\mathbf{w}$ 和 $\sum {\alpha }_i{y}_i=0$ 带入原拉格朗日函数 $L(\mathbf{w},b,\alpha )$ 中，我们可以得到仅依赖于 $\alpha$ 的表达式：

$$L(\alpha )=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i^T{\mathbf{x}}_j)$$

这里，内积 ${\mathbf{x}}_i^T{\mathbf{x}}_j$ 可以被核函数 $K({\mathbf{x}}_i,{\mathbf{x}}_j)$ 替代，这允许我们在特征空间中实现非线性映射。于是，目标函数成为：

$$L(\alpha )=\max (\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j))$$
$$0=\sum _{i=1}^m{\alpha }_i{y}_i$$

接下来，在存在约束条件下，求得最大值。

SMO算法优化

SMO每次选择两个乘数 ${\alpha }_1$ 和 ${\alpha }_2$ 并固定其他的乘数，对它们进行优化。SMO算法会计算这两个乘数的最优值，同时保持它们和的恒定不变（因为 $\sum {\alpha }_i{y}_i=0$ 必须一直满足）。

将原本 $L({\alpha }_1...{\alpha }_m)$化简为$L({\alpha }_1{\alpha }_2)$；现在我们尝试将$\sum {\alpha }_i{y}_i=0$ 展开

$${\alpha }_1{y}_1+{\alpha }_2{y}_2+\sum _{i=3}^m{\alpha }_i{y}_i=0$$

具体的解析步骤包括

1. 计算 ${\alpha }_2$ 的最优解的未剪辑版本
2. 如果需要，将这个解剪辑到其可能的区间 $[L,H]$，其中 $L$ 和 $H$ 是由不等式约束决定的上下界。
3. ${\alpha }_1$ 随后可以根据 ${\alpha }_2$ 和等式约束 ${\alpha }_1{y}_1+{\alpha }_2{y}_2=\text{constant}$ 直接计算出来。

完成上述步骤后，我们就可以更新这两个乘数的值，并继续迭代过程，直到所有 ( \alpha ) 满足KKT条件或达到某个收敛标准。

数学化简过程【固定 $i,j\ge 3$ 】

首先，我们有
$$L(\alpha )=\max (\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j))$$

然后因为前面按照SMO算法的启发式思想，我们可以转换成以下式子
$$\max \sum _{i=1}^m{\alpha }_i=({\alpha }_1+{\alpha }_2+\sum _{i=3}^m{\alpha }_i)$$

当然，你想要将条件拆分出来，可以这样写：

$$\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)=$$

$$\left[\begin{array}{cc}{\alpha }_1{y}_1{\alpha }_1{y}_1{\kappa }_{11}& \text{for }i=1,j=1\end{array}\right]+$$

$$\left[\begin{array}{cc}{\alpha }_1{y}_1{\alpha }_2{y}_2{\kappa }_{12}& \text{for }i=1,j=2\end{array}\right]+$$

$$\left[\begin{array}{cc}{\sum }_{j=3}^m{\alpha }_1{y}_1{\alpha }_j{y}_j{\kappa }_{1j}& \text{for }i=1,j\ge 3\end{array}\right]+$$

$$\left[\begin{array}{cc}{\alpha }_2{y}_2{\alpha }_1{y}_1{\kappa }_{12}& \text{for }i=2,j=1\end{array}\right]+$$

$$\left[\begin{array}{cc}{\alpha }_2{y}_2{\alpha }_2{y}_2{\kappa }_{22}& \text{for }i=2,j=2\end{array}\right]$$

$$\left[\begin{array}{cc}{\sum }_{j=3}^m{\alpha }_2{y}_2{\alpha }_j{y}_j{\kappa }_{2j}& \text{for }i=2,j\ge 3\end{array}\right]+$$

$$\left[\begin{array}{cc}{\sum }_{i=3}^m{\alpha }_i{y}_i{\alpha }_1{y}_1{\kappa }_{1i}& \text{for }i\ge 3,j=1\end{array}\right]+$$

$$\left[\begin{array}{cc}{\sum }_{i=3}^m{\alpha }_i{y}_i{\alpha }_2{y}_2{\kappa }_{2i}& \text{for }i\ge 3,j=2\end{array}\right]+$$

$$\left[\begin{array}{cc}{\sum }_{i=3}^m{\sum }_{j=3}^m{\alpha }_i{y}_i{\alpha }_j{y}_j{\kappa }_{ij}& \text{for }i\ge 3,j\ge 3\end{array}\right]$$

最终，我们合并同类项（1,2）和(2,1)是一样的；同理，（1,3）和（3,1）也一样。
得到结果

$$\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)={\alpha }_1{y}_1{\alpha }_1{y}_1{\kappa }_{11}+2{\alpha }_1{y}_1{\alpha }_2{y}_2{\kappa }_{12}+2\sum _{j=3}^m{\alpha }_1{y}_1{\alpha }_j{y}_j{\kappa }_{1j}+{\alpha }_2{y}_2{\alpha }_2{y}_2{\kappa }_{22}+2\sum _{j=3}^m{\alpha }_2{y}_2{\alpha }_j{y}_j{\kappa }_{2j}+\sum _{i=3}^m\sum _{j=3}^m{\alpha }_i{y}_i{\alpha }_j{y}_j{\kappa }_{ij}$$

因为我们的思想是将>=3的都固定下来，所以对应的$i\ge 3$和$j\ge 3$都是常数，在后面的式子计算中，我们可以省略（${\sum }_{i=3}^m{\sum }_{j=3}^m{\alpha }_i{y}_i{\alpha }_j{y}_j{\kappa }_{ij}$和 ${\sum }_{i=3}^m{\alpha }_i$）

因为我们可以通过左右同时 减去常数构造一个新的函数

因此可得
$$L^{\prime }({\alpha }_1{\alpha }_2)={\alpha }_1+{\alpha }_2-\frac{1}{2}({\alpha }_1^2{y}_1^2{K}_{11}+2{\alpha }_1{y}_1{\alpha }_2{y}_2{K}_{12}+2\sum _{j=3}^m{\alpha }_1{y}_1{\alpha }_j{y}_j{\kappa }_{1j}+{\alpha }_2^2{y}_2^2{K}_{22}++2\sum _{j=3}^m{\alpha }_2{y}_2{\alpha }_j{y}_j{K}_{2j})$$

所以现在的问题转换为求 $L^{\prime }({\alpha }_1{\alpha }_2)$ 的极值，但是这里是两个参数，所以这里我们需要转换为一个参数

计算 ${\alpha }_2$ 的最优解的未剪辑版本

当我们知道了${\alpha }_1$或者${\alpha }_2$，另外的就可以通过解析解求得

注意我们之前${\alpha }_1$和${\alpha }_2$针对展开后的结果
$${\alpha }_1{y}_1+{\alpha }_2{y}_2+\sum _{i=3}^m{\alpha }_i{y}_i=0$$

因为固定了 $i\ge 3$后面的值，所以 ${\sum }_{i=3}^m{\alpha }_i{y}_i$这一块就是一个常数！

因此我们可以得到
$${\alpha }_1{y}_1+{\alpha }_2{y}_2=C（常数）$$

同乘$y_1$后，得到 ${\alpha }_1$

因为$y_i$只能取值 +1或-1，所以其平方就是1

$${\alpha }_1=y_1(C-{\alpha }_2{y}_2)$$

现在我们需要将 ${\alpha }_1$带入到前面的 $L^{\prime }({\alpha }_1{\alpha }_2)$函数中，得到单变量的函数$L^{\prime }({\alpha }_2)$

$$L^{\prime }({\alpha }_2)=y_1(C-{\alpha }_2{y}_2)+{\alpha }_2-\frac{1}{2}[(C-{\alpha }_2{y}_2{)}^2{K}_{11}+2y_1(C-{\alpha }_2{y}_2)y_1{\alpha }_2{y}_2{K}_{12}+2\sum _{j=3}^m{y}_1(C-{\alpha }_2{y}_2)y_1{\alpha }_j{y}_j{\kappa }_{1j}+{\alpha }_2^2{y}_2^2{K}_{22}++2\sum _{j=3}^m{\alpha }_2{y}_2{\alpha }_j{y}_j{K}_{2j}]$$

化简后得到
$$L^{\prime }({\alpha }_2)=y_1(C-{\alpha }_2{y}_2)+{\alpha }_2-\frac{1}{2}[(C-{\alpha }_2{y}_2{)}^2{K}_{11}+2(C-{\alpha }_2{y}_2){\alpha }_2{y}_2{K}_{12}+2\sum _{j=3}^m(C-{\alpha }_2{y}_2){\alpha }_j{y}_j{K}_{1j}+{\alpha }_2^2{y}_2^2{K}_{22}++2\sum _{j=3}^m{\alpha }_2{y}_2{\alpha }_j{y}_j{K}_{2j}]$$

现在我们对 ${\alpha }_2$求偏导数——求取极值
$$\frac{\partial L^{\prime }}{\partial {\alpha }_2}=-y_1{y}_2-\frac{1}{2}[2(C-{\alpha }_2)(-y_2)K_{11}+2C{y}_2{K}_{12}-4{\alpha }_2{K}_{12}+2{\alpha }_2{K}_{22}-2\sum _{i=3}^m{y}_2{\alpha }_i{y}_i{K}_{1i}+2\sum _{i=3}^m{y}_2{\alpha }_i{y}_i{K}_{2i}]$$

我们将其化简一下，并另偏导为0
$$\frac{\partial L^{\prime }}{\partial {\alpha }_2}=1-y_1{y}_2+C{y}_2{K}_{11}-{\alpha }_2{K}_{11}-C{y}_2{K}_{12}+2{\alpha }_2{K}_{12}-{\alpha }_2{K}_{22}+\sum _{i=3}^m{y}_2{\alpha }_i{y}_i{K}_{1i}-\sum _{i=3}^m{y}_2{\alpha }_i{y}_i{K}_{2i}=0$$

我们寻找一下带有 ${\alpha }_2$的式子：

• $-{\alpha }_2{K}_{11}$
• $2{\alpha }_2{K}_{12}$
• $-{\alpha }_2{K}_{22}$

所以我们将${\alpha }_2$移动到等式一边
$${\alpha }_2(K_{11}-2K_{12}+K_{22})=1-y_1{y}_2+C{y}_2{K}_{11}-C{y}_2{K}_{12}+\sum _{i=3}^m{y}_2{\alpha }_i{y}_i{K}_{1i}-\sum _{i=3}^m{y}_2{\alpha }_i{y}_i{K}_{2i}$$

我们进一步进行化简

• C是一个常数
• 提取$y_2$
  $${\alpha }_2^{new}(K_{11}-2K_{12}+K_{22})=y_2(y_2-y_1+C{K}_{11}-C{K}_{12}+\sum _{i=3}^m{\alpha }_i{y}_i{K}_{1i}-\sum _{i=3}^m{\alpha }_i{y}_i{K}_{2i})$$

因为这里我们是一个迭代的值，然后结合前面我们固定了其他的值，因此我们可以得到
$${\alpha }_1^{old}{y}_1+{\alpha }_2^{old}{y}_2=C={\alpha }_1^{new}{y}_1+{\alpha }_2^{new}{y}_2$$

然后替换进去之后得到
$${\alpha }_2^{new}(K_{11}-2K_{12}+K_{22})=y_2[y_2-y_1+({\alpha }_1^{old}{y}_1+{\alpha }_2^{old}{y}_2)K_{11}-({\alpha }_1^{old}{y}_1+{\alpha }_2^{old}{y}_2)K_{12}+\sum _{i=3}^m{\alpha }_i{y}_i{K}_{1i}-\sum _{i=3}^m{\alpha }_i{y}_i{K}_{2i}]$$

我们发现这个 ${\sum }_{i=3}^m$有点难以消除，我们重新审视一下我们求的目标函数
$$f(x)={\mathbf{w}}^T\mathbf{x}+b$$
$$\mathbf{w}=\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i$$
同样的，我们尝试将除了 ${\alpha }_1$和${\alpha }_2$之外的值都固定下来
$$f(x)={\alpha }_1{y}_1{K}_{11}+{\alpha }_2{y}_2{K}_{22}+\sum _{i=3}^m{\alpha }_i{y}_i{\mathbf{x}}_i+b$$

所以，我们可以得到关于${\sum }_{i=3}^m{\alpha }_i{y}_i{\mathbf{x}}_i$
$$\sum _{i=3}^m{\alpha }_i{y}_i{K}_{1i}=f(x_1)-{\alpha }_1{y}_1{K}_{11}-{\alpha }_2{y}_2{K}_{12}-b$$

同样的，
$$\sum _{i=3}^m{\alpha }_i{y}_i{K}_{2i}=f(x_2)-{\alpha }_1{y}_1{K}_{12}-{\alpha }_2{y}_2{K}_{22}-b$$

带入后得到
$${\alpha }_2^{new}(K_{11}-2K_{12}+K_{22})=y_2[y_2-y_1+{\alpha }_1^{old}{y}_1{K}_{11}+{\alpha }_2^{old}{y}_2{K}_{11}-{\alpha }_1^{old}{y}_1{K}_{12}-{\alpha }_2^{old}{y}_2{K}_{12}+f(x_1)-{\alpha }_1^{old}{y}_1{K}_{11}-{\alpha }_2^{old}{y}_2{K}_{22}-f(x_2)+{\alpha }_1^{old}{y}_1{K}_{12}+{\alpha }_2^{old}{y}_2{K}_{22}]$$

继续化简！
$${\alpha }_2^{new}(K_{11}-2K_{12}+K_{22})=y_2[y_2-y_1+{\alpha }_2^{old}{y}_2{K}_{11}-2{\alpha }_1^{old}{y}_1{K}_{12}+f(x_1)-f(x_2)+{\alpha }_2^{old}{y}_2{K}_{22}]$$

我们整理一下得到
$${\alpha }_2^{new}(K_{11}-2K_{12}+K_{22})=y_2[f(x_1)-y_1-(f(x_2)-y_2)+{\alpha }_2^{old}{y}_2(K_{11}-K_{12}+K_{22})]$$

这个时候另 $E=f(x)-y$，$\eta =K_{11}-K_{12}+K_{22}$，因此可以得到
$${\alpha }_2^{new}\eta =y_2(E1-E2+a_2^{old}{y}_2\eta )$$

因此，得到${\alpha }_2$
$${\alpha }_2=\frac{y_2(E1-E2+a_2^{old}{y}_2\eta )}{\eta }$$

化简得到最终式子
$${\alpha }_2=a_2^{old}+\frac{y_2(E1-E2)}{\eta }$$
对应的，${\alpha }_1$等于

$${\alpha }_1=y_1(C-a_2^{new}{y}_2)$$

理解了，我们将直观语言与数学推导结合，以确保即使是对这些数学原理不熟悉的读者也能理解。

SMO算法中的剪辑边界理解与推导

在序列最小优化（SMO）算法的执行过程中，重要的一步是确定拉格朗日乘数的剪辑边界。这个步骤确保乘数值在优化过程中保持有效并遵守SVM的约束条件。

约束条件

每个拉格朗日乘数 ${\alpha }_i$ 必须满足两个基本约束条件：

1. 它们的取值范围在0和某个上限 $C$ 之间，这里的 $C$ 是一个预设的正则化参数，用以控制模型的复杂度。
2. 所有样本的 ${\alpha }_i{y}_i$ 乘积之和必须等于0，以满足SVM的约束条件。

当优化 ${\alpha }_1$ 和 ${\alpha }_2$ 时，由于所有其他的乘数都保持不变，这两个乘数的加权和也必须保持不变。这一和在优化前已知，记为 $\zeta$，即：

$${\alpha }_1^{old}{y}_1+{\alpha }_2^{old}{y}_2=\zeta$$

剪辑边界的数学推导

剪辑边界 $L$ 和 $H$ 的推导取决于 $y_1$ 和 $y_2$ 的值。这两个标签值表示样本所属的类别，且只能是1或-1。以下是两种情况的具体推导：

情况一：$y_1 \neq y_2)

当 $y_1$ 和 $y_2$ 有不同的符号时（比如 $y_1=1$，$y_2=-1$），我们有：

$${\alpha }_2={\alpha }_1-\zeta \text{(因为 y2=−1)}$$

由于 $0\le {\alpha }_2\le C$，我们可以得出：

• $L=\max (0,{\alpha }_2^{old}-{\alpha }_1^{old})$，确保在 ${\alpha }_1$ 增加时，${\alpha }_2$ 不会变为负值。
• $H=\min (C,C+{\alpha }_2^{old}-{\alpha }_1^{old})$，确保在 ${\alpha }_1$ 减少时，${\alpha }_2$ 不会超过上限 $C$

情况二：$y_1=y_2$

当 $y_1$ 和 $y_2$ 有相同的符号时（假设都为1），我们有：

$${\alpha }_2=\zeta -{\alpha }_1$$

由此可推导出：

• $L=\max (0,{\alpha }_1^{old}+{\alpha }_2^{old}-C)$，避免在 ${\alpha }_1$ 和 ${\alpha }_2$ 同时增加时超出 $C$。
• $H=\min (C,{\alpha }_1^{old}+{\alpha }_2^{old})$，防止在 ${\alpha }_1$ 和 ${\alpha }_2$ 同时减少时出现负值。

计算 ${\alpha }_1$和 ${\alpha }_2$

接下来，我们需要计算 ${\alpha }_2$ 的新值。这可以通过目标函数 $L$ 的偏导数来实现，前面我们已经求过了，这里就直接给出结果

令 $E_i=u_i-y_i$ 为模型对第 (i) 个样本的预测误差，$u_i$ 是模型的预测输出，那么我们可以通过求导得到：

$${\alpha }_2^{new,unc}={\alpha }_2^{old}+\frac{y_2(E_1-E_2)}{\eta }$$

其中 $\eta$ 是 $K({\mathbf{x}}_1,{\mathbf{x}}_1)+K({\mathbf{x}}_2,{\mathbf{x}}_2)-2K({\mathbf{x}}_1,{\mathbf{x}}_2)$，它是目标函数的二次项系数。

最后，我们必须对 ${\alpha }_2^{new,unc}$ 进行剪辑，以确保它在 $L$ 和 $H$ 的范围内：

$${\alpha }_2^{new}=\{\begin{array}{ll}H& \text{if }{\alpha }_2^{new,unc}>H\\ {\alpha }_2^{new,unc}& \text{if }L\le {\alpha }_2^{new,unc}\le H\\ L& \text{if }{\alpha }_2^{new,unc}<L\end{array}$$

一旦有了 ${\alpha }_2^{new}$，我们就可以直接计算 ${\alpha }_1^{new}$ 以满足等式约束：

$${\alpha }_1^{new}={\alpha }_1^{old}+y_1{y}_2({\alpha }_2^{old}-{\alpha }_2^{new})$$

这样，我们就得到了一对新的拉格朗日乘数 ${\alpha }_1^{new}$ 和 ${\alpha }_2^{new}$，它们满足原始问题的约束条件，同时最大化了对偶问题的目标函数。通过迭代这个过程，SMO算法可以高效地求解出所有的拉格朗日乘数，最终得到SVM的解。

偏置 ( b ) 和误差 ( E ) 的推导

在序列最小优化（SMO）算法中，不仅需要优化拉格朗日乘数 $\alpha$，还必须计算出偏置 $b$ 和误差 $E$ 来构建完整的支持向量机模型。偏置 $b$ 对于确定最优超平面的位置至关重要，而误差 $E$ 用于评估分类的准确性和进行进一步的优化。

计算偏置 $b$

偏置 $b$ 的计算基于那些处于边界上的支持向量，即满足 $0<{\alpha }_i<C$ 的样本。这些样本严格遵守：

$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)=1$$

重新整理这个等式，我们可以解出 $b$：

$$b=y_i-{\mathbf{w}}^T{\mathbf{x}}_i$$

其中 $\mathbf{w}$ 由 $\mathbf{w}={\sum }_{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i$ 计算得到。为了提高计算的稳定性和减少随机误差，通常采用所有支持向量得到的 $b$ 值的平均值：

$$b=\frac{1}{n_{SV}}\sum _{i\in SV}(y_i-\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_j^T{\mathbf{x}}_i)$$

这里 $SV$ 表示所有支持向量的索引集合，$n_{SV}$ 是支持向量的数量。

确实，这段内容简要地描述了误差 ( E_i ) 的定义，但没有提供详细的计算或推导过程。让我们详细说明 ( E_i ) 的计算过程，以及它如何用于SMO算法中选择乘数进行优化。

误差 $E_i$ 的详细计算和推导

定义误差 $E_i$

在SVM中，误差 $E_i$ 表示模型对第 $i$ 个样本的预测输出 $u_i$ 和实际标签 $y_i$ 之间的差异。它的计算公式是：

$$E_i=u_i-y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)-y_i$$

推导模型输出 $u_i$

模型的预测输出 $u_i$ 由决策函数确定：

$$u_i={\mathbf{w}}^T{\mathbf{x}}_i+b$$

其中，权重向量 $\mathbf{w}$ 是由所有支持向量的拉格朗日乘数和对应的训练样本的特征向量的乘积的和表示：

$$\mathbf{w}=\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_j$$

将 $\mathbf{w}$ 代入 $u_i$ 的表达式中，我们得到：

$$u_i=\left(\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_j^T\right){\mathbf{x}}_i+b=\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_j^T{\mathbf{x}}_i+b$$

更新和计算 $E_i$

因此，$E_i$ 可以重写为：

$$E_i=\left(\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_j^T{\mathbf{x}}_i+b\right)-y_i$$

这表明 $E_i$ 是由当前所有拉格朗日乘数 ${\alpha }_j$、对应的类标签 $y_j$、训练数据的内积以及偏置 $b$ 共同决定的。

$E_i$ 在SMO中的应用

在SMO算法中，$E_i$ 用于决定哪两个乘数需要被优化。算法通常选取两个乘数：一个是最大化目标函数的梯度违反程度的乘数（通常选择 $E_i$ 最大或最小的样本），另一个则是与其成对优化的乘数。选择这两个乘数是为了尝试最大程度地减少目标函数，即减少误差 $E$。

选择标准

1. 选择 ${\alpha }_1$: 选择违反KKT条件最严重的乘数。
2. 选择 ${\alpha }_2$: 在非边界乘数中选择使 $|E_1-E_2|$ 最大的 ${\alpha }_2$。这是基于启发式的，目的是选择有助于最快收敛的乘数。

通过这种方式，SMO算法有效地使用 E_i$ 来引导搜索过程，确保每一步都朝着减少整体分类误差的方向前进。

整合 $b$ 和 $E$ 的更新过程

在优化 ${\alpha }_1$ 和 ${\alpha }_2$ 后，我们需要重新计算 $b$ 和 $E$。假设 ${\alpha }_2$ 更新后的值为 ${\alpha }_2^{new}$，我们计算 $b$ 的新值，考虑两种情况，以使得新的 $b$ 对所有支持向量都有效：

1. 如果 $0<{\alpha }_2^{new}<C$，那么 $x_2$ 是一个支持向量，可以直接用上述 $b$ 的更新公式。
2. 如果 ${\alpha }_2^{new}$ 达到边界 0 或 $C$ ，则需要通过其他支持向量来平均计算 $b$。

每次更新 $\alpha$ 后，都需要更新所有样本的 $E$ 值，以便下一次迭代使用：

$$E_i^{new}={\mathbf{w}}^T{\mathbf{x}}_i+b^{new}-y_i$$

这篇关于复现SMO算法：深入探索序列最小优化的分析方法【三、算法原理揭秘-1】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---