亮劼导读 第一期

时间:2017年1月
作者:洪亮劼 ,Etsy数据科学主管,前雅虎研究院高级研发经理
声明:“亮劼导读”精选自作者个人微博的《论文每日读》系列,经作者授权定期发布。如需阅读时效性更强的论文,请关注作者个人微博

【2017.01.16】NIPS 2016 Tutorial 优化问题

最近几年在优化领域有什么进展呢?归纳起来一点就是,能使用SVRG就是用SVRG!
​​

最近几年,大数据(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

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

2016年在深度学习界火热的无疑要数GAN,这里我们来导读一篇Tutorial文章。

​​文章地址: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的分类

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 2016优化理论文章的精选进行导读,期望对大家有所启发。

​​在NIPS会议上,有这么一批文章,因为没有太多或者根本没有试验内容,常常被人忽视。在这里,我们对这些文章中的精华部分进行简单的导读,希望能够对读者有所启发。今天我们关注在“优化”这一主题。

  1. 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也可以达到同样的效果。
  2. 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的算法。
  3. MetaGrad: Multiple Learning Rates in Online Learning [NIPS 2016] [长文]
    这篇文章讲了这么一个思路,那就是同时运行多个Learning Rate,然后用一个Master Algorithm来结合这些Learning Rates。注意,这个算法和AdaGrad的区别是,最终整个算法依然只有一个Learning Rate而AdaGrad是每一个Dimension都有一个不同的Learning Rate。
  4. 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的表现都很不错。
  5. Barzilai-Borwein Step Size for Stochastic Gradient Descent [NIPS 2016]​
    这篇文章主要是把Barzilai-Borwein方法应用到SVRG和普通的SGD上。Barzilai-Borwein的主要思想就是逼近Hessian Matrix,从而达到不需要使用Step-size的目的。
Report Story