当前位置: 首页 > news >正文

SMO算法 公式推导

min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i ⋅ x j ) − ∑ i = 1 N α i s.t.  ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , ⋯ , N (9-69) \begin{aligned} & \min_{\alpha} \quad \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j K(x_i \cdot x_j) - \sum_{i=1}^{N} \alpha_i \\ & \text { s.t. } \quad \sum_{i=1}^{N} \alpha_i y_i = 0 \\ & \quad 0 \leq \alpha_i \leq C, \quad i = 1, 2, \cdots, N \tag{9-69} \end{aligned} αmin21i=1Nj=1NαiαjyiyjK(xixj)i=1Nαi s.t. i=1Nαiyi=00αiC,i=1,2,,N(9-69)

9.4.2 SMO 算法

SMO 算法主要用来求解式(9-69)的凸二次规划问题,在该问题中,变量是拉格朗日乘子 α i \alpha_i αi,一个 α i \alpha_i αi 对应一个样本点 ( x i , y i ) (x_i, y_i) (xi,yi),所以变量总数就是样本量 N N N。SMO 算法是一种针对非线性支持向量机凸优化问题快速求解的优化算法,其基本想法是:不断地将原二次规划问题分解为只有两个变量的子二次规划问题,并对该子问题进行解析和求解,直到所有变量都满足 KKT 条件为止。

假设选择的两个变量为 α 1 \alpha_1 α1 α 2 \alpha_2 α2 α 3 , α 4 , ⋯ , α N \alpha_3, \alpha_4, \cdots, \alpha_N α3,α4,,αN 固定,那么式(9-69)的子问题可以表示为:

min ⁡ α 1 , α 2 S ( α 1 , α 2 ) = 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) + y 1 α 1 ∑ i = 3 N y i α i K i 1 + y 2 α 2 ∑ i = 3 N y i α i K i 2 s.t. α 1 y 1 + α 2 y 2 = − ∑ i = 3 N y i α i = γ 0 ≤ α i ≤ C , i = 1 , 2 (9-72) \begin{split} \min_{\alpha_1, \alpha_2} & \quad S(\alpha_1, \alpha_2) = \frac{1}{2} K_{11} \alpha_1^2 + \frac{1}{2} K_{22} \alpha_2^2 + y_1 y_2 K_{12} \alpha_1 \alpha_2 - (\alpha_1 + \alpha_2) + \\ & \quad y_1 \alpha_1 \sum_{i=3}^N y_i \alpha_i K_{i1} + y_2 \alpha_2 \sum_{i=3}^N y_i \alpha_i K_{i2} \\ \text{s.t.} & \quad \alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}^N y_i \alpha_i = \gamma \\ & \quad 0 \leq \alpha_i \leq C, \quad i = 1, 2 \tag{9-72} \end{split} α1,α2mins.t.S(α1,α2)=21K11α12+21K22α22+y1y2K12α1α2(α1+α2)+y1α1i=3NyiαiKi1+y2α2i=3NyiαiKi2α1y1+α2y2=i=3Nyiαi=γ0αiC,i=1,2(9-72)

其中 K i j = K ( x i , x j ) K_{ij} = K(x_i, x_j) Kij=K(xi,xj)

式(9-72)即为两个变量的二次规划问题,先分析约束条件来考虑 α 2 \alpha_2 α2 的上下界问题。 α 1 \alpha_1 α1 α 2 \alpha_2 α2 都在 [ 0 , C ] [0, C] [0,C] 范围内,由式(9-72)的第一个约束条件可知, ( α 1 , α 2 ) (\alpha_1, \alpha_2) (α1,α2) 在平行于 [ 0 , C ] × [ 0 , C ] [0, C] \times [0, C] [0,C]×[0,C] 的对角线的直线上,如图 9-10 所示。

图 9-10 两个变量优化问题

由图 9-10 可得 α 2 \alpha_2 α2 的上下界描述如下:当 y 1 ≠ y 2 y_1 \neq y_2 y1=y2 时,下界 L = max ⁡ ( 0 , α 2 − α 1 ) L = \max(0, \alpha_2 - \alpha_1) L=max(0,α2α1),上界 H = min ⁡ ( C , C + α 2 − α 1 ) H = \min(C, C + \alpha_2 - \alpha_1) H=min(C,C+α2α1);当 y 1 = y 2 y_1 = y_2 y1=y2 时,下界 L = max ⁡ ( 0 , α 2 + α 1 − C ) L = \max(0, \alpha_2 + \alpha_1 - C) L=max(0,α2+α1C),上界 H = min ⁡ ( C , α 2 + α 1 ) H = \min(C, \alpha_2 + \alpha_1) H=min(C,α2+α1)

下面对 α 1 \alpha_1 α1 α 2 \alpha_2 α2 求解进行简单推导。假设子问题式(9-72)的初始可行解为 α 1 old \alpha_1^\text{old} α1old α 2 old \alpha_2^\text{old} α2old,最优解为 α 1 new \alpha_1^\text{new} α1new α 2 new \alpha_2^\text{new} α2new,沿着约束方向上未经截断的 α 2 \alpha_2 α2 的最优解为 α 2 new, unc \alpha_2^\text{new, unc} α2new, unc。一般情况下,我们尝试首先沿着约束方向求未经截断即不考虑式(9-72)的第二个约束条件的最优解 α 2 new, unc \alpha_2^\text{new, unc} α2new, unc,然后再求截断后的最优解 α 2 new \alpha_2^\text{new} α2new

令:
g ( x ) = ∑ i = 1 N α i y i K ( x i , x ) + b (9-73) g(x) = \sum_{i=1}^N \alpha_i y_i K(x_i, x) + b \tag{9-73} g(x)=i=1NαiyiK(xi,x)+b(9-73)

E i = g ( x i ) − y i = ( ∑ j = 1 N α j y j K ( x j , x i ) + b ) − y i (9-74) E_i = g(x_i) - y_i = \left( \sum_{j=1}^N \alpha_j y_j K(x_j, x_i) + b \right) - y_i \tag{9-74} Ei=g(xi)yi=(j=1NαjyjK(xj,xi)+b)yi(9-74)

i = 1 , 2 i = 1, 2 i=1,2 时, E i E_i Ei 为函数 g ( x ) g(x) g(x) 对输入 x i x_i xi 的预测值和真实值 y i y_i yi 之间的误差。

关于目标函数对 α 2 \alpha_2 α2 求偏导并令其为 0,可求得未经截断的 α 2 \alpha_2 α2 的最优解为:
α 2 new, unc = α 2 old + y 2 ( E 1 − E 2 ) κ (9-75) \alpha_2^\text{new, unc} = \alpha_2^\text{old} + \frac{y_2(E_1 - E_2)}{\kappa} \tag{9-75} α2new, unc=α2old+κy2(E1E2)(9-75)

其中,
κ = K 11 + K 22 − 2 K 12 = ∥ ϕ ( x 1 ) − ϕ ( x 2 ) ∥ 2 (9-76) \kappa = K_{11} + K_{22} - 2K_{12} = \|\phi(x_1) - \phi(x_2)\|^2 \tag{9-76} κ=K11+K222K12=ϕ(x1)ϕ(x2)2(9-76)

ϕ ( x ) \phi(x) ϕ(x) 为输入空间在特征空间中的映射。

经截断后的 α 2 \alpha_2 α2 可表示为:
α 2 new = { H , α 2 new, unc > H α 2 new, unc , L ≤ α 2 new, unc ≤ H L , α 2 new, unc < L (9-77) \alpha_2^\text{new} = \begin{cases} H, & \alpha_2^\text{new, unc} > H \\ \alpha_2^\text{new, unc}, & L \leq \alpha_2^\text{new, unc} \leq H \\ L, & \alpha_2^\text{new, unc} < L \tag{9-77} \end{cases} α2new= H,α2new, unc,L,α2new, unc>HLα2new, uncHα2new, unc<L(9-77)

接着基于 α 2 new \alpha_2^\text{new} α2new 可求得 α 1 new \alpha_1^\text{new} α1new
α 1 new = α 1 old + y 1 y 2 ( α 2 old − α 2 new ) (9-78) \alpha_1^\text{new} = \alpha_1^\text{old} + y_1 y_2 \left( \alpha_2^\text{old} - \alpha_2^\text{new} \right) \tag{9-78} α1new=α1old+y1y2(α2oldα2new)(9-78)

最后,每次完成两个变量的优化后,还需要重新计算参数 b b b b b b 的计算分为四种情况:

0 < α 1 new < C 0 < \alpha_1^\text{new} < C 0<α1new<C 时,由:
∑ i = 1 N α i y i K i 1 + b = y 1 (9-79) \sum_{i=1}^N \alpha_i y_i K_{i1} + b = y_1 \tag{9-79} i=1NαiyiKi1+b=y1(9-79)

可得:
b 1 new = y 1 − ∑ i = 3 N α i y i K i 1 − α 1 new y 1 K 11 − α 2 new y 2 K 21 (9-80) b_1^\text{new} = y_1 - \sum_{i=3}^N \alpha_i y_i K_{i1} - \alpha_1^\text{new} y_1 K_{11} - \alpha_2^\text{new} y_2 K_{21} \tag{9-80} b1new=y1i=3NαiyiKi1α1newy1K11α2newy2K21(9-80)

同样,当 0 < α 2 new < C 0 < \alpha_2^\text{new} < C 0<α2new<C 时,有:
b 2 new = y 2 − ∑ i = 3 N α i y i K i 1 − α 2 new y 2 K 22 − α 1 new y 1 K 12 (9-81) b_2^\text{new} = y_2 - \sum_{i=3}^N \alpha_i y_i K_{i1} - \alpha_2^\text{new} y_2 K_{22} - \alpha_1^\text{new} y_1 K_{12} \tag{9-81} b2new=y2i=3NαiyiKi1α2newy2K22α1newy1K12(9-81)

α 1 new \alpha_1^\text{new} α1new α 2 new \alpha_2^\text{new} α2new 同时满足 0 < α 1 new < C 0 < \alpha_1^\text{new} < C 0<α1new<C 时,有:
b 1 new = b 2 new (9-82) b_1^\text{new} = b_2^\text{new} \tag{9-82} b1new=b2new(9-82)

最后一种情况是, α 1 new \alpha_1^\text{new} α1new α 2 new \alpha_2^\text{new} α2new 都不在 [ 0 , C ] [0, C] [0,C] 范围内, b 1 new b_1^\text{new} b1new b 2 new b_2^\text{new} b2new 都满足 KKT 条件,直接对其取均值即可。

综上,参数 b b b 可计算归纳为:
b new = { b 1 new , 0 < α 1 new < C b 2 new , 0 < α 2 new < C b 1 new + b 2 new 2 , 其他 (9-83) b^\text{new} = \begin{cases} b_1^\text{new}, & 0 < \alpha_1^\text{new} < C \\ b_2^\text{new}, & 0 < \alpha_2^\text{new} < C \\ \frac{b_1^\text{new} + b_2^\text{new}}{2}, & 其他 \end{cases} \tag{9-83} bnew= b1new,b2new,2b1new+b2new,0<α1new<C0<α2new<C其他(9-83)


以下是本文部分公式的详细解释:
公式9-72
拉格朗日乘子上界和下界
公式9-78

http://www.lryc.cn/news/473978.html

相关文章:

  • nodejs包管理器pnpm
  • 【postman】工具下载安装
  • Java_Springboot核心配置详解
  • 太速科技-9-基于DSP TMS320C6678+FPGA XC7V690T的6U VPX信号处理卡
  • 在线UI设计工具:创意与效率的结合
  • 【MyBatis源码】SqlSessionFactoryBuilder源码分析
  • Percona XtraBackup数据备份方案
  • 聚“芯”而行,华普微亮相第五届Silicon Labs Works With大会
  • Java 用户随机选择导入ZIP文件,解压内部word模板并入库,Windows/可视化Linux系统某麒麟国防系统...均可适配
  • 【C++】C++17结构化绑定、std::optional、std::variant、std::any
  • C#的起源。J++语言的由来?J#和J++傻傻分不清?
  • Flutter 在 对接 google play 时,利用 android studio 可视化生成 已签名的aab包
  • 使用web.dev提供的工具实现浏览器消息推送服务
  • 计算机系统结构为什么用architecture 而不是structure?
  • sqoop问题汇总记录
  • Git 创建新的分支但清空提交记录
  • SQL PRIMARY KEY
  • 软件测试学习笔记丨Flask操作数据库-对象与数据模型
  • IntelliJ IDEA使用 MybatisX-Generator 插件 自动生成Entity+Mapper+Mapper.xml等代码
  • vue中如何为不同功能设置不同的默认打印设置(设置不同的打印机)
  • 经纬恒润INTEWORK-VBA新版本正式发布
  • 金蝶云数据集成至MySQL的高效解决方案
  • Day02 C++ 环境设置
  • AQS是什么
  • Spring IOC容器简介
  • 【backstopjs】入门安装环境
  • LocalDate 类常用方法详解(日期时间类)
  • kmp desktop实现excel预览
  • OB_GINS_day3
  • 【Python3】【力扣题】405. 数字转换为十六进制数