&昨天一个朋友问我最近是不是又在敲C++、Java啊？写篇blog正名
& & &--题记
接触稀疏理论的著作快一个月了还是没写一篇博客，主要是觉得自己的想法还不是很成熟、理解不够，等过些日子写点稀疏方面的。看稀疏理论的时候还在看数字图像处理、小波导论、凸优化和傅里叶分析，其实小波和傅里叶有点相同，可算作一本，周末应该会写一篇小波的博客，今天先写一篇关于凸优化的博客，主要是分享一些我最近看的资料。
凸优化问题是数学优化问题的一个特殊分支，其包括最小二乘法、线性规划等理论完备的问题。尽管人们对凸优化问题的讨论已经有几个世纪的历史，但是近来一些新的科学发展仍在推动发展凸优化理论。
第一个发展是对内点法的认知：这种方法最早是1980年用来解决线性规划问题的，现在也可以用来解决凸优化问题，包括半定规划、二阶锥规划等问题。
第二个发展是发现凸优化在实际中的应用范围比我们以前想象的广泛得多，比如自动控制之理论、信号的估计和处理、通信网络、电子电路设计、数据分析与建模、统计、金融等方面。同时在组合优化和全局优化问题方面也有很广的应用。
将问题转化或表示为一个凸优化问题会带来很多优势。
优势1：是该问题可以通过使用内点法或者其他凸优化解法reliably
and efficiently解决。而且这些解决方案可以可靠地内嵌到计算机辅助系统或者分析工具、甚至可以用于实时自动控制系统。
优势2：将问题转化为凸优化问题拥有理论优势，例如关于对偶问题我们会有全新的解释并且得到有效地解决。
对于学习计算数学的人，凸优化问题是一个很重要的理论。在我看来，凸优化是紧接高级线性代数（如最小二乘、奇异值）和线性规划后最重要的值得我们关注的地方。
我用的材料主要是斯坦福的Convex Optimization课程，相对来说会偏基础，适合初学者，：
主要分享三个文件：
1、Convex Optimization：斯坦福课程教材，其实是他们教学多年的讲义合编。主页是：，教材、上课视频都可以在这儿找到，看了两节了，口音略重。
2、Additional Exercises for Convex
Optimization：不解释，一些小练习，不是很难。
3、cvx-w64.zip：斯坦福大学Grant和Boyd教授等开发的凸优化matlab工具箱。
斯坦福的那本教材刚刚看完两章，感觉很基础，不过急着blog，刚刚装了下cvx-w64。我用的是windows 64 + Matlab
解压缩下载的cvx-w64.zip，我放在了D盘，打开matlab在命令窗口输入：
&& cd D:\cvx
&& cvx_setup
---------------------------------------------------------------------------
CVX: Software for Disciplined Convex
Programming&&&&&&
(c)2014 CVX Research
Version 2.1, Build 1085
(9a166a6)&&&&&&&&&&&&&&&&&&
Tue Jun 3 13:52:20 2014
---------------------------------------------------------------------------
Installation info:
&&& MATLAB
version: 8.3 (R2014a)
&&& OS: Windows
8 amd64 version 6.2
version: 1.7.0_11
Verfying CVX directory contents:
&&& No missing
Preferences:
C:\Users\Frank\AppData\Roaming\MathWorks\MATLAB\cvx_prefs.mat
License host:
&&& Username:
&&& Host ID:
14feb59c59f4 (eth4)
Installed license:
No valid licenses found.
这里会命令窗口提示No license
installed，需要你提前到他们的官方网站上申请licenses，如果申请了的话继续命令窗口输入：
&& cvx_setup ~/licenses/cvx_license.mat
到这里工具箱的安装就算是完成了。
运行一个关于最小二乘的例子：
% Input data
m = 16; n = 8;
A = randn(m,n);
b = randn(m,1);
% Matlab version
x_ls = A \
% cvx version
&&& variable
&&& minimize(
norm(A*x-b) )
norm(A*x_ls-b): 2.0354
norm(A*x-b):&&&
cvx_optval:&&&&
cvx_status:&&&&
Verify that x_ls == x:
&& x_ls& = [
-0.2628& 0.4 -1.0844&
0.0& 0.0603& 0.3802
= [ -0.2628& 0.4
-1.0844& 0.0&
0.0603& 0.3802 ]
Residual vector:
&& A*x-b = [ -0.0
-0.9543& 0.8 -0.3426
-0.1870& 0.2960& 0.6024
-0.0440& 0.9&
0.0849& 0.9323& 0.2
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。学运筹学之前，在知乎查过运筹学入门方面的问题，没有得到想要的答案。现在过运筹学了，自己提问，自己回答。&br&&br&涉及到专业入门书籍、资料的推荐，因为萝卜青菜各有所爱，难以保证所推荐的适合大多人。仅供参考。&br&&br&说到运筹学入门书籍，似乎离不开 Frederick
S. Hillier 和 Gerald J. Lieberman 的《&b&Introduction to Operations Research&/b&》（&a href=&///?target=http%3A///subject/2250362/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Introduction to Operations Research (豆瓣)&i class=&icon-external&&&/i&&/a&），在国内由清华大学的胡运权翻译成《&b&运筹学导论&/b&》(&a href=&///?target=http%3A///subject/2253276/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&运筹学导论 (豆瓣)&i class=&icon-external&&&/i&&/a&)，但是只是截取了部分章节，重点选取了线性规划的章节。这本书英文版网上有电子书，百度或者谷歌一下 “Introduction to Operations Research pdf ”就没问题的。&br&&br&我谷歌百度了一下运筹学入门书籍，无论是英文搜索还是中文搜索，大多都提到《运筹学导论》这本书，因此最开始是使用的这本书作为入门。另外，自己偏爱 Coursera，因此选了 Coursera 上科罗拉多大学波德分校开设的《&b&线性和整数规划&/b&》（&a href=&///?target=https%3A//www.coursera.org/course/linearprogramming& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Coursera.org&i class=&icon-external&&&/i&&/a&）作为主要教学视频。&br&&br&&u&一般而言，对于专业课，教材加教学视频，外加不懂时谷歌搜索，就可以很好地自学了。&/u&&br&&br&非常可惜的是，这本书和这个视频都不适合用于入门，对于我。《运筹学导论》在学生还没入门的时候讲了太多运筹学的复杂运用，对于最基本的单纯形法讲解跳跃性太大，行文还不加介绍直接使用“超平面”、“凸集”等等概念，反复看都难以理解。此书基本内容都难以理解，作者却还同时介绍 MPL、LINGO、LINDO 编程，Excel解决线性规划问题，如果能力没有达到这样水平，只会越学越没有兴趣。顺带提一句，如果中英文对照着看的人，会发现这本书翻译瑕疵太多，部分地方直接影响阅读（比如第九版第165页将“Corner-Point Infeasible Solution” 翻译成“角点可行解”）。&br&&br&另外要补充说明，我在读《运筹学导论》非单纯形法介绍部分，即运输问题、指派问题、整数规划、动态规划、决策分析的时候，觉得读的很顺，而且有实际运用的介绍，感觉学习非单纯形法部分用这本书作为第一教材，确实合适。&br&&br&再说说 Coursera 上的《线性和整数规划》，此教学视频最大的优势在于有视频教学和课后习题搭配，加之介绍了 Excel 和 Python 解决线性规划问题，另外有 Python 代码，有兴趣的可以学习一下。不过课程由两人讲授，其中一人讲得是印度口音英语，他还是主讲，实在让人难受。&br&&br&&b&&u&下面进入正题，运筹学如何入门？&/u&&/b&&br&&br&我最推荐的入门视频：&a href=&///?target=http%3A///user/DrSalimian/videos%3Fsort%3Ddd%26view%3D46%26tag_id%3DUC8L2asKJn-kNwBHVllQCs5A.3.operations-research%26shelf_id%3D3& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&DrSalimian&i class=&icon-external&&&/i&&/a& 的线性规划系列视频（资源地址：&a href=&///?target=http%3A///courses/IEGR440/MOOCOR.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&MOOCOR - Masud Salimian's Operations Research Course&i class=&icon-external&&&/i&&/a&），讲得非常基础，而且十分清晰，基本上是 Step By Step的讲解，为我扫清了好多好多的疑惑。跟着他把线性规划的各个子内容（Simplex, Big-M Technique, Two-Phase Technique, Matrix Form Simplex, Revised Simplex, Duality）学好了，一步步跟下来是很简单顺畅，基本上Simplex就掌握了。&br&&br&在学习 Simplex 的时候，DrSalimian的教程是主线，利用《运筹学导论》还有谷歌搜索作为补充。比如听 Big-M 不太了解，就搜索 Big-M Method，然后看看其他大学放在网上的 pdf，这样效果甚好。&br&&br&学习完 Simplex 之后，《运筹学导论》就开始发挥作用了，这本书从第10章动态规划开始，是可以作为第一教材。然后有不太理解的地方，用网上资料，以及 Youtube 上的视频来补充。&br&&br&---------------其他一些资源--------------&br&《&a href=&///?target=http%3A//carlossicoli.free.fr/D/Dantzig_G.%2C_Thapa_M.-Linear_programming._Vol.1._Introduction%28Springer%2C74s%29_MOc_.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Linear
Programming 1: Introduction&i class=&icon-external&&&/i&&/a&》, George B. Dantzig, Mukund N. Thapa: 这本书是Simplex Method发明人Dantzig写的，书，可以在一些问题不懂的时候参考，不过同样不适合作为入门的第一教材。可能因为Dantzig是数学家，书中思维很严谨，很多Lemma，Theorem，Corrolary，以及证明和推倒。&br&&br&&a href=&///?target=http%3A//ocw.nctu.edu.tw/upload/classbfs748.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Transportation
Problems&i class=&icon-external&&&/i&&/a&，一个小专题 pdf，帮我理解了运输问题，把解法一步步讲得很清楚，初始化阶段介绍了三个方法：North-West, Russell, Vogel。&br&&br&印度理工推出的系列视频，从入门到进阶十分详细，对印度英语不熟悉的同学可能会听着很难受，Salimian为我们整理了这一系列视频：&a href=&///?target=http%3A///courses/OR/OR_videos_YouTube.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Masud Salimian's Operations Research Course&i class=&icon-external&&&/i&&/a&。
学运筹学之前，在知乎查过运筹学入门方面的问题，没有得到想要的答案。现在过运筹学了，自己提问，自己回答。 涉及到专业入门书籍、资料的推荐，因为萝卜青菜各有所爱，难以保证所推荐的适合大多人。仅供参考。 说到运筹学入门书籍，似乎离不开 Frederick
&p&前几天刚从澳大利亚回来，悉尼离波士顿20多个小时的飞机，也是挑战我坐飞机的极限了。老实说，ICML‘17之行比我在夏威夷参加的CVPR'17收获更大，这其中一个原因可能是我已经很熟悉CVPR上面发表的工作的套路了，ICML相关的paper还涉及比较少。我在实验室里分享了一个总结 ，顺便也在知乎分享一些我开会的片段吧。这里分享的主要跟我关注相关的论文，不喜勿拍。&/p&&p&参加ICML对我来说是个很好的学习交流机会，正好ICML一个workshop我有个invited talk，所以在夏威夷开完CVPR直接飞悉尼了。总的来说，ICML的开会行程非常紧凑，白天是oral session和keynote，晚上是poster session。因为每篇论文都有oral presentation，同时有8个parallel session，所以只能挑自己最感兴趣的去参加。这次ICML大概有400篇论文，2500注册人数，比起CVPR‘17的5000人大会，还是稍微好了点。&/p&&p&前面第一天和最后两天是tutorial和workshop。往往一个顶会的tutorial和workshop能反映目前研究的热点。我参加了下面几个，&/p&&p&&b&Tutorial on Interpretable Machine Learning&/b&&/p&&ul&&li&Webpage: (&u&&a href=&///?target=http%3A//people.csail.mit.edu/beenkim/icml_tutorial.html& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&people.csail.mit.edu/be&/span&&span class=&invisible&&enkim/icml_tutorial.html&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&).&/li&&li&Given by Been Kim (slide: &u&&a href=&///?target=http%3A//people.csail.mit.edu/beenkim/papers/BeenK_FinaleDV_ICML2017_tutorial.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&people.csail.mit.edu/be&/span&&span class=&invisible&&enkim/papers/BeenK_FinaleDV_ICML2017_tutorial.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u& )&/li&&/ul&&p&挺high-level的介绍了什么是机器学习算法的可解释性，以及相关的问题和研究工作。我之前CVPR‘17的那个network dissection也被提了一下。&/p&&p&&b&Tutorial on Seq2seq learning&/b&&/p&&ul&&li&&u&&a href=&///?target=https%3A///view/seq2seq-icml17& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/view/s&/span&&span class=&invisible&&eq2seq-icml17&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&, Given by Oriol Vinyals&/li&&li&Slides: &u&&a href=&///?target=https%3A///presentation/d/1quIMxEEPEf5EkRHc2USQaoJRC4QNX6_KomdZTBMBWjk/edit%23slide%3Did.g_0_293& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/present&/span&&span class=&invisible&&ation/d/1quIMxEEPEf5EkRHc2USQaoJRC4QNX6_KomdZTBMBWjk/edit#slide=id.g_0_293&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&&/li&&/ul&&p&Oriol风头十足，他在sequence learning上面也做了一系列工作。从RNN，到attention-based sequence model，以及到怎么用pixelCNN去估计natural image statistics。这个slide是个很好的总结。不过最近RNN好像并不是这么火了，FAIR那边更推崇直接用CNN取代RNN，ICML的那篇Convoluaiton sequence to sequence learning (&u&&a href=&///?target=https%3A//arxiv.org/pdf/.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&2.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&) 可能是一个新起点，毕竟RNN的训练和测试速度都有瓶颈。&/p&&p&&b&Tutorial on Deep Reinforcement Learning, decision making, and control&/b&&/p&&ul&&li&Given by Sergey Levine and Chelsea Finn.&/li&&li&&u&&a href=&///?target=https%3A///view/icml17deeprl& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/view/i&/span&&span class=&invisible&&cml17deeprl&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u& &/li&&li&Slide: &u&&a href=&///?target=https%3A///file/d/0B_j5EZzjlxchV2l3TGJPdTljM1k/view& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/file/d&/span&&span class=&invisible&&/0B_j5EZzjlxchV2l3TGJPdTljM1k/view&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u& &/li&&/ul&&p&DRL不用说了，绝对热点。Chelsea Finn也是炙手可热的AI红人。。。&/p&&p&&b&Workshop on Visualization for Deep Learning.&/b&&/p&&ul&&li&&u&&a href=&///?target=http%3A//icmlviz.github.io/schedule/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&icmlviz.github.io/sched&/span&&span class=&invisible&&ule/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&&/li&&/ul&&p&我在这个workshop上面有个invited talk，讲了Interpreting deep visual representation的相关工作，slide在这里：&u&&a href=&///?target=http%3A//people.csail.mit.edu/bzhou/ppt/presentation_ICML_workshop.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&people.csail.mit.edu/bz&/span&&span class=&invisible&&hou/ppt/presentation_ICML_workshop.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&. &/p&&p&&b&Workshop on Video gaming and machine learning&/b&&/p&&ul&&li&&u&&a href=&///?target=https%3A//syhw.github.io/vgml_workshop_icml2017/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&syhw.github.io/vgml_wor&/span&&span class=&invisible&&kshop_icml2017/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u& &/li&&/ul&&p&打游戏也是目前AI的热点问题啊。几家大公司如DeepMind, OpenAI, FAIR都在猛搞。DeepMind在这个时间点上公布跟暴雪合作开放Starcraft API。OpenAI也在ICML的最后一天搞个大新闻。看Dota和Starcraft打完了大家又该打啥。。&/p&&p&&b&正会&/b&&/p&&p&开场的keynote是Bernard Scholopf做的，关于Causality inference的，topic很有意思，但是talk讲得并不是很有意思。提到了一本新书Elements of Causaul inference: PDF draft: &u&&a href=&///?target=http%3A//www.math.ku.dk/%7Epeters/jonas_files/bookDRAFT11-online-.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&math.ku.dk/~peters/jona&/span&&span class=&invisible&&s_files/bookDRAFT11-online-.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&&/p&&ul&&li&&b&The loss surface of deep and wide neural networks: &/b&&u&&a href=&///?target=http%3A//proceedings.mlr.press/v70/nguyen17a/nguyen17a.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&proceedings.mlr.press/v&/span&&span class=&invisible&&70/nguyen17a/nguyen17a.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u& &/li&&/ul&&p&it argues that all local minima are global optimal given that the number of hidden units of one layer of the network is larger than the number of training points.&/p&&ul&&li&&b&On expressive power of deep neural networks: &/b&&u&&a href=&///?target=http%3A//proceedings.mlr.press/v70/raghu17a/raghu17a.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&proceedings.mlr.press/v&/span&&span class=&invisible&&70/raghu17a/raghu17a.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&&/li&&/ul&&p&On the problem of neural network expressivity, which seeks to characterize how structural properties of a neural network affect the functions it is able to compute&/p&&p&两篇deep learning theory相关的论文。&/p&&ul&&li&&b&Video Pixel CNN&/b& (&u&&a href=&///?target=https%3A//arxiv.org/pdf/.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&7.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u& )：&/li&&/ul&&p&把pixelCNN的扩展到video上面，直接暴力地学习natural video statistics。我一直觉得PixelCNN可以跟GAN匹敌，但是好像Deepmind的东西并不是很积极的open-source， reddit上面大家都吐槽无法复现PixelCNN的结果。&/p&&ul&&li&&b&Model-agnostic meta-learning for fast adaption of deep networks &/b&(&u&&a href=&///?target=https%3A//arxiv.org/pdf/.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&0.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&) &/li&&/ul&&p&关于few-shot learning的论文。这一两年meta-learning蛮火（呃，meta-learning的大致意思是meta-learner learns how to update the parameters of the learner’s model)。是个非常简单的思路，实验在supervised learning和reinforcement learning都有测试，属于想法简单，实验非常solid的套路。&/p&&ul&&li&&b&Understanding the black-box predictions via influence functions &/b&(&u&&a href=&///?target=https%3A//arxiv.org/pdf/.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&0.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&) &/li&&/ul&&p&今年的ICML的best paper。恭喜Percy Liang，今年ICML和COLT都是best paper。这篇论文我也是非常推崇。首先是分析的问题很重要，如何去理解黑箱分类器。再者是分析的手法挺另辟蹊径，从training data本身去寻找跟testing data预测的相关性，挺elegant地用了统计里面叫做influence function的东西作为量度。&/p&&ul&&li&&b&Curiosity-driven exploration by self-supervised prediction &/b&(&u&&a href=&///?target=https%3A//arxiv.org/pdf/.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&3.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&) : &/li&&/ul&&p&Berkeley那边做CV的组出的关于DRL的论文，在VizDoom和超级马里奥上面都有测试（&u&&a href=&///?target=https%3A//pathak22.github.io/noreward-rl/%25EF%25BC%2589& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&https://pathak22.github.io/noreward-rl/）&i class=&icon-external&&&/i&&/a&&/u& 大致是在rl模型里面更强调exploration without extrinsic reward.&/p&&ul&&li&&b&Schema Networks: Zero-shot Transfer with a Generative Causal Model of Intuitive Physics &/b&(&u&&a href=&///?target=https%3A//arxiv.org/pdf/.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&7.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u& ): &/li&&/ul&&p&Vicarious AI公司的工作。Vicarious一直很神秘，一直号称做强AI。这个工作跟Q-learning不一样的地方是直接对环境进行explictly建模，这样环境里面每个东西就变成了个entity，训练过程中得到的weight其实就是各个entity之间的关系，形成了各种human interpretable schema。而且这些schema更像是游戏之中的物理定律，很容易解释和扩展到新的任务之中去。挺有insight的工作。&/p&&ul&&li&&b&Test of time award paper: Combining online and offline knowledge in UST &/b&(&u&&a href=&///?target=http%3A//www.machinelearning.org/proceedings/icml2007/papers/387.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&machinelearning.org/pro&/span&&span class=&invisible&&ceedings/icml2007/papers/387.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&)&/li&&/ul&&p&十年沉淀下来的paper。想不到David Silver在Go上面已经有十多年的积累。David和Sylvain没能到场，但是录制了一段视频，从这篇test of time award paper说起，在一小时的时间里给大家分享了AlphaGo的前世今生。从改进UCT，到value network，从9x9格子围棋上尝试模仿业余选手，到19x19格子围棋战胜人类世界冠军，一个人在同一个问题上花费十年寒暑，真是让人动容。真希望这个视频能放出来。&/p&&ul&&li&&b&Cognitive psychology for deep neural networks: a shape bias case study &/b&(&u&&a href=&///?target=https%3A//arxiv.org/pdf/.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&6.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&) &/li&&/ul&&p&DeepMind的一篇从设计心理学实验来分析深度学习网络的论文，让人耳目一新。关于这篇论文的科普帖子：&u&&a href=&///?target=https%3A///blog/cognitive-psychology/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/blog/cogni&/span&&span class=&invisible&&tive-psychology/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u& &/p&&p&&br&&/p&&p&还有一些基于神经网络的炫酷的应用：比如说跳舞机，流体力学仿真，网页浏览AI agent，量子化学。。。&/p&&ul&&li&&b&Dance Dance Convolution&/b& (&u&&a href=&///?target=https%3A//arxiv.org/pdf/.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&1.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&) &/li&&li&&b&Accelerating Eulerian Fluid Simulation With Convolutional Networks &/b&(&u&&a href=&///?target=http%3A//proceedings.mlr.press/v70/tompson17a/tompson17a.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&proceedings.mlr.press/v&/span&&span class=&invisible&&70/tompson17a/tompson17a.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&) : &/li&&/ul&&p&&u&project page: &a href=&///?target=http%3A//cims.nyu.edu/%7Eschlacht/CNNFluids.htm& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&cims.nyu.edu/~schlacht/&/span&&span class=&invisible&&CNNFluids.htm&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u& &/p&&ul&&li&&b&World of Bits: An Open-Domain Platform for Web-Based Agents&/b& (&u&&a href=&///?target=http%3A//proceedings.mlr.press/v70/shi17a/shi17a.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&proceedings.mlr.press/v&/span&&span class=&invisible&&70/shi17a/shi17a.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&) &/li&&li&&b&Neural Message Passing for Quantum Chemistry &/b&(&u&&a href=&///?target=https%3A//arxiv.org/pdf/.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&2.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/u&) &/li&&/ul&&p&&br&&/p&&p&-----------分割线-----------&/p&&p&&img data-rawwidth=&960& data-rawheight=&1280& src=&/v2-bf131ad2ef3b77f9f552e5_b.jpg& class=&origin_image zh-lightbox-thumb& width=&960& data-original=&/v2-bf131ad2ef3b77f9f552e5_r.jpg&&&/p&&br&（图文无关：悉尼冬日暖阳下公然打劫小伙伴午餐的海鸥）&p&我在实验室内部还分享了个ICML'17 note，感兴趣的话请移步（国内Google Doc需要翻墙）：&a href=&///?target=https%3A///document/d/1MJRNTGccyU3Jv_slB5PE85PcKsyk5CgCASqfiQZLO5s/edit%3Fusp%3Dsharing& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/documen&/span&&span class=&invisible&&t/d/1MJRNTGccyU3Jv_slB5PE85PcKsyk5CgCASqfiQZLO5s/edit?usp=sharing&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&
前几天刚从澳大利亚回来，悉尼离波士顿20多个小时的飞机，也是挑战我坐飞机的极限了。老实说，ICML‘17之行比我在夏威夷参加的CVPR'17收获更大，这其中一个原因可能是我已经很熟悉CVPR上面发表的工作的套路了，ICML相关的paper还涉及比较少。我在实验室里分…
&p&给《机器视觉与应用》课程出大作业的时候，正好涉及到这方面内容，所以简单整理了一下（参考 Hinton 的课程）。按照之前的套路写：&/p&&br&&p&&u&&b&是什么&/b&&/u&&/p&&p&过拟合（overfitting）是指在模型参数拟合过程中的问题，由于训练数据包含&b&抽样误差&/b&，训练时，复杂的模型将抽样误差也考虑在内，将抽样误差也进行了很好的拟合。&/p&&p&具体表现就是最终模型在训练集上效果好；在测试集上效果差。模型泛化能力弱。&/p&&img src=&/v2-953f6e7ce85ace1c855705_b.png& data-rawwidth=&977& data-rawheight=&401& class=&origin_image zh-lightbox-thumb& width=&977& data-original=&/v2-953f6e7ce85ace1c855705_r.png&&&br&&p&&b&&u&为什么&/u&&/b&&/p&&p&&u&为什么要解决过拟合现象？&/u&这是因为我们拟合的模型一般是用来预测未知的结果（不在训练集内），过拟合虽然在训练集上效果好，但是在实际使用时（测试集）效果差。同时，在很多问题上，我们无法穷尽所有状态，不可能将所有情况都包含在训练集上。所以，必须要解决过拟合问题。&/p&&p&&u&为什么在机器学习中比较常见？&/u&这是因为机器学习算法为了满足尽可能复杂的任务，其模型的拟合能力一般远远高于问题复杂度，也就是说，机器学习算法有「拟合出正确规则的前提下，进一步拟合噪声」的能力。&/p&&p&而传统的函数拟合问题（如机器人系统辨识），一般都是通过经验、物理、数学等推导出一个含参模型，模型复杂度确定了，只需要调整个别参数即可。模型「无多余能力」拟合噪声。&/p&&br&&p&&b&&u&怎么样&/u&&/b&&/p&&p&既然过拟合这么讨厌，我们应该怎么防止过拟合呢？最近深度学习比较火，我就以神经网络为例吧：&/p&&img src=&/v2-df0ae79b4a647bdc5edc0fb_b.png& data-rawwidth=&852& data-rawheight=&532& class=&origin_image zh-lightbox-thumb& width=&852& data-original=&/v2-df0ae79b4a647bdc5edc0fb_r.png&&&p&&b&1. 获取更多数据 &/b&&/p&&p&这是解决过拟合最有效的方法，只要给足够多的数据，让模型「看见」尽可能多的「例外情况」，它就会不断修正自己，从而得到更好的结果：&/p&&img src=&/v2-d6acbbea45d7c1d023c8e54f3ea84566_b.png& data-rawwidth=&843& data-rawheight=&532& class=&origin_image zh-lightbox-thumb& width=&843& data-original=&/v2-d6acbbea45d7c1d023c8e54f3ea84566_r.png&&&p&如何获取更多数据，可以有以下几个方法：&/p&&ul&&li&&u&从数据源头获取更多数据&/u&：这个是容易想到的，例如物体分类，我就再多拍几张照片好了；但是，在很多情况下，大幅增加数据本身就不容易；另外，我们不清楚获取多少数据才算够；&/li&&li&&u&根据当前数据集估计数据分布参数，使用该分布产生更多数据&/u&：这个一般不用，因为估计分布参数的过程也会代入抽样误差。&/li&&li&&u&数据增强（Data Augmentation）&/u&：通过一定规则扩充数据。如在物体分类问题里，物体在图像中的位置、姿态、尺度，整体图片明暗度等都不会影响分类结果。我们就可以通过图像平移、翻转、缩放、切割等手段将数据库成倍扩充；&/li&&/ul&&img src=&/v2-cdbee1e375c0d3e68ff0e4d_b.png& data-rawwidth=&1323& data-rawheight=&889& class=&origin_image zh-lightbox-thumb& width=&1323& data-original=&/v2-cdbee1e375c0d3e68ff0e4d_r.png&&&br&&p&&b&2. 使用合适的模型&/b&&/p&&p&前面说了，过拟合主要是有两个原因造成的：数据太少+模型太复杂。所以，我们可以通过使用合适复杂度的模型来防止过拟合问题，让其足够拟合真正的规则，同时又不至于拟合太多抽样误差。&/p&&p&（&i&PS：如果能通过物理、数学建模，确定模型复杂度，这是最好的方法，这也就是为什么深度学习这么火的现在，我还坚持说初学者要学掌握传统的建模方法。&/i&）&/p&&p&对于神经网络而言，我们可以从以下四个方面来&b&限制网络能力&/b&：
&/p&&br&&p&&u&2.1 网络结构 Architecture&/u&&/p&&p&这个很好理解，减少网络的层数、神经元个数等均可以限制网络的拟合能力；&/p&&img src=&/v2-1a1e88a4_b.png& data-rawwidth=&656& data-rawheight=&415& class=&origin_image zh-lightbox-thumb& width=&656& data-original=&/v2-1a1e88a4_r.png&&&br&&p&&u&2.2 训练时间 Early stopping&/u&&/p&&p&对于每个神经元而言，其激活函数在不同区间的性能是不同的：&/p&&img src=&/v2-f6c8a5a1ee_b.png& data-rawwidth=&779& data-rawheight=&387& class=&origin_image zh-lightbox-thumb& width=&779& data-original=&/v2-f6c8a5a1ee_r.png&&&p&当网络权值较小时，神经元的激活函数工作在线性区，此时神经元的拟合能力较弱（类似线性神经元）。&/p&&p&有了上述共识之后，我们就可以解释为什么限制训练时间（early stopping）有用：因为我们在初始化网络的时候一般都是初始为较小的权值。训练时间越长，部分网络权值可能越大。如果我们在合适时间停止训练，就可以将网络的能力限制在一定范围内。&/p&&br&&p&&u&2.3 限制权值 Weight-decay，也叫正则化（regularization）&/u&&/p&&p&原理同上，但是这类方法直接将权值的大小加入到 Cost 里，在训练的时候限制权值变大。以 L2 regularization为例：&/p&&img src=&///equation?tex=C%3DC_0%2B%5Cfrac%7B%5Clambda%7D%7B2n%7D%5Ccdot%5Csum_i%7Bw_i%5E2%7D& alt=&C=C_0+\frac{\lambda}{2n}\cdot\sum_i{w_i^2}& eeimg=&1&&&p&训练过程需要降低整体的 Cost，这时候，一方面能降低实际输出与样本之间的误差 &img src=&///equation?tex=C_0& alt=&C_0& eeimg=&1&& ，也能降低权值大小。&/p&&br&&p&&u&2.4 增加噪声 Noise&/u&&/p&&p&给网络加噪声也有很多方法：&/p&&p&2.4.1 在输入中加噪声：&/p&&p&噪声会随着网络传播，按照权值的平方放大，并传播到输出层，对误差 Cost 产生影响。推导直接看 Hinton 的 PPT 吧：&/p&&img src=&/v2-dd68a0b4e7092eb1beced34e11614b04_b.png& data-rawwidth=&864& data-rawheight=&460& class=&origin_image zh-lightbox-thumb& width=&864& data-original=&/v2-dd68a0b4e7092eb1beced34e11614b04_r.png&&&p&在输入中加高斯噪声，会在输出中生成 &img src=&///equation?tex=%5Csum_i%5Csigma_i%5E2%5Ccdot+w_i%5E2& alt=&\sum_i\sigma_i^2\cdot w_i^2& eeimg=&1&& 的干扰项。训练时，减小误差，同时也会对噪声产生的干扰项进行惩罚，达到减小权值的平方的目的，达到与 L2 regularization 类似的效果（对比公式）。&/p&&p&2.4.2 在权值上加噪声&/p&&p&在初始化网络的时候，用0均值的高斯分布作为初始化。Alex Graves 的手写识别 RNN 就是用了这个方法&/p&&blockquote&Graves, Alex, et al. &A novel connectionist system for unconstrained handwriting recognition.& &i&IEEE transactions on pattern analysis and machine intelligence&/i& 31.5 (2009): 855-868.&/blockquote&&p&- It may work better, especially in recurrent networks (Hinton)&/p&&p&2.4.3 对网络的响应加噪声&/p&&p&如在前向传播过程中，让默写神经元的输出变为 binary 或 random。显然，这种有点乱来的做法会打乱网络的训练过程，让训练更慢，但据 Hinton 说，在测试集上效果会有显著提升 （But it does significantly better on the test set!）。&/p&&br&&p&&b&3. 结合多种模型&/b&&/p&&p&简而言之，训练多个模型，以每个模型的平均输出作为结果。&/p&&p&从 N 个模型里随机选择一个作为输出的期望误差 &img src=&///equation?tex=%3C%5Bt-y_i%5D%5E2%3E& alt=&&[t-y_i]^2&& eeimg=&1&& ，会比所有模型的平均输出的误差 &img src=&///equation?tex=%3C%5Bt-%5Coverline%7By%7D%5D%5E2%3E& alt=&&[t-\overline{y}]^2&& eeimg=&1&& 大（&i&我不知道公式里的圆括号为什么显示不了&/i&）：&/p&&img src=&/v2-7c680a822f0_b.png& data-rawwidth=&1020& data-rawheight=&377& class=&origin_image zh-lightbox-thumb& width=&1020& data-original=&/v2-7c680a822f0_r.png&&&p&大概基于这个原理，就可以有很多方法了：&/p&&p&3.1
Bagging&/p&&p&简单理解，就是分段函数的概念：用不同的模型拟合不同部分的训练集。以随机森林（Rand Forests）为例，就是训练了一堆互不关联的决策树。但由于训练神经网络本身就需要耗费较多自由，所以一般不单独使用神经网络做Bagging。&/p&&p&3.2 Boosting&/p&&p&既然训练复杂神经网络比较慢，那我们就可以只使用简单的神经网络（层数、神经元数限制等）。通过训练一系列简单的神经网络，加权平均其输出。&/p&&img src=&/v2-a64fbfadfa2dd75ed99fcd_b.png& data-rawwidth=&558& data-rawheight=&303& class=&origin_image zh-lightbox-thumb& width=&558& data-original=&/v2-a64fbfadfa2dd75ed99fcd_r.png&&&p&3.3 Dropout&/p&&p&这是一个很高效的方法。&/p&&img src=&/v2-9dfdb3a81e5aaadeb36d5814_b.png& data-rawwidth=&336& data-rawheight=&341& class=&content_image& width=&336&&&p&在训练时，&b&每次&/b&随机（如50%概率）忽略隐层的某些节点；这样，我们相当于随机从2^H个模型中采样选择模型；同时，由于每个网络只见过一个训练数据（每次都是随机的新网络），所以类似 &b&bagging &/b&的做法，这就是我为什么将它分类到「结合多种模型」中；&/p&&p&此外，而不同模型之间权值共享（共同使用这 H 个神经元的连接权值），相当于一种权值正则方法，实际效果比 L2 regularization 更好。&/p&&br&&p&&b&4. 贝叶斯方法&/b&&/p&&p&这部分我还没有想好怎么才能讲得清楚，为了不误导初学者，我就先空着，以后如果想清楚了再更新。当然，这也是防止过拟合的一类重要方法。&/p&&img src=&/v2-bac2f6fb95_b.png& data-rawwidth=&753& data-rawheight=&315& class=&origin_image zh-lightbox-thumb& width=&753& data-original=&/v2-bac2f6fb95_r.png&&&br&&p&综上：&/p&&img src=&/v2-1c2b0e7bc8c6d5eede473_b.png& data-rawwidth=&808& data-rawheight=&523& class=&origin_image zh-lightbox-thumb& width=&808& data-original=&/v2-1c2b0e7bc8c6d5eede473_r.png&&
给《机器视觉与应用》课程出大作业的时候，正好涉及到这方面内容，所以简单整理了一下（参考 Hinton 的课程）。按照之前的套路写： 是什么过拟合（overfitting）是指在模型参数拟合过程中的问题，由于训练数据包含抽样误差，训练时，复杂的模型将抽样误差也…
&p&###&/p&&p&欢迎转载和分享给更多人，无需标明作者和链接，但如果标了会更显得尊重别人的成果，谢谢&/p&&p&###&/p&&p&首先，&b&请你不要一上来就对着书按着顺序学&/b&。&/p&&p&运筹学是一个子方向很多的学科，线性规划，整数规划，非线性规划，随机过程，随机规划，存储量，博弈论，鲁棒优化，最优控制。。。每一个方向里面全是数学，有浅一点的，有很深的，一大堆符号，要都学，学很久，而且也会学得很痛苦，因为他们之间虽然有关系，但是关系不密切。刚开始，我觉得有必要知道这门学科的&b&灵魂&/b&。&/p&&p&==================================================================&/p&&p&学运筹不要一上来就去钻，例如一上来就学最最基本的线性规划，是因为如果这么学，其实你学的是优化部分的应用数学，不是运筹学。运筹学不仅仅包括优化。优化只是理论部分。例如线性规划是一种刻画某些现实问题的模型，如果只关注于线性规划本身，那其实有很大一部分是在关注线性规划的数学理论。解线性规划里面的数学理论就多了去了：线性不等式的代表性，对偶理论，各种单纯性法，椭圆法和各种内点法，现在还在发展。里面每一个理论都不是随便看看就能通的，特别对于数学基础不算很好的同学而言。有些教授对里面的数学还讲一些high level的想法，但是国内教科书一般就直接上定义XXX，定理XXX，两下就可以晕了。。。运筹学现在很受关注，很多社科和工科学生都在接触，花太多时间在数学理论部分上，对他们而言挺可惜的。&/p&&p&关键是，对大多数人，里面的数学压根不需要学，&b&我们有软件解！有不少还是开源的！&/b&这个自己搜搜就好，其它回答也提到一些了。现在运筹学领域的专家们都给我们把各种解法自动化了，何必不好好利用，还自己慢慢理解算法？再慢慢编程？&/p&&p&所以如果只是入门，最重要是看看这一大堆运筹学里面不同的理论都是干什么的，哪些模型好解，哪些难解，现在很多我们接触到的模型都有定论的。&/p&&p&&br&&/p&&p&&b&运筹学里面其实更重要的是建模&/b&。换言之，就是&b&看现实问题和数学语言是怎么对应的&/b&。这个因为考试的原因，太容易被忽略了其重要性。&/p&&p&建模这事情说难不难说易不易。易在好像就是定义几个变量，定义一下变量之间的关系和目标函数。难在&br&&b&１.　对现实问题要看透：什么才是问题里面的最重要的因素，抓住重点&/b& &b&２.　找到最合适的数学语言和它对应，&/b& &b&３.　模型要尽量容易解&/b&。&/p&&p&第一点是因问题而异的，没法聊。第二点是可以通过了解各种模型适用于刻画具有什么结构的问题来达到。运筹学里面有很多模型。举几个例子：&br&１.　线性规划能表示所有有线性结构的问题，例如做采购，我们知道了每家供应商的固定价格和最大供应量，我们希望最小化成本，那总成本＝单价×数量，这个就是这个问题里面的线性关系。&br&２.　整数规划能处理一些线性规划处理不了的问题。例如还是采购，假如选了某家供应商，每选定一个供应商，还要增加一个固定成本，于是我们就要多设一个变量来代表是不是选了这个供应商，这时候就需要整数限制。不然那个变量解出来等于０.５，我们只选半个它？&br&３.　当现实问题涉及多个参与者，每个参与者都有自己优化的东西，这时候就涉及互动，就可以将博弈论派上用场了。&br&４.　如果见到一个系统是随时间变化的，就可以考虑用最优控制。&br&等等等等。&/p&&p&懂了对自己身边的具体问题建模，再拿个软件解一下模型，对大部分人就够了。所以要看书或者看视频自学的话，第一步是，每一章只看前面讲建模（modeling或者formulation）那一节。够用了。&/p&&p&但是对于要更深入地去懂运筹学还不够。&br&&b&做得好的运筹学问题都是这样的：&/b& &b&１.　深刻认识现实问题&/b& &b&２.　用数学语言描述问题（建模）&/b& &b&３.　用数学工具研究模型&/b& &b&４.　再把研究出来的成果从数学语言翻译成我们能看懂的语言&/b&（例如汉语，英语。。。）&/p&&p&前面我们只聊到１,２和一点点３，真正的美出现在４。４的重要意义在于如果我们把一个问题解出来了，但是看不懂解出来的是什么，那么我们对这个问题其实是没有增加多少认识的。有些时候还会导致其他问题，例如你在解决某个现实问题的时候，你把一个计算机解出来给你的解拿来用了，发现现实情况不像你想象中那样，那怎么办？是计算机算解错了吗？还是你的模型没建好吗？如果有人给你投资做一个某些方面的优化系统，人家能信得过这样靠建个模型解个解得出的方案吗？大多数不懂你在做什么的人是不会信的。所以好的解可以提供&b&insight！（能让人读懂的现实含义）&/b&&/p&&p&例如Kelly Gambling，假如已知有n匹马，他们胜率分别是b_i,跑第一的话投1块钱能赢o_i块钱，你总共有100块钱（你可以当成一百万，具体数目不重要，关键是比例），投到第i匹马的钱是100p_i。假如你要买马买无数次，那应该怎么分配你的钱到各匹马上去？这个问题的解就是p_i和b_i成比例。给我们的insight就是，获胜几率大的多放点钱，几率小的少放点钱，就是这么简单。这个model的解给了我们分散投资的idea。&/p&&p&这是最简单的情况，马和马之间是indepedent的，如果是投资股票，股票之间可能有相关性，如果这个相关性很重要，建模的时候就把它也考虑进去，得到考虑了相关性的解，再试图去interpret你的解。如果相关性不太重要，就没必要把模型搞复杂。&/p&&p&&br&&/p&&p&能得到给我们insight的解难吗？当然难！&/p&&p&要想４出现，前面的１，２,３一定要简洁而深刻。模型既能抓住问题的重点，还要足够简单，不然最后出来的结果怎么可能让人看得懂。这里头需要的可不仅是扎实的数学基础，数学只是描述问题的一种语言，更重要的还是对具体问题的认识和对建出来的模型的预判。&/p&&p&对于一个现实问题，建立一个简单好解又能较好地描述现实情况的模型，是一种艺术。这是数学界甚至科学界追求的美的原则：&b&simple and elegant&/b&.&/p&
###欢迎转载和分享给更多人，无需标明作者和链接，但如果标了会更显得尊重别人的成果，谢谢###首先，请你不要一上来就对着书按着顺序学。运筹学是一个子方向很多的学科，线性规划，整数规划，非线性规划，随机过程，随机规划，存储量，博弈论，鲁棒优化，最…
&p&===&/p&&p&强行加广告：发布非梯度优化python工具包 ZOOpt release 0.1 欢迎尝试 &a href=&///?target=https%3A///eyounx/ZOOpt& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/eyounx/ZOOpt&/span&&span class=&invisible&&&/span&&i class=&icon-external&&&/i&&/a& 示例包括非凸损失分类器学习、直接策略优化强化学习、L0范数稀疏回归直接求解&/p&&p&===以下是原文&/p&&p&不是。优化的原理可以这么理解：&b&利用关于最优解的信息，不断逼近最优解&/b&。&/p&&p&梯度下降（或上升）方法有效的前提条件是，&b&梯度方向指向最优解方向&/b&，因此沿着梯度方向前进即可靠近最优解，这时梯度就是关于最优解的非常有效的信息。在凸函数、quasi凸函数等比较简单的问题上，确实能够满足这一前提，因此梯度可以work，当然也可能有比梯度更高效的关于最优解的信息。然而&b&当优化目标有大量局部极值时，绝大多数解空间位置的梯度方向不再指向最优解&/b&，因此梯度方法无法逼近最优解，能找到局部极值就已经很不错了。下面是两个经典的例子，可以拿梯度下降来感受一下。&/p&&img src=&/v2-111c5c49f95db_b.jpg& data-rawwidth=&1984& data-rawheight=&722& class=&origin_image zh-lightbox-thumb& width=&1984& data-original=&/v2-111c5c49f95db_r.jpg&&&p&更坏的消息是，上面这两个图只是2维函数，通常这一类函数，其局部极值的数量随着空间维度的增长指数增加，2维有100个局部极值，10维能有100亿个局部极值&/p&&img src=&/v2-9ecf93da388_b.jpg& data-rawwidth=&140& data-rawheight=&119& class=&content_image& width=&140&&&p&那么有没有能解决所有问题的优化方法呢？&b&答案是没有！&/b&前面有人说到No Free Lunch Theorem（没有免费的午餐定理），可惜只贴了文章截图而没有解释，我重讲一遍。NFLT的证明大意是这样的：&/p&&blockquote&首先，我们考虑所有可能的问题。什么是“所有可能”的问题，如果我们假定一个解的函数值可以有“优、良、中、差”，那么你任意拿出一个解、并且任意选“优、良、中、差”之一的评价，“所有可能”的问题中就有那么一个问题，在这个解上正好是你给出的评价；&br&其次，所有的问题等概率出现。也就是说，你任意拿出一个解，说这个解是优、良、中、差四个评价的问题一样多，不会有其中一种评价更多一点；&br&然后，在等概率的所有问题上，计算一个算法能找到的解的好坏。这时你会发现，如果算法在一个问题上能找到优解，那么就存在另外的问题这个算法的结果是良、中、差。这么一来，一个算法在等概率的所有问题上的总体性能就成了常数，与算法无关了，于是所有算法也就跟随机搜索一样了&/blockquote&&p&NFLT考虑的是离散空间优化的问题，在连续空间稍有不同，不过大体相当。NFLT更多的是被当作算法设计的哲学指导思想，优化和学习算法都应当考虑一个范围的问题，而不是试图设计放之四海而皆准的算法。&/p&&p&那么上面这么多局部极值的问题到底能不能解，至少解得比随机搜索要更好？在一定层度上可以。我们来考虑这么一个函数，这函数在最优解处最小，这是当然，但在不是最优解处，这函数不能随便变动，只能在一定范围内变动，这个范围与这个解离最优解的距离相关，距离越远，变化的范围可以越大。这一类函数就叫做 Local Lipschitz 函数[1]。下图是一个示意图，只要函数在这个范围之内就可以，不管是否连续、是否有多个局部极值。&/p&&img src=&/v2-158ef19db854fedbc041_b.png& data-rawwidth=&300& data-rawheight=&222& class=&content_image& width=&300&&&p&可见， Local Lipschitz 函数可以非常复杂，很多复杂的优化问题看起来都可以归为这一类函数，例如前面的两个函数图像。而好消息是，&b&无论有多少局部极值，Local Lipschitz 函数可以有效求解&/b&。这里有效求解的意思是，任给逼近层度&img src=&///equation?tex=%5Cepsilon& alt=&\epsilon& eeimg=&1&&，能在多项式时间找到与最优解只差&img src=&///equation?tex=%5Cepsilon& alt=&\epsilon& eeimg=&1&&的解，即 &img src=&///equation?tex=f%28x%29+-+f_%7B%5Cmin%7D%5Cleq+%5Cepsilon& alt=&f(x) - f_{\min}\leq \epsilon& eeimg=&1&&，多项式则是关于空间维度、&img src=&///equation?tex=1%2F%5Cepsilon& alt=&1/\epsilon& eeimg=&1&& 以及Local Lipschitz范围的斜率等。&/p&&p&那么是怎么求解的呢？求解的原理如同刚开始说的一样，要找到关于最优解的信息。对于这么复杂的函数，梯度是不能用了，那么最优解的信息怎么去找呢，一个总体的思路是解空间采样，通过采样一批解、并且计算出这一批解的函数值，能够大体了解目标函数的走势，再不断精化。这就是一大类非梯度优化算法。&/p&&p&针对 Local Lipschitz 函数，一种非梯度优化方法是[1]中的Optimistic Optimization，基于upper confidence bound的思想，通过切分搜索空间来不断精化搜索。然而这一类方法在很多测试中收敛得相当慢。（插入硬广）另一种方法是[2]中的基于模型的方法RACOS，[3]中进行了改进，代码见github: &a href=&///?target=https%3A///eyounx/RACOS& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&eyounx/RACOS&i class=&icon-external&&&/i&&/a& &/p&&p&贝叶斯优化也是一类可用于求解多个局部极值的非梯度方法，其求解的函数类型为“以高斯过程分布的函数”，不太好描述具体的函数应该长成什么样子，总体来说应该是比较平滑的函数。然而贝叶斯优化参数很多，到高维容易退化为随机搜索，通常开足马力可以跑一跑500维以下的问题。（又来硬广）RACOS可以跑上万维，如果加上随机嵌入技术[4]，可以跑更高维度的优化问题。&/p&&p&总的来说，关注梯度优化的人太多，而非梯度优化更适合解决复杂问题，值得更多关注。&br&&/p&&p&参考文献：&/p&&p&[1] R. Munos. &a href=&///?target=https%3A//hal.inria.fr/hal-& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning&i class=&icon-external&&&/i&&/a&. Foundations and Trends in Machine Learning7(1):1– 130, 2014.&/p&&p&[2] Y. Yu, H. Qian, and Y.-Q. Hu. &a href=&///?target=http%3A//www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12367& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Derivative-free optimization via classification&i class=&icon-external&&&/i&&/a&. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI'16), Phoenix, AZ, 2016, pp.&a href=&tel:&&&/a&&/p&&p&[3] Y.-Q. Hu, H. Qian, and Y. Yu. &a href=&///?target=http%3A//aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14929& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Sequential classification-based optimization for direct policy search&i class=&icon-external&&&/i&&/a&. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI’17), San Francisco, CA, 2017.&/p&&p&[4] H. Qian, Y.-Q. Hu and Y. Yu. &a href=&///?target=http%3A//www.ijcai.org/Proceedings/16/Papers/278.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Derivative-free optimization of high-dimensional non-convex functions by sequential random embeddings&i class=&icon-external&&&/i&&/a&. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI'16), New York, NY, 2016, pp.&a href=&tel:&&&/a&.&/p&
===强行加广告：发布非梯度优化python工具包 ZOOpt release 0.1 欢迎尝试
示例包括非凸损失分类器学习、直接策略优化强化学习、L0范数稀疏回归直接求解===以下是原文不是。优化的原理可以这么理解：利用关于最优解的信息，不断逼近最…
&p&本人优化方向Phd一枚，两本书都很认真的读过。这两本都是很有名的优化入门书籍，都写的很棒，不需要太多基础就能读懂。怎么读看你的需求。&/p&&p&Numerical Optimization我认为是必读的。这本书讲了各种优化算法，对于经典的方法覆盖非常全面。相对于其他优化的入门著作，这本书理论比较少，但把每个算法原理都讲得很明白，而且讲了每种算法在使用中很多practical的问题，这是我认为这本书很好的一个方面（做优化的人大部分数学出身，大牛们一般不屑于去讨论practical issue，但真的用起来的时候，你就会发现这些问题是很重要的）。无论是针对以后做优化方向的研究工作的，还是只是需要应用优化算法的，我觉得都可以读这本书。&/p&&p&Convex Optimization这本书相对来说更加理论一些，介绍的算法比较少。虽然涉及到的理论都是比较初级的，但写的很清楚，例子非常多，如果认真读完并且做下后面的习题，可以帮你打下比较扎实的理论基础。我PhD刚入学时，老板就要求我们先把这本书前几章理论部分刷完。&/p&&br&&p&接下来说一些具体的建议：&/p&&ol&&li&如果你想知道如何将问题formulate成优化问题、这个优化问题的性质是怎样的能否求到全局最优化、如何将你的问题转换成一个常见形式的优化问题（比如LP、SDP等）以便于利用现有的求解器求解，而并不关心优化算法本身的原理，那么请读Convex Optimization；&/li&&li&如果你已经知道了你的问题的数学形式，但想寻求更好的优化算法来有效的求解，那么请读Numerical Optimization；&/li&&li&如果你想对优化领域有比较完整的理解，那么这两本书都是要读的。如果这两本书都读完了，想更进一步，Nolinear Programming和Introductory Lectures on Convex Optimization等书会是你很好的选择。&/li&&/ol&
本人优化方向Phd一枚，两本书都很认真的读过。这两本都是很有名的优化入门书籍，都写的很棒，不需要太多基础就能读懂。怎么读看你的需求。Numerical Optimization我认为是必读的。这本书讲了各种优化算法，对于经典的方法覆盖非常全面。相对于其他优化的入…
&p&前言--正本清源：&b&优化理论（运筹学）&/b&，研究的是如何求解目标函数在约束条件下的最优解。机器学习、人工智能中的绝大部分问题，到最后基本都会&b&归结为&/b&求解优化问题，因此学习优化理论是非常有必要的。&/p&&p&机器学习中用到的优化，只是整个&b&运筹学&/b&（最优化理论）中的一瞥。只需一门Numerical Optimization(数值优化)或Convex Optimization(凸优化)即可。还有更简单粗暴的，书名直接叫做CONVEX OPTIMIZATION IN ENGINEERING(工程中的凸优化)--机器学习中用到的优化和运筹学相比确实挺“工程”的。&/p&&p&下面是三本书目和下载链接（当然是&b&英文原版&/b&的，还是免费的）：&/p&&p&1，Numerical Optimization，&b&西北大学和美国阿贡实验室&/b&著（他引2w次）&/p&&a href=&///?target=http%3A//www./%7Ewangchao/maa/Numerical_Optimization.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&/~wangcha&/span&&span class=&invisible&&o/maa/Numerical_Optimization.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&p&2，Convex Optimization，&b&斯坦福和UCLA&/b&教授著&/p&&a href=&///?target=https%3A//web.stanford.edu/%7Eboyd/cvxbook/bv_cvxbook.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&web.stanford.edu/~boyd/&/span&&span class=&invisible&&cvxbook/bv_cvxbook.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&p&3，CONVEX OPTIMIZATION IN ENGINEERING Modeling Analysis Algorithms，&b&以色列理工&/b&教授著&/p&&a href=&///?target=http%3A//www.st.ewi.tudelft.nl/%7Eroos/courses/WI4218/tud00r.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&st.ewi.tudelft.nl/~roos&/span&&span class=&invisible&&/courses/WI4218/tud00r.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&p&不喜欢看书的小伙伴，推荐Youtube（油管）搜索相关课程（当然你要自学怎么翻墙咯），很多&b&世界名校的教授&/b&都非常无私地把自己上课视频上传油管。例如：&/p&&p&&b&斯坦福大学&/b& Stephen Boyd教授在电子工程系（Electrical Engineering ）开的Convex Optimization课程(EE 364A，感谢评论区，该课为研究生课程）：&/p&&a href=&///?target=https%3A///watch%3Fv%3DMcLq1hEq3UY& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://www.&/span&&span class=&visible&&/watch?&/span&&span class=&invisible&&v=McLq1hEq3UY&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&p&说实话，运筹学出生的楼主，看到机器学习中的优化理论基本都是&b&直接跳过&/b&的，因为实在太&b&基础&/b&了。（喷子莫喷，学完运筹学下绝大部分优化课程再喷也不迟）&/p&&p&运筹学作为专门研究优化理论的学科，其下分支是&b&极为庞大&/b&的，那么机器学习中优化理论只需一门convex optimization的原因在于，机器学习处理&b&数据之庞大&/b&，因此基本假设便目标方程和约束空间是convex和continuous。这样导致运筹学的另外半壁江山nonconvex和integer optimization（NP难问题）在机器学习的领域没有什么用武之地。&/p&&p&当然随着计算机运算效率的提高，也开始有学者把nonconvex和integer optimization应用于机器学习，比如楼主，还有楼主最近一篇paper的合作者之一，机器学习领域的法国国立应用科学学院（INSA）及诺曼底大学的Stephane Canu教授，就是这股潮流其中之二--我们利用混合整数规划模型直接求解L0范式的优化问题(通常的策略是求解L1或Lp范式--转化成convex 和continuous)。&/p&&p&因此如果你纯粹做机器学习的应用，那么学convex optimization就行，并且不用太在意理论性的东西，这是运筹学的研究者去研究的；如果搞&b&科研&/b&，建议学完convex后可以跟进nonconvex和integer programming，因为以前没人用，把没有用过的理论应用过来，效果好就是一个新发现和好paper－－欢迎入坑。&/p&&br&&p&如果你想入门机器学习、人工智能，除了优化还有很多其他许多基础课程，下面给你由浅入深一一列举：&/p&&p&&a href=&/question//answer/& class=&internal&&&span class=&invisible&&https://www.&/span&&span class=&visible&&/question/5062&/span&&span class=&invisible&&3000/answer/&/span&&span class=&ellipsis&&&/span&&/a&（想学数据分析（人工智能）需要学哪些课程？）&/p&&p&如果对运筹学感兴趣，可以看看楼主在下面的回答：&/p&&a href=&/question//answer/& class=&internal&&运筹学如何入门？ - 知乎&/a&&p&&b&也欢迎参加我号举办的“运筹学综述”知乎live，探讨关于运筹学、优化、AI的相关话题：&/b&&/p&&p&&b&&a href=&/lives/002432& class=&internal&&知乎 Live - 全新的实时问答&/a&（大数据人工智能时代的运筹学-知乎Live）&/b&&/p&&p&最后希望大家关注楼主的运筹学专栏，了解&b&优化理论的本源&/b&－－运筹学。&/p&&a href=&/operations-research& class=&internal&&[运筹帷幄]大数据和人工智能时代下的运筹学 - 知乎专栏&/a&
前言--正本清源：优化理论（运筹学），研究的是如何求解目标函数在约束条件下的最优解。机器学习、人工智能中的绝大部分问题，到最后基本都会归结为求解优化问题，因此学习优化理论是非常有必要的。机器学习中用到的优化，只是整个运筹学（最优化理论）中的…
一张图让你明白：&br&&img src=&/68fbca479543_b.jpg& data-rawwidth=&886& data-rawheight=&563& class=&origin_image zh-lightbox-thumb& width=&886& data-original=&/68fbca479543_r.jpg&&======================================================&br&按照 &a data-hash=&828da5d68a& href=&///people/828da5d68a& class=&member_mention& data-editable=&true& data-title=&@陳浩& data-tip=&p$b$828da5d68a& data-hovercard=&p$b$828da5d68a&&@陳浩&/a& 的建议做一点补充说明：&br&1、集合 X 上的偏序 ≤ 是指满足以下条件的二元关系：&br&(i) 对任意 x∈X，x≤x；&br&(ii) 对任意 x,y∈X，若 x≤y，y≤x，则 x=y；&br&(iii) 对任意 x,y,z∈X，若 x≤y，y≤z，则 x≤z。&br&2、上面的图分别表示一个&b&偏序集&/b&，图中的小圆圈表示偏序集中的点，连线表示大小关系。&br&3、如果两个&b&相邻&/b&的点之间有连线，则下面的点&上面的点（x&y 的意思是 x≤y 且 x≠y）。&br&4、对于不相邻的点，其大小关系由 1(iii) 决定（如果可以比较大小的话）。&br&5、如果两个点之间没有连线，或者虽然有间接的连线但不符合 1(iii) 所述情形，则&b&不能比较大小&/b&。&br&6、maximum 的意思是“最大”，表示该偏序集中其他的点都比它小；maximal 的意思是“极大”，表示该偏序集中没有比它更大的点，即该偏序集中的其他点要么比它小，要么和它不能比较大小。minimum 和 minimal 的意思同理。&br&7、注意与中文微积分教材中函数的最值与极值区分。函数的最大值/最小值是指在整个定义域上的最大值/最小值；而函数的极大值/极小值是指“局部最大值/局部最小值”，即极大值/极小值是在它的某个邻域内的最大值/最小值。
一张图让你明白： ====================================================== 按照
的建议做一点补充说明： 1、集合 X 上的偏序 ≤ 是指满足以下条件的二元关系： (i) 对任意 x∈X，x≤x； (ii) 对任意 x,y∈X，若 x≤y，y≤x，则 x=y； (iii) 对任意 …
&p&我稍微归纳总结一下：&/p&&p&优化方面经典的三本优化著作,可根据自身情况选读&/p&&ul&&li&&b&Convex Optimization &a href=&///?target=http%3A//web.stanford.edu/%7Eboyd/cvxbook/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Convex Optimization - Boyd and Vandenberghe&i class=&icon-external&&&/i&&/a&&/b&&/li&&ul&&li&Convex optimization有公开课视频，不想翻墙的话国内优酷网站上也有 (链接：&a href=&///?target=http%3A///v_show/id_XMjM0OTk5OTQ0.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Convex Optimization I Lecture 1&i class=&icon-external&&&/i&&/a&)，可惜没有字幕，不过正好也可以练一下听力，老师风趣幽默的很；国内有中译本《凸优化》，可以辅助阅读&/li&&/ul&&li&&b&Numerical Optimization &a href=&///?target=http%3A///us/book/1& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Numerical Optimization | Jorge Nocedal | Springe&i class=&icon-external&&&/i&&/a&r&/b&&/li&&ul&&li&经典的一本数值优化的教材，复旦大学吴立德老师讲授数值优化，优酷上也有公开课（链接：&a href=&///?target=http%3A///albumlist/show%3Fid%3Dascending%3D1%26page%3D1& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&吴立德《数值优化》 - 播单 - 优酷视频&i class=&icon-external&&&/i&&/a&）&/li&&/ul&&li&&b&Nonlinear Programming &a href=&///?target=https%3A///Nonlinear-Programming-Dimitri-P-Bertsekas/dp/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Dimitri P. Bertsekas, Dimitri P. Bertsekas&i class=&icon-external&&&/i&&/a&&/b&&/li&&ul&&li&国内有中译本《非线形规划》挺不错，实验同学正在看说挺通俗易懂的&/li&&/ul&&/ul&&p&若是深度学习方面的优化问题话&/p&&ul&&li&主要还是一阶优化算法，不深究理论从应用角度上看还算简单，强力推荐Bengio的&b&《Deep Learning》&/b&的第8章 &b&Optimization for traning deep models &/b&(书主页链接：&a href=&///?target=http%3A//www.deeplearningbook.org& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Deep Learning&i class=&icon-external&&&/i&&/a&)，认真看完该章节便有全局的了解&/li&&li&实践的话，斯坦福的&b&CS231n Convolutional Neural Networks for Visual Recognition&/b&中的有神经网络训练的slides及notes，简直是良心的课程（链接：&a href=&///?target=http%3A//cs231n.stanford.edu/syllabus.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&CS231n: Convolutional Neural Networks for Visual Recognition&i class=&icon-external&&&/i&&/a&）&/li&&/ul&&p&Optimization是机器学习中非常非常重要的问题，基本上机器学习问题最后都会规约成一个目标函数去求解，optimization便是求解目标函数中参数的重要工具，建议学习时循序渐进，每遇到一个模型，其对应的优化算法搞懂，慢慢将知识串起来！日积月累，便了然于胸了！&/p&&br&&p&个人理解，有误之处，欢迎指正！&/p&
我稍微归纳总结一下：优化方面经典的三本优化著作,可根据自身情况选读Convex Optimization Convex optimization有公开课视频，不想翻墙的话国内优酷网站上也有 (链接：)，可惜…
其实stochastic optimization和distributed optimization都不是新问题&br&distributed optimization早期的研究可以追溯到80年代，stochastic optimization更是大家都已经在用的老生常谈的算法。之所以，现在这两个问题依旧是热门研究领域，主要是这几年数据增多，出现的很多优化问题需要足够快的算法，尤其是机器学习领域，大量的“&b&模型求解问题&/b&”本质上都是“&b&数值优化问题&/b&”和“&b&采样问题&/b&”。而常用的优化算法，比如Gradient Descent(梯度下降)，Newton method(牛顿法)等计算量太大，不能满足需求。为了应对大规模的优化问题，常见的两种思路就是引入stochastic和distribution。&br&&br&这两年，这方面的工作急剧增多。&br&&br&stochastic optimization方面，原始的SGD是一种sublinear convergence的算法(在strongly convex条件下)，这几年，&b&SAG&/b&、&b&SVRG&/b&、&b&SAGA&/b&等有linear convergence的SGD算法引起比较大的关注，算是stochastic optimization方面的新进展，我把这几篇论文的地址贴在下面(注意，其实这都不是入门级的paper)：&br&1. SAG: &a href=&///?target=http%3A//papers.nips.cc/paper/4633-a-stochastic-gradient-method-with-an-exponential-convergence-_rate-for-finite-training-sets.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&papers.nips.cc/paper/46&/span&&span class=&invisible&&33-a-stochastic-gradient-method-with-an-exponential-convergence-_rate-for-finite-training-sets.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&2. SVRG: &a href=&///?target=http%3A//www.stat.rutgers.edu/home/tzhang/papers/nips13-svrg.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&stat.rutgers.edu/home/t&/span&&span class=&invisible&&zhang/papers/nips13-svrg.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&3. SAGA:
&a href=&///?target=http%3A//papers.nips.cc/paper/5258-saga-a-fast-incremental-gradient-method-with-support-for-non-strongly-convex-composite-objectives.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&papers.nips.cc/paper/52&/span&&span class=&invisible&&58-saga-a-fast-incremental-gradient-method-with-support-for-non-strongly-convex-composite-objectives.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&除了SGD的发展，stochastic coordinate descent方面也是出现了一对papers。&br&&br&distributed optimization方面，这方面的工作分成两类，一类是系统，另一类的理论分析。系统方面比如有 &a data-hash=&13fd0fce2affd948bfd821a8f7ed10f3& href=&///people/13fd0fce2affd948bfd821a8f7ed10f3& class=&member_mention& data-editable=&true& data-title=&@李沐& data-tip=&p$b$13fd0fce2affd948bfd821a8f7ed10f3& data-hovercard=&p$b$13fd0fce2affd948bfd821a8f7ed10f3&&@李沐&/a& 他们做的基于parameter server的优化系统(BTW, 他们的论文中了OSDI)，还有MSRA前段时间发布的DMTK。distributed optimization理论方面可以分成两类，一类是同步分布式/并行算法，如下面两篇Martin Jaggi他们做的：&br&1. COCOA: &a href=&///?target=http%3A//papers.nips.cc/paper/5599-communication-efficient-distributed-dual-coordinate-ascent.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&papers.nips.cc/paper/55&/span&&span class=&invisible&&99-communication-efficient-distributed-dual-coordinate-ascent.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&2. COCOA+: &a href=&///?target=http%3A//arxiv.org/pdf/v2.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&arxiv.org/pdf/&/span&&span class=&invisible&&8v2.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&另一类是异步分布式/并行算法，比如&br&1. Hogwild!:
&a href=&///?target=https%3A//www.eecs.berkeley.edu/%7Ebrecht/papers/hogwildTR.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://www.&/span&&span class=&visible&&eecs.berkeley.edu/~brec&/span&&span class=&invisible&&ht/papers/hogwildTR.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&(注意，上面的说法可能有点混淆 分布式 和 多线程并行，但是从算法收敛性分析角度看，其实很相似)&br&&br&回到题主关心的问题 “&b&推荐两篇入门的文章&/b&”，以上提到的算法本质都是first-order optimization算法，这方面很多东西的基础其实是共通的，如果对optimization感兴趣，可以看看Nesterov的著作：&a href=&///?target=https%3A///citations%3Fview_op%3Dview_citation%26hl%3Den%26user%3DDJ8Ep8YAAAAJ%26citation_for_view%3DDJ8Ep8YAAAAJ%3A1qzjygNMrQYC& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Introductory lectures on convex optimization&i class=&icon-external&&&/i&&/a&
其实stochastic optimization和distributed optimization都不是新问题 distributed optimization早期的研究可以追溯到80年代，stochastic optimization更是大家都已经在用的老生常谈的算法。之所以，现在这两个问题依旧是热门研究领域，主要是这几年数据增…
&p&&b&少年，如今这个时代，单纯看书是不够的，请配合大牛的课程vedio一起学习！&/b&&/p&&p&（1）如楼上所说的，S. Boyd and L. Vandenberghe. 写的书 &Convex Optimization&
听说不错，我没看过... 然后S.Boyd 还给了配套的课程video可以一起学习 &a href=&///?target=http%3A//web.stanford.edu/class/ee364a/videos.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&EE364a: Lecture Videos&i class=&icon-external&&&/i&&/a&, 听说有新版本的video ，我没找到。&/p&&p&( 2 ) CMU 有个老师叫Ryan T 开了门Convex Optimization上过一些，感觉不错，我没看完，你可以试试，这里是链接：&a href=&///?target=http%3A//www.stat.cmu.edu/%7Eryantibs/convexopt/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Convex Optimization&i class=&icon-external&&&/i&&/a& 。&/p&&p&（3）Nesterov 的《Introductory Lectures on Convex Programming》推荐你看看前两章引入convex 概念的，写的挺好的。我写过一篇读这个文章的小笔记，你可以辅助着看：&a href=&/p/& class=&internal&&从Nesterov的角度看：我们为什么要研究凸优化？ - 知乎专栏&/a&&/p&&p&（4）关于 Stochastic 的算法 我还推荐你看看 L
Bottou 的 &a href=&///?target=https%3A//arxiv.org/abs/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&[] Optimization Methods for Large-Scale Machine Learning&i class=&icon-external&&&/i&&/a&
确实写的不错，我看了开头，写了点读书心得，可以对照着看看&a href=&/p/& class=&internal&&为什么我们更宠爱“随机”梯度下降？&/a&&/p&&p&（5）评论里 &a class=&member_mention& href=&///people/aed503baa23abcf3e1117f& data-hash=&aed503baa23abcf3e1117f& data-hovercard=&p$b$aed503baa23abcf3e1117f&&@各人&/a& 给出的意见感觉还蛮中肯的，故复录于下：入门凸优化的话看el ghaoui那本optimization models可能好点，毕竟从线代开始讲，而且很多proof和一些涉及到几何/分析的东西都被带过了。凸分析必须boyd了，虽然那本实际上还是require不少mathematical maturity的。boyd那本书我非常喜欢，一点废话都没有解释的特别清楚，书后习题也非常有意思，我自己是把lp/qp/duality那几章全部刷了一遍。&/p&&p&&br&&/p&&p&&b&如果纯粹学习，看看（1）就够了，想做做research 那么（2）（3）（4）都看完了，也不够，哈哈哈哈哈！！！&/b&&/p&&p&&br&&/p&&p&最后，你如果热情不减，还想继续了解优化算法，欢迎关注&b&我&/b& &a class=&member_mention& href=&///people/08b0dcfca079& data-hash=&08b0dcfca079& data-hovercard=&p$b$08b0dcfca079&&@王哲&/a& 和&b&我的专栏&/b&。。。&b&我会写写自己学习凸\非凸优化的心得&/b&，大家一起学习交流。&/p&&p&&a href=&/optimization& class=&internal&&非凸优化学习之路 - 知乎专栏&/a&&/p&&p&第一篇文章是： &a href=&/p/& class=&internal&&从Nesterov的角度看：我们为什么要研究凸优化？ - 知乎专栏&/a&&/p&&p&第二篇文章是：&a href=&/p/& class=&internal&&非凸优化基石：Lipschitz Condition - 知乎专栏&/a&&/p&&p&第三篇文章是：&a href=&/p/& class=&internal&&当我们谈论收敛速度时，我们都在谈什么？ - 知乎专栏&/a&&/p&&p&&br&&/p&&p&&b&最最后，从大量知识的喜悦中脱离一下，点个赞呗。&/b&&/p&
少年，如今这个时代，单纯看书是不够的，请配合大牛的课程vedio一起学习！（1）如楼上所说的，S. Boyd and L. Vandenberghe. 写的书 &Convex Optimization& 听说不错，我没看过... 然后S.Boyd 还给了配套的课程video可以一起学习 , …
&p&我基于自己的理解聊一聊凸优化，具体实际中的凸优化的用处各位答主也给出了相应的答案，在此就不赘述。因为不了解题主的背景和基础，就尽量浅显地谈起吧，不会放太多理论推导。不过在看我的回答之前，可以先了解下凸函数、凸集、凸锥（简称“三凸”）的定义。&/p&&p&首先，我们还是要看下，什么是凸优化？抛开凸优化中的种种理论和算法不谈，纯粹的看优化模型，&b&凸优化就是：1、在最小化（最大化）的要求下，2、目标函数是一个凸函数（凹函数），3、同时约束条件所形成的可行域集合是一个凸集。&/b&以上三个条件都必须满足。而世间万物千变万化，随便抽一个函数或集合它都可能不是凸的。&/p&&p&所以，先回答题主的第一个问题，&b&这个世上的绝大部分优化问题当然不是凸优化问题&/b&。既然如此，为什么凸优化这么重要呢，以及凸优化有什么用呢？（另外，凸优化并不能看成是某一种优化方法）无非三点：&/p&&p&&b&1、还是有相当一部分问题是或等价于凸优化问题。&/b&有许多问题都可以直接建立成凸优化模型（比如：线性规划LP（Linear Programming）、某些特殊的二次规划QP（Quadratic Programming）、锥规划CP（Conic Programming）其中包括：要求约束中变量落在一个二阶锥里的二阶锥规划SOCP（Second Order Cone Programming）、要求约束中变量是半正定矩阵的半定规划SDP（Semi-Definite Programming）等）。以上这些类型，总之就是要符合凸优化上述的要求。需要说明的就是，许多可行域都可以看作是凸锥（Convex Cone）的交集，所以将以上一些类型的约束混合起来，依然是凸优化问题。&/p&&p&另外还有一些问题，可以等价的转化为凸优化问题。例如 Linear-Fractional Programming (LFP)，目标函数是两个仿射函数（Affine Function）的比，约束是一个多面体。这种目标函数具有既是拟凸又是拟凹的性质，通过一个叫做 Charnes-Cooper transformation 的转化，可以变成一个线性规划。同时，如果我们要最大化 LFP 的目标函数，且其约束仅是一个0-1整数约束（这显然不是一个凸集），我们可以将其直接松弛（Relax）成0到1的约束，并且和原问题等价。因为最大化拟凸函数，最优值一定可以落在可行域的极点上。这个结论可以用来帮助解决 Multi Nomial Logit（MNL）选择模型下的商品搭配问题（ Assortment Optimization）。&/p&&p&又例如，与组合优化相关的整数规划模型里，当最小化一个线性函数 &img src=&///equation?tex=c%5ETx& alt=&c^Tx& eeimg=&1&& ，变量 &img src=&///equation?tex=x& alt=&x& eeimg=&1&& 只能取整数，约束条件为 &img src=&///equation?tex=Ax%5Cgeq+b& alt=&Ax\geq b& eeimg=&1&& 时，如果 &img src=&///equation?tex=b& alt=&b& eeimg=&1&& 为整数向量且 &img src=&///equation?tex=A& alt=&A& eeimg=&1&& 是完全幺模（Totally Unimodular）的矩阵，我们可以将原问题松弛，即将整数约束去掉，变成线性规划。此时的最优解必然仍为整数，且即是原问题的最优解。这一结论经常用于调度（Scheduling）问题和指派（Appointment）问题。以上两类问题即是与凸优化直接等价的问题，还有一些优化问题本身就是NP-Hard，怎么处理我们后面再说。&/p&&p&&b&2、大部分凸优化问题解起来比较快，也即多项式时间可解问题（P）。&/b&如果你的问题能直接或间接&b&（但必须是等