经典论文 之 亮劼导读 第二期
我爱计算机 作者：洪亮劼
【2017-03-01】NIPS 2016 其他文章精选
NIPS 2016精选文章分类导读
之前我们已经分享了不少NIPS 2016的文章。在这里，我们对剩下的文章中的精华部分按照分类进行简单的导读，希望能够对读者有所启发。
Optimization
- 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 withreplacement的基础上的。SGD基于Without-Replacement的分析则较少见到，然而从Practice的角度来说，Without-Replacement的Sampling又更加常见。那么这篇文章弥补了这么一个空白。文章的主要贡献是对于SVRG的分析，在常规情况下，以及在Distributed Learning的情况下，SVRG的表现都很不错。 - Regularized Nonlinear Acceleration[NIPS 2016]
这篇文章讨论的是Strongly Convex的优化问题中的加速问题。所谓加速，就是指在用一阶方法（类似Gradient Descent）如果增快Convergence的速度。和以前的加速方法不同的是， 这篇文章提供的加速方法基于一个叫Approximate Minimal Polynomial Extrapolation的技术，并且这篇文章为这个技术提供了详细的理论证明。文章没有传统意义的实验。
Probabilistic Models and Estimation
- Global Analysis of Expectation Maximization for Mixtures of Two Gaussians[NIPS 2016]
EM算法已经在Statistical Learning中占据了很经典的位置。然而，大家可能有所不知道的是，关于EM算法的理论依据则相对比较薄弱。这篇文章其实并没有解决EM算法在一般通常意义下的理论讨论问题，而是解决了一个非常简单的特例，那就是Mixtures of Two Gaussians的情况。 - Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences[NIPS 2016]
这篇文章和上一篇文章很类似，也是在研究经典的Gaussian Mixture Models（GMM）。这篇文章的核心内容是说，在Component的数目大于等于3的情况下，Population Likelihood可能会有非常差的Local Maxima，而EM Algorithm有可能被Trap到这些Local Maxima里面。文章提供了一些理论证据来说明，小心的初始化非常重要。
Deep Learning
- Conditional Generative Moment-Matching Networks[NIPS 2016]
这篇文章是把最近提出的Generative Moment-Matching Networks（GMMN）延伸到了Discriminative Modeling的情况（也就是说的Conditional的部分）。那么这个GMMN到底是什么意思呢？简单说来，类似于GAN，GMMN定义了一个基于Maximum Mean Discrepancy（MMD）为目标函数的训练深度网络的方法。所谓MMD其实简单说来就是测量两个分布是否相同的一个工具。那么这篇文章，延伸了MMD到Conditional的情况，并且以此为一个目标函数来训练深度网络。 - Swapout: Learning an Ensemble of Deep Architectures[NIPS 2016]
这篇文章介绍了一个新颖的训练深度结构的方法叫做Swapout。简单说来，Swapout允许每一个Unit可以被Drop，或者整个Blocks都被Skip。也就是集成了之前的Dropout和Stochastic Depth Skips两方面的优势。这篇文章可以泛读一下，总体感觉理论依据比较薄弱，更像是Dropout的一个简单延伸。 - Architectural Complexity Measures of Recurrent Neural Networks[NIPS 2016]
这篇文章来自一个庞大的作者群。总的目标说起来，就是想给RNN一种架构的复杂度描述。那么，这篇文章提出了三种复杂度：Recurrent Depth、Feedforward Depth以及Recurrent Skip Coefficient。这篇文章不仅从理论上论证了这三种量度的存在，而且用了一系列实验对这三种量度进行了解释。如果你对于深度学习模型的理论框架有兴趣，建议泛读这篇文章。 - On Multiplicative Integration with Recurrent Neural Networks[NIPS 2016]
这篇文章认为，传统的RNN框架都尝试用Additive Building Block的模式把各个模块组合起来。那么，这篇文章希望使用”乘积“的模式。作者们展示了这种“乘积”模式比“加和”模式要好的一些原因。文章有大量的实验部分。总体来说，这是一个“小改动”的文章。
【2017-02-27】WSDM 2017其他文章精选
WSDM 2017的其他文章精选
Neural Survival Recommender [PDF]
这篇文章也来自于CMU的Alex Smola组。文章的核心内容是如何用LSTM同时预测推荐系统的用户偏好以及用户的下一次活跃时间（返回站点的时间）。文章的核心的思想还是比较直观的。不过依然觉得是LSTM等Deep Learning思想的比较“浅”的应用。对于推荐领域的读者来说，建议泛读。
Managing Risk of Bidding in Display Advertising [PDF]
这篇文章来自北京大学、上海交通大学，YOYI以及University College London的学者们。传统上，在RTB中，Bid的模型都没有考虑到整个CTR的Uncertainty，也就是说以前的Auction算法中往往采用的是CTR的点估计（Point Estimation）。这篇文章的一个贡献就是提供了一个有Closed-form的CTR Distribution。然后再把这个Distribution的Mean和Variance给应用到Value-at-Risk这一个理论中。这篇文章建议有广告背景的读者精读。有推荐或者搜索背景的读者可以泛读，特别是CTR Distribution的内容以及Value-at-Risk的一系列理论。
A Comparison of Document-at-a-Time and Score-at-a-Time Query Evaluation [PDF]
这篇文章讲的是搜索引擎中的Index的Query Evaluation的方法比较。在当前各种Open Source（比如，Lucene或者Solr）搜索引擎大行其道的今天，这样的文章貌似没有什么价值。但是，其实这样的文章能够带领一般的读者对于Query Evaluation技术有一个比较大概的了解，其实是非常有价值的科普文章。比如这篇文章中提到的WAND,BMW以及JASS都是Query Evaluation领域的经典算法，当你的Lucene或者Solr或者Elastic Search运行很慢的时候，你也许还是需要知道一些底层的原理。
Trustworthy Analysis of Online A/B Tests: Pitfalls, Challenges and Solutions [PDF]
这篇文章来自微软的一批学者。文章对工业界做Online Test很有指导价值。这篇文章说的是这么一个很实用的场景。那就是在做A/B Testing的时候，我们Randomization的Unit和我们做分析的Unit很有可能不一样（比如按照页面做Randomization，却要用用户做分析），那么在这样的情况下，IID的假设可能就不成立，特别是在计算Variance的时候，常常就会有问题。这篇文章解决的就是在Unit不一样的情况下，给出了一个一般意义的Variance的计算公式。这篇文章非常适合工业界需要做A/B Testing的读者精读。
【2017-02-26】Learning from User Interactions in Personal Search
WSDM 2017文章，讲如何解决“个人搜索”问题，来自Google的团队作者
文章地址：WSDM 2017
这篇文章来自Google的个人搜索团队，所有作者都是信息检索界响当当的学者。Marc Najork之前来自微软硅谷研究院，曾是ACM Transaction on Web的主编。微软硅谷研究院解散之后来到Google。而Donald Metzler、Xuanhui Wang以及Michael Bendersky都是信息检索界大牛W. Bruce Croft的得意门生。
这篇文章是要解决所谓个人搜索（Personal Search）的问题。个人搜索，顾名思义，也就是说对个人的文档进行搜索（比如电子邮件、文本文件、图片、资料等）。由于这样特殊的产品需求，传统的很多方法都不能够直接适用。另外一个特殊的需求就是，由于涉及到用户的个人隐私，不能够盲目把不同用户的信息交互到一起。
要解决这些问题，这篇文章提供了这样一个基本思路，那就是把用户的Query以及文档都映射到一个Attribute的空间。在这个空间里，所有的信息都可以跨用户横向比较。那么，下面的问题就是我们如何把这些信息给映射到这个Attribute的空间。作者们采用了构建一个图（Graph）的做法。在这个图上有四个类型的节点，文档、Query、文档的Attribute和Query的Attribute。两种节点之间的链接是通过Feature Function来定义的。这一点很像Markov Random Field的构建。这也难怪作者之一的Donald Metzler曾经是提倡使用这类模型的主要推手。那么定义这个一个Feature Graph，之后作者们提出了两种思路来使用这个Feature Graph，一种就是直接用机器学习的方法；另一种则是手工方法和机器学习方法的混合。这篇文章采用了第二种方法，因为这样在一个生产系统中可能更加稳定。从整体上来看，整个技术层面并不复杂，不过这里的思路相对来说比较新颖。同时，作者还提到了如何从点击数据中提取有效的训练数据。
在最后的实验方面，作者们展示了提出的这种方法的有效性。不过，值得一提的是，因为数据集和整个问题的特殊性，这篇文章并没法和很多其他方法进行公平比较。所以，文章值得对搜索和信息检索研究有兴趣的读者泛读。
【2017-02-26】Recurrent Recommender Networks
WSDM 2017文章，讲如何把深度学习和推荐系统相结合。
文章地址：WSDM 2017
这篇文章来自卡内基梅隆大学的Alex Smola的实验室以及谷歌研究院的Amr Ahmed，阵容可谓非常强大。
从传统的概率图模型（Probabilistic Graphical Model）的角度来说，要想能够对时间信息（Temporal）进行有效建模，则必须采用Sequential Monte Carlo等其他办法。这些办法往往计算非常复杂而且极易出错。所以，这篇文章希望通过RNN来帮助这样的建模场景。
说白了，文章就是希望能够用RNN来对现在的观测值以及模型参数的时间变化进行统一建模。当然，另外一个比较好的选择就是LSTM。这篇文章采用了LSTM。有了时间的变化以后，在单一时间的Rating Prediction，则是用户方面信息和物品（文章中采用的是电影）信息的点积，非常类似传统的矩阵分解模式。有一个小改动的地方来自于最后的预测结果是一个与时间有关的变化和与实践无关变量的一个分解。这一点主要是为了让不同时间段的变化都能够被模型解释。这么看似简单一个模型最大的问题其实是优化算法，如果使用简单的Back-propagation，计算量则会很大。这篇文章采用了一个叫Subspace Descent的方法，使得优化算法本身能够比较便捷。
在实验中，文章比较了TimeSVD++以及之前提出的AutoRec，在IMDB和Netflix的数据集上都有显著的提高。当然，从比较大的角度来看，这篇文章的意义其实非常有限，主要是最近类似思路的文章其实已经有不少，并且从学术贡献来看，这篇文章并且真正完全解答如何用深度学习和推荐系统结合的更加的根本问题。这篇文章适合熟悉推荐系统的读者快速阅读。
【2017-02-24】Learning Sensitive Combinations of A/B Metrics
WSDM 2017文章，来自俄罗斯搜索引擎团队Yandex，讲如何通过学习，来构建A/B Testing的指标
文章地址：WSDM 2017
这篇文章来自俄罗斯搜索引擎团队Yandex。近几年以来，Yandex的研究人员已经陆续发表了一系列的文章来推动在线A/B实验的研究和实践。
这篇文章是要解决什么问题呢？在A/B在线测试中，我们希望观测到的指标有方向性，能够告诉我们用户的喜好变化；同时，我们也希望这个指标能够很容易观测，不需要大量的数据长时间观察。这篇文章提出了这么一个假设，那就是我们能否通过数据以及历史信息，学习到一组指标的组合，使得这个学习到的结果满足上述条件呢？
Yandex通过对8个关键指标的建模，使得学习到的指标达到了3.42倍的“敏感度”（Sensitivity），相比于之前的指标而言，也就是达到了约11倍的Sample Size的削减，可以说效果非常显著。
那么，这篇文章的作者是如何做的呢？首先，每一个实验单元（可以是一个用户，一个Session或者一个Query）都被一个Feature Vector所描述。这里的Feature Vector，有可能就是我们已知的指标本身。那么，整个问题的设置就成为了，学习一个这些Feature Vector的线性组合，使得学习到的新指标对于未来的实验，更加具有“敏感度”。在这篇文章里，作者讨论了多种定义“敏感度”的方法，而最终采用的是通过z-score来衡量。这样的选择，非常接近普通的t-test的需要。也就使得这篇文章的实用度更加广泛。
如果来解这么一个优化问题就成为了文章下一个重点。文章简单介绍采用Geometric的方法来接这个优化问题的思路，并且也探讨了一下这种方法和Linear Discriminant Analysis的联系。然而作者们认为这个思路并不适合大多数的情况，于是文章介绍了一个基于标准优化算法的思路。也就是，利用定义的“敏感度”z-score，作为衡量两个实验结果的“距离函数”，最终的目标函数是包括这么三个部分：1）尽量让已知A/B有效果的实验里的距离不减少；2）尽量让已知的A/A实验的结果不变化；3）尽量分离已知A/B实验效果不明显的结果。当然，这个目标函数是Non-Convex的，不过文章依然使用了L-BFGS来解这个优化问题。
从实验来说，作者们用了118个历史实验数据来学习这个函数，得到的效果都是学习到的指标能够更好的指导实验的结果，同时采用学习到的指标能够大幅度降低需要达到统计意义效果明显（Statistically Significant）的数据量，这对于真实的工业环境来说是非常有意义的方法。这篇文章建议所有工业界的读者精读。
【2017-02-22】Real-Time Bidding by Reinforcement Learning in Ad
WSDM 2017论文，讲如何把强化学习（Reinforcement Learning）融合到Real-Time Bidding中
文章地址：WSDM 2017
这篇文章的作者团队来自上海交大和伦敦大学学院（University College London）。这篇文章是继强化学习被应用到搜索和推荐领域之后，又一个把强化学习应用到一个重要领域的尝试。与推荐和搜索不同的是，RTB因为其实时性，更加讲究能够对于一个决策过程进行动态调整，从而能够提供最优的解决方案。
目前大多数Bidding算法或者是策略（Strategy）的核心问题，就是他们都是静态的一个决策过程。那么，这篇文章的主要思路就是用Markov Decision Process（MDP）来对RTB进行建模。MDP的一般建模，需要三个必备元素，那就是State、Action和Reward。这里，State是一个（当前时间，剩余预算，当前Feature Vector）这么一个三元组；Action则是以State为输入，输出一个少于当前预算的Bid；Reward在这篇文章里定义为在当前Feature Vector为输入情况下的点击率（CTR）或者是0（没有赢得Auction的情况）。MDP除了这三个要素以外，一般还需要定义从每一个状态跳转另外状态的转移概率。这篇文章里，转移概率是一个Feature Vector的概率分布和市场价格分布的一个乘积。市场价格分布取决于现在的Feature Vector和当前的Bid价格。
整个MDP的布局设置好以后，RTB的问题就转换成为了如何在MDP中找到最优Action的决策问题。和传统的MDP一样，文章介绍了通过Value Iteration的方式来找到最佳的Value函数，然后通过找到的Value函数，来找到最佳的Bidding策略。然而，这样的方法，只适合在比较小规模的数据上，原因是第一个阶段的得到最佳Value函数的步骤太过于耗时。文章介绍了一种在大规模数据上的思路，那就是去通过小数据来学习Value函数的表达，然后应用到大规模数据上。
这篇文章在两个数据集上做了实验，一个是PinYou的数据，另一个是YOYI的数据，数量都算是当前比较大的RTB数据集了。从实验结果上来看， 采用MDP的方法比能够比其他方法大幅度有效得提高CTR，以及各项指标。除了在这两个数据集上的结果以外，这篇文章还在Vlion DSP的线上系统进行了评测，在CTR基本和以前方法持平的情况下，CPM和eCPC都更加有效。
总之，这篇文章对于希望探索强化学习在广告或者是推荐以及搜索等领域的应用有着一定的借鉴意义。从目前的情况下来看，算法依然比较复杂，而且Value函数的逼近可能有不小的性能损失。另外，这篇文章的参考文献部分十分详尽。对于想了解RTB的朋友来说，是一个不可多得的言简意赅的介绍。
【2017-02-21】Unbiased Learning-to-Rank with Biased Feedback
这篇文章获得了WSDM 2017最佳论文。
文章地址：WSDM 2017
这篇文章来自康奈尔大学的Thorsten Joachims以及他的学生。Thorsten在上一个十年的学术研究中，因为开发SVMLight而名声显赫。他也是最早思考如何利用用户反馈数据进行排序模型（Ranking Model）训练的学者。
那么，这篇获奖论文主要是要解决一个什么样的问题呢？其实，这篇文章要尝试解决的问题在学术和工业界的应用中非常普遍，可以说是一个困扰学者和普通的工程人员已久的一个问题。那就是，如何从“有偏差”用户反馈数据中，训练“无偏差”的排序模型。为什么用户反馈数据会“有偏差”呢？其实道理很简单，用户在和系统交互的时候，受到各方面因素的干扰，从而只对部分信息进行了反馈而忽略了其他信息。比如，在搜索引擎里，因为排版的因素，用户可能仅仅对排名靠前的几个文档进行查看，而彻底忽略排名靠后的所有文档，即便这些文档其实可能是相关的。另外一个更加常见的“偏差”则是由现在的“作业系统”（Production System）引起的。“作业系统”往往根据现有的算法或者模型选择出了用户可能最偏好的少部分文档，而大多数文档用户则没有可能见到，和前面情况一下，即便这些文档有可能是十分相关的。于是，用户的反馈就受到了现在系统的影响，而后面的机器学习很有可能仅能从现在系统的偏好中改进，而有可能无法提升到全局最优的情况。传统中，很多学者和从业人员已经意识到了直接使用用户“有偏差”反馈的数据，特别是点击数据，会产生问题。但是很长一段时间来，大家并没有找到如何系统得解决这个问题。
Thorsten首先在这篇文章中提出了基于Inverse Propensity Scoring（IPS）的Partial-Info Learning-to-Rank。这部分内容其实并没有太多的新意，不过是把从Multi-armed Bandit领域用IPS来做Unbiased Offline Evaluation的思路借鉴过来。不过文章指出了一个核心问题，那就是如何来估计这些Propensity Probability，其实也就是当前系统选择各个文档的概率。传统上，特别是以前的Unbiased Offline Evaluation基于随机产生文档顺序，因此这些Propensity Probability都是Uniform分布的。但这样的设计在现实中是不可能的，因为Uniform分布的文档，用户体验会变得很差。那么，这篇文章则是要直击这个痛点。这篇文章采取了这样一个思路。 那就是，文章假设现在系统的“偏差”可以通过一个Position-based Click Model with Click Noise（PCMCN）来解释。简单说来PCMCN就是来对用户查看一个排序文档进行建模，从而达到可以Propensity Probability能够被方便预测，这么一个目的。为了能够PCMCN，作者们还提出了一个基于交换两个位置文档的实验方法，用于收集数据。值得肯定的是，仅仅交换两个位置文档的方法，相比于以前的Uniform的方法，要更加注重用户体验。
文章的实验部分展示了在人工数据以及真实系统中的表现。总体说来，能够对“有偏差”的用户数据建模，比直接利用这些数据，训练的模型效果要来的好得多。这篇文章非常值得推荐系统、搜索引擎等方面的研究和工程人员精读。
