• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

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

ml admin 5年前 (2015-05-30) 3085次浏览 1个评论 扫描二维码

引言

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

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

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

凸集

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

下图中给出凸集的示意图

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

仿射变换

公式定义如下:

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

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

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

凸集分离定理

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

注意上式中可以取等号:

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

 

超平面示意图

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

凸函数

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

 

凸函数示意图

凸函数的充要条件

一阶微分充要条件

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

 

一阶微分充要条件

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

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

二阶可微充要条件

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

注意:

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

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

必要性:

 

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

凸优化

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

优化问题的基本形式:

凸优化问题的基本形式:

局部-全局最优解证明

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

对偶问题

强对偶条件

 

KKT 条件

结语

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


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明机器学习导论(1)–凸优化
喜欢 (3)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!

(1)个小伙伴在吐槽