机器学习导论(1)–凸优化

4,000次阅读
一条评论

引言

前段时间给师弟师妹们做关于就业的指导,在交流的过程中也提到了关于算法相关的一些资料,七月-结构算法之前关注的博客中算法这块写的比较好的博客之一,比较推荐。最近七月搭建了视频网站七月-视频网站,视频资料都还不错,推荐去看看~

博主也是看了这些视频对于有些问题有些深入的了解,所以和大家分享一些自己的理解~

在讲述凸优化之前需要理解一些基本的概念

凸集

定义:在集合C内任意两点的连线都在集合C内,则称集合C为凸集。使用数学公式的定义的话则为对于C中任意给定的

机器学习导论(1)--凸优化

下图中给出凸集的示意图

机器学习导论(1)--凸优化

在日常的数学学习中发现用于凸集属性的数据集合还是很多,比如超平面、半空间、多面锥(ps:可能不同的人说法不一样,有点陈伟多面体空间,本质上是由多个超平面组合而成的多面空间)。

仿射变换

公式定义如下:

机器学习导论(1)--凸优化

仿射变换完成数据的平移、伸缩和投影。

若函数F是放射变换则下列公式:

机器学习导论(1)--凸优化

  • n若S为凸集,则f(S)为凸集;
  • n若f(S)为凸集,则S为凸集。

凸集分离定理

假设C和D为两不相交的凸集,则存在超平面P,P可以将C和D分离。

机器学习导论(1)--凸优化

注意上式中可以取等号:

  • 所以:逆命题:“若两个凸集C和D的分割超平面存在,C和D不相交”为假命题。
  • 加强条件:若两个凸集至少有一个是开集,那么当且仅当存在分割超平面,它们不相交

 

机器学习导论(1)--凸优化

超平面示意图

为什么要介绍仿射变换、凸集分离定理,因为在后面的相关机器学习算法、一般问题凸优化处理中会使用到,因此在这里提前做个说明。下面正式开始介绍凸优化的相关知识了~Come on 小伙伴

凸函数

假设函数f的定义域D(f)为凸集,且满足

机器学习导论(1)--凸优化

 

机器学习导论(1)--凸优化

凸函数示意图

凸函数的充要条件

一阶微分充要条件

若f一阶可微,则函数f为凸函数当前仅当f的定义域D(f)为凸集,且

机器学习导论(1)--凸优化

 

机器学习导论(1)--凸优化

一阶微分充要条件

对于上面的一阶微分补充以下几点:

  • 结合凸函数图像和支撑超平面理解该问题
  • 对于凸函数,其一阶Taylor近似本质上是该函数的全局下估计。
  • 反之,如果一个函数的一阶Taylor近似总是起全局下估计,则该函数是凸函数。
  • 该不等式说明从一个函数的局部信息,可以得到一定程度的全局信息。

二阶可微充要条件

假设函数f二阶可微,则函数f为凸函数当前仅当D(f)为凸集,且

机器学习导论(1)--凸优化

注意:

  • 若f是一元函数,上式表示二阶导大于等于0
  • 若f是多元函数,上式表示二阶导Hessian矩阵半正定。

下面给出f是多元函数下的证明过程

必要性:

 

机器学习导论(1)--凸优化

如果Hesse矩阵是正定的则f(x)为严格的凸函数~(博主不像手动输入Latex代码了,手都酸了~下面贴图了,但是会说明秦楚)

凸优化

凸优化问题的基本形式如下所示:

机器学习导论(1)--凸优化

优化问题的基本形式:

机器学习导论(1)--凸优化

凸优化问题的基本形式:

机器学习导论(1)--凸优化

局部-全局最优解证明

可是为什么凸优化问题的局部最优解是全局最优解,下面给出证明:

机器学习导论(1)--凸优化

对偶问题

机器学习导论(1)--凸优化

机器学习导论(1)--凸优化

机器学习导论(1)--凸优化

强对偶条件

机器学习导论(1)--凸优化

 

KKT条件

机器学习导论(1)--凸优化

结语

终于搞完了,本文讲解了从凸集到凸优化的问题,详细描述的凸优化的关键问题比如:凸函数的充要条件、局部最优是全局最优等。最后给出凸优化一般问题转化为拉格朗日方程,结合对偶函数做出相关计算,同时给出强对偶天剑和KKT条件(SVM中会使用到~)

admin
版权声明:本站原创文章,由admin2015-05-30发表,共计1384字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(一条评论)
boostcj@126.com 博主
2015-05-30 18:37:22 回复

:wink: