热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

模式识别笔记3-支持向量机SVM

1.线性SVM对两类点的划分问题,这里对比下逻辑回归和SVM的区别:逻辑回归的思想是,将所有点到决策平面的距离作为损失来进行训练,目标是到决策平面的距离和最小SVM的思想是,只

1. 线性SVM


对两类点的划分问题,这里对比下逻辑回归和SVM的区别:

  • 逻辑回归的思想是,将所有点到决策平面的距离作为损失来进行训练,目标是到决策平面的距离和最小
  • SVM的思想是,只关注支持向量(图中圈出的点)到决策平面的距离,最大化这个距离。

对于所有样本点 \(\{(x_i,y_i)\}, i = 1,2,\cdots, m\) ,SVM划分正负样本,即 \(y\in\{1,-1\}\) ,则有:
\[ \begin{align} \begin{cases} y_i = +1, w^Tx_i +b >0\\ y_i = -1, w^Tx_i +b<0 \end{cases} \end{align} \]
这里对式子(1)进行一个放缩变换。超平面由参数对 \((w,b)\) 决定,若超平面 \((w',b')\) 能将样本正确分类,那么总存在一个放缩变换 \(\zeta w \mapsto w'\)\(\zeta b \mapsto b'\) 使得下列式子成立:
\[ \begin{align} \begin{cases} y_i = +1, w^Tx_i +b \geq1\\ y_i = -1, w^Tx_i +b\leq1 \end{cases} \end{align} \]
其中,正负样本中各有几个样例使得(2)的等号成立,这些样例被称为 支持向量
SVM的优化目标即是最大化间隔,而两个异类的支持向量到决策平面的距离是:
\[ \begin{align} \gamma = \frac{2}{||w||} \end{align} \]
同时,该优化目标函数具有约束,即式子(2),整理后写在一起:
\[ \notag \begin{array}{l} \max \limits_{w,b}\frac{2}{||w||}\\ s.t. y_i(w^Tx_i +b)\geq1, i=1,2,\cdots,n \end{array} \]
这等价于最小化 \(w\) 的范数:
\[ \begin{align} \begin{array}{l} \min \limits_{w,b}\frac{1}{2}||w||^2\\ s.t. y_i(w^Tx_i +b)\geq1, i=1,2,\cdots,m \end{array} \end{align} \]
式(4)就是SVM的基本型。

2. 对偶问题

式子(4)是一个不等式优化问题,有 \(m\) 个约束条件和 1 个 优化目标,对于这类问题,可以用拉格朗日乘数法来解决。
引入乘数因子 $\alpha $ :
\[ \begin{align} L(w,b,\alpha) = \frac{1}{2}||w||^2+\sum_i^m\alpha_i (1-y_i(w^Tx_i +b)) \end{align} \]
我们令:
\[ \begin{align} \theta(w)=\max \limits_{\alpha_i\geq0}L(w,b,\alpha) \end{align} \]
结合(5)(6)来说,如果 \(y_i(w^Tx_i+b)\geq1\)\(\alpha_i\geq0\) 有任何一个不满足,则 \(\theta(w)=+\infty\) ,所以当约束条件满足时,则有 \(\theta(w)=\frac{1}{2}||w||^2\), 即我们要最小化的目标。因此我们最初的目标函数变成了:
\[ \begin{align} \min \limits_{w,b}\frac{1}{2}||w||^2=\min \limits_{w,b}\theta(w)=\min \limits_{w,b}\max \limits_{\alpha_i\geq0}L(w,b,\alpha)=p^* \end{align} \]
这就是由拉格朗日乘数法引出的原问题。我们假定它的最优值时 \(p^*\)
现在我们把$\min $ 和 \(\max\) 倒置一下,得到它的 对偶问题
\[ \begin{align} \max \limits_{\alpha_i\geq0} \min \limits_{w,b}L(w,b,\alpha)=d^* \end{align} \]
同样我们假定它的最优值时 \(d^*\)。对比一下原问题和对偶问题:

  • 原问题:一个函数最大值中最小的一个值 \(p^*\)
  • 对偶问题: 一个函数最小值中最大的一个 \(d^*\)

显然有 \(d^*\leq p^*\)。即原问题的对偶问题确定了原问题的下界。当然,在满足Slater条件和KKT条件的情况下 \(d^*=q^*\),我们称之强对偶性。看一下Slater条件的定义:

Slater条件:如果主问题是凸优化问题,即不等式约束为凸函数,等式约束为仿射函数(线性变换),且可行域中至少有一点使得不等式约束严格成立,则强对偶性成立。

Slater条件保证鞍点的存在。而KKT条件保证函数可微。这样鞍点就可通过拉格朗日函数求导得到。
再讲KKT条件前,看一下对偶问题的求解:
对于内层最小化,求 \(L\) 关于 \(w, b\) 的偏导为0,解得的结果如下:
\[ \begin{align} w &= \sum \alpha_i y_i x_i\\ 0 &=\sum \alpha_i y_i \end{align} \]
带回式子(5),消去 \(w,b\),得到最终的优化函数为:
\[ \begin{align} \notag \max \limits_{\alpha}\sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}a_ia_jy_iy_jx_i^Tx_j\\ s.t. 0 =\sum \alpha_i y_i ,\\ \notag \alpha \geq 0 \end{align} \]

3. KKT条件

KKT是在满足一些有规则的条件下,一个非线性规则问题能有最优解的一个充分必要条件。也就是说,只要约束条件按照这个KKT给出的规则列出,然后符合KKT条件的,就可以有最优解。这是一个广义化拉格朗日乘数的成果。
对于不等式约束,需要满足KKT条件,这里讲一下KKT条件是怎么来的。

上图展示了一个2不等式约束优化问题,简单起见,这里在2维空间内讨论。

  • 右下角方是优化目标函数\(f(x)\)的等高线。
  • 左上方灰色部分是两个约束 \(g_1(x), g_2(x)\) 组成可行解区域。

假定在约束条件下,最优解为 \(x^*\) 。显然该点是2个约束条件以及某条等高线相交点。在该点处有3个梯度,分别用三个箭头表示:

  • 红色箭头代表等高线梯度,它的方向代表优化目标函数值增大的方向,即 \(\nabla f(x^*)\)
  • 绿色箭头代表约束在边缘处的负梯度,代表约束曲线值缩小的方向。

红色箭头必然加载俩绿色箭头中间(如果红色箭头不满足这个条件,那么必然存在更小的等高线穿过可行解区域),即 \(\nabla f(x^*)\) 必然可以由 \(-\nabla g_1(x^*)\)\(-\nabla g_x(x^*)\) 线性表示,且系数一定为正。
于是引出了第一二个KKT条件:
\[ \begin{align} \nabla f(x^*)+\mu_1\nabla g_1(x^*)+\mu_2\nabla g_2(x^*)=0\\ \mu_1\geq0,\mu_2\geq0 \end{align} \]
然而,不一定所有的约束条件都对最优解起作用,比如下图的三约束优化问题:

显然 \(g_3(x)\) 对最优解不起作用。此时,最优解在 \(g_1(x)\)\(g_2(x)\) 上,而不在 \(g_3(x)\) 上。此时,对于前两个KKT条件,有:
\[ \begin{align} \mu_1\geq0,\mu_2\geq0,\mu_3\geq0\\ \nabla f(x^*)+\mu_1 \nabla g_1(x^*)+\mu_2\nabla g_2(x^*)+\mu_3\nabla g_3(x^*)=0 \end{align} \]
对于(13)来说,我们不想让 \(g_3(x)\) 起作用,可以加入一个条件,使得 \(\mu_3=0\) 即可。于是引入第三个KKT条件:
\[ \begin{align} \mu_1g_1(x^*)+\mu_2g_2(x^*)+\mu_3g_3(x^*)=0 \end{align} \]
由于 \(g_1(x^*)=g_2(x^*)=0\), 那么自然的 \(\mu_3=0\),其实条件(16)等价于\(\mu_kg_k(x^*)=0\)
推广到多维等式\(h_j(x)\)和不等式约束\(g_k(x)\)
\[ \begin{align} \nabla f(x^*)+\sum_{j=1}^{m}\lambda_j\nabla h_j(x^*)+\sum_{k=1}^{m}\,u_k\nabla g_k(x^*)=0\\ h_j(x^*)=0, g_k(x^*)\leq0\\ \lambda_j\neq0, \mu_k\geq0, \mu_kg_k(x^*)=0 \end{align} \]
式子(17)(18)(19)合称KKT条件。
回顾我们的SVM优化问题, 注意,在SVM基本型中,参数空间是由\((w,b)\)构成的,而\((x,y)\)对都是已知的
添加上SVM基本型,即公式(4)的条件:
\[ \begin{align} \max \limits_{\alpha}\sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}a_ia_jy_iy_jx_i^Tx_j\\ s.t. 0 =\sum \alpha_i y_i ,\\ \alpha \geq 0\\ y_if(x_i)-1\geq0 \end{align} \]
式子(18)是由 \(L(w,b,\alpha)\)\(w,b\)偏导为0求出,即满足了KKT条件(2),最终整理得,优化目标为:
\[ \begin{align} \max \limits_{\alpha}\sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}a_ia_jy_iy_jx_i^Tx_j\\ s.t. \sum \alpha_i y_i=0 ,\\ \alpha \geq 0\\ \end{align} \]
然后KKT要求这一过程满足:
\[ \begin{align} \begin{cases} \alpha_i\geq0\\ y_if(x_i)-1\geq0\\ \alpha_i(y_if(x_i)-1)=0 \end{cases} \end{align} \]
注意公式(27)的第三个式子 ,对于任意的训练样本\((x_i,y_i)\) 总满足\(\alpha_i=0\)\(y_if(x_i)=1\), 若 \(\alpha_i=0\), 那么它就不会在优化目标(24)中出现,若\(y_if(x_i)=1\),那么它就是一个支持向量。这就引出了SVM的重要性质:训练完成后,大部分训练样本都不需要保留,最终模型只跟支持向量有关。

4. 解的形式

使用二次规划或者SMO算法解出 \(\alpha\) 后,SVM的解的由以下形式给出
\[ \begin{align} w = \sum \alpha_i y_i x_i \end{align} \]
而注意到 对于任意的支持向量\((x_s, y_s)\),都有 \(y_sf(x_s)=1\),即:
\[ y_s\left( \sum_{i\in S}\alpha_iy_ix_i^Tx_s+b\right)=1 \]
其中 \(S\) 是所有支持向量的下标集合。理论上可以选择任意的支持向量通过求解(29)得到,但现实任务一般采用更鲁棒的形式,即使用所有支持向量求均值:
\[ \begin{align} b=\frac{1}{|S|}\sum_{s\in S}\left(y_s-\sum_{i\in S}\alpha_iy_ix_i^Tx_s\right) \end{align} \]

5. 参考资料

1. 如何通俗地讲解对偶问题?尤其是拉格朗日对偶lagrangian duality? - 彭一洋的回答 - 知
2. 理解支持向量机三层境界


推荐阅读
  • 机器学习算法:SVM(支持向量机)
    SVM算法(SupportVectorMachine,支持向量机)的核心思想有2点:1、如果数据线性可分,那么基于最大间隔的方式来确定超平面,以确保全局最优, ... [详细]
  • H5技术实现经典游戏《贪吃蛇》
    本文将分享一个使用HTML5技术实现的经典小游戏——《贪吃蛇》。通过H5技术,我们将探讨如何构建这款游戏的两种主要玩法:积分闯关和无尽模式。 ... [详细]
  • Go从入门到精通系列视频之go编程语言密码学哈希算法(二) ... [详细]
  • 计算机学报精选论文概览(2020-2022)
    本文汇总了2020年至2022年间《计算机学报》上发表的若干重要论文,旨在为即将投稿的研究者提供参考。 ... [详细]
  • 从键盘输入年、月、日,要求输出当前日期为当年的第多少天。今天凯凯君又去参加了笔试,碰到了这样一个题目,从键盘输入年、月、日,要求输出当前日期为当年的第多少天。面对这个题目你首先想到 ... [详细]
  • 本文介绍如何使用OpenCV和线性支持向量机(SVM)模型来开发一个简单的人脸识别系统,特别关注在只有一个用户数据集时的处理方法。 ... [详细]
  • 在2019中国国际智能产业博览会上,百度董事长兼CEO李彦宏强调,人工智能应务实推进其在各行业的应用。随后,在“ABC SUMMIT 2019百度云智峰会”上,百度展示了通过“云+AI”推动AI工业化和产业智能化的最新成果。 ... [详细]
  • 在机器学习领域,深入探讨了概率论与数理统计的基础知识,特别是这些理论在数据挖掘中的应用。文章重点分析了偏差(Bias)与方差(Variance)之间的平衡问题,强调了方差反映了不同训练模型之间的差异,例如在K折交叉验证中,不同模型之间的性能差异显著。此外,还讨论了如何通过优化模型选择和参数调整来有效控制这一平衡,以提高模型的泛化能力。 ... [详细]
  • 分隔超平面:将数据集分割开来的直线叫做分隔超平面。超平面:如果数据集是N维的,那么就需要N-1维的某对象来对数据进行分割。该对象叫做超平面,也就是分类的决策边界。间隔:一个点 ... [详细]
  • 概述SVM(支持向量机)是一个二分类的模型,它的主要思想就是间隔最大化,那么问题来了,什么是间隔最大化&#x ... [详细]
  • 机器学习算法常见面试题目总结,Go语言社区,Golang程序员人脉社 ... [详细]
  •   作为一种编程语言,Python比C#,Java,C和C++更具吸引力。它被称为“胶水语言”,它也被喜欢它的程序员誉为“美丽”的编程语言。从云计算,客户端到物联网终端,Pytho ... [详细]
  • 圣诞节到了,智能菌想送你一份礼物
    关注网易智能,聚焦AI大事件,读懂下一个大时代!(机器学习算法地图见文末)圣诞节的赠书活动来了! ... [详细]
  • sklearn数据集库中的常用数据集类型介绍
    本文介绍了sklearn数据集库中常用的数据集类型,包括玩具数据集和样本生成器。其中详细介绍了波士顿房价数据集,包含了波士顿506处房屋的13种不同特征以及房屋价格,适用于回归任务。 ... [详细]
  • 浏览器中的异常检测算法及其在深度学习中的应用
    本文介绍了在浏览器中进行异常检测的算法,包括统计学方法和机器学习方法,并探讨了异常检测在深度学习中的应用。异常检测在金融领域的信用卡欺诈、企业安全领域的非法入侵、IT运维中的设备维护时间点预测等方面具有广泛的应用。通过使用TensorFlow.js进行异常检测,可以实现对单变量和多变量异常的检测。统计学方法通过估计数据的分布概率来计算数据点的异常概率,而机器学习方法则通过训练数据来建立异常检测模型。 ... [详细]
author-avatar
mobiledu2502917953
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有