热门标签 | 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. 理解支持向量机三层境界


推荐阅读
  • 本文介绍如何使用OpenCV和线性支持向量机(SVM)模型来开发一个简单的人脸识别系统,特别关注在只有一个用户数据集时的处理方法。 ... [详细]
  • Ihavetwomethodsofgeneratingmdistinctrandomnumbersintherange[0..n-1]我有两种方法在范围[0.n-1]中生 ... [详细]
  • 在2019中国国际智能产业博览会上,百度董事长兼CEO李彦宏强调,人工智能应务实推进其在各行业的应用。随后,在“ABC SUMMIT 2019百度云智峰会”上,百度展示了通过“云+AI”推动AI工业化和产业智能化的最新成果。 ... [详细]
  • 本文提出了一种基于栈结构的高效四则运算表达式求值方法。该方法能够处理包含加、减、乘、除运算符以及十进制整数和小括号的算术表达式。通过定义和实现栈的基本操作,如入栈、出栈和判空等,算法能够准确地解析并计算输入的表达式,最终输出其计算结果。此方法不仅提高了计算效率,还增强了对复杂表达式的处理能力。 ... [详细]
  • 在机器学习领域,深入探讨了概率论与数理统计的基础知识,特别是这些理论在数据挖掘中的应用。文章重点分析了偏差(Bias)与方差(Variance)之间的平衡问题,强调了方差反映了不同训练模型之间的差异,例如在K折交叉验证中,不同模型之间的性能差异显著。此外,还讨论了如何通过优化模型选择和参数调整来有效控制这一平衡,以提高模型的泛化能力。 ... [详细]
  • 从2019年AI顶级会议最佳论文,探索深度学习的理论根基与前沿进展 ... [详细]
  • 本文深入探讨了算法进阶中的多个核心主题,包括最大似然估计在统计建模中的应用、赔率计算在风险评估中的重要性、FuzzyWuzzy库在字符串相似度匹配中的高效使用、主成分分析(PCA)在数据降维与特征提取中的关键作用,以及One-Hot编码在处理分类变量时的技术细节。通过这些内容,读者将获得对算法应用的全面理解。 ... [详细]
  •     目标检测是计算机视觉一个非常重要的子任务。目标检测需要发现并准确定位自然图片中的物体。在2012年之前,目标检测主要基于手工设计的特征以及传统分类器。2012年以后,出现了 ... [详细]
  • 深度学习: 目标函数
    Introduction目标函数是深度学习之心,是模型训练的发动机。目标函数(objectfunction)损失函数(lossfunction)代价函数(costfunction) ... [详细]
  • 分隔超平面:将数据集分割开来的直线叫做分隔超平面。超平面:如果数据集是N维的,那么就需要N-1维的某对象来对数据进行分割。该对象叫做超平面,也就是分类的决策边界。间隔:一个点 ... [详细]
  • 这是我在复习时整理的笔记,过一遍就稳了,建议还是把PPT过一遍,老师考的都是基础题,大部分都在PPT上,特别是 ... [详细]
  • 概述SVM(支持向量机)是一个二分类的模型,它的主要思想就是间隔最大化,那么问题来了,什么是间隔最大化&#x ... [详细]
  • 机器学习算法常见面试题目总结,Go语言社区,Golang程序员人脉社 ... [详细]
  •   作为一种编程语言,Python比C#,Java,C和C++更具吸引力。它被称为“胶水语言”,它也被喜欢它的程序员誉为“美丽”的编程语言。从云计算,客户端到物联网终端,Pytho ... [详细]
  • 圣诞节到了,智能菌想送你一份礼物
    关注网易智能,聚焦AI大事件,读懂下一个大时代!(机器学习算法地图见文末)圣诞节的赠书活动来了! ... [详细]
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社区 版权所有