算法优化之道:避开鞍点

来源:互联网
更新时间:2016/4/7 11:15:51
责任编辑:李志喜
字体:

凸函数比较简单——它们通常只有一个局部最小值。非凸函数则更加复杂。在这篇文章中,我们将讨论不同类型的临界点( critical points) ,当你在寻找凸路径( convex path )的时候可能会遇到。特别是,基于梯度下降的简单启发式学习方法,在很多情形下会致使你在多项式时间内陷入局部最小值( local minimum ) 。

临界点类型

点击图片看大图中国学网 www.xue163.com

为了最小化函数f:Rn→R,最流行的方法就是往负梯度方向前进?f(x)(为了简便起见,我们假定谈及的所有函数都是可微的),即:

y=x?η?f(x),

其中η表示步长。这就是梯度下降算法(gradient descentalgorithm)。

每当梯度?f(x)不等于零的时候,只要我们选择一个足够小的步长η,算法就可以保证目标函数向局部最优解前进。当梯度?f(x)等零向量时,该点称为临界点(critical point),此时梯度下降算法就会陷入局部最优解。对于(强)凸函数,它只有一个临界点(critical point),也是全局最小值点(global minimum)。

然而,对于非凸函数,仅仅考虑梯度等于零向量远远不够。来看一个简单的实例:

y=x12?x22.

当x=(0,0)时,梯度为零向量,很明显此点并不是局部最小值点,因为当x=(0,?)时函数值更小。在这种情况下,(0,0)点叫作该函数的鞍点(saddle point)。

为了区分这种情况,我们需要考虑二阶导数?2f(x)——一个n×n的矩阵(通常称作Hessian矩阵),第i,j项等于 点击图片看大图。当Hessian矩阵正定时(即对任意的u≠0,有u??2f(x)u > 0恒成立),对于任何方向向量u,通过二阶泰勒展开式点击图片看大图,可知x必定是一个局部最小值点。同样,当Hessian矩阵负定时,此点是一个局部最大值点;当Hessian矩阵同时具有正负特征值时,此点便是鞍点。

对于许多问题,包括 learning deep nets ,几乎所有的局部最优解都有与全局最优解(global optimum)非常相似的函数值,因此能够找到一个局部最小值就足够好了。然而,寻找一个局部最小值也属于NP-hard问题(参见 Anandkumar,GE 2006 中的讨论一节)。实践当中,许多流行的优化技术都是基于一阶导的优化算法:它们只观察梯度信息,并没有明确计算Hessian矩阵。这样的算法可能会陷入鞍点之中。

在文章的剩下部分,我们首先会介绍,收敛于鞍点的可能性是很大的,因为大多数自然目标函数都有指数级的鞍点。然后,我们会讨论如何对算法进行优化,让它能够尝试去避开鞍点。

对称与鞍点

许多学习问题都可以被抽象为寻找k个不同的分量(比如特征,中心…)。例如,在 聚类 问题中,有n个点,我们想要寻找k个簇,使得各个点到离它们最近的簇的距离之和最小。又如在一个两层的 神经网络 中,我们试图在中间层寻找一个含有k个不同神经元的网络。在我 先前的文章 中谈到过张量分解(tensor decomposition),其本质上也是寻找k个不同的秩为1的分量。

解决此类问题的一种流行方法是设计一个目标函数:设x1,x2,…,xK∈Rn表示所求的中心(centers),让目标函数f(x1,…,x)来衡量函数解的可行性。当向量x1,x2,…,xK是我们需要的k的分量时,此函数值会达到最小。

www.xue163.com true http://www.xue163.com/184/6/1843322.html report 3486 算法优化之道:避开鞍点,凸函数比较简单——它们通常只有一个局部最小值。非凸函数则更加复杂。在这篇文章中,我们将讨论不同类型的临界点(criticalpoints),当你在寻找凸路径(convexpath)的时候可能会遇到。特别是,基于梯度下降的简单启发式学习方法,在很多情形...
最近关注
首页推荐
热门图片
最新添加资讯
24小时热门资讯
算法优化之道 避开算法 之道鞍点是什么c语言求鞍点找出二维数组的鞍点鞍点问题c语言鞍点c语言二维数组鞍点找鞍点
精彩资讯
精彩推荐
热点推荐
真视界
精彩图片
社区精粹
关于本站 | 广告服务 | 手机版 | 商务合作 | 免责申明 | 招聘信息 | 联系我们
Copyright © 2004-2016 Xue163.com All Rights Reserved. 中国学网 版权所有
京ICP备10044368号-1 京公网安备11010802011102号
荐闻 | 学网头条知识问答 | 装修 | 作业 | 荐闻 | 学网头条精彩微信 | 新闻中心 | 软件教室 | 设计大全 | 网络相关 | 英语学习 | 开发编程 | 考试中心 | 参考范文 | 管理文库 | 营销中心 | 站长之家 | IT信息中心 | 商学院 | 数码大全 | 硬件DIY | 企业服务 | 网吧在线 | 问吧 | 百科 | 硬件知识 | 本网视点 | 文库 | 手机 | 平板 | 汽车 | 游戏 | 家电 | 精彩摄影 | 时尚科技 | 现代家居 | IT女人 | 经验 | 每日新闻 | 健康养生 | 图书馆 | 猎奇 | 精彩看点 | 图库 | 新闻中心 | 软件教室 | 设计大全 | 网络相关 | 英语学习 | 开发编程 | 考试中心 | 参考范文 | 管理文库 | 营销中心 | 站长之家 | IT信息中心 | 商学院 | 数码大全 | 硬件DIY | 企业服务 | 网吧在线 | 问吧 | 百科 | 硬件知识 | 本网视点 | 文库 | 手机 | 平板 | 汽车 | 游戏 | 家电 | 精彩摄影 | 时尚科技 | 现代家居 | IT女人 | 经验 | 每日新闻 | 健康养生 | 图书馆 | 精彩微信 | 猎奇 | 精彩看点 | 图库编程 方案 信息windows方案windows answer文档机构教育文档问答中心IT编程数码信息解决方案信息中心IT科技