从凸优化到SVM

栏目: 数据库 · 发布时间: 6年前

内容简介:开个新坑,总结下最近看的凸优化的东西,主要来自于CS229的讲义。前半部分介绍凸优化的问题定义,后半部分介绍对偶问题和KKT条件,并使用SVM作为例子,展示凸优化在机器学习中的应用。这部分也是SVM理论部分不太好理解的部分,希望我能把它梳理清楚明白。介绍凸函数之前,首先介绍凸集。函数必须定义在凸集上,才能有后续是否是凸函数的讨论。

开个新坑,总结下最近看的凸优化的东西,主要来自于CS229的讲义。前半部分介绍凸优化的问题定义,后半部分介绍对偶问题和KKT条件,并使用SVM作为例子,展示凸优化在机器学习中的应用。这部分也是SVM理论部分不太好理解的部分,希望我能把它梳理清楚明白。

从凸优化到SVM

凸函数

介绍凸函数之前,首先介绍凸集。函数必须定义在凸集上,才能有后续是否是凸函数的讨论。

凸集

若集合$C$中任取两个元素$x$和$y$,对于任意$\theta \in [0,1]$且$\theta \in \mathbb{R}$,都有下面的不等式成立,则集合$C$是凸集:

这句话翻译成不严谨的几何描述,就是在集合$C$中任取两点画一条线段,那么线段上的所有点都必须在$C$内,如下图所示。为何是这样呢?设$t = \theta x + (1-\theta) y$,稍作变形,可以得到,$t - y = \theta(x-y)$。这说明,$t-y$和$x-y$两个向量共线,也就是这三点共线。由$\theta$的取值范围,进一步知道,$t$在两点之间。这样,我们就把上面抽象的式子和下面直观的图建立了联系。

从凸优化到SVM

下面不加证明给出几个特殊的凸集:

  • $\mathbb{R}^n$
  • $\{ x; \Vert x\Vert_p \le 1\}$,可以用范数的三角不等式证明
  • 凸集的交集

凸函数

与凸集的定义相类似,如果一个函数$f$定义在凸集上,而且对于其定义域上的任意两个变量取值$x$和$y$,对于任意$\theta \in [0,1]$且$\theta \in \mathbb{R}$,都有下式成立,则函数$f$是凸函数:


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

未来是湿的

未来是湿的

[美] 克莱·舍基 / 胡泳、沈满琳 / 中国人民大学出版社 / 2009-5 / 39.80

一位妇女丢掉了手机,但征召了一群志愿者将其从盗窃者手中夺回。一个旅客在乘坐飞机时领受恶劣服务,她通过自己的博客发动了一场全民运动。在伦敦地铁爆炸案和印度洋海啸中,公民们用可拍照手机提供了比摄影记者更完备的记录。世界上最大的百科全书是由管理甚少的参与者们撰写的…… 不论在何处,你都能看见人们走到一起彼此分享,共同工作,或是发起某种公共行动。一部集众人之力的百科全书、一个丢失手机的传奇,这些事情......一起来看看 《未来是湿的》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具