亮劼导读 第一期
我爱计算机 时间：2017年1月
作者：洪亮劼 ，Etsy数据科学主管，前雅虎研究院高级研发经理
声明：“亮劼导读”精选自作者个人微博的《论文每日读》系列，经作者授权定期发布。如需阅读时效性更强的论文，请关注作者个人微博。
【2017.01.16】NIPS 2016 Tutorial 优化问题
最近几年，大数据（BigData）以及深度学习（DL）的发展，使得机器学习(ML)以及人工智能技术（AI）的普及成为了可能性。在烟花繁多的DL发展的背后，有一条比较隐蔽的技术发展线路常常容易被人忽视，那就是优化算法（Optimization)的发展。在NIPS 2016上，优化算法专家Francis Bach以及Suvrit Sra做了一个关于优化的Tutorial，内容非常丰富，并且着重涵盖了优化算法在最近几年的比较大的发展。在这里我们就给大家对这个资料进行简单的导读。
信息点一 优化的论文究竟看什么
我们在具体谈论这个Tutorial之前，需要想一想这么一个问题，那就是对于这些资料，我们究竟要了解什么？因为对于很多非优化领域的学者或者技术人员来说，优化方面的技术文章常常充满了各式证明，而往往容易不得要领。对于在优化方面有研究兴趣的朋友来说，我们当然还是推荐仔细阅读这些资料，并且认真推演相关结论。而对于非优化领域的朋友来说，我们觉得需要了解这么两个重要内容：
- 哪些算法在哪些场景下是目前推荐的算法
- 这些算法的主要优缺点是什么
也就是说，从纯应用的角度来说，如何能够在有一个场景的情况下，找到自己需要的算法，并且很清楚知道这样算法的优缺点。那么，带着这样的目的，我们来看一看这个Tutorial的内容。
这个Tutorial其实就讲了两个问题，在单机情况下，如何对Convex以及Non-Convex的问题进行Finite-Sum优化。所谓Finite-Sum，其实就是指在有限数据集的情况下的优化问题。另外一个问题，则是在分布式的情况下，优化问题又有什么进展。我们下面就来看一看这两个问题。
信息点二 Convex的Finite-Sum问题
在传统的Convex领域，我们已经有两个Stochastic Gradient Descent（SGD）作为一个强有力的Baseline。那么，SGD的问题是什么？SGD的问题是在Finite-Sum的情况下，Convergence Rate要差于普通的Gradient Descent (GD)，也就是说，SGD对于优化来说，Convergence的速度要比GD要慢得多。
在这个Tutorial里，重点介绍了两个算法，第一个叫Stochastic Average Gradient（SAG），最早也是Bach等人发表在NIPS 2012上的。这个算法的核心思想就是保留SGD每一轮的Gradient信息，重新计算本轮Sample到数据的Gradient，利用所有数据Gradient的平均值进行计算。在Strongly-Convex的问题中，SAG能达到和GD类似的Convergence Rate，而在Non-Strongly-Convex的问题中，SAG能够比SGD要好得多。当然，SAG的劣势也很明显，那就是要存储所有的Gradient信息。
介绍的第二个算法，叫做Stochastic Variance Reduced Gradient（SVRG）。这个算法的好处是顾名思义，能对Gradient的估计起到Variance Reduction的作用。这个算法的好处是不需要存储所有的Gradient信息，而是在一个内循环的时候需要两次Gradient的Evaluation。Convergence Rate和SAG一样。
信息点三 Non-Convex的Finite-Sum问题
这里Non-Convex的领域，包括了对于一般神经网络的优化问题。那么，在这里，主要是对SVRG进行了重新分析，来证明SVRG其实也在Non-Convex的情况下可以运行的不错。当然，这里讲了在Non-Convex下的，SVRG的各种推广和扩展。有兴趣的朋友，可以看一看
这篇文章来了解一些具体内容。
信息点四 分布式优化问题
在大规模计算的情况下，特别是Mini-Batch的情况下，SVRG比SGD要优化得多。这是SVRG在这篇Tutorial里面反复被提及的又一个例证。同时，又一个很重要的观点，那就是在分布式优化的情况下，虽然异步（Asynchronous）更新很容易，也就是大家尝尝在分布式情况下做的，但这并不改变SGD的Convergence Rate。这里的推荐，依然是SVRG的异步版本，也就是各个单机自己先对SVRG进行计算，然后再集合信息。这方面已经有了不少Extension。
从整个Tutorial来说，我们可以看到一个明显的信号，那就是，只要有Finite-Sum的结构，就可以适用SVRG来解决，甭管是Convex还是Non-Convex，还是异步分布式的情况。这可以说是这个Tutorial最大的Takeaway。
【2017.01.10】NIPS 2016 Tutorial: Variational Inference
资料地址：PDF
在之前介绍的NIPS 2016介绍关于GAN的Tutorial中，Ian Goodfellow提到了除了GAN之外的Generative Models，其中最近几年比较火热的要数Variational Inference（VI)所带动的Graphical Models和Deep Learning（DL）的结合，以及VI本身在受到DL框架影响下走入的Automated Variational Inference的道路。
在今年NIPS 2016上，VI研究的领军人物David Blei及其实验室的Rajesh Ranganath，外加来自Google DeepMind的Shakir Mohamed一起做了一场关于VI现代方法以及前沿研究的Tutorial，内容非常详实也极具参考价值，同时也是对于曾经对VI有所了解的研究者来说很好的复习和重新学习的机会。在这篇短文里，我们就来导读一下这个Tutorial的内容。
信息点一 对于VI的基础和历史介绍
Tutorial把VI前后二十多年的发展，从八十年代开始借鉴统计物理的思想到九十年代后期Jordan写成著名的Review Paper，再到近期的发展动向，整个VI发展的主要脉络很清晰的表达了出来。重要的学者以及工作也都在Tutorial有所提及。由于David Blei的关系，Tutorial的基础部分很自然用到了LDA作为经典的模型案例。相信不少读者都是通过LDA来学习掌握VI的基本思想的。这部分的内容可以帮助大家复习VI到底要干什么以及什么是ELBO的概念。在熟悉了ELBO的概念之后，很自然的，传统VI的基本思路就是通过Mean-Field Approximation来对Variational Distribution进行分解和逼近。另外，在传统的VI的基础上如何衍生出Stochastic Optimization也是在这一波新发展之前的VI的最重要的革新。
信息点二 现代VI发展方向之自动化
熟悉DL的读者都知道，现代DL Framework如Tensorflow、Theano、MxNet等的核心就是能够对Neural Networks自动求导并且能够对Computational Graph进行自动运算，通过运算而优化目标函数。这样的好处是，不管模型怎么变化，优化过程都很类似。传统的Graphical Models则没有享受这样的便利，需要每一个模型单独推导优化过程。同时，因为模型的差异，这些优化过程的难易程度有很大的差距，因此对于推广Graphical Models并没有带来真正得好处。那么，如何对Graphical Models能够做优化自动化，就成为了VI在最近几年发展的重要方向之一。这里面，主要有两个思路：
- 利用Score Function Estimator
- ELBO的Pathwise Gradients
这两个思路都在Tutorial里有详细的说明，这里就不复述了。总之，核心思想就是对于ELBO难以直接计算的部分，进行简化或者估算，并且这样的操作是建立在对任意模型的基础上。这样，就能够达到对于整体运算的模块化，从而达到自动化的目的。
信息点三 现代VI发展方向之结构化逼近
因为在优化算法成为Graphical Models的瓶颈，因此传统的VI只能采取比较单一的Mean-Field Approximation，而这样的坏处自然是模型丧失了所有的结构，也就从某种意义上丧失了Graphical Models的核心意义。那么，因为优化算法可以逐渐做到自动化了，那么对于VI，自然得，大家就开始寻求更加真实，更加能够抓住数据结构的Variational Approximation。这方面近几年的尝试有利用Autoregressive Model，也有用Change-of-variables，和Auxiliary variables的。大家可以参考看看Tutorial。目前的感觉是，还没有看到采用更加复杂Approximation所带来的真正好处，并且是在优化算法大幅度复杂化的基础上。
整个Tutorial非常流畅，结尾处还罗列了所有重要的文献资料。这个Tutorial非常适合对于VI想进一步了解的学者学习。
【2017.01.05】NIPS 2016 Tutorial: GAN
文章地址：arXiv
2016年在Deep Learning界比较火热的概念无疑要数Generative Adversarial Networks（GAN）。年末的NIPS 2016大会上，GAN的提出者Ian Goodfellow做了一场Tutorial，详细介绍了GAN的一些细节和发展现状。日前，他把Tutorial的内容整理成了一篇有57页长的介绍文章。这里，我们对这篇文章进行导读，希望能够帮助读者理清GAN的一些信息。
信息点一：Generative Modeling的重要性
在文章中，Ian详细阐述了Generative Modeling的重要性。也就是说，相比于Predictive Modeling而言，Generative Modeling看重如何产生数据，而并不是提高预测精度等等。那么为什么要研究这类模型呢？有这么一些重要原因：
- 和Reinforcement Learning的关系，特别是能够在一个虚拟的环境中。这对于很多现实中可能产生灾难后果的场景来说至关重要。
- 可以用于Semi-supervised Learning。
- 可以更好的对Multi-modal的数据建模。
- 有一些Task需要有能力产生具有真实感的数据，比如创作艺术、比如图像到图像的翻译。
信息点二：Deep Generative Models的分类
这是这篇文章的出彩的地方之一。Ian并没有简单介绍GAN的基本原理，而是把GAN放在了一个更加大的背景中，把各种Deep Generative Models进行了分类，把各类模型的优劣进行了总结。对于这一节信息，建议对Deep Learning感兴趣的读者认真阅读。我们把这个分类图复制在下面供大家参考。
Deep Generative Models的分类
Ian在这一节的介绍时也道出了GAN的重点劣势，那就是训练GAN需要寻找一个Game的Nash Equilibrium，这可能是比Optimization Problem更加复杂的一类问题。
信息点三 GAN的原理和Trick
整篇文章的核心当然是讲解GAN的原理。这里需要一般读者特别注意的是，Ian对于GAN的描述非常严谨，那就是：
- 区分开了哪些是GAN的框架内容
- 哪些是Cost Function的选择
- 哪些是目前流行的GAN架构（DCGAN）。然后就是哪些是GAN和其他模型的联系。
这样读者可以非常明白得弄懂这些内容之间的联系。比如Cost Function这块，或者Training Process这块，哪些可能是有理论基础的内容，而哪些是Heuristic。建议读者精读这部分内容。
另外，读者也需要对于原理性的东西，以及Trick部分的内容进行区分。简单说来，Trick部分就是根据实际情况的经验，未必是放之四海而皆准的原理。
信息点四 研究前沿
从GAN的研究前沿，我们可以看出有这么些核心问题，GAN还并没有解决。
- 那么最重要的问题，可能就是训练有可能不收敛，并且容易有所谓Mode Collapse的问题。
Ian坦言这个问题可能直接导致GAN无法更加广泛应用。另外，如何利用学习到的Code的方式，目前感觉还非常Heuristic，这部分可能还需要更加自然的模型。
总之，这篇Tutorial非常值得细读。这里的信息点希望能够帮助到读者对于GAN的分析和体会。
【2017.01.04】NIPS 2016优化文章精选
在NIPS会议上，有这么一批文章，因为没有太多或者根本没有试验内容，常常被人忽视。在这里，我们对这些文章中的精华部分进行简单的导读，希望能够对读者有所启发。今天我们关注在“优化”这一主题。
- Optimal Learning for Multi-pass Stochastic Gradient Methods [NIPS 2016]
虽然通常情况下，优化理论文章都在讨论One-pass Stochasic Gradient Descent（SGD）的收敛情况，但这篇文章则是要讨论一个更加普遍的情况，那就是SGD多次遍历数据集。文章的主要贡献是证明了，在多次遍历数据的情况下，使用一个Fixed Step-Size可以达到最优的Error Bounds，同时，使用Mini-Batch并且使用比较大的Step-Size也可以达到同样的效果。 - A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing [NIPS 2016]
Factorization Machine（FM）是近几年兴起的比较通用的Predictive Model，常常用于广告和推荐场景。这篇文章把FM推广到了一般的情形（gFM），并且建立了FM和Rank-One Matrix Sensing之间的联系。同时，在这篇文章中，作者们还提出了One-Pass来解决gFM的算法。 - MetaGrad: Multiple Learning Rates in Online Learning [NIPS 2016] [长文]
这篇文章讲了这么一个思路，那就是同时运行多个Learning Rate，然后用一个Master Algorithm来结合这些Learning Rates。注意，这个算法和AdaGrad的区别是，最终整个算法依然只有一个Learning Rate而AdaGrad是每一个Dimension都有一个不同的Learning Rate。 - Without-Replacement Sampling for Stochastic Gradient Methods[NIPS 2016]
通常情况下，传统的理论文章对Stochastic Gradient Descent（SGD）的分析都是建立在Sample with replacement的基础上的。SGD基于Without-Replacement的分析则较少见到，然而从Practice的角度来说，Without-Replacement的Sampling又更加常见。那么这篇文章弥补了这么一个空白。文章的主要贡献是对于SVRG的分析，在常规情况下，以及在Distributed Learning的情况下，SVRG的表现都很不错。 - Barzilai-Borwein Step Size for Stochastic Gradient Descent [NIPS 2016]
这篇文章主要是把Barzilai-Borwein方法应用到SVRG和普通的SGD上。Barzilai-Borwein的主要思想就是逼近Hessian Matrix，从而达到不需要使用Step-size的目的。
