ICML 2018 | 腾讯AI Lab详解16篇入选论文

7月10日至15日,第 35 届国际机器学习会议(ICML 2018)将在瑞典斯德哥尔摩举行。ICML是机器学习领域最顶级的学术会议,今年共收到2473篇投递论文,比去年的1676篇提高47.6%,增幅显著。最终入围论文共621篇,接收率25%,与去年26%持平。

这是腾讯AI Lab第二次参与这一顶级会议,共有16篇论文入选,去年则入选4篇,均位居国内企业前列。我们将在下文中分三类介绍这些文章——新模型与新框架、分布式与去中心化、及机器学习优化方法与理论研究。有的研究具有多重贡献,并不严格按照研究内容区分。

第一部分:新模型与新框架

1、用于强化学习的基于反馈的树搜索

Feedback-based Tree Search for Reinforcement Learning

论文地址:https://arxiv.org/abs/1805.05935

蒙特卡洛树搜索(MCTS)已经在游戏智能体方面取得了很大的成功(比如 AlphaGo),但对于 Atari 或 MOBA 等需要快速决策的视频游戏,树搜索的速度却太慢了。针对这一问题,该论文提出了一种新型的基于模型的强化学习技术,可在原无限范围的马尔可夫决策过程的小型有限范围版本批量上迭代式地应用 MCTS。在以离策略的方式完成强化学习训练之后,智能体无需进一步的树搜索就能实现快速实时的决策。

研究者将这一思想融合到了一个基于反馈的框架中,其中 MCTS 会使用其根节点处生成的观察结果来更新自己的叶节点评估器。其反馈过程如下图所示:(1)从一批采样的状态(三角形)开始运行一组树搜索,(2)使用第 k 次迭代时的策略函数近似(PFA)πk 和价值函数近似(VFA)Vk 的叶估计被用于树搜索过程,(3)使用树搜索结果更新 πk+1 和 Vk+1。

研究者对该方法进行了理论分析,结果表明当样本量足够大且进行了足够多的树搜索时,估计得到的策略能够接近最优表现。这也是对基于批 MCTS 的强化学习方法的首个理论分析。

研究者还使用深度神经网络实现了这种基于反馈的树搜索算法并在《王者荣耀》1v1 模式上进行了测试。为了进行对比,研究者训练了 5 个操控英雄狄仁杰的智能体,结果他们提出的新方法显著优于其它方法,下图给出了他们的方法训练的智能体相对于其它智能体随时间的金币比值变化。

其中,NR 是指没有 rollout 但参数设置与该论文的新方法一样的智能体,DPI 是使用了直接策略迭代的智能体,AVI 是使用了近似价值迭代的智能体,SL 是一个在大约 10 万对人类游戏数据的状态/动作对上通过监督学习训练得到的智能体。

2、通过学习迁移实现迁移学习

Transfer Learning via Learning to Transfer

论文地址:

https://ai.tencent.com/ailab/media/publications//icml/148_Transfer_Learning_via_Learning_to_Transfer.pdf

迁移学习的三个核心研究问题是:何时迁移、如何迁移和迁移什么。为特定的迁移任务选择合适的迁移算法往往需要高成本的计算或相关领域的专业知识。为了能更有效地找到适合当前任务的迁移算法,研究者根据人类执行迁移学习的方式,设计了一种可根据之前的迁移学习经历提升新领域之间的迁移学习有效性的新框架:学习迁移(L2T:Learning to Transfer)。

L2T 分为两个阶段。在第一个阶段,每个迁移学习经历都会被编码成三个组件:一对源域和目标域、它们之间被迁移的知识(被参数化为隐含特征向量)、迁移学习带来的性能提升比。然后再从所有经历中学习一个反射函数(reflection function),该函数能将领域对和它们之间被迁移的知识映射到性能提升比。研究者相信这个反射函数就具备决定迁移什么和如何迁移的迁移学习能力。在第二个阶段,新出现的领域对之间所要迁移的内容则可以通过最大化所学习到的反射函数的值而得到优化。

为了证明这种迁移学习方法的优越性,研究者在 Caltech-256 和 Sketches 这两个图像数据集上对 L2T 框架进行了实验评估。下图给出了 L2T 及另外 9 种基准方法在 6 个源域和目标域对上的分类准确度。


可以看到,不管源域与目标域有较紧密的联系(比如 (a) 中的“galaxy”、“saturn”和“sun”)还是没有显著关联(比如 (c) 和 (f)),L2T 方法的表现都明显优于其它所有基准方法。

3、通过强化学习实现端到端的主动目标跟踪

End-to-end Active Object Tracking via Reinforcement Learning

论文地址:https://arxiv.org/abs/1705.10561

目标跟踪的目标是根据视频的初始帧中的目标标注定位该目标在连续视频中的位置。对于移动机器人无人机等视角会变动的平台或目标会离开当前拍摄场景的情况,跟踪目标时通常还需要对摄像头的拍摄角度进行持续调整。该论文提出了一种使用强化学习的端到端的主动目标跟踪方法,可直接根据画面情况调整摄像头角度。具体而言,研究者使用了一个 ConvNet-LSTM 网络,其输入为原始视频帧,输出为相机运动动作(前进、向左等)。

上图展示了这个 ConvNet-LSTM 网络的架构,其中的强化学习部分使用了一种当前最佳的强化学习算法 A3C。

因为在现实场景上训练端到端的主动跟踪器还无法实现,所以研究者在 ViZDoom 和 Unreal Engine 进行了模拟训练。在这些虚拟环境中,智能体(跟踪器)以第一人称视角观察状态(视觉帧)并采取动作,然后环境会返回更新后的状态(下一帧)。研究者还设计了一个新的奖励函数以让智能体更加紧跟目标。

实验结果表明,这种端到端的主动跟踪方法能取得优异的表现,并且还具有很好的泛化能力,能够在目标运动路径、目标外观、背景不同以及出现干扰目标时依然稳健地执行主动跟踪。另外,当目标偶尔脱离跟踪时(比如目标突然移动),该方法还能恢复对目标的跟踪。下表给出了不同跟踪方法在 ViZDoom 环境的几个不同场景上的表现比较,其中 AR 表示累积奖励(类似于精确度),EL 表示 episode 长度(类似于成功跟踪的持续帧数)。

最后,研究者还在 VOT 数据集上执行了一些定性评估,结果表明从虚拟场景学习到的跟踪能力也有望迁移到真实世界场景中。

4、使用局部坐标编码的对抗学习

Adversarial Learning with Local Coordinate Coding

论文地址:https://arxiv.org/abs/1806.04895

生成对抗网络(GAN)是近来一个非常热门的研究方向,也实现了一些成功应用。但 GAN 仍有一些局限性:很多研究都使用了简单的先验分布,GAN 在隐含分布的维度上的泛化能力是未知的。针对这些问题,研究者基于对图像的流形假设提出了一种全新的生成模型,该模型使用了局部坐标编码(LCC),可提升 GAN 在生成拟真图像上的表现。

上图展示了该论文提出的 LCC-GAN 方案。研究者首先使用了一个自动编码器(AE)在隐含流形上学习了嵌入来获取数据中的含义信息。然后,他们又使用 LCC 学习一组基数来在该隐含流形上构建局部坐标系统。之后,他们再通过使用一个与一组编码相关的线性函数来近似生成器而将 LCC 引入了 GAN。基于这种近似,他们再通过利用在隐含流形上的局部信息而提出了一种基于 LCC 的采样方法。LCC-GAN 的具体训练过程如下:

其中 LCC 采样方法分为两个步骤:(1)给定一个局部坐标系,我们随机选择一个隐含点(可以是一个基(basis)),然后找到其 d-最近邻点;(2)我们构建一个 M 维向量作为采样的 LCC 编码。其中,该向量的每个元素都对应于那个基的权重

研究者用 PyTorch 实现了 LCC-GAN 并通过大量基于真实世界数据集的实验对该方法进行了评估。结果表明 LCC-GAN 的表现优于其它多种 GAN 方法(Vanilla GAN、WGAN、Progressive GAN)。下图展示了 LCC-GAN 和 Progressive GAN 基于 CelebA 数据集的人脸生成结果比较。


研究者还推导了 LCC-GAN 的泛化界限,并证明维度较小的输入就足以实现优良的泛化表现。

5、一种可变度量超松弛混合临近外梯度方法的算法框架

An Algorithmic Framework of Variable Metric Over-Relaxed Hybrid Proximal Extra-Gradient Method

论文地址:https://arxiv.org/abs/1805.06137

极大单调算子包含(maximal monotone operator inclusion)问题是非平滑凸优化和凸凹鞍点优化的 Karush-Kuhn-Tucker(KKT)广义方程的一种扩展,其包含大量重要的优化问题并且在统计学、机器学习、信号与图像处理等领域有广泛的应用。在该论文中,研究者关注的算子包含问题是:

其中, X是一个有限维度的线性向量空间,T:X⇉X是一个极大单调算子。

针对这一问题,研究者提出了一种可变度量超松弛混合临近外梯度方法(VMOR-HPE)的新型算法框架,能保证在解决该问题时的全局收敛。不同于已有的混合临近外梯度(HPE)方法,该框架能根据一种全新的相对误差准则来生成迭代序列,并且还在外梯度步骤中引入了一种超松弛的步长来提升其收敛速度。尤其值得一提的是,这个外梯度步长和超松弛步长都可以事先设定为固定常量,而不是从某个投影问题中获取的值,这能减少很多计算量。

研究者还提供了该框架的迭代复杂度和局部线性收敛速率,从理论上证明一个较大的超松弛步长有助于加速 VMOR-HPE。并且,研究者在文中严格证明了VMOR-HPE算法框架包含大量一阶原始算法和一阶原始-对偶算法为特例。此外,研究者还将 VMOR-HPE 应用到了一类 具有线性等式约束的多块可分复合凸优化问题的KKT 广义方程上,得到了一种尺度化的外梯度校正步骤的临近交替方向乘子法(PADMM-EBB),在该步骤中的尺度化矩阵是通过一种分块式的 Barzilai-Borwein 线搜索技术生成的。该算法的迭代格式如下:

PADMM-EBB 算法

最后,研究者在合成和真实数据集上进行了实验,将 PADMM-EBB 应用在了非负双图正则化低秩表征问题上,结果表明该方法是有效的。

研究表明,这种 VMOR-HPE 算法框架能为原始与原始-对偶算法提供新见解并可用作证明它们的收敛性、迭代复杂度和局部线性收敛速率的强大分析技术。

第二部分:分布式与去中心化

6、针对次模函数最小化的元素安全筛选算法

Safe Element Screening for Submodular Function Minimization

下载地址:https://arxiv.org/abs/1805.08527

次模函数可以看成是离散函数中的凸函数,其在众多领域中有着重要应用,比如:机器学习计算机视觉信号处理。然而,在大规模实际应用中,次模函数最小化问题的求解依然是一个具有挑战性的问题。在本文中,我们第一次尝试将大规模稀疏学习中新兴的筛选方法扩展到次模函数最小化中,以加快它的求解过程。通过仔细研究次模函数最小化问题和其对应凸问题之间的关系以及该凸问题最优解的估计,我们提出了一种新颖安全的元素筛选算法,能够在优化过程中迅速检测出一定包含在最优解中的元素(我们称为活跃元素)以及一定不包含在最优解中的元素(不活跃元素)。通过删除不活跃元素和固定活跃元素,问题规模得以显著减小,从而我们能够在不损失任何精度的情况下大大减少计算量。据我们所知,我们的方法是次模函数最优化领域乃至组合优化领域中的第一个筛选算法。因此,我们的方法为加速次模函数最小化算法提供了一种新思路。在合成数据集和实际数据集上的实验结果均证实我们的算法能够显著加速次模函数最小化问题的求解。

研究者首先研究了 SFM 和对应的凸近端问题之间的关系,还研究了这些近端问题的准确原始最优估计。基于该研究,他们提出了一种全新的安全筛选方法:不活动和活动元素筛选(IAES)。该框架由两个筛选规则构成:不活动元素筛选(IES)和活动元素筛选(AES);这两个规则在 IAES 框架中是交替执行的,如下算法 2 所示。

最终该框架可快速识别确保可在优化过程中被包含(活动元素)在 SFM 的最终最优解之内或被排除在外(不活动元素)的元素。然后,研究者可移除不活动元素并固定活动元素,从而大幅降低问题规模,进而在不降低准确度的前提下显著降低计算成本。

该研究为加速 SFM 算法指出了一个新方向。研究者在合成和真实数据集上进行了实验,结果表明他们所提出的方法确实能实现显著加速。下表给出了在图像分割任务上求解 SFM 的运行时间结果(单位:秒)。

可以看到,IAES 带来的加速效果非常明显,最高甚至可达 30.7 倍!

7、生成对抗网络的复合函数梯度学习

Composite Functional Gradient Learning of Generative Adversarial Models

论文地址:https://arxiv.org/abs/1801.06309

生成对抗网络(GAN)已经得到了非常广泛的研究和使用,但由于不稳定问题,GAN 往往难以训练。从数学上看,GAN 求解的是一种最小最大优化问题。而这篇论文则首先提出了一个不依赖于传统的最小最大形式的生成对抗方法理论。该理论表明,使用一个强大的鉴别器可以学习到优良的生成器,并使得每一个函数梯度(functional gradient)步骤之后真实数据分布和生成数据分布之间的 KL 散度都能得到改善,直至收敛到零。

基于这一理论,研究者提出了一种稳定的新型生成对抗方法,即复合函数梯度学习(CFG);如算法 1 所示。

在此基础上,研究者又提出了渐进式 CFG(ICFG,见算法 2)以及更进一步的近似式 ICFG(xICFG,见算法 3)。其中 ICFG 是以渐进方式使用生成器的更新一点一点地逐步更新鉴别器,使得生成器可以不断提供新的更有难度的样本,从而防止鉴别器过拟合。而 xICFG 则能通过训练一个固定大小的近似器(近似 ICFG 所获得的生成器的行为)来对 ICFG 得到的生成器进行压缩,从而提升效率。

研究者还发现,通常的使用 logistic 模型的 GAN 与使用一种极端设置的 xICFG 的特例高度相关,即:GAN 的生成器更新等效于粗略近似 T=1 的 ICFG 得到的生成器。这个视角是理解 GAN 的不稳定性的新角度,即:GAN 的不稳定性源自 T 过小以及粗略近似。

研究者进行了图像生成的实验,结果表明他们提出的新方法是有效的。下图给出了各种方法生成的图像的质量(inception 分数)随训练时间的变化情况。

可以看到,尽管 GAN1(使用了 logd 技巧的 GAN)在 LSUN 数据集上偶尔有更优的表现,但 xICFG 的表现总体更优且更稳定。

8、用于高斯图模型中最优估计的图非凸优化

Graphical Nonconvex Optimization for Optimal Estimation in Gaussian Graphical Model

论文地址:https://arxiv.org/abs/1706.01158

高斯图模型已被广泛用于表示一组变量之间的成对的条件依赖关系。graphical lasso 是估计高斯图模型的最常用方法之一。但是,它还未达到理想的收敛速度。具体而言,一般认为 graphical lasso 的谱范数中的最优收敛率大约为

其中 n 是样本规模,d 是节点数量,s 是实际的图中的边数。

在这篇论文中,研究者提出了用于高斯图模型中的最优估计的图非凸优化。然后又通过一系列自适应的凸程序来近似求解。研究者指出,尽管新提出的方法求解的是一系列凸程序,但研究表明在某些规律性条件下,这种新提出的用于估计稀疏集中度矩阵的估计器能实现 的理想收敛率,就好像非零位置事先已知一样。算法 1 展示了这个近似求解过程。然后,通过使用估计的边际方差来重新调整逆相关矩阵,可以得到该集中度矩阵的一个估计器,其谱范数收敛率大约为  和  中的最大值。

算法 1 可使用 glasso 等现有的 R 语言软件包实现。

这种新提出的方法在计算上是可行的,并且能得到能实现理想收敛速度的估计器。使用凸程序通过序列近似引入的统计误差可以使用稀疏模式的概念来进一步提升。

研究者分析了新提出的估计器的理论性质,还将这种新方法扩展到了半参数图模型中,并通过数值研究表明新提出的估计器在估计高斯图模型方面的表现优于其它常用方法。

9、用于大型多类分类问题的候选项与噪声估计

Candidates v.s. Noises Estimation for Large Multi-Class Classification Problem

论文地址:https://arxiv.org/abs/1711.00658

图像分类和语言建模等很多任务的类别数量往往很大,采样是应对这类任务的常用方法,能够帮助降低计算成本和提升训练速度。这篇论文对这一思想进行了扩展,提出了一种使用一个类别子集(候选项类别,其余类别被称为噪声类别——会被采样用于表示所有噪声)的用于多类分类问题的方法:候选项与噪声估计(CANE)。

研究者表明 CANE 总是能保持一致的表现并且很有计算效率。此外,当被观察到的标签有很高的概率属于被选择的候选项时,所得到的估计器会有很低的统计方差,接近最大似然估计器的统计方差。

研究者通过两个具体算法展现了 CANE 方法的优越性。其一是用于 CANE 的一般随机优化过程(算法 1):

另外,研究者还使用了一种树结构(叶表示类别)来促进对候选项选择的快速波束搜索(算法 2)。这种波束搜索具有更低的复杂度,能快速得到预测结果,还能自然地输出最靠前的多项预测。

研究者实验了 CANE 方法在有大量类别的多类分类问题和神经语言建模任务中的应用。下图展示了各种方法在不同分类数据集上的测试准确度随 epoch 的变化情况。可以看到,有更大候选项集的 CANE 在准确度方面基本优于其它方法,有时甚至能超过 softmax 方法。而且 CANE 方法的收敛速度明显胜过噪音对比估计(NCE)和 Blackout。

下图则给出了神经语言建模实验的结果。可以看到,CANE 方法的收敛速度比 NCE 和 Blackout 更快,同时还达到了与 softmax 方法同等的困惑度。

总体而言,实验结果表明 CANE 的预测准确度优于 NCE 及其变体方法和多种之前最佳的树分类器,同时其速度也显著优于标准的 O(K) 方法。

10、使用演示的策略优化

Policy Optimization with Demonstrations

论文地址:

https://ai.tencent.com/ailab/media/publications//icml/152_Policy_Optimization_with_Demonstrations.pdf

强化学习方法而言,探索仍然是一个突出的难题,尤其是在奖励信号稀疏的环境中。目前针对这一问题的研究方向主要有两个:1)通过鼓励智能体访问之前从未见过的状态来重塑原来的奖励函数;2)使用从某个专家策略采样的演示轨迹来引导学习过程。从演示中学习的方法看起来有克服探索难题的希望,但这通常需要难以收集的质量很高的演示。

结合这两种思路,研究者提出了一种有效地利用可用演示来引导探索的方法,即强制所学到的策略与当前演示之间的占有率匹配。这种方法背后的直观思想是,当奖励信号不可用时,智能体应该在早期学习阶段模拟所演示的行为,从而实现探索。在获得了足够多的能力之后,智能体就可以自己探索新状态了。这实际上是一种动态的固有奖励机制,可被引入强化学习用于重塑原生的奖励。

基于此,研究者开发了一种全新的使用演示的策略优化(POfD)方法,可从演示数据获取知识来提升探索效果。研究表明 POfD 能隐式地塑造动态奖励并助益策略提升。此外,它还可以与策略梯度方法结合起来得到当前最佳的结果。

研究者在一系列常见的基准稀疏奖励任务上进行了实验。结果发现,他们提出的方法的表现甚至可媲美用在理想密集奖励环境中的策略梯度方法;而且即使演示很少且不完美,这种新方法依然表现优异。下面两张图给出了新提出的 POfD 方法与几种强基准方法分别在具有离散动作空间和连续工作空间的稀疏环境中的学习曲线

各种方法在具有连续动作空间的稀疏环境中的学习曲线

11、边密度屏障:组合推理中的计算-统计权衡

The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference

统计推理的一大最主要目标是确定变量之间的依赖结构,即推理底层图模型的结构。这篇论文关注的是一个更加具体的推理问题:检验底层图中是否有特定的组合结构。

尽管对这一问题的信息论极限的研究已有很多了,但能否通过有效的算法得到这样的极限很大程度仍未被研究过。此外,检验问题(尤其是图模型的组合结构)的构建方式对信息论极限的可达成性的影响方式也并不明朗。

为了理解这两个问题,研究者在这篇论文中描述了图模型中组合推理的这种基本极限;并基于一种 oracle 计算模型量化研究了达到这个信息论极限所需的最小计算复杂度。

研究证明,要在空图上检验团(clique)、最近邻图、完美匹配等常见组合结构,或在小团上检验大团,信息论极限是无法通过一般的可实现算法达到的。

更重要的是,研究者定义了名为弱边密度 µ 和强边密度 µ' 的结构量。根据定义,边集的弱边密度表征了可从一个无效(null)变到另一个图的关键边的密集程度。这能反应这两个图的差异水平。强边密度是另一个表征这两个图的差异水平的量,且总是不小于弱边密度。下面给出了 µ 和 µ' 的定义:

这两个结构量的一大突出性质是它们仅依赖于被测试的组合结构的拓扑性质。它们能帮助研究者理解组合推理问题的结构性质决定其计算复杂度的方式。研究表明,如果 µ 远小于 µ',则信息论下界和计算有效的下界之间会存在明显差距。下面给出了 4 个案例的具体最优比率;可以看到,这些案例都存在统计与计算的权衡。

本研究也是首个确定和解释无向图模型中组合推理问题的统计和计算之间的基本权衡的研究。

第三部分:机器学习优化方法与理论研究

12、异步去中心化并行随机梯度下降

Asynchronous Decentralized Parallel Stochastic Gradient Descent

论文地址:https://arxiv.org/abs/1710.06952

最常用的分布式机器学习系统要么是同步的,要么就是中心化异步的。AllReduce-SGD 这样的同步算法在异构环境中表现很差,而使用参数服务器的异步算法则存在很多问题,其中包括工作器(worker)很多时参数服务器的通信问题以及当参数服务器的流量拥堵时收敛性下降的问题。

研究者在这篇论文中提出了一种异步去中心化并行随机梯度下降(AD-PSGD),能在异构环境中表现稳健且通信效率高并能维持最佳的收敛速率。理论分析表明 AD-PSGD 能以和 SGD 一样的最优速度收敛,并且能随工作器的数量线性提速。下面是该算法的工作过程:


研究者使用 Torch 和 MPI 在多达 128 个 P100 GPU 的 IBM S822LC 集群上实现和评估了 AD-PSGD。实验结果表明,AD-PSGD 的表现优于最佳的去中心化并行 SGD(D-PSGD)、异构并行 SGD(A-PSGD)和标准的数据并行 SGD(AllReduce-SGD)。AD-PSGD 在异构环境中的表现往往能超出其它方法多个数量级。

下图给出了在 ImageNet 数据集上基于 ResNet-50 模型得到的训练损失和每 epoch 训练时间情况。可以看到,AD-PSGD 和 AllReduce-SGD 的收敛情况接近,都优于 D-PSGD。在使用 64 个工作器时,AD-PSGD 每 epoch 耗时 264 秒,而另外两种方法每 epoch 耗时会超过 1000 秒。

下图则展示了各种方法在 CIFAR10 上为 VGG(通信密集型)和 ResNet-20(计算密集型)模型带来的加速情况。可以明显看到 AD-PSGD 一直都有最优的表现。

AD-PSGD 是首个在超过 100 个 GPU 的规模上达到接近 AllReduce-SGD 的 epoch 收敛速度的异步算法。

13、D2:在去中心化数据上的去中心化训练

D2: Decentralized Training over Decentralized Data

论文地址:https://arxiv.org/abs/1803.07068

以去中心化的方式训练机器学习模型近来得到了很大的研究关注。在使用多个工作器训练机器学习模型时(其中每一个都会从自己的数据源收集数据),从各个不同的工作器收集的数据也各不相同时这些数据是最有用的。但是,近期的很多去中心化并行随机梯度下降(D-PSGD)研究都假设托管在不同工作器上的数据并没有很大的差异——否则这些方法的收敛速度会非常慢。

研究者在这篇论文中提出了一种全新的去中心化并行随机梯度下降算法 D2,该算法是为各工作器之间数据差异很大的情况(可以说是“去中心化”数据)设计的。

D2 基于标准的 D-PSGD 算法,但添加了一个降低方差的组件。在这种 D2 算法中,每个工作器都会存储上一轮迭代的随机梯度和局部模型,并将它们与当前的随机梯度和局部模型线性地结合到一起。这能将收敛速度改善,其中 ζ2 是不同工作器上的数据差异,σ2 是每个工作器内的数据方差,n 是工作器的数量,T 是迭代次数。

研究者在图像分类任务上对 D2 进行了评估,其中每个工作器都仅能读取一个有限标签集的数据。实验结果表明 D2 的表现显著优于 D-PSGD。下面给出了在无数据混洗(unshuffled)情况下(不同工作器之间的数据差异最大)的不同分布式训练算法的收敛性比较。


可以看到,D-PSGD 算法的收敛速度比中心化方法慢,而 D2 也比 D-PSGD 快很多,并且损失非常接近中心化算法。

14、实现更高效的随机去中心化学习:更快收敛和稀疏通信

Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication

论文地址:https://arxiv.org/abs/1805.09969

去中心化优化问题近来得到了越来越大的关注。大多数现有方法都是确定性的,具有很高的每次迭代成本,并且收敛速度与问题条件数呈二次关系。此外,为了确保收敛还必需密集的通信,即使数据集是稀疏的也是如此。

在这篇论文中,研究者将去中心化优化问题泛化成了一个单调算子根查找问题,并提出了一种名为去中心化随机反向聚合(DSBA)的算法。


在 DSBA 的计算步骤,每个节点都会计算一个随机近似的单调算子的预解式(resolvent),以降低对问题条件数的依赖程度。这样的预解式接受脊回归等问题中的闭式解。在 DSBA 的通信步骤,每个节点都接收连续迭代之间差异的非零分量,以重建其临近节点的迭代。因为 ℓ2-relaxed AUC 最大化问题等效于凸凹函数的极小极大问题,其微分是一个单调算子,因此能无缝地适配 DSBA 的形式。

该算法具有以下优势:(1)能以与问题条件数呈线性的速度以几何方式收敛,(2)可以仅使用稀疏通信实现。此外,DSBA 还能处理 AUC 最大化等无法在去中心化设置中高效解决的学习问题。研究者在论文中也给出了对该算法的收敛性分析。

研究者在凸最小化和 AUC 最大化上进行了实验,结果表明新提出的方法是有效的。下图给出了 DSBA 与几种之前最佳方法在 logistic 回归上的结果比较


可以看到,DSBA 的表现是最优的,而且能以更低的计算成本更快地收敛

15、误差补偿式量化 SGD 及其在大规模分布式优化中的应用

Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization

论文地址:https://arxiv.org/abs/1806.08054

这一轮机器学习热潮的出现很大程度上得益于计算机处理能力的指数级发展以及出现了可用于训练模型的海量数据。为了有效地完成海量数据的训练,往往需要用到分布式优化方法,其中包括数据并行化的处理方法。但在这样的分布式框架中,各个节点之间的通信速度往往会成为整体性能的关键制约因素。目前的常见解决方法是对节点之间的通信信息进行压缩,但这会引入量化误差。

为了解决这一问题,这篇论文提出通过使用累积的所有之前的量化误差的误差反馈方案来补偿当前的局部梯度。研究者将该方法称为“误差补偿式量化随机梯度下降(ECQ-SGD)”。实验结果表明这种方法能实现比很多基准方法更快更稳定的收敛。下面是该算法的工作过程:

在量化完成之后,总体通信成本会降至 32+dr 比特(r ≪ 32),远少于原来的 32 位全精度梯度所需的 32d 比特;其中 d 是原向量的维度;其中 s 是非零量化级别的数量:s 越大,则量化越细粒度,通信成本也就越高。下图给出了在 ILSVRC-12 数据集上训练 ResNet-50 模型时,使用不同数量的 GPU 的吞吐量情况比较:

在使用 512 个 GPU 进行训练时,ECQ-SGD 相对于普通 SGD 实现了 143.5% 的加速(每秒各 66.42k 与 27.28k 张图像)。如果节点之间的带宽更小,这样的优势还会更加显著。

研究者还在该论文中提供了该方法的理论保证:分析了其收敛行为并证明了其相对于其它之前最佳方法的优势。

16、使用联网智能体的完全去中心化多智能体强化学习

Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents

论文地址:https://arxiv.org/abs/1802.08757

在多智能体强化学习(MARL)问题中,多个智能体的联合行动会影响它们所处的共同环境。在每个状态,每个智能体都会执行一个动作,这些动作共同决定了环境的下一个状态和每个智能体的奖励。此外,这些智能体可能针对的是不同的任务,会有不同的奖励函数;但每个智能体都只能观察自己的奖励。每个智能体都会基于局部观察到的信息以及从网络中的临近智能体接受到的信息各自做出决策。在这种设置内,所有智能体的整体目标是通过与其临近智能体交换信息而最大化在整个网络上的全局平均回报。

针对这一问题的中心化方法存在可扩展性和稳健性等方面的问题,因此,研究者在这篇论文中基于一种用于 MARL 的全新策略梯度定理提出了两种去中心化 actor-critic 算法;结合函数近似,可应用于状态和智能体数量都非常大的大规模 MARL 问题。


基于动作-价值函数的联网式 actor-critic 算法

基于状态-价值 TD 误差的联网式 actor-critic 算法

具体来说,actor 步骤是由每个智能体单独执行的,无需推断其它智能体的策略。对于 critic 步骤,研究者提出了一种在整个网络通过通信实现的共识更新(consensus update),即每个智能体都会与其网络中的临近智能体共享其价值函数的估计,从而得到一个共识估计。这个估计又会被用在后续的 actor 步骤中。通过这种方式,每个智能体的局部信息都能散布到整个网络,从而最大化整个网络层面的奖励。

这种算法是完全渐进式的,可以以一种在线形式实现。研究者还提供了当价值函数位于线性函数类别内近似求取时的算法收敛性分析。

研究者使用线性和非线性函数近似执行了大量模拟实验,对所提出的算法进行了验证。下图给出了当使用神经网络进行函数近似时,在协同导航任务上的全局平均奖励。其中 Central-1 和 Central-2 分别是算法 1 和算法 2 对应的中心化方法。

研究者表示该研究是首个使用函数近似的联网智能体的完全去中心化 MARL 算法研究。


腾讯AI实验室
腾讯AI实验室

入门ICML 2018
1
相关数据
自动编码器技术

自动编码器是用于无监督学习高效编码的人工神经网络。 自动编码器的目的是学习一组数据的表示(编码),通常用于降维。 最近,自动编码器已经越来越广泛地用于生成模型的训练。

范数技术

范数(norm),是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域,是一个函数,其为向量空间内的所有向量赋予非零的正长度或大小。半范数反而可以为非零的向量赋予零长度。

策略迭代技术

策略迭代算法直接操纵策略,而不是通过最优值函数间接找到策略。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

分类数据技术

一种特征,拥有一组离散的可能值。以某个名为 house style 的分类特征为例,该特征拥有一组离散的可能值(共三个),即 Tudor, ranch, colonial。通过将 house style 表示成分类数据,相应模型可以学习 Tudor、ranch 和 colonial 分别对房价的影响。 有时,离散集中的值是互斥的,只能将其中一个值应用于指定样本。例如,car maker 分类特征可能只允许一个样本有一个值 (Toyota)。在其他情况下,则可以应用多个值。一辆车可能会被喷涂多种不同的颜色,因此,car color 分类特征可能会允许单个样本具有多个值(例如 red 和 white)。

学习曲线技术

在机器学习领域,学习曲线通常是表现学习准确率随着训练次数/时长/数据量的增长而变化的曲线

阿尔法围棋技术

阿尔法围棋是于2014年开始由英国伦敦Google DeepMind公司开发的人工智能围棋程序。AlphaGo是第一个打败人类职业棋手的计算机程序,也是第一个打败围棋世界冠军的计算机程序,可以说是历史上最强的棋手。 技术上来说,AlphaGo的算法结合了机器学习(machine learning)和树搜索(tree search)技术,并使用了大量的人类、电脑的对弈来进行训练。AlphaGo使用蒙特卡洛树搜索(MCTS:Monte-Carlo Tree Search),以价值网络(value network)和策略网络(policy network)为指导,其中价值网络用于预测游戏的胜利者,策略网络用于选择下一步行动。价值网络和策略网络都是使用深度神经网络技术实现的,神经网络的输入是经过预处理的围棋面板的描述(description of Go board)。

最大似然估计技术

极大似然估计是统计学中用来估计概率模型参数的一种方法

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

凸优化技术

凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单,譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用,如次导数等。 凸优化应用于很多学科领域,诸如自动控制系统,信号处理,通讯和网络,电子电路设计,数据分析和建模,统计学(最优化设计),以及金融。在近来运算能力提高和最优化理论发展的背景下,一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化(凸最小化)问题,例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。

线搜索技术

最优化问题中,线搜索是一种寻找目标函数 的局部最小值 的近似方法。 它是最基础的迭代近似方法之一,另一种是置信域方法。 线搜索近似首先找到一个使目标函数 下降的方向,然后计算 应该沿着这个方向移动的步长。 下降方向可以通过多种方法计算,比如梯度下降法,牛顿法和拟牛顿法。

计算机视觉技术

计算机视觉(CV)是指机器感知环境的能力。这一技术类别中的经典任务有图像形成、图像处理、图像提取和图像的三维推理。目标识别和面部识别也是很重要的研究领域。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

梯度下降技术

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

随机梯度下降技术

梯度下降(Gradient Descent)是遵循成本函数的梯度来最小化一个函数的过程。这个过程涉及到对成本形式以及其衍生形式的认知,使得我们可以从已知的给定点朝既定方向移动。比如向下朝最小值移动。 在机器学习中,我们可以利用随机梯度下降的方法来最小化训练模型中的误差,即每次迭代时完成一次评估和更新。 这种优化算法的工作原理是模型每看到一个训练实例,就对其作出预测,并重复迭代该过程到一定的次数。这个流程可以用于找出能导致训练数据最小误差的模型的系数。

监督学习技术

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

噪音技术

噪音是一个随机误差或观测变量的方差。在拟合数据的过程中,我们常见的公式$y=f(x)+\epsilon$中$\epsilon$即为噪音。 数据通常包含噪音,错误,例外或不确定性,或者不完整。 错误和噪音可能会混淆数据挖掘过程,从而导致错误模式的衍生。去除噪音是数据挖掘(data mining)或知识发现(Knowledge Discovery in Database,KDD)的一个重要步骤。

分类问题技术

分类问题是数据挖掘处理的一个重要组成部分,在机器学习领域,分类问题通常被认为属于监督式学习(supervised learning),也就是说,分类问题的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类。根据类别的数量还可以进一步将分类问题划分为二元分类(binary classification)和多元分类(multiclass classification)。

规范化技术

规范化:将属性数据按比例缩放,使之落入一个小的特定区间,如-1.0 到1.0 或0.0 到1.0。 通过将属性数据按比例缩放,使之落入一个小的特定区间,如0.0到1.0,对属性规范化。对于距离度量分类算法,如涉及神经网络或诸如最临近分类和聚类的分类算法,规范化特别有用。如果使用神经网络后向传播算法进行分类挖掘,对于训练样本属性输入值规范化将有助于加快学习阶段的速度。对于基于距离的方法,规范化可以帮助防止具有较大初始值域的属性与具有较小初始值域的属相相比,权重过大。有许多数据规范化的方法,包括最小-最大规范化、z-score规范化和按小数定标规范化。

迁移学习技术

迁移学习是一种机器学习方法,就是把为任务 A 开发的模型作为初始点,重新使用在为任务 B 开发模型的过程中。迁移学习是通过从已学习的相关任务中转移知识来改进学习的新任务,虽然大多数机器学习算法都是为了解决单个任务而设计的,但是促进迁移学习的算法的开发是机器学习社区持续关注的话题。 迁移学习对人类来说很常见,例如,我们可能会发现学习识别苹果可能有助于识别梨,或者学习弹奏电子琴可能有助于学习钢琴。

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

无人机技术

无人机(Uncrewed vehicle、Unmanned vehicle、Drone)或称无人载具是一种无搭载人员的载具。通常使用遥控、导引或自动驾驶来控制。可在科学研究、军事、休闲娱乐用途上使用。

图像处理技术

图像处理是指对图像进行分析、加工和处理,使其满足视觉、心理或其他要求的技术。 图像处理是信号处理在图像领域上的一个应用。 目前大多数的图像均是以数字形式存储,因而图像处理很多情况下指数字图像处理。

信号处理技术

信号处理涉及到信号的分析、合成和修改。信号被宽泛地定义为传递“关于某种现象的行为或属性的信息(如声音、图像和生物测量)”的函数。例如,信号处理技术用于提高信号传输的保真度、存储效率和主观质量,并在测量信号中强调或检测感兴趣的组件。我们熟悉的语音、图像都可以看做是一种信号形式。因此,对于语音、图像的增强、降噪、识别等等操作本质上都是信号处理。

马尔可夫决策过程技术

马尔可夫决策过程为决策者在随机环境下做出决策提供了数学架构模型,为动态规划与强化学习的最优化问题提供了有效的数学工具,广泛用于机器人学、自动化控制、经济学、以及工业界等领域。当我们提及马尔可夫决策过程时,我们一般特指其在离散时间中的随机控制过程:即对于每个时间节点,当该过程处于某状态(s)时,决策者可采取在该状态下被允许的任意决策(a),此后下一步系统状态将随机产生,同时回馈给决策者相应的期望值,该状态转移具有马尔可夫性质。

生成模型技术

在概率统计理论中, 生成模型是指能够随机生成观测数据的模型,尤其是在给定某些隐含参数的条件下。 它给观测值和标注数据序列指定一个联合概率分布。 在机器学习中,生成模型可以用来直接对数据建模(例如根据某个变量的概率密度函数进行数据采样),也可以用来建立变量间的条件概率分布。

生成对抗网络技术

生成对抗网络是一种无监督学习方法,是一种通过用对抗网络来训练生成模型的架构。它由两个网络组成:用来拟合数据分布的生成网络G,和用来判断输入是否“真实”的判别网络D。在训练过程中,生成网络-G通过接受一个随机的噪声来尽量模仿训练集中的真实图片去“欺骗”D,而D则尽可能的分辨真实数据和生成网络的输出,从而形成两个网络的博弈过程。理想的情况下,博弈的结果会得到一个可以“以假乱真”的生成模型。

WGAN技术

就其本质而言,任何生成模型的目标都是让模型(习得地)的分布与真实数据之间的差异达到最小。然而,传统 GAN 中的判别器 D 并不会当模型与真实的分布重叠度不够时去提供足够的信息来估计这个差异度——这导致生成器得不到一个强有力的反馈信息(特别是在训练之初),此外生成器的稳定性也普遍不足。 Wasserstein GAN 在原来的基础之上添加了一些新的方法,让判别器 D 去拟合模型与真实分布之间的 Wasserstein 距离。Wassersterin 距离会大致估计出「调整一个分布去匹配另一个分布还需要多少工作」。此外,其定义的方式十分值得注意,它甚至可以适用于非重叠的分布。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

信息论技术

信息论是在信息可以量度的基础上,研究有效地和可靠地传递信息的科学,它涉及信息量度、信息特性、信息传输速率、信道容量、干扰对信息传输的影响等方面的知识。通常把上述范围的信息论称为狭义的信息论,又因为它的创始人是香农,故又称为香农信息论。

深度神经网络技术

深度神经网络(DNN)是深度学习的一种框架,它是一种具备至少一个隐层的神经网络。与浅层神经网络类似,深度神经网络也能够为复杂非线性系统提供建模,但多出的层次为模型提供了更高的抽象层次,因而提高了模型的能力。

移动机器人技术

移动机器人是一种能够移动的自动机器。移动机器人具有在其环境中移动的能力,并且不固定到一个物理位置。移动机器人可以“自动”主要是指它们能够在没有物理或机电引导装置的情况下导航非受控环境。相比之下,传统的工业机器人或多或少都是固定的(stationary)机械臂或抓取组件。

暂无评论
暂无评论~