全面解读ICML 2017五大研究热点 | 腾讯AI Lab独家解析

上图：本届ICML领域主席、腾讯AI Lab主任张潼博士现场发表演讲

下图：展台前络绎不绝的学者

以下为腾讯AI Lab机器学习团队在会后对五大研究领域的回顾与独家解析。

所提及论文下载地址：http://t.cn/R9WyXxz

强化学习是机器学习的重要分支，通过试错或模仿专家的方式学习可靠策略，解决序列决策问题。其应用领域包括视频游戏AI、无人驾驶、机器人控制、物流管理和仓储调度等。粗略统计，本届ICML有40余篇强化学习相关论文，涵盖了收敛性分析、连续控制、搜索与探索、多智能体与博弈论、模仿学习与转导、端到端深度强化学习等多个方面。

这次会议的研究中体现出三大特点：一、深度学习范式被广为采用，研究者将对问题的理解和先验知识做成了复杂网络模型的子模块，并采用端到端的方式训练；二、来自机器人领域的学者持续影响连续控制方面的研究；三、团队配合多智能体方面的研究吸引了越来越多的注意力。另外，「视频游戏与机器学习」研讨会（Workshop）环节发布了新的强化学习模拟器平台。我们重点关注了以下文章：

1） FeUdal Networks for Hierarchical Reinforcement Learning

本文由Google DeepMind发表。策略网络被划分为两个模块：管理者和工作者。管理者模块在低时间分辨率工作，产生中长期子目标；工作者模块在高时间分辨率工作，从管理者模块拿到子目标，并上原始的环境观测一起输出当前时刻的决策动作。本文这种精巧设计的网络结构能自动「发现」子目标，并自动学出相应的「子策略」，而之前的工作都采用了手调子目标的方式，在灵活性和通用性不如本文所提出的算法。

本文的管理者-工作者网络结构

实验表明该方法确实能够成功的自动发现「子目标」并学出「子策略」。下图展示了该方法在「蒙特祖玛的复仇」游戏环境[1]上的结果。

[1]该游戏特点是有多幕切换，奖励信号稀疏且延迟很长，例如在某一幕拿到了剑要再回到前两幕斩杀某个骷髅怪。

2）Improving Stochastic Policy Gradients in Continuous Control with Deep Reinforcement Learning using the Beta Distribution

本文由卡内基梅隆大学发表。假设输出的连续控制信号从Beta分布中采样，本文通过一个深度神经网络直接学习、预测Beta分布的两个参数。在连续控制的文献中，以往工作多采用高斯分布假设并直接学习和预测高斯分布的均值和方差。但高斯分布在数值上是无界的，对一些需要安全策略的场合这种性质极不合理。例如，自动驾驶中，左右打盘的角度无论如何不能太大。而Beta分布刚好满足左右有界这一性质（如下图）。

本文方法的实现非常简单但又十分有效，在机器人控制模拟环境mujoco的多个任务中取得的结果超过了基于高斯分布的连续控制方法（如下图）。

3） Coordinated Multi-Agent Imitation Learning

本文由加州理工大学、迪斯尼研究院和STATS公司（该公司有大量体育比赛的各类实际数据）联合发表，通过模仿学习方式学出多智能体控制模型。本文收集了大量英超足球比赛数据，使用结构学习方式自动学出智能体和实际数据的合理对应关系。这里的对应关系是指，比如当前智能体在某个具体位置到底是更适合学习前锋、前卫还是中场的行为。

通过动态构造对应关系，本文算法绕开了多智能体模仿学习中对应关系可能存在模糊或不确定性这一难题，例如边后卫助攻到前场后，到底该表现得更像后卫还是更像前锋。实验表明该方法学出的控制策略与专家数据（来自实际的英超比赛）更为接近，见下左图中的白圈，而定量结果可见下图右。

4）其他话题

在「视频游戏与机器学习」研讨会环节，暴雪公司宣布开源并发布《星际争霸2》的C++编程接口，开发者通过其可获得游戏内部状态、操纵游戏单位执行指定动作等。其还公布了几十万一对一比赛回放文件，记录了匿名玩家的操作序列。暴雪还与Google DeepMind合作，推出了相应的Python版本接口。

C++ APIs效果现场演示

Python接口，访问特征图层

另外，Facebook AI Research发布了新的强化学习框架ELF，其特点为支持多种环境-执行器的并发模型（一对一，多对一、一对多，多对多），这会为现代强化学习算法的实现，如模特卡罗树搜索（MCTS）和自我对战（Self Play），带来极大便利。

随机优化算法是指每次只随机采样一个或少量几个（Mini-batch）训练样本对模型更新的优化方法。因其有低内存消耗、低单次迭代计算复杂度等特点，被广泛应用于大规模机器学习模型训练中，包括绝大多数深度学习模型的训练。粗略统计，本届ICML有20余篇随机优化相关论文，大致可分为一阶随机优化、二阶随机优化和非凸随机优化三个大方向。

本次会议的相关论文中体现出两大特点：二阶随机优化算法被更多研究者所关注；非凸随机优化，特别是针对深度学习的非凸随机优化算法成为一个新的研究热点。我们重点关注了以下几篇论文：

1）Follow the Moving Leader in Deep Learning

本文由香港科技大学发表。在深度学习中，参数以及数据分布都会随着迭代进行不断变化，这使得深度学习模型的训练一直是一个具有挑战性的问题。针对这一问题，本文提出了全新的FTML算法，具有更快收敛速度。与已有优化算法（如FTRL）不同的是，本文的FTML算法迭代中，越新样本具有越大权重，这使算法更能适应数据分布变化，有更快收敛速度。多个数据集上深度学习模型训练实验结果显示，FTML比其他已有算法收敛更快。

模型训练实验结果

2）Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter

本文由微软研究院发表。随机梯度下降和梯度下降是当前求解非凸机器学习模型的常用方法，本文借用方差下降随机优化算法SVRG的关键思路，并对目标函数的强非凸性做更细致的分析，提出了针对于非凸随机优化问题的新算法Natasha，比目前标准算法更高效。作者的创新之处，是提出了一套针对强非凸函数更细致的分析方法，并在此基础上设计了针对非凸优化问题更精细的随机算法，能有效利用强非凸函数的结构信息。理论分析结果显示，在强非凸参数大于某个常数时，本文所提出的算法具有更低的计算复杂度。

计算复杂度对比结果

3）A Unifying Framework for Convergence Analysis of Approximate Newton Methods

本文由上海交通大学和北京大学联合发表。近似牛顿算法，如Sketched-Newton和Subsampled-Newton，是一类高效的二阶随机优化算法，因其单次迭代计算复杂度较低、收敛速度快等特点受到广泛关注。但已有理论的分析结果和其在实际应用中的性能表现在很多方面并不一致。本文为二阶随机优化算法提出了一套新的分析工具，解决了多个理论及应用中表现不一致的问题。

在创新点上，作者将多种近似牛顿算法统一到同一个算法框架中，对其局部收敛性质做统一分析，解决了多个理论分析结果和实际应用性能不一致的问题，并为新算法设计提供了新的思路。本文从理论上证明了：一、近似牛顿算法的线性收敛速度不需要Hessian矩阵满足Lipschitz连续，但是算法平方收敛速度需要此连续。二、Hessian矩阵的条件数和Sketched-Newton的性能不相关。 

连续（非）凸优化在机器学习中起着举足轻重的作用，大部分机器学习问题均可建模成某一类连续（非）凸优化问题。粗略统计，本届ICML大概有40篇连续优化的论文，其中半数以上为非凸连续优化内容。另外，由于深度学习的流行，一阶优化算法相关论文也占有相当大的比重。我们将重点介绍以下三个研究：

1）GSOS: Gauss-Seidel Operator Splitting Algorithm for Multi-Term Nonsmooth Convex Composite Optimization

这篇论文由腾讯AI Lab、中山大学和香港中文大学合作完成，提出了新的求解多块非光滑复合凸优化问题的算子分裂算法。该算法采用Gauss-Seidel迭代及算子分裂的技巧处理不可分的非光滑正则项。通过用单调算子理论，文中给出多块非光滑复合凸优化问题最优解集以及算法的等价刻画，并利用该等价刻画来巧妙的建立了所提算法的全局收敛性。最后本文以实验证实了该算法的有效性。

2）Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms

这篇论文由芝加哥大学和微软研究院共同完成，提出两类新的原对偶一阶算法来求解经验风险最小化的凸优化问题。通过自适应地利用样本数据中暗含的强凸性质，文中证明了这两类新算法的线性收敛速率。另外，通过利用Dual-free的技巧，文中将算法中Euclidean距离下的邻近算子替换为Bregman距离下的邻近算子，从而得到两类Dual-free原对偶算法变体。最后实验证明该算法的有效性。

3）Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to Non-smooth Concave Maximization

这篇论文由罗格斯大学和南京信息工程大学共同完成，作者首次建立了有稀疏约束的极小化问题Lagrange对偶理论。基于此，本文提出了求解具有稀疏约束的极小化问题的对偶硬阈值（Dual ITH）算法及其随机版本的变体，并在无需采样算子满足限制同构性质（RIP）的条件下建立了算法收敛性。这篇论文从实验上说明了该算法在具有稀疏约束的极小化问题上效果为目前最佳。