前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >怎么理解凸优化及其在SVM中的应用

怎么理解凸优化及其在SVM中的应用

原创
作者头像
汪毅雄
修改2019-10-14 22:41:10
1.4K0
修改2019-10-14 22:41:10
举报
文章被收录于专栏:汪毅雄的专栏

凸优化理论广泛用于机器学习中,也是数学规划领域很重要的一个分支,当然也是很复杂的。本文总结一下我获取的资料和个人在一些难点上的理解。

当我们要求一个函数 min f(x) 的时候,如果 f(x) 可导,我们通过是通过求 f(x) 的导数来得。

但是如果函数 f(x) 带约束条件,那么问题就开始变复杂了。凸优化的目标就是解决带约束条件函数的极值问题

凸优化解决的通用模型是:

很显然,所有的极值问题都可以转化成如上的模型。面对这个问题,凸优化理论怎么处理的呢?

1、满足条件

不是所有的极值问题都可以适用的凸优化理论的,它必须满足以下条件

1、目标函数 f(x) 为凸函数

2、不等式约束函数 g(x) 为凸函数

3、等式约束函数 h(x) 为仿射函数

只有同时满足以上3个条件,才属于凸优化的范畴。

1.1 凸函数是什么

可以这样理解:

1、定义域为凸集,凸集几何意义表示为:如果集合中任意2个元素连线上的点也在集合C中,则C为凸集,下图左图为凸集,右图为非凸集。

2、二阶可导,且二阶导数大于0

1.2仿射函数是什么

一句话就是最高阶数为1的函数,如:Ax+b;

可以这么理解条件3,等式约束条件 h(x)=0 可以这么写

也就是说 h(x) 和 -h(x) 都必须同时是凸函数,那么其二阶导数就必须为0,也就是说阶数不能超过1.

2、原始问题

对于凸优化的通用模型,由于其带有约束条件,很难处理,因此我们会考虑怎么用一个式子来表述那个通用模型呢?

其拉格朗日函数的max就在求min的时候就可以作为等价模型,这句话很拗口,这块也是一个难以琢磨的点,很多资料都是直接给出结果,我这边试着一步一步剖析。

我们写出模型的拉格朗日表达式

如果这么定义拉格朗日表达式,那么

就上述模型就等价于 f(x),为什么呢?

我么可以看到这个函数是以α,β的函数,其中α必须大于等于0. 那么 g(x)、f(x)、h(x)都可以看作常量。而我们的约束条件是:

A、设想一下不满足约束条件的话:

1)假设 g(x)>0 h(x)=0,那么拉格朗日函数可表示为

这是一个线性函数,因为 g(x)>0,所以函数的最大值点肯定是在α为+∞的时候,因此这种情况

的值为+∞。

2)假设 g(x)<=0 h(x)!=0,那么拉格朗日函数可表示为

同理,如果h(x)>0,则函数的最大值点肯定是在β为+∞的时候取到。如果h(x)<0,则函数的最大值点肯定是在β为-∞的时候取到。也就是无论如何,

的值依然为+∞。

也就是说,如果不满足约束条件,

的值永远为+∞

B、如果满足约束条件的话,那么拉格朗日函数可表示为

由于α>=0, g(x)<=0,所以

必然为0或负数,也就是说,这时候

值就为 f(x)。

而在求min f(x)的情况下,如果不满足约束条件

的值为+∞,只有满足才为f(x)。因此当且仅当,在求min f(x)的前提下:

所以min-max就是我们转化的原始问题!

3、对偶问题

3.1 为什么要转成对偶问题 - 个人理解?

1) 方便求解

2) 规划理论中,对于不知道有没有解的情况,可以通过对偶问题来缩小范围。

引用一个经典的由不是很恰当的例子说:

·要证明一个人有罪,那么举出他犯罪的例子即可。

·要证明一个人无罪呢?这是不可能的。往往很多原始问题就很类似。

所以可以通过它的对偶问题来说:

·如果无法找到他有罪的证据,那么他就是无罪的。

这样问题就变得有可行解了。

3.2 怎么理解对偶问题?

先写出拉格朗日表达式:

把原始问题转成其对偶问题,也就是先求max转成先求min:

为什么这种转化是可行的呢?因为两者始终存在这么一个关系

且在满足kkt条件的前提下,两者是相等的!

用图来说就是

3.2.1 为什么min-max >= max-min?

1、先简单理解一下这个,对于任意的存在最小值的 f(x), 总有任意的x*,都有:

其中等式成立的条件是

也就是在x*处的导数为0.

2、min是以x为参数的函数,假设它的最优解为x*,那么原始问题的结果为:

max是以α、β为参数的函数,假设它的最优解为α*、β*,那么对偶问题的结果为:

3、那么我们都有以下推断

由于由以下关系,所以第一个大于等于号成立

由step1中所讲述的,第二个大于等于号也成立

因此min-max >= max-min是成立的。

3.2.2 KKT条件

在本节最开始说了,我们需要的:

不是原问题 > 对偶问题,而是原问题 = 对偶问题。

因此在3.2.1推导的公式中,两个大于等于号必须取等号,这就能推导出我们的KKT条件。

在第一个大于等号中,强制其为等号,推导出的条件为:

·条件1(著名的互补松弛定理):

,也就是

在第二个大于等号中,强制其为等号,推导出的条件为:

·条件2

拉格朗日不等式约束条件:

·条件3

初始条件:

·条件4

·条件5

如果同时满足以上5个条件,那么原问题就可以等价于对偶问题

凸优化与SVM

1、满足条件

回到SVM的初始模型

可以看到,

是二次函数,典型的凸函数!

而约束条件最高阶只有一阶,确实是仿射函数。

也就是说,SVM可以套用凸优化理论。

2、建模

可以很简单的写出,其拉格朗日形式为:

其对偶问题是先求以w、b为参数的min,再求以α为参数的max,这部分具体推导已经在文章

机器学习之SVM原理 》中做了,有兴趣可以了解。

最终得到的结果是:

3、KKT条件

如果两个问题等价,那么其KKT条件,我们也套用模型中内容,可以推导出:

那么有:

1、初始条件:

2、拉格朗日条件:

3、互补松弛条件:

4、参数导数为0条件:

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档