首页 > 其他分享 >机器学习5_支持向量机_原问题和对偶问题——MOOC

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

时间:2024-11-10 13:14:49浏览次数:3  
标签: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)

标签:MOOC,定义,定理,问题,条件,向量,对偶
From: https://blog.csdn.net/Jay_NanX/article/details/143613798

相关文章

  • 向量数据库 PieCloudVector 进阶系列丨打造以 LLM 为基础的聊天机器人
    本系列前两篇文章深入探讨了PieCloudVector在图片和音频数据上的应用之后,本文将聚焦于文本数据,探索PieCloudVector对于文本数据的向量化处理、存储以及检索,并最终结合LLM打造聊天机器人的全流程。在自然语言处理任务中涉及到大量对文本数据的处理、分析和理解,而向量数据库......
  • 改进的蜣螂算法(IDBO)优化支持向量机原理及MATLAB代码复现
    目录0引言1数学模型2模型性能可视化3MATLAB代码3.1伪代码程序图3.2IDBO-SVR、IDBO-SVM0引言针对DBO全局探索能力不足、易陷入局部最优以及收敛精度不理想等问题,有学者提出了一种混合多策略改进的蜣螂优化算法(IDBO)。该算法采用混沌映射结合随机反向学习策略初始......
  • 逻辑回归处理非线性关系与支持向量机的性能对比
            逻辑回归是一种常用的线性分类方法,通常用于处理线性关系的二分类任务。但是,对于非线性问题,传统的逻辑回归模型可能表现不佳,因为它假设数据可以被一个线性决策边界分割开来。为了使逻辑回归能够处理非线性关系,我们可以采取一些方法,比如特征变换和多项式扩展,从而......
  • 向量检索服务-应用场景
    本文为您介绍向量检索服务在电商智能搜索和偏好推荐、自然语言处理等AI问答系统、图库类网站多模态搜索、视频检索、分子检测与筛选等场景下的应用。电商智能搜索和偏好推荐场景在电商智能搜索和偏好推荐场景中,向量数据库可以实现基于向量相似度的搜索和推荐功能。例如一个电商......
  • 机器学习3_支持向量机_线性不可分——MOOC
    线性不可分的情况如果训练样本是线性不可分的,那么上一节问题的是无解的,即不存在  和  满足上面所有N个限制条件。对于线性不可分的情况,需要适当放松限制条件,使得问题有解。放松限制条件的基本思路: 对每个训练样本及标签  设置松弛变量(slackvariable)对于线性不可......
  • 机器学习2_支持向量机_线性可分——MOOC
    定义线性可分(LinearSeparable)二维 三维特征空间维度  四维时,二维的情况下分割圆圈和叉的直线。线性不可分(NonlinearSeparable)不存在一条直线二维 三维特征空间维度  四维时,三维的情况下,分割圆圈和叉的平面将会变成超平面(Hyperplane)。由于人眼对空间的感......
  • 机器学习1_机器学习定义——MOOC
    一、机器学习定义定义一1959年ArthurSamuel提出机器学习的定义:MachineLearningisFieldsofstudythatgivescomputerstheabilitytolearnwithoutbeingexplicitlyprogrammed.译文:机器学习是这样的领域,它赋予计算机学习的能力,(这种学习能力)不是通过显著式的编......
  • 零基础学习Spring AI Java AI使用向量数据库postgresql 检索增强生成 RAG
    零基础学习SpringAIJavaAI使用向量数据库postgresql检索增强生成RAG向量数据库是一种特殊类型的数据库,在人工智能应用中发挥着至关重要的作用。在向量数据库中,查询与传统的关系数据库不同。它们不是进行精确匹配,而是执行相似性搜索。当给定一个向量作为查询时,向量数......
  • 如何定义ggplot2 的scale_fill_manual() 中参数 values 的命名向量?
    需求背景对R语言中,ggplot2的scale_fill_manual()函数的values参数理解不到位,它这里需要的是一个命名向量,无法在c()函数内部直接创建一个向量。举例说明,以不同分类数据的条形图来作为图例。比如我有14个不同物种,绘制其不同颜色的条形图,注意颜色不能随便定义,需要指定每个......
  • faiss用于大数据量的向量检索
    背景:10亿(Billion级别)的数据应该是一个很大的数据了,尤其是维度在768+级别(还有1024,1536等),这个数据量我做了一个实验,shape为(1kw,768)的array(numpy)占内存为30G(float32格式),如果能降低为float16更好不过,但似乎faiss没有这种方法或者精度有所损失。那么对于5亿级别的数据(vectors),占内存......