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=1∑Nj=1∑NαiαjyiyjK(xi⋅xj)−i=1∑Nαi s.t. i=1∑Nαiyi=00≤αi≤C,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=3∑NyiαiKi1+y2α2i=3∑NyiαiKi2α1y1+α2y2=−i=3∑Nyiαi=γ0≤αi≤C,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 可得 α 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+α1−C),上界 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=1∑Nα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=1∑Nα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(E1−E2)(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+K22−2K12=∥ϕ(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, unc≤Hα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=1∑Nα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=y1−i=3∑Nα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=y2−i=3∑Nα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
相关文章:
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_{i1}^{N} \sum_{j1}^{N} \alpha_i \alpha_j…...
nodejs包管理器pnpm
简介 通常在nodejs项目中我们使用npm或者yarn做为默认的包管理器,但是pnpm的出现让我们的包管理器有了更多的选择,pnpm相比npm具有以下优势: 速度更快,pnpm在安装依赖时,会将依赖包缓存到全局目录,下次安…...
【postman】工具下载安装
postman作用 postman用于测试http协议接口,无论是开发, 还是测试人员, 都有必要学习使用postman来测试接口, 用起来非常方便。 环境安装 postman 可以直接在chrome 上安装插件,当然大部分的同学是没法连接到谷歌商店的,我们可以在电脑本地…...
Java_Springboot核心配置详解
Spring Boot以其简洁、高效和约定优于配置的理念,极大地简化了Java应用的开发流程。在Spring Boot中,核心配置是应用启动和运行的基础。本文将详细介绍Spring Boot中的两种配置文件格式、基础注解的配置方式、自定义配置以及多环境配置。 一、Spring Bo…...
太速科技-9-基于DSP TMS320C6678+FPGA XC7V690T的6U VPX信号处理卡
基于DSP TMS320C6678FPGA XC7V690T的6U VPX信号处理卡 一、概述 本板卡基于标准6U VPX 架构,为通用高性能信号处理平台,系我公司自主研发。板卡采用一片TI DSP TMS320C6678和一片Xilinx公司Virtex 7系列的FPGA XC7V690T-2FFG1761I作为主处理器&#…...
在线UI设计工具:创意与效率的结合
随着UI设计领域的快速增长,设计师们纷纷投身于这一行业,选择一款合适的UI设计工具变得至关重要。除了经典的UI设计软件,在线UI设计工具因其灵活性和便捷性,越来越受到设计师们的喜爱。这种不受时间和地点限制,且不依赖…...
【MyBatis源码】SqlSessionFactoryBuilder源码分析
文章目录 概述类结构从 InputStream 创建 SqlSessionFactoryXMLConfigBuilder构建ConfigurationXMLConfigBuilder初始化方法parse()方法parseConfiguration属性(properties) 概述 SqlSessionFactory 是 MyBatis 的核心接口之一,提供创建 Sql…...
Percona XtraBackup数据备份方案
一、简介 官方文档:https://docs.percona.com/percona-xtrabackup/innovation-release/index.html Percona XtraBackup 是一款适用于基于 MySQL 的服务器的开源热备份实用程序,可让您的数据库在计划的维护时段内保持完全可用。无论是 24x7 高负载服务器还是低交易量服务器,…...
聚“芯”而行,华普微亮相第五届Silicon Labs Works With大会
2024年10月24日,由致力于以安全、智能无线连接技术建立更互联世界的全球领导厂商Silicon Labs主办的第五届Works With开发者大会在上海雅乐居万豪侯爵酒店成功举办。 作为全球性的物联网年度“盛宴”,本届大会群英荟萃,不仅有着来自生态大厂的…...
Java 用户随机选择导入ZIP文件,解压内部word模板并入库,Windows/可视化Linux系统某麒麟国防系统...均可适配
1.效果 压缩包内部文件 2.依赖 <!--支持Zip--><dependency><groupId>net.lingala.zip4j</groupId><artifactId>zip4j</artifactId><version>2.11.5</version></dependency>总之是要File类变MultipartFile类型的 好像是…...
【C++】C++17结构化绑定、std::optional、std::variant、std::any
二十二、C17中的结构化绑定、std::optional、std::variant、std::any 本部分是一个小系列,介绍C17中新引入的、用来解决各种不同返回情况的、标准库新组件。 1、C的结构化绑定 结构化绑定structured bindings是C17中引入的一项特性,它允许开发者方便地…...
C#的起源。J++语言的由来?J#和J++傻傻分不清?
C#的起源 C#读音是C Sharp, 它是微软为了对抗Java而生,最早是J,效率比Java还好,后来被Sun公司起诉J破坏了平台无关性,微软重新开发C#. C#和Java一样都定位为中间件语言,用虚拟机执行编译的字节码以达到跨平台目的。从语…...
Flutter 在 对接 google play 时,利用 android studio 可视化生成 已签名的aab包
android studio 可视化生成 aab包 第一 : 先说注意事项 在Flutter项目里面,直接打开当前项目是不行的,不显示相应操作,需要在Android 目录打开,直白点就是直接打开项目里面的Android 目录 不然会出现的一些问题 第一…...
使用web.dev提供的工具实现浏览器消息推送服务
文章目录 前言实现工具和效果实现原理实现过程前端接收用户订阅请求将用户订阅信息更新到后端后端实现接收并保存订阅信息的接口后端实现消息推送的逻辑前言 对于电商独立站来说,新品上架或者促销活动上线及时通知到用户是很重要的,通知的渠道有很多,其中就包括浏览器消息推…...
计算机系统结构为什么用architecture 而不是structure?
architecture本意是建筑学、建筑艺术,其含义就是建筑的样子和背后的设计思想,用于计算机科学可以表达计算机的系统结构和后面的设计原理:它长什么样?它为什么长这样? 与architecture 对应的词是structure (…...
sqoop问题汇总记录
此篇博客仅记录在使用sqoop时遇到的各种问题。持续更新,有问题评论区一起探讨,写得有不足之处见谅。 Oracle_to_hive 1. main ERROR Could not register mbeans java.security.AccessControlException: access denied ("javax.management.MBeanTr…...
Git 创建新的分支但清空提交记录
有时候需要创建新的分支,但是原有分支的提交非常多,不好区分哪些是创建分支之后的提交。 那么就把原分支的提交全部去掉 要从 分支1 创建 分支2,并确保 分支2 不包含任何提交历史,同时文件与 分支1 的最后一次提交一致࿰…...
SQL PRIMARY KEY
SQL PRIMARY KEY 概述 在关系型数据库中,主键(PRIMARY KEY)是一个非常重要的概念。它是表中每一行数据的唯一标识符,用于保证数据的完整性和准确性。本文将详细介绍SQL中的主键,包括其定义、作用、如何创建和修改主键…...
软件测试学习笔记丨Flask操作数据库-对象与数据模型
本文转自测试人社区,原文链接:https://ceshiren.com/t/topic/23440 对象与数据模型 数据模型:是数据特征的抽象,抽象层次上描述了系统的静态特征、动态行为和约束条件,为数据库系统的信息表示与操作提供一个抽象的框架…...
IntelliJ IDEA使用 MybatisX-Generator 插件 自动生成Entity+Mapper+Mapper.xml等代码
一、Intellij安装MybatisX插件: 首先点击 Intellij->Preference->Plugins,然后搜索MybatisX,点击安装: 2 打开数据库 在IntelliJ IDEA 连接Mysql数据库,选择表,点击右键,选择 Mybatis…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...
【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...
大数据驱动企业决策智能化的路径与实践
📝个人主页🌹:慌ZHANG-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、引言:数据驱动的企业竞争力重构 在这个瞬息万变的商业时代,“快者胜”的竞争逻辑愈发明显。企业如何在复杂环…...
【版本控制】GitHub Desktop 入门教程与开源协作全流程解析
目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork(创建个人副本)步骤 2: Clone(克隆…...
