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

机器学习5_支持向量机_原问题和对偶问题——MOOC

目录

原问题与对偶问题的定义

定义该原问题的对偶问题如下

在定义了函数  的基础上,对偶问题如下:

综合原问题和对偶问题的定义得到:

定理一

对偶差距(Duality Gap)

强对偶定理(Strong Duality Theorem)

假如  成立,又根据定理一推出不等式

转化为对偶问题

首先将

得到

最小化:

限制条件:

再整理一下

最小化: 或  

限制条件:

用对偶理论求解该问题的对偶问题

对偶问题

按照对偶问题的定义,可以将对偶问题写成如下形式:

如何将原问题化为对偶问题


原问题(Prime Problem)

对偶问题(Dual Problem)

原问题与对偶问题的定义

最小化(Minimize):f\left ( \omega \right )

限制条件(Subject to):g_i(\omega )\leq 0,i=1\sim K

                                          h_i(\omega )= 0,i=1\sim m

自变量为 \omega\Leftarrow 多维向量

目标函数是 f\left ( \omega \right ) 

定义该原问题的对偶问题如下

定义函数:

L(\omega ,\alpha ,\beta )=f(\omega )+\displaystyle\sum_{i=1}^{K}\alpha _ig_i(\omega )+\displaystyle\sum_{i=1}^{K}\beta _ih_i(\omega )

向量的形式 \Rightarrow  =f(\omega )+\alpha ^Tg(\omega )+\beta ^Th(\omega )

其中 \alpha =[\alpha _1,\alpha _2,...,\alpha _k]^T\beta =[\beta _1,\beta _2,...,\beta _M]^T

g(\omega )=[g_1(\omega ),g_2(\omega ),...,g_K(\omega )]^Th(\omega )=[h_1(\omega ),h_2(\omega ),...,h_M(\omega )]^T

在定义了函数 L(\omega ,\alpha ,\beta ) 的基础上,对偶问题如下:

最大化:\theta (\alpha ,\beta )=inf\text{ }L(\omega ,\alpha ,\beta ),所有定义域内的 \omega

限制条件:\alpha _i\geq 0,i=1\sim K

综合原问题和对偶问题的定义得到:

定理一

如果 \omega ^* 是原问题的解,(\alpha ^*,\beta ^*) 是对偶问题的解则有:

f(\omega ^*)\geqslant \theta (\alpha ^*,\beta ^*)

证明:\theta (\alpha^* ,\beta ^*)=inf\text{ }L(\omega ,\alpha^* ,\beta ^*)

                             \leq L(\omega^* ,\alpha^* ,\beta^* )

                     =f(\omega ^*)+\alpha ^{*T}g(\omega ^*)+\beta ^{*T}h(\omega ^*)

                             \leq f(\omega ^*)

\because  \omega ^* 是原问题的解

\therefore  g(\omega ^*)\leqslant 0h(\omega ^*)= 0

\because  (\alpha ^*,\beta ^*) 是对偶问题的解

\therefore  \alpha (\omega ^*)\geqslant 0


对偶差距(Duality Gap)

f(\omega ^*)- \theta (\alpha ^*,\beta ^*)

根据定理一,对偶差距 \geqslant 0


强对偶定理(Strong Duality Theorem)

如果 g(\omega )=A\omega +bh(\omega )=C\omega +df(\omega ) 为凸函数,则有 f(\omega ^*)= \theta (\alpha ^*,\beta ^*),则对偶差距为0。

如果:原问题的目标函数是凸函数,限制条件是线性函数。

那么原问题的解 f(\omega ^*)= \theta (\alpha ^*,\beta ^*),对偶差距等于0。

假如 f(\omega ^*)= \theta (\alpha ^*,\beta ^*) 成立,又根据定理一推出不等式

若 f(\omega ^*)= \theta (\alpha ^*,\beta ^*),则定理一中必然能够推出,对于所有的 i=1\sim K,要么 \alpha _i=0,要么 g_i(\omega ^*)=0。这个条件成为KKT条件


转化为对偶问题

支持向量机的原问题满足强对偶定理

首先将

\delta _i\geq 0(i=1\sim N) 转换成 \delta _i\leq 0(i=1\sim N)

得到

最小化:\frac{1}{2}\left \| \omega \right \|^2-C \displaystyle\Sigma _{i=1}^N \delta _i
限制条件:

        (1)\delta _i\leq 0(i=1\sim N)

        (2)y_i[\omega ^T\varphi (X_i)+b]\geq 1+\delta _i,(i=1\sim N)

再整理一下

最小化:\frac{1}{2}\left \| \omega \right \|^2-C \displaystyle\Sigma _{i=1}^N \delta _i 或  \frac{1}{2}\left \| \omega \right \|^2+C \displaystyle\Sigma _{i=1}^N \delta _i

                \Uparrow 情况1                          \Uparrow 情况2

限制条件:

        (1)\delta _i\leq 0(i=1\sim N)

        (2)1+\delta _i-y_i\omega ^T\varphi (X_i)-y_ib\leq 0 ,(i=1\sim N) 

两个限制条件都是线性的,支持向量机的目标函数是凸的,它满足强对偶定理。

用对偶理论求解该问题的对偶问题

对偶问题

自变量 \omega 等于这里的 \left ( \omega ,b,\delta _i \right )

不等式 g_i(\omega )\leq 0 在这里被分成了两部分,

        一部分:\delta _i\leq 0(i=1\sim N)

        另一部分:1+\delta _i-y_i\omega ^T\varphi (X_i)-y_ib\leq 0 ,(i=1\sim N)

不存在 h_i(\omega )

按照对偶问题的定义,可以将对偶问题写成如下形式:

最大化:

\theta (\alpha ,\beta )=inf_{\omega ,\delta _i,b} \left \{ \frac{1}{2}\left \| \omega \right \|^2-C \sum_{i=1}^{N}\beta _i\delta _i+\sum_{i=1}^{N} \alpha _i\left [1+\delta _i-y_i\omega ^T\varphi (X_i)-y_ib \right ] \right \}

限制条件:

        (1)\alpha _i\geq 0

        (2)\beta _i\geq 0

如何将原问题化为对偶问题

遍历所有 \left ( \omega ,b,\delta _i \right ) 求最小值

对 \left ( \omega ,b,\delta _i \right ) 求导并令导数为 \textbf{0}

(1)\frac{\partial \theta }{\partial\omega }=\omega-\sum_{i=1}^{N}\alpha _i\varphi (X_i)y_i=0 \text{ } \Rightarrow \text{ } \omega=\sum_{i=1}^{N}\alpha _iy_i\varphi (X_i)

(2)\frac{\partial \theta }{\partial\delta _i }=-C+\alpha _i+\beta _i=0 \text{ } \Rightarrow \text{ }\alpha _i+\beta _i=C

(3)\frac{\partial \theta }{\partial b }=-\sum_{i=1}^{N}\alpha _iy_i=0 \text{ } \Rightarrow \text{ } \sum_{i=1}^{N}\alpha _iy_i=0

(1)用的是向量的求导准则,(2)、(3)用的是常规的自变量求导。

将获得的三个式子代入到表达中

将支持向量机的原问题化为对偶问题:

最大化:

\theta (\alpha ,\beta )=\sum_{i=1}^{N}\alpha _i-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_i y_j\alpha _i\alpha _j\varphi (X_i)^T\varphi (X_j)

限制条件:

        (1)0\leq \alpha _i\leq C,(i=1\sim N)

前面:\alpha _i\geq 0,\beta _i\geq 0

根据:\alpha _i+\beta _i=C \text{ }

        \Rightarrow \text{ }\beta _i=C-\alpha_i\geqslant 0

        (2)\sum_{i=1}^{N}\alpha _iy_i=0,(i=1\sim N)

相关文章:

机器学习5_支持向量机_原问题和对偶问题——MOOC

目录 原问题与对偶问题的定义 定义该原问题的对偶问题如下 在定义了函数 的基础上,对偶问题如下: 综合原问题和对偶问题的定义得到: 定理一 对偶差距(Duality Gap) 强对偶定理(Strong Duality Theo…...

索引的细节

目录 什么是线性 搜索算法? 算法:二进制搜索算法 二进制搜索如何工作? 什么是二叉排序树? 构建二叉排序树 什么是AVL树? AVL树的性能分析 什么是线性 搜索算法? 线性搜索是一种非常简单的搜索算法。在…...

LeetCode 540.有序数组中的单一元素

思路一:hash,键存入元素,值存入次数,然后遍历,不是最优解 思路二:二分查找 假设数组为 [1, 1, 2, 2, 3, 4, 4],其中唯一出现一次的元素是 3。在一个有序数组中,如果没有唯一的元素&…...

【图文】【DIY便签】如何自行编译OPENCV使用动态库

1 去官网下载安装包和源码 下面红色圈中的是源码,绿色圈中的是安装包: 2 配置工具链 安装过程不说了,教程到处都是。编译的话使用CMAKE,配置如下: 上面两个路径分别是: 源码目录编译生成的文件放置的位…...

WordPress文章自动提交Bing搜索引擎:PHP推送脚本教程

随着网站SEO优化的重要性日益增加,将新发布的内容快速提交到搜索引擎显得尤为重要。尤其对于Bing站长平台,自动化推送能让Bing尽快发现和索引我们网站的新内容。本文将详细介绍如何通过PHP脚本自动推送WordPress当天发布的文章至Bing站长平台,确保新文章被Bing及时收录。 前…...

C++题目分享

嗨嗨嗨,我又来更新这个系列了,很久没更新了。让我们看一看有那些有趣的题目: 题目一: 1.以单链表作为存储结构,实现线性表的就地逆置(提示,就地逆置:在不使用额外的数据结构或空间…...

【Spring 框架】初识 Spring

文章目录 前言1. 什么是 Spring2. 什么是 Maven3. 第一个 SpringBoot 项目4. 项目讲解结语 前言 在前面我们一起学习了 JavaSE 的基础知识,随着学习的深入,我们也将逐步介绍 JavaEE 的内容,像 Spring 框架,Mybatis 等等。在本篇博…...

链表(Linkedlist)

序言 我们都了解链表是一种数据的存储结构,在Java使用中逻辑与c,c语言数据结构别无二致,但主要由于Java中不存在指针的说法,从而导致在实现过程中的代码不同,所以在学习的过程中我们无需过于担心,逻辑都是…...

信息安全工程师(79)网络安全测评概况

一、定义与目的 网络安全测评是指参照一定的标准规范要求,通过一系列的技术、管理方法,获取评估对象的网络安全状况信息,并对其给出相应的网络安全情况综合判定。其对象主要为信息系统的组成要素或信息系统自身。网络安全测评的目的是为了提高…...

保研考研机试攻略:python笔记(3)

🐨🐨🐨11sort 与 sorted 区别 sort 是应用在 list 上的方法,sorted 可以对所有可迭代的对象进行排序操作。 list 的 sort 方法返回的是对已经存在的列表进行操作, 无返回值,而内建函数 sorted 方法返回的…...

刘卫国MATLAB程序设计与应用课后答案PDF第三版

刘卫国《MATLAB程序设计与应用》(第三版)是对普通高等教育“十一五”国家级规划教材《MATLAB程序设计与应用》(第二版)的一次全面修订。全书总体保持第二版原有体系结构,但根据技术发展和应用的需要扩充了许多新内容。全书强调数学方法、算法…...

【鉴权】Web 会话管理:Cookie、Session 和 Token 深度对比

目录 引言一、Cookie二、Session三、Token (JWT)四、总结对比五、Token、Session 和 Cookie 的选择总结 引言 在现代 Web 开发中,Cookie、Session 和 Token 都是用于用户身份验证和状态管理的常见技术。每种技术有其特定的应用场景和优缺点,理解它们之间…...

ArkTS--应用状态

应用状态 应用状态相关的内容需要使用模拟器或真机调试,在API 11开始也支持preview 1.LocalStorage LocalStorage是页面级的UI状态存储,通过Entry装饰器接收参数可以在页面内共享数据 1.1 页面内共享数据 import {MyUser} from ../model/MyUser //用户对…...

yolov8涨点系列之引入CBAM注意力机制

文章目录 YOLOv8 中添加注意力机制 CBAM 具有多方面的好处特征增强与选择通道注意力方面空间注意力方面 提高模型性能计算效率优化: yolov8增加CBAM具体步骤CBAM代码(1)在__init.pyconv.py文件的__all__内添加‘CBAM’(2)conv.py文件复制粘贴CBAM代码(3)修改task.py…...

java标准JavaBean类

1. public class test {//属性private String username;private String password;private String email;private String gender;private int age;//快捷键//altinsert//altFninsert//插件PTG1秒生成标准Javabean //插件ptg c//空参public test() {}//全部参数…...

MATLAB界面设计全攻略:从基础入门到高级应用

引言 MATLAB作为一种功能强大的科学计算软件,不仅可以进行各种复杂的数值计算,还可以通过其图形用户界面设计工具(GUI)为用户提供可视化操作界面。本教程旨在详细介绍MATLAB界面设计的全过程,为初学者提供从入门到精通…...

JavaScript API部分知识点

一、Dom获取&属性操作 (一)、 Web API 基本认知 1、变量声明 const 声明的值不能更改,而且const声明变量的时候需要里面进行初始化 但是对于引用数据类型,const声明的变量,里面存的不是 值,是 地址…...

钉钉调试微应用整理2

第一步 新建应用 钉钉开放平台](https://open-dev.dingtalk.com/) 去新增应用 第二步 配置应用信息 把本地代码运行起来&#xff0c;并设置本地地址 第三步 在本地代码添加调试命令 这里有2中添加方式 哪一种都可以 方式一&#xff1a; index.html页面中 <!DOCTYPE h…...

C++初级入门(1)

第一部分 基础语法入门 一、基础 1、变量与常量 1、变量 变量存在的意义:方便管理内存空间 2、常量 用于记录程序中不可更改的数据 #define 常量名 常量值 const 数据类型 常量名常量值 ; 2、数据类型 1、整型 short 2字节 int 4字节 long Wi…...

group_concat配置影响程序出bug

在 ThinkPHP 5 中&#xff0c;想要临时修改 MySQL 数据库的 group_concat_max_len 参数&#xff0c;可以使用 原生 SQL 执行 来修改该值。你可以通过 Db 类来执行 SQL 语句&#xff0c;从而修改会话&#xff08;Session&#xff09;级别的变量。 步骤 设置 group_concat_max_l…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...

python打卡第47天

昨天代码中注意力热图的部分顺移至今天 知识点回顾&#xff1a; 热力图 作业&#xff1a;对比不同卷积层热图可视化的结果 def visualize_attention_map(model, test_loader, device, class_names, num_samples3):"""可视化模型的注意力热力图&#xff0c;展示模…...

如何做好一份技术文档?从规划到实践的完整指南

如何做好一份技术文档&#xff1f;从规划到实践的完整指南 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...