本文主要是介绍复现SMO算法:序列最小优化的启发式方法【三、算法原理揭秘-2】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
接下来的内容将转向SMO算法的第二个核心组成部分——选择要优化的乘数的启发式方法。在这篇博客中,我们将探讨算法如何通过启发式选择策略高效地识别
和更新
拉格朗日乘数。通过对比直接优化的分析方法和启发式方法
的策略选择,我们能够更全面地理解SMO算法在解决支持向量机(SVM)优化问题中的独特优势。
启发式方法
- 二、选择要优化的乘数的启发式方法
二、选择要优化的乘数的启发式方法
SMO算法包含两个主要步骤:选择需要优化的拉格朗日乘数对和优化这些乘数。算法采用启发式方法选择乘数对,加快收敛速度并确保选择的对最可能迅速改善模型性能。
1.外层循环 - 选择 α 1 \alpha_1 α1:
- 遍历所有训练样本,识别违反KKT条件最严重的样本作为 α 1 \alpha_1 α1。
- 如果某个样本不满足以下条件之一,它就被认为违反了KKT条件:
- 如果 α i = 0 \alpha_i = 0 αi=0,则要求 y i u i ≥ 1 y_i u_i \geq 1 yiui≥1。
- 如果 0 < α i < C 0 < \alpha_i < C 0<αi<C,则要求 y i u i = 1 y_i u_i = 1 yiui=1。
- 如果 α i = C \alpha_i = C αi=C,则要求 y i u i ≤ 1 y_i u_i \leq 1 yiui≤1。
- 如果所有在边界上的支持向量满足KKT条件,则扩展搜索至整个训练集。
2.内层循环 - 选择 α 2 \alpha_2 α2:
- 选择使得 ∣ E 1 − E 2 ∣ |E_1 - E_2| ∣E1−E2∣ 最大的 α 2 \alpha_2 α2,其中 E i = u i − y i E_i = u_i - y_i Ei=ui−yi 是样本 i i i 的预测误差,这有助于实现 α 2 \alpha_2 α2 的最大变化。
3. 计算和更新 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2:
推导过程,请见博客:复现SMO算法:深入探索序列最小优化的分析方法【三、算法原理揭秘-1】
在SMO算法中, α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 的优化是算法的核心。这两个乘数的更新是通过解析方法完成的,目的是最大化SVM的目标函数。这一过程可以分为几个步骤:
-
计算误差差值:
E 1 = u 1 − y 1 , E 2 = u 2 − y 2 E_1 = u_1 - y_1, \quad E_2 = u_2 - y_2 E1=u1−y1,E2=u2−y2
其中, u i u_i ui 是模型对第 i i i 个样本的预测输出, y i y_i yi 是实际标签。 -
计算二乘数的上下界:
为了满足约束条件 0 ≤ α i ≤ C 0 \leq \alpha_i \leq C 0≤αi≤C 和 ∑ i = 1 N α i y i = 0 \sum_{i=1}^{N} \alpha_i y_i = 0 ∑i=1Nαiyi=0,我们需要计算 α 2 \alpha_2 α2 的上下界(L 和 H)。- 如果 y 1 ≠ y 2 y_1 \neq y_2 y1=y2:
L = max ( 0 , α 2 o l d − α 1 o l d ) , H = min ( C , C + α 2 o l d − α 1 o l d ) L = \max(0, \alpha_2^{old} - \alpha_1^{old}), \quad H = \min(C, C + \alpha_2^{old} - \alpha_1^{old}) L=max(0,α2old−α1old),H=min(C,C+α2old−α1old) - 如果 y 1 = y 2 y_1 = y_2 y1=y2:
L = max ( 0 , α 1 o l d + α 2 o l d − C ) , H = min ( C , α 1 o l d + α 2 o l d ) L = \max(0, \alpha_1^{old} + \alpha_2^{old} - C), \quad H = \min(C, \alpha_1^{old} + \alpha_2^{old}) L=max(0,α1old+α2old−C),H=min(C,α1old+α2old)
- 如果 y 1 ≠ y 2 y_1 \neq y_2 y1=y2:
-
计算 α 2 \alpha_2 α2 的新值:
α 2 \alpha_2 α2 的新值由下式给出:
α 2 n e w = α 2 o l d + y 2 ( E 1 − E 2 ) η \alpha_2^{new} = \alpha_2^{old} + \frac{y_2 (E_1 - E_2)}{\eta} α2new=α2old+ηy2(E1−E2)
其中, η \eta η 是核函数 K ( x 1 , x 2 ) K(x_1, x_2) K(x1,x2) 的二阶导数,可以理解为对问题的“曲率”或调整步幅的影响因子。 -
剪辑 α 2 \alpha_2 α2:
α 2 n e w \alpha_2^{new} α2new 需要在其界限 L 和 H 之间被剪辑:
α 2 n e w , c l i p p e d = min ( max ( α 2 n e w , L ) , H ) \alpha_2^{new, clipped} = \min(\max(\alpha_2^{new}, L), H) α2new,clipped=min(max(α2new,L),H) -
更新 α 1 \alpha_1 α1:
根据 α 2 \alpha_2 α2 的变化更新 α 1 \alpha_1 α1:
α 1 n e w = α 1 o l d + y 1 y 2 ( α 2 o l d − α 2 n e w , c l i p p e d ) \alpha_1^{new} = \alpha_1^{old} + y_1 y_2 (\alpha_2^{old} - \alpha_2^{new, clipped}) α1new=α1old+y1y2(α2old−α2new,clipped)
更新偏置 b b b 和误差 E i E_i Ei:
- 根据新的乘数值重新计算偏置 b b b:
b n e w = b o l d − Δ b b_{new} = b_{old} - \Delta b bnew=bold−Δb - Δ b \Delta b Δb 根据 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 的变化量及其对应样本的 y i y_i yi 和 E i E_i Ei 值计算得出。
- 重新计算所有样本的误差 E i E_i Ei:
E i = ( w T x i + b ) − y i E_i = (\mathbf{w}^T \mathbf{x}_i + b) - y_i Ei=(wTxi+b)−yi - 更新权重向量 w \mathbf{w} w:
w = ∑ j = 1 m α j y j x j \mathbf{w} = \sum_{j=1}^m \alpha_j y_j \mathbf{x}_j w=j=1∑mαjyjxj
关键问题解析
问题一:如何判定违反KKT条件最严重?
违反KKT条件的程度是通过样本的乘数 α i \alpha_i αi 和它们的函数间隔 y i u i y_i u_i yiui 的关系来判定的。具体方法如下:
- α i = 0 \alpha_i = 0 αi=0 的样本:理论上应满足 y i u i ≥ 1 y_i u_i \geq 1 yiui≥1。如果 y i u i < 1 − ϵ y_i u_i < 1 - \epsilon yiui<1−ϵ,这种违反被视为严重。
- 0 < α i < C 0 < \alpha_i < C 0<αi<C 的样本:应精确满足 y i u i = 1 y_i u_i = 1 yiui=1。偏
离1超过 ϵ \epsilon ϵ 的情况被认为违反严重。
- α i = C \alpha_i = C αi=C 的样本:应满足 y i u i ≤ 1 y_i u_i \leq 1 yiui≤1。如果 y i u i > 1 + ϵ y_i u_i > 1 + \epsilon yiui>1+ϵ,同样视为严重违反。
问题二:计算 ∣ E 1 − E 2 ∣ |E_1 - E_2| ∣E1−E2∣ 最大的 α 2 \alpha_2 α2
- 误差 E i E_i Ei 的计算公式为:
E i = ( ∑ j = 1 m α j y j K ( x j , x i ) + b ) − y i E_i = (\sum_{j=1}^m \alpha_j y_j K(x_j, x_i) + b) - y_i Ei=(j=1∑mαjyjK(xj,xi)+b)−yi - 选择 α 2 \alpha_2 α2 通过寻找最大化 ∣ E 1 − E 2 ∣ |E_1 - E_2| ∣E1−E2∣ 的 α j \alpha_j αj 实现,即:
j = arg max j ∣ E 1 − E j ∣ j = \arg\max_j |E_1 - E_j| j=argjmax∣E1−Ej∣
伪代码实现
初始化所有乘数 alpha_i = 0
为所有 i 初始化误差 E_i
k = 0重复直至收敛:// 外部循环选择 alpha_1对每个样本 i:计算 u_i = sum(alpha_j * y_j * K(x_j, x_i)) + b检查KKT条件如果违反:alpha_1 = alpha_iE_1 = E_i// 内部循环选择 alpha_2找到最大化 |E_1 - E_j| 的 jalpha_2 = alpha_jE_2 = E_j// 优化 alpha_1 和 alpha_2更新 alpha_1 和 alpha_2更新 b 重新计算误差k += 1检查收敛条件
这篇关于复现SMO算法:序列最小优化的启发式方法【三、算法原理揭秘-2】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!