标签归档:无约束最优化

凸优化及无约束最优化相关资料

很多年前,我的师兄 Jian Zhu 在这里发表过一个系列《无约束最优化》,当时我写下了一段话:

估计有些读者看到这个题目的时候会觉得很数学,和自然语言处理没什么关系,不过如果你听说过最大熵模型、条件随机场,并且知道它们在自然语言处理中被广泛应用,甚至你明白其核心的参数训练算法中有一种叫LBFGS,那么本文就是对这类用于解无约束优化算法的Quasi-Newton Method的初步介绍。

事实上,无论机器学习还是机器学习中的深度学习,数值优化算法都是核心之一,而在这方面,斯坦福大学Stephen Boyd教授等所著的《凸优化》堪称经典:Convex Optimization – Boyd and Vandenberghe ,而且该书的英文电子版在该书主页上可以直接免费下载:

http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

还附带了长达301页的Slides:

http://web.stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf

以及额外的练习题、相关代码数据文件:

http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook_extra_exercises.pdf
http://web.stanford.edu/~boyd/cvxbook/cvxbook_additional_exercises/

相当贴心,另外Stephen Boyd教授2014年还在斯坦福大学自家的MOOC平台上开过相关课程: CVX101

https://class.stanford.edu/courses/Engineering/CVX101

提示是:A MOOC on convex optimization, CVX101, was run from 1/21/14 to 3/14/14. If you register for it, you can access all the course materials.

不知道现在注册是否还可以访问课程材料,我当年竟然注册过这门课程,所以还能访问相关资料:

这本书也有中文翻译版,由清华大学出版社出版:

http://www.tup.tsinghua.edu.cn/bookscenter/book_03184902.html

最后提供上述相关材料的打包下载,包括凸优化课程视频、英文原版书籍、练习题和Slides,另外也包括《无约束最优化》的PDF文档,感兴趣的同学可以关注我们的公众号AINLP,回复"youhua"下载:

注:原创文章,转载请注明出处及保留链接“我爱自然语言处理”:http://www.52nlp.cn

本文链接地址:凸优化及无约束最优化相关资料 http://www.52nlp.cn/?p=11222

Start your future on Coursera today.

无约束最优化五

3.2 Quasi-Newton Method
  Quasi-Newton Method每一步计算过程中仅涉及到函数值和函数梯度值计算,这样有效避免了Newton Method中涉及到的Hessian矩阵计算问题。于Newton Method不同的是Quasi-Newton Method在每点处构建一个如下的近似模型: 继续阅读

Start your future on Coursera today.

无约束最优化四

3.Quasi-Newton Method
  在第2节中我们了解了步长的概念,以及从x_k走到x_k+1点使用line search方法计算步长的方法。不过我们在那里忽略了一个重要的概念,即“方向”。从第2节,我们了解到从每一点x_k走到下一点x_k+1时,需要给出要走的“方向”,只有“方向”确定好之后,才能在此基础上应用line search方法找到对应的“步长”,因此在解决了“步长”计算问题之后,这里我们将和大家一起了解一下每一步的“方向”如何确定。本节分为2大部分,首先我们通过newton method引入方向的概念,在此基础上引入quasi-newton method。然后引入quasi-newton method中的一种重要方法BFGS method,并在BFGS method的基础上介绍用于大规模计算的LBFGS method算法,同时以此结束本节的所有内容。 继续阅读

Start your future on Coursera today.

无约束最优化三

2.2 a_k步长的选择
  了解了a_k的合理性之后,就相当于获得了标尺,在此基础上我们可以选择合适的策略来求取a_k。所有的line search过程在计算每一步的a_k时,均需要提供一个初始点a_0,然后再此基础上生成一系列的{a_i},直到a_i满足2.1节所规定的条件为止,此时该a_k即被确定为a_i,或者未找到一个合适的a_k。这里我们仅介绍目前常用的策略平方插值和立方插值法。因此本节内容分为两部分,2.2.1节介绍选择a_k常用的平方插值和立方插值法,2.2.2节介绍由x_k点到x_k+1点,方向确定为p_k后,步长a_k具体计算过程。 继续阅读

Start your future on Coursera today.

无约束最优化二

2.1 a_k合理性讨论
  如下将要讨论关于a_k需要满足的两个条件,当a_k满足这两个条件后,就可以认为从x_k点移动到x_k+1点的步长已经确定下来了。第一个条件为sufficient decrease condition,从直观角度来看,该条件主要要用保证x_k+1点的函数值要小于x_k点的函数值,满足该条件后,才有全局收敛 的可能性。第二个条件为curvature condition,从直观角度来看,该条件主要用于保证x_k点经过步长a_k的移动到达x_k+1后,▽f_k+1小于▽f_k。 继续阅读

Start your future on Coursera today.

无约束最优化一

  估计有些读者看到这个题目的时候会觉得很数学,和自然语言处理没什么关系,不过如果你听说过最大熵模型、条件随机场,并且知道它们在自然语言处理中被广泛应用,甚至你明白其核心的参数训练算法中有一种叫LBFGS,那么本文就是对这类用于解无约束优化算法的Quasi-Newton Method的初步介绍。
  事实上,这个系列的作者是我的师兄jianzhu,他在中文分词、语言模型方面的研究很深入,如果大家对于srilm的源代码感兴趣,可以参考他个人博客上写的“srilm阅读文档系列”,很有帮助。我曾经向他约过稿,他说业余时间在学数学,比较忙,还以为他没有时间给52nlp写文章,没想到今天晚上他突然交给了我这篇文档,比较长,我会分几部分陆续放在博客上。这里非常感谢他对52nlp的支持,以下内容作者为jianzhu。 继续阅读

Start your future on Coursera today.