## AISTATS 2017精选论文

涉及人工智能、机器学习、统计学习理论等多方面技术的顶级会议-第20届人工智能和统计（The 20th International Conference on Artificial Intelligence and Statistics，多数时候简称 AISTATS 会议）今年4月20日-22日在美国弗罗里达州的劳德代尔堡（Fort Lauderdale）举行。历史上，AISTATS 相比于 ICML 或者 NIPS，是一个相对比较“轻量级”（主要是指大会的发表论文数目）的偏重理论和全方面统计学习的学术大会。这个会议的涵盖面非常广泛并且理论文章比较多，一般的读者很难从浩如烟海的文献中即刻抓取到有用信息，这里笔者从众多文章中精选出5篇有代表性的文章，为读者提供思路。

#### Stochastic Rank-1 Bandits

**概要：这篇文章探讨的是在一组列和行的向量所组成的乘积空间里做 Multi-armed Bandit 问题。文章对推荐系统有研究的学者和实践者有启发。**

文章作者来自于几个大学和 Adobe Research。其中 Branislav Kveton 和 Zheng Wen 在过去几年发表过多篇关于 Bandits 的文章，值得关注。

文章解决的是一个在应用中经常遇到的问题，那就是每一步 Agent 是从一对 Row 和
 Column 的 Arms 中选择，并且得到它们的外积（Outer Product）作为 Reward。这个设置从搜索中的 Position-based Model 以及从广告的推广中都有应用。

具体的设置是这样的，先假设我们有 K 行，L 列，在每一个时间 T 步骤中有一个行（Row）向量 u，从一个分布中抽取（Draw）出来，同时有一个列（Column）向量 v，从另外一个分布中抽取出来。这两个抽取的动作是完全独立的。在这样的情况下， Agent
 在时间 T，需要选择一个综合的 Arm，也就是一个两维的坐标，i 和 j，从而在 u 和 v 的外积（Outer Product）这个矩阵中得到坐标为 i 和 j 的回报（Reward）。文章指出，这个设置可以被当做是有 K 乘以 L 那么多个 Arm 的简单的 Multi-armed Bandit。那么当然可以用 UCB1 或者是 LinUCB 去解。然而文章中分析了这样做的不现实性，最主要的难点在 K 和 L 都比较大的情况下，把这个场景的算法当做原始的
 Multi-armed Bandit 就会有过大的 Regret。文章提出了一个叫做 Rank1Elim 的算法来有效的解决这个问题。我们这里不提这个算法的细节。总体说来，这个算法的核心思想，就是减少行和列的数量，使得需要 Explore 的数量大大减少。这也就是算法中所谓
 Elimination 的来历。

那么，怎么来减少行列的数量呢？虽然作者们没有直接指出，不过这里采用和核心思想就是
 Clustering。也就是说，有相似回报（Reward）的行与列都归并在一起，并且只留下一个。这样，就能大大减少整个搜索空间。文章主要的篇幅用在了证明上。

文章在 MovenLens 的数据集上做了一组实验，并且显示了比 UCB1 的 Regret 有非常大的提高。这篇文章适合对推荐系统的 Exploitation 和 Exploration 有研究的学者泛读。

#### Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method

**摘要：这篇文章讨论如何在大规模数据的情况下加速传统的 Stochastic Gradient
 的方法，使得最后的算法和目标的数据量无关 。**

这篇文章的作者们来自加州大学伯克利分校。作者之一 Michael Jordan 是机器学习的权威学者之一，曾经在概率图模型的时期有突出的贡献。

文章主要讨论大规模 Convex 优化的场景。在这方面，已经有了相当丰富的学术成果。那么，这篇文章的主要贡献在什么地方呢？文章主要想在算法的准确性和通讯成本上下文章。
具体说来，文章提出的算法是想在 Stochastic Variance Reduced Gradient（SVRG）上进行更改。SVRG 的主要特征就是利用全部数据的 Gradient 来对 SGD 的 Variance 进行控制。因此 SVRG 的计算成本（Computation Cost）是
 O((n+m)T)，这里 n 是数据的总数，m 是 Step-size，而 T 是论数。SVRG 的通讯成本也是这么多。这里面的主要成本在于每一轮都需要对全局数据进行访问。作者们提出了一种叫 Stochastically Controlled Stochastic Gradient（SCSG）的新算法。总的来说，就是对 SVRG 进行了两个改进：

每一轮并不用全局的数据进行 Gradient 的计算，而是从一个全局的子集 Batch 中估计 Gradient，子集的大小是 B。

每一轮的 SGD 的更新数目也不是一个定值，而是一个和之前那个子集大小有关系，基于
 Geometric Distribution 的随机数。

剩下的更新步骤和 SVRG 一模一样。然而，这样的改变之后，新算法的计算成本成为了
 O((B+N)T)。也就是说，这是一个不依赖全局数据量大小的数值。而通过分析，作者们也比较了 SCSG 的通讯成本和一些原本就为了通讯成本而设计的算法，在很多情况下，SCSG 的通讯成本更优。作者通过 MNIST 数据集的实验发现，SCSG 达到相同的准确度，需要比 SVRG 更少的轮数，和每一轮更少的数据。可以说，这个算法可能会成为 SVRG 的简单替代。对于大规模机器学习有兴趣的读者可以泛读。

#### Decentralized Collaborative Learning of Personalized Models over Networks

**摘要：如何在一个互联的网络情况下让每个节点学习一个可靠的模型是目前移动互联网时代所要解决的技术难题之一，本文提出了一个方案。**

文章的作者们来自法国 INRIA 和里尔大学（Universite de Lille）。文章讨论了一个非常实用也有广泛应用的问题，那就是所谓的 Decentralized Collaborative Learning 的问题，或者是说如何学习有效的个人模型（Personalized Models）的问题。

在移动网络的情况下，不同的用户可能在移动设备（比如手机上）已经对一些内容进行了交互。那么，传统的方式，就是把这些用户产生的数据集中到一个中心服务器，然后由中心服务器进行一个全局的优化。可以看出，在这样的情况下，有相当多的代价都放到了网络通信上。同时，还有一个问题，那就是全局的最优可能并不是每个用户的最优情况，所以还需要考虑用户的个别情况。

比较快捷的方式是每个用户有一个自己的模型（Personalized Models），这个模型产生于用户自己的数据，并且能够很快地在这个局部的数据上进行优化。然而这样的问题可能没法利用全局更多的数据，从而能够为用户提供服务。特别是用户还并没有产生很多交互的时候，这时候可能更需要依赖于全局信息为用户提供服务。文章提出了这么几个解决方案。首先，作者构建了一个用户之间的图（Graph）。这个图的目的是来衡量各个用户节点之间的距离。注意，这里的距离不是物理距离，而是可以通过其他信息来定义的一个图。每个节点之间有一个权重（Weight），也可以通过其他信息定义。在这个图的基础上，作者们借用了传统的 Label Propagation，这里其实是 Model Propagation 的方式，让这个图上相近节点的模型参数相似。在传统的 Label Propagation 方式下，此优化算法有一个 Closed-Form 的结论。当然，并不是所有的情况下，都能够直接去解这个
 Closed-Form 的结论，于是文章后面就提出了异步（Asynchronous）的算法来解这个问题。

异步算法的核心其实还是一样的思路，不过就是需要从相近的节点去更新现在的模型。作者们探讨了一个更加复杂的情况，那就是个人模型本身并不是事先更新好，而是一边更新，一边和周围节点同步。作者这里采用了 ADMM 的思路来对这样目标进行优化。这里就不复述了。比较意外的是，文章本身并没有在大规模的数据上做实验，而是人为构造了一些实验数据（从非分布式的情况下）。所以实验的结果本身并没有过多的价值。不过文章提出的
 Model Propagation 的算法应该说是直观可行，很适合对大规模机器学习有兴趣的学者和实验者精读。

#### Fast Bayesian Optimization of Machine Learning Hyper-parameters on Large Datasets

**摘要：这篇文章探讨了如何在 Pinterest 中对用户的意图进行描述。**

文章的作者是一队来自德国的学者，分别来自 University of Freiburg 和 Max Planck Institute for Intelligent Systems。讨论了一个很实际的问题，那就是如何对一个机器学习算法进行自动调参数。

文章针对这几年逐渐火热起来的 Bayesian Optimization，开发了一个快速、并且能够在大规模数据上运行的算法。传统的机器学习算法有很多所谓的超参数（Hyper-parameter）需要设置。而这些超参数往往对最后的算法性能有至关重要的影响。在一般的情况下，如何寻找最佳的超参数组合则成为了很多专家的必备“技能”。而对于机器算法本身而言，取决于算法的复杂程度，有时候寻找一组合适的超参数意味着非常大的计算代价。

这篇文章讨论了这么一个思路，那就是，既然在全局数据上对算法进行评估计算代价太大，可能对于直接调参过于困难，那能否在一个数据的子集上进行调参，然后把获得的结果看能否运用到更大一点的子集上，最终运用到全集上。这里，我们来回顾一下 Bayesian Optimization 的简单原理。首先，我们有一个“黑盒”的目标函数，任务是找到这个目标函数最小值所对应的参数值（超参数）。这里，我们需要一个这个目标函数的先验分布，同时我们还需要一个所谓的 Acquisition Function，用来衡量在某个点的参数值的
 Utility。有了这些设置，一个通常情况下的 Bayesian Optimization 的步骤是这样的：

用数值优化的方法在 Acquisition Function 的帮助下，找到下一个 Promising 的点；

带入这个 Promising 的点到黑盒函数中，得到当前的值，并且更新现在的数据集；

更新目标函数的先验分布以及 Acquisition Function。

通常情况下，Bayesian Optimization 的研究喜欢用 Gaussian Processes（GP）来做目标函数的先验分布。而对于 Acquisition Function，这里有好几种可能性，比如文章举了 Expected Improvement（EI）、Upper Confidence Bound（UCB）、Entropy Search（ES）等例子。文章使用了 EI 和 ES。这篇文章提出思路的第一步，是把原来那个黑盒函数增加了一个参数，也就是除了原来的超参数以外，增加了一个数据集大小的参数。这个参数按照比例（从0到1的一个值）来调整相对的数据集大小。那么，如何应用这个参数呢？这里的技巧是，在 GP 里，需要有一个 Kernel 的设置。原本这个
 Kernel 是定义在两组超参数之间的，在文章里，这个 Kernel 就定义在“超参数和数据集大小”这个 Pair 与另外一个 Pair 之间。于是，这里就能够通过已经经典的设置得到需要的效果。

文章还提出了一个新的 Acquisition Function 用来平衡 Information Gain 和
 Cost。文章用 SVM 在 MNIST 做了实验，还用 CNN 在 CIFAR-10 以及 SVHN 上做了实验，以及还用 ResNe t在 CIFAR-10 上做了实验。总体上说，提出来的算法比之前的方法快10倍到100倍。并且，相比较的一些其他算法（比如一开始就在全集上进行计算的方法）都没法完成实验。文章的基本思路和相关研究值得机器学习实践者学习。

#### Communication-Efficient Learning of Deep Networks from Decentralized Data

**摘要：这篇文章研究在分布网络的情况下，数据往往不是 IID 分布的，于是在这样的情况下进行大规模机器学习就成为了一种挑战，这篇来自 Google 的文章就是针对这样的挑战提出了一种简单实用的方法。**
 
文章作者来自 Google，核心内容是一个非常有实际意义的问题，那就是在分布式网络的情况下，如何构建合理的机器学习框架。

这里说的分布式网络，指的是类似于手机网络这样的系统，用户有不同的数据集合（按照统计意义来说，通常是非 IID 的），并且这里面主要的成本是通信成本，而非计算成本。传统的设置是不同的分布的数据可能是均匀 IID 的，而作者们认为在现实情况下，这是很难达到的一种状态。这里面还需要考虑的一些情况就是，如果作为手机客户端的话，每天能够参与优化模型的时间和次数都是有限的（根据电量等因素），因此如何设计一套有效的优化方案就显得非常必要。这篇文章提出的方案其实非常简单直观。算法总共有三个基本的参数，C（0到1）控制相对有多少数量的客户端参与优化，E 控制每一轮多少轮 SGD 需要在客户端运行，B 是每一轮的 Mini-Batch 的数目大小。算法的思路是：

每一轮都随机选择出 C 那么多的客户端；

对于每个客户端进行 Mini-Batch 的大小为 B，轮数为 E 的 SGD 更新；

对于参数直接进行加权平均（这里的权重是每个客户端的数据相对大小）。

文章对这里的最后一步进行了说明。之前有其他研究表明，如何直接对参数空间进行加权平均，特别是 Non-Convex 的问题，会得到任意坏的结果。文章中，作者们对于这样的问题处理是让每一轮各个客户端的起始参数值相同（也就是前一轮的全局参数值）。这一步使得算法效果大幅度提高。

文章在一系列的数据集上做了大量的实验，基本都是基于神经网络的模型，例如 LSTM、CNN 等。效果应该说是非常显著和惊人，绝大多数情况下，提出的算法能够在大幅度比较小的情况下，达到简单 SGD 很多轮才能达到的精读。虽然这篇文章提出的算法简单可行，并且也有不错的实验结果。但是比较令人遗憾的是，作者们并没有给出更多的分析，证明这样做的确可以让参数达到全局最优或者局部最优。对大规模机器学习有兴趣的读者可以精读这篇文章。