7月10日至15日，第 35 屆國(guó)際機(jī)器學(xué)習(xí)會(huì)議（ICML 2018）將在瑞典斯德哥爾摩舉行。ICML是機(jī)器學(xué)習(xí)領(lǐng)域最頂級(jí)的學(xué)術(shù)會(huì)議，今年共收到2473篇投遞論文，比去年的1676篇提高47.6%，增幅顯著。最終入圍論文共621篇，接收率25%，與去年26%持平。

這是騰訊AI Lab第二次參與這一頂級(jí)會(huì)議，共有16篇論文入選，去年則入選4篇，均位居國(guó)內(nèi)企業(yè)前列。我們將在下文中分三類介紹這些文章——新模型與新框架、分布式與去中心化、及機(jī)器學(xué)習(xí)優(yōu)化方法與理論研究。有的研究具有多重貢獻(xiàn)，并不嚴(yán)格按照研究?jī)?nèi)容區(qū)分。

1、用于強(qiáng)化學(xué)習(xí)的基于反饋的樹搜索 Feedback-based Tree Search for Reinforcement Learning

論文地址：https:///abs/1805.05935

蒙特卡洛樹搜索（MCTS）已經(jīng)在游戲智能體方面取得了很大的成功（比如 AlphaGo），但對(duì)于 Atari 或 MOBA 等需要快速?zèng)Q策的視頻游戲，樹搜索的速度卻太慢了。針對(duì)這一問(wèn)題，該論文提出了一種新型的基于模型的強(qiáng)化學(xué)習(xí)技術(shù)，可在原無(wú)限范圍的馬爾可夫決策過(guò)程的小型有限范圍版本批量上迭代式地應(yīng)用 MCTS。在以離策略的方式完成強(qiáng)化學(xué)習(xí)訓(xùn)練之后，智能體無(wú)需進(jìn)一步的樹搜索就能實(shí)現(xiàn)快速實(shí)時(shí)的決策。

研究者將這一思想融合到了一個(gè)基于反饋的框架中，其中 MCTS 會(huì)使用其根節(jié)點(diǎn)處生成的觀察結(jié)果來(lái)更新自己的葉節(jié)點(diǎn)評(píng)估器。其反饋過(guò)程如下圖所示：（1）從一批采樣的狀態(tài)（三角形）開始運(yùn)行一組樹搜索，（2）使用第 k 次迭代時(shí)的策略函數(shù)近似（PFA）πk 和價(jià)值函數(shù)近似（VFA）Vk 的葉估計(jì)被用于樹搜索過(guò)程，（3）使用樹搜索結(jié)果更新 πk+1 和 Vk+1。

研究者對(duì)該方法進(jìn)行了理論分析，結(jié)果表明當(dāng)樣本量足夠大且進(jìn)行了足夠多的樹搜索時(shí)，估計(jì)得到的策略能夠接近最優(yōu)表現(xiàn)。這也是對(duì)基于批 MCTS 的強(qiáng)化學(xué)習(xí)方法的首個(gè)理論分析。

研究者還使用深度神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了這種基于反饋的樹搜索算法并在《王者榮耀》1v1 模式上進(jìn)行了測(cè)試。為了進(jìn)行對(duì)比，研究者訓(xùn)練了 5 個(gè)操控英雄狄仁杰的智能體，結(jié)果他們提出的新方法顯著優(yōu)于其它方法，下圖給出了他們的方法訓(xùn)練的智能體相對(duì)于其它智能體隨時(shí)間的金幣比值變化。

其中，NR 是指沒(méi)有 rollout 但參數(shù)設(shè)置與該論文的新方法一樣的智能體，DPI 是使用了直接策略迭代的智能體，AVI 是使用了近似價(jià)值迭代的智能體，SL 是一個(gè)在大約 10 萬(wàn)對(duì)人類游戲數(shù)據(jù)的狀態(tài)/動(dòng)作對(duì)上通過(guò)監(jiān)督學(xué)習(xí)訓(xùn)練得到的智能體。

2、通過(guò)學(xué)習(xí)遷移實(shí)現(xiàn)遷移學(xué)習(xí) Transfer Learning via Learning to Transfer

論文地址：

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

遷移學(xué)習(xí)的三個(gè)核心研究問(wèn)題是：何時(shí)遷移、如何遷移和遷移什么。為特定的遷移任務(wù)選擇合適的遷移算法往往需要高成本的計(jì)算或相關(guān)領(lǐng)域的專業(yè)知識(shí)。為了能更有效地找到適合當(dāng)前任務(wù)的遷移算法，研究者根據(jù)人類執(zhí)行遷移學(xué)習(xí)的方式，設(shè)計(jì)了一種可根據(jù)之前的遷移學(xué)習(xí)經(jīng)歷提升新領(lǐng)域之間的遷移學(xué)習(xí)有效性的新框架：學(xué)習(xí)遷移（L2T：Learning to Transfer）。

L2T 分為兩個(gè)階段。在第一個(gè)階段，每個(gè)遷移學(xué)習(xí)經(jīng)歷都會(huì)被編碼成三個(gè)組件：一對(duì)源域和目標(biāo)域、它們之間被遷移的知識(shí)（被參數(shù)化為隱含特征向量）、遷移學(xué)習(xí)帶來(lái)的性能提升比。然后再?gòu)乃薪?jīng)歷中學(xué)習(xí)一個(gè)反射函數(shù)（reflection function），該函數(shù)能將領(lǐng)域?qū)退鼈冎g被遷移的知識(shí)映射到性能提升比。研究者相信這個(gè)反射函數(shù)就具備決定遷移什么和如何遷移的遷移學(xué)習(xí)能力。在第二個(gè)階段，新出現(xiàn)的領(lǐng)域?qū)χg所要遷移的內(nèi)容則可以通過(guò)最大化所學(xué)習(xí)到的反射函數(shù)的值而得到優(yōu)化。

為了證明這種遷移學(xué)習(xí)方法的優(yōu)越性，研究者在 Caltech-256 和 Sketches 這兩個(gè)圖像數(shù)據(jù)集上對(duì) L2T 框架進(jìn)行了實(shí)驗(yàn)評(píng)估。下圖給出了 L2T 及另外 9 種基準(zhǔn)方法在 6 個(gè)源域和目標(biāo)域?qū)ι系姆诸悳?zhǔn)確度。

可以看到，不管源域與目標(biāo)域有較緊密的聯(lián)系（比如 (a) 中的“galaxy”、“saturn”和“sun”）還是沒(méi)有顯著關(guān)聯(lián)（比如 (c) 和 (f)），L2T 方法的表現(xiàn)都明顯優(yōu)于其它所有基準(zhǔn)方法。

3、通過(guò)強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)端到端的主動(dòng)目標(biāo)跟蹤 End-to-end Active Object Tracking via Reinforcement Learning

論文地址：https:///abs/1705.10561

目標(biāo)跟蹤的目標(biāo)是根據(jù)視頻的初始幀中的目標(biāo)標(biāo)注定位該目標(biāo)在連續(xù)視頻中的位置。對(duì)于移動(dòng)機(jī)器人和無(wú)人機(jī)等視角會(huì)變動(dòng)的平臺(tái)或目標(biāo)會(huì)離開當(dāng)前拍攝場(chǎng)景的情況，跟蹤目標(biāo)時(shí)通常還需要對(duì)攝像頭的拍攝角度進(jìn)行持續(xù)調(diào)整。該論文提出了一種使用強(qiáng)化學(xué)習(xí)的端到端的主動(dòng)目標(biāo)跟蹤方法，可直接根據(jù)畫面情況調(diào)整攝像頭角度。具體而言，研究者使用了一個(gè) ConvNet-LSTM 網(wǎng)絡(luò)，其輸入為原始視頻幀，輸出為相機(jī)運(yùn)動(dòng)動(dòng)作（前進(jìn)、向左等）。

上圖展示了這個(gè) ConvNet-LSTM 網(wǎng)絡(luò)的架構(gòu)，其中的強(qiáng)化學(xué)習(xí)部分使用了一種當(dāng)前最佳的強(qiáng)化學(xué)習(xí)算法 A3C。

因?yàn)樵诂F(xiàn)實(shí)場(chǎng)景上訓(xùn)練端到端的主動(dòng)跟蹤器還無(wú)法實(shí)現(xiàn)，所以研究者在 ViZDoom 和 Unreal Engine 進(jìn)行了模擬訓(xùn)練。在這些虛擬環(huán)境中，智能體（跟蹤器）以第一人稱視角觀察狀態(tài)（視覺(jué)幀）并采取動(dòng)作，然后環(huán)境會(huì)返回更新后的狀態(tài)（下一幀）。研究者還設(shè)計(jì)了一個(gè)新的獎(jiǎng)勵(lì)函數(shù)以讓智能體更加緊跟目標(biāo)。

實(shí)驗(yàn)結(jié)果表明，這種端到端的主動(dòng)跟蹤方法能取得優(yōu)異的表現(xiàn)，并且還具有很好的泛化能力，能夠在目標(biāo)運(yùn)動(dòng)路徑、目標(biāo)外觀、背景不同以及出現(xiàn)干擾目標(biāo)時(shí)依然穩(wěn)健地執(zhí)行主動(dòng)跟蹤。另外，當(dāng)目標(biāo)偶爾脫離跟蹤時(shí)（比如目標(biāo)突然移動(dòng)），該方法還能恢復(fù)對(duì)目標(biāo)的跟蹤。下表給出了不同跟蹤方法在 ViZDoom 環(huán)境的幾個(gè)不同場(chǎng)景上的表現(xiàn)比較，其中 AR 表示累積獎(jiǎng)勵(lì)（類似于精確度），EL 表示 episode 長(zhǎng)度（類似于成功跟蹤的持續(xù)幀數(shù)）。

最后，研究者還在 VOT 數(shù)據(jù)集上執(zhí)行了一些定性評(píng)估，結(jié)果表明從虛擬場(chǎng)景學(xué)習(xí)到的跟蹤能力也有望遷移到真實(shí)世界場(chǎng)景中。

4、使用局部坐標(biāo)編碼的對(duì)抗學(xué)習(xí) Adversarial Learning with Local Coordinate Coding

論文地址：https:///abs/1806.04895

生成對(duì)抗網(wǎng)絡(luò)（GAN）是近來(lái)一個(gè)非常熱門的研究方向，也實(shí)現(xiàn)了一些成功應(yīng)用。但 GAN 仍有一些局限性：很多研究都使用了簡(jiǎn)單的先驗(yàn)分布，GAN 在隱含分布的維度上的泛化能力是未知的。針對(duì)這些問(wèn)題，研究者基于對(duì)圖像的流形假設(shè)提出了一種全新的生成模型，該模型使用了局部坐標(biāo)編碼（LCC），可提升 GAN 在生成擬真圖像上的表現(xiàn)。

上圖展示了該論文提出的 LCC-GAN 方案。研究者首先使用了一個(gè)自動(dòng)編碼器（AE）在隱含流形上學(xué)習(xí)了嵌入來(lái)獲取數(shù)據(jù)中的含義信息。然后，他們又使用 LCC 學(xué)習(xí)一組基數(shù)來(lái)在該隱含流形上構(gòu)建局部坐標(biāo)系統(tǒng)。之后，他們?cè)偻ㄟ^(guò)使用一個(gè)與一組編碼相關(guān)的線性函數(shù)來(lái)近似生成器而將 LCC 引入了 GAN?；谶@種近似，他們?cè)偻ㄟ^(guò)利用在隱含流形上的局部信息而提出了一種基于 LCC 的采樣方法。LCC-GAN 的具體訓(xùn)練過(guò)程如下：

其中 LCC 采樣方法分為兩個(gè)步驟：（1）給定一個(gè)局部坐標(biāo)系，我們隨機(jī)選擇一個(gè)隱含點(diǎn)（可以是一個(gè)基（basis）），然后找到其 d-最近鄰點(diǎn)；（2）我們構(gòu)建一個(gè) M 維向量作為采樣的 LCC 編碼。其中，該向量的每個(gè)元素都對(duì)應(yīng)于那個(gè)基的權(quán)重。

研究者用 PyTorch 實(shí)現(xiàn)了 LCC-GAN 并通過(guò)大量基于真實(shí)世界數(shù)據(jù)集的實(shí)驗(yàn)對(duì)該方法進(jìn)行了評(píng)估。結(jié)果表明 LCC-GAN 的表現(xiàn)優(yōu)于其它多種 GAN 方法（Vanilla GAN、WGAN、Progressive GAN）。下圖展示了 LCC-GAN 和 Progressive GAN 基于 CelebA 數(shù)據(jù)集的人臉生成結(jié)果比較。

研究者還推導(dǎo)了 LCC-GAN 的泛化界限，并證明維度較小的輸入就足以實(shí)現(xiàn)優(yōu)良的泛化表現(xiàn)。

5、一種可變度量超松弛混合臨近外梯度方法的算法框架 An Algorithmic Framework of Variable Metric Over-Relaxed Hybrid Proximal Extra-Gradient Method

論文地址：https:///abs/1805.06137

極大單調(diào)算子包含（maximal monotone operator inclusion）問(wèn)題是非平滑凸優(yōu)化和凸凹鞍點(diǎn)優(yōu)化的 Karush-Kuhn-Tucker（KKT）廣義方程的一種擴(kuò)展，其包含大量重要的優(yōu)化問(wèn)題并且在統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、信號(hào)與圖像處理等領(lǐng)域有廣泛的應(yīng)用。在該論文中，研究者關(guān)注的算子包含問(wèn)題是：

其中， X是一個(gè)有限維度的線性向量空間，T:X?X是一個(gè)極大單調(diào)算子。

針對(duì)這一問(wèn)題，研究者提出了一種可變度量超松弛混合臨近外梯度方法（VMOR-HPE）的新型算法框架，能保證在解決該問(wèn)題時(shí)的全局收斂。不同于已有的混合臨近外梯度（HPE）方法，該框架能根據(jù)一種全新的相對(duì)誤差準(zhǔn)則來(lái)生成迭代序列，并且還在外梯度步驟中引入了一種超松弛的步長(zhǎng)來(lái)提升其收斂速度。尤其值得一提的是，這個(gè)外梯度步長(zhǎng)和超松弛步長(zhǎng)都可以事先設(shè)定為固定常量，而不是從某個(gè)投影問(wèn)題中獲取的值，這能減少很多計(jì)算量。

研究者還提供了該框架的迭代復(fù)雜度和局部線性收斂速率，從理論上證明一個(gè)較大的超松弛步長(zhǎng)有助于加速 VMOR-HPE。并且，研究者在文中嚴(yán)格證明了VMOR-HPE算法框架包含大量一階原始算法和一階原始-對(duì)偶算法為特例。此外，研究者還將 VMOR-HPE 應(yīng)用到了一類 具有線性等式約束的多塊可分復(fù)合凸優(yōu)化問(wèn)題的KKT 廣義方程上，得到了一種尺度化的外梯度校正步驟的臨近交替方向乘子法（PADMM-EBB），在該步驟中的尺度化矩陣是通過(guò)一種分塊式的 Barzilai-Borwein 線搜索技術(shù)生成的。該算法的迭代格式如下：

PADMM-EBB 算法

最后，研究者在合成和真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，將 PADMM-EBB 應(yīng)用在了非負(fù)雙圖正則化低秩表征問(wèn)題上，結(jié)果表明該方法是有效的。

研究表明，這種 VMOR-HPE 算法框架能為原始與原始-對(duì)偶算法提供新見解并可用作證明它們的收斂性、迭代復(fù)雜度和局部線性收斂速率的強(qiáng)大分析技術(shù)。

研究者首先研究了 SFM 和對(duì)應(yīng)的凸近端問(wèn)題之間的關(guān)系，還研究了這些近端問(wèn)題的準(zhǔn)確原始最優(yōu)估計(jì)?；谠撗芯浚麄兲岢隽艘环N全新的安全篩選方法：不活動(dòng)和活動(dòng)元素篩選（IAES）。該框架由兩個(gè)篩選規(guī)則構(gòu)成：不活動(dòng)元素篩選（IES）和活動(dòng)元素篩選（AES）；這兩個(gè)規(guī)則在 IAES 框架中是交替執(zhí)行的，如下算法 2 所示。

最終該框架可快速識(shí)別確保可在優(yōu)化過(guò)程中被包含（活動(dòng)元素）在 SFM 的最終最優(yōu)解之內(nèi)或被排除在外（不活動(dòng)元素）的元素。然后，研究者可移除不活動(dòng)元素并固定活動(dòng)元素，從而大幅降低問(wèn)題規(guī)模，進(jìn)而在不降低準(zhǔn)確度的前提下顯著降低計(jì)算成本。

該研究為加速 SFM 算法指出了一個(gè)新方向。研究者在合成和真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明他們所提出的方法確實(shí)能實(shí)現(xiàn)顯著加速。下表給出了在圖像分割任務(wù)上求解 SFM 的運(yùn)行時(shí)間結(jié)果（單位：秒）。

可以看到，IAES 帶來(lái)的加速效果非常明顯，最高甚至可達(dá) 30.7 倍！

7、生成對(duì)抗網(wǎng)絡(luò)的復(fù)合函數(shù)梯度學(xué)習(xí) Composite Functional Gradient Learning of Generative Adversarial Models

論文地址：https:///abs/1801.06309

生成對(duì)抗網(wǎng)絡(luò)（GAN）已經(jīng)得到了非常廣泛的研究和使用，但由于不穩(wěn)定問(wèn)題，GAN 往往難以訓(xùn)練。從數(shù)學(xué)上看，GAN 求解的是一種最小最大優(yōu)化問(wèn)題。而這篇論文則首先提出了一個(gè)不依賴于傳統(tǒng)的最小最大形式的生成對(duì)抗方法理論。該理論表明，使用一個(gè)強(qiáng)大的鑒別器可以學(xué)習(xí)到優(yōu)良的生成器，并使得每一個(gè)函數(shù)梯度（functional gradient）步驟之后真實(shí)數(shù)據(jù)分布和生成數(shù)據(jù)分布之間的 KL 散度都能得到改善，直至收斂到零。

基于這一理論，研究者提出了一種穩(wěn)定的新型生成對(duì)抗方法，即復(fù)合函數(shù)梯度學(xué)習(xí)（CFG）；如算法 1 所示。

在此基礎(chǔ)上，研究者又提出了漸進(jìn)式 CFG（ICFG，見算法 2）以及更進(jìn)一步的近似式 ICFG（xICFG，見算法 3）。其中 ICFG 是以漸進(jìn)方式使用生成器的更新一點(diǎn)一點(diǎn)地逐步更新鑒別器，使得生成器可以不斷提供新的更有難度的樣本，從而防止鑒別器過(guò)擬合。而 xICFG 則能通過(guò)訓(xùn)練一個(gè)固定大小的近似器（近似 ICFG 所獲得的生成器的行為）來(lái)對(duì) ICFG 得到的生成器進(jìn)行壓縮，從而提升效率。

研究者還發(fā)現(xiàn)，通常的使用 logistic 模型的 GAN 與使用一種極端設(shè)置的 xICFG 的特例高度相關(guān)，即：GAN 的生成器更新等效于粗略近似 T=1 的 ICFG 得到的生成器。這個(gè)視角是理解 GAN 的不穩(wěn)定性的新角度，即：GAN 的不穩(wěn)定性源自 T 過(guò)小以及粗略近似。

研究者進(jìn)行了圖像生成的實(shí)驗(yàn)，結(jié)果表明他們提出的新方法是有效的。下圖給出了各種方法生成的圖像的質(zhì)量（inception 分?jǐn)?shù)）隨訓(xùn)練時(shí)間的變化情況。

可以看到，盡管 GAN1（使用了 logd 技巧的 GAN）在 LSUN 數(shù)據(jù)集上偶爾有更優(yōu)的表現(xiàn)，但 xICFG 的表現(xiàn)總體更優(yōu)且更穩(wěn)定。

8、用于高斯圖模型中最優(yōu)估計(jì)的圖非凸優(yōu)化 Graphical Nonconvex Optimization for Optimal Estimation in Gaussian Graphical Model

論文地址：https:///abs/1706.01158

高斯圖模型已被廣泛用于表示一組變量之間的成對(duì)的條件依賴關(guān)系。graphical lasso 是估計(jì)高斯圖模型的最常用方法之一。但是，它還未達(dá)到理想的收斂速度。具體而言，一般認(rèn)為 graphical lasso 的譜范數(shù)中的最優(yōu)收斂率大約為

其中 n 是樣本規(guī)模，d 是節(jié)點(diǎn)數(shù)量，s 是實(shí)際的圖中的邊數(shù)。

在這篇論文中，研究者提出了用于高斯圖模型中的最優(yōu)估計(jì)的圖非凸優(yōu)化。然后又通過(guò)一系列自適應(yīng)的凸程序來(lái)近似求解。研究者指出，盡管新提出的方法求解的是一系列凸程序，但研究表明在某些規(guī)律性條件下，這種新提出的用于估計(jì)稀疏集中度矩陣的估計(jì)器能實(shí)現(xiàn) 的理想收斂率，就好像非零位置事先已知一樣。算法 1 展示了這個(gè)近似求解過(guò)程。然后，通過(guò)使用估計(jì)的邊際方差來(lái)重新調(diào)整逆相關(guān)矩陣，可以得到該集中度矩陣的一個(gè)估計(jì)器。

算法 1 可使用 glasso 等現(xiàn)有的 R 語(yǔ)言軟件包實(shí)現(xiàn)。

這種新提出的方法在計(jì)算上是可行的，并且能得到能實(shí)現(xiàn)理想收斂速度的估計(jì)器。使用凸程序通過(guò)序列近似引入的統(tǒng)計(jì)誤差可以使用稀疏模式的概念來(lái)進(jìn)一步提升。

研究者分析了新提出的估計(jì)器的理論性質(zhì)，還將這種新方法擴(kuò)展到了半?yún)?shù)圖模型中，并通過(guò)數(shù)值研究表明新提出的估計(jì)器在估計(jì)高斯圖模型方面的表現(xiàn)優(yōu)于其它常用方法。

9、用于大型多類分類問(wèn)題的候選項(xiàng)與噪聲估計(jì) Candidates v.s. Noises Estimation for Large Multi-Class Classification Problem

論文地址：https:///abs/1711.00658

圖像分類和語(yǔ)言建模等很多任務(wù)的類別數(shù)量往往很大，采樣是應(yīng)對(duì)這類任務(wù)的常用方法，能夠幫助降低計(jì)算成本和提升訓(xùn)練速度。這篇論文對(duì)這一思想進(jìn)行了擴(kuò)展，提出了一種使用一個(gè)類別子集（候選項(xiàng)類別，其余類別被稱為噪聲類別——會(huì)被采樣用于表示所有噪聲）的用于多類分類問(wèn)題的方法：候選項(xiàng)與噪聲估計(jì)（CANE）。

研究者表明 CANE 總是能保持一致的表現(xiàn)并且很有計(jì)算效率。此外，當(dāng)被觀察到的標(biāo)簽有很高的概率屬于被選擇的候選項(xiàng)時(shí)，所得到的估計(jì)器會(huì)有很低的統(tǒng)計(jì)方差，接近最大似然估計(jì)器的統(tǒng)計(jì)方差。

研究者通過(guò)兩個(gè)具體算法展現(xiàn)了 CANE 方法的優(yōu)越性。其一是用于 CANE 的一般隨機(jī)優(yōu)化過(guò)程（算法 1）：

下圖則給出了神經(jīng)語(yǔ)言建模實(shí)驗(yàn)的結(jié)果?？梢钥吹?，CANE 方法的收斂速度比 NCE 和 Blackout 更快，同時(shí)還達(dá)到了與 softmax 方法同等的困惑度。

總體而言，實(shí)驗(yàn)結(jié)果表明 CANE 的預(yù)測(cè)準(zhǔn)確度優(yōu)于 NCE 及其變體方法和多種之前最佳的樹分類器，同時(shí)其速度也顯著優(yōu)于標(biāo)準(zhǔn)的 O(K) 方法。

10、使用演示的策略優(yōu)化 Policy Optimization with Demonstrations

論文地址：

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

對(duì)強(qiáng)化學(xué)習(xí)方法而言，探索仍然是一個(gè)突出的難題，尤其是在獎(jiǎng)勵(lì)信號(hào)稀疏的環(huán)境中。目前針對(duì)這一問(wèn)題的研究方向主要有兩個(gè)：1）通過(guò)鼓勵(lì)智能體訪問(wèn)之前從未見過(guò)的狀態(tài)來(lái)重塑原來(lái)的獎(jiǎng)勵(lì)函數(shù)；2）使用從某個(gè)專家策略采樣的演示軌跡來(lái)引導(dǎo)學(xué)習(xí)過(guò)程。從演示中學(xué)習(xí)的方法看起來(lái)有克服探索難題的希望，但這通常需要難以收集的質(zhì)量很高的演示。

結(jié)合這兩種思路，研究者提出了一種有效地利用可用演示來(lái)引導(dǎo)探索的方法，即強(qiáng)制所學(xué)到的策略與當(dāng)前演示之間的占有率匹配。這種方法背后的直觀思想是，當(dāng)獎(jiǎng)勵(lì)信號(hào)不可用時(shí)，智能體應(yīng)該在早期學(xué)習(xí)階段模擬所演示的行為，從而實(shí)現(xiàn)探索。在獲得了足夠多的能力之后，智能體就可以自己探索新狀態(tài)了。這實(shí)際上是一種動(dòng)態(tài)的固有獎(jiǎng)勵(lì)機(jī)制，可被引入強(qiáng)化學(xué)習(xí)用于重塑原生的獎(jiǎng)勵(lì)。

基于此，研究者開發(fā)了一種全新的使用演示的策略優(yōu)化（POfD）方法，可從演示數(shù)據(jù)獲取知識(shí)來(lái)提升探索效果。研究表明 POfD 能隱式地塑造動(dòng)態(tài)獎(jiǎng)勵(lì)并助益策略提升。此外，它還可以與策略梯度方法結(jié)合起來(lái)得到當(dāng)前最佳的結(jié)果。

研究者在一系列常見的基準(zhǔn)稀疏獎(jiǎng)勵(lì)任務(wù)上進(jìn)行了實(shí)驗(yàn)。結(jié)果發(fā)現(xiàn)，他們提出的方法的表現(xiàn)甚至可媲美用在理想密集獎(jiǎng)勵(lì)環(huán)境中的策略梯度方法；而且即使演示很少且不完美，這種新方法依然表現(xiàn)優(yōu)異。下面兩張圖給出了新提出的 POfD 方法與幾種強(qiáng)基準(zhǔn)方法分別在具有離散動(dòng)作空間和連續(xù)工作空間的稀疏環(huán)境中的學(xué)習(xí)曲線。

各種方法在具有連續(xù)動(dòng)作空間的稀疏環(huán)境中的學(xué)習(xí)曲線

11、邊密度屏障：組合推理中的計(jì)算-統(tǒng)計(jì)權(quán)衡 The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference

統(tǒng)計(jì)推理的一大最主要目標(biāo)是確定變量之間的依賴結(jié)構(gòu)，即推理底層圖模型的結(jié)構(gòu)。這篇論文關(guān)注的是一個(gè)更加具體的推理問(wèn)題：檢驗(yàn)底層圖中是否有特定的組合結(jié)構(gòu)。

盡管對(duì)這一問(wèn)題的信息論極限的研究已有很多了，但能否通過(guò)有效的算法得到這樣的極限很大程度仍未被研究過(guò)。此外，檢驗(yàn)問(wèn)題（尤其是圖模型的組合結(jié)構(gòu)）的構(gòu)建方式對(duì)信息論極限的可達(dá)成性的影響方式也并不明朗。

為了理解這兩個(gè)問(wèn)題，研究者在這篇論文中描述了圖模型中組合推理的這種基本極限；并基于一種 oracle 計(jì)算模型量化研究了達(dá)到這個(gè)信息論極限所需的最小計(jì)算復(fù)雜度。

研究證明，要在空?qǐng)D上檢驗(yàn)團(tuán)（clique）、最近鄰圖、完美匹配等常見組合結(jié)構(gòu)，或在小團(tuán)上檢驗(yàn)大團(tuán)，信息論極限是無(wú)法通過(guò)一般的可實(shí)現(xiàn)算法達(dá)到的。

更重要的是，研究者定義了名為弱邊密度 μ 和強(qiáng)邊密度 μ' 的結(jié)構(gòu)量。根據(jù)定義，邊集的弱邊密度表征了可從一個(gè)無(wú)效（null）變到另一個(gè)圖的關(guān)鍵邊的密集程度。這能反應(yīng)這兩個(gè)圖的差異水平。強(qiáng)邊密度是另一個(gè)表征這兩個(gè)圖的差異水平的量，且總是不小于弱邊密度。下面給出了 μ 和 μ' 的定義：

這兩個(gè)結(jié)構(gòu)量的一大突出性質(zhì)是它們僅依賴于被測(cè)試的組合結(jié)構(gòu)的拓?fù)湫再|(zhì)。它們能幫助研究者理解組合推理問(wèn)題的結(jié)構(gòu)性質(zhì)決定其計(jì)算復(fù)雜度的方式。研究表明，如果 μ 遠(yuǎn)小于 μ'，則信息論下界和計(jì)算有效的下界之間會(huì)存在明顯差距。下面給出了 4 個(gè)案例的具體最優(yōu)比率；可以看到，這些案例都存在統(tǒng)計(jì)與計(jì)算的權(quán)衡。

本研究也是首個(gè)確定和解釋無(wú)向圖模型中組合推理問(wèn)題的統(tǒng)計(jì)和計(jì)算之間的基本權(quán)衡的研究。

12、異步去中心化并行隨機(jī)梯度下降 Asynchronous Decentralized Parallel Stochastic Gradient Descent

論文地址：https:///abs/1710.06952

最常用的分布式機(jī)器學(xué)習(xí)系統(tǒng)要么是同步的，要么就是中心化異步的。AllReduce-SGD 這樣的同步算法在異構(gòu)環(huán)境中表現(xiàn)很差，而使用參數(shù)服務(wù)器的異步算法則存在很多問(wèn)題，其中包括工作器（worker）很多時(shí)參數(shù)服務(wù)器的通信問(wèn)題以及當(dāng)參數(shù)服務(wù)器的流量擁堵時(shí)收斂性下降的問(wèn)題。

研究者在這篇論文中提出了一種異步去中心化并行隨機(jī)梯度下降（AD-PSGD），能在異構(gòu)環(huán)境中表現(xiàn)穩(wěn)健且通信效率高并能維持最佳的收斂速率。理論分析表明 AD-PSGD 能以和 SGD 一樣的最優(yōu)速度收斂，并且能隨工作器的數(shù)量線性提速。下面是該算法的工作過(guò)程：

研究者使用 Torch 和 MPI 在多達(dá) 128 個(gè) P100 GPU 的 IBM S822LC 集群上實(shí)現(xiàn)和評(píng)估了 AD-PSGD。實(shí)驗(yàn)結(jié)果表明，AD-PSGD 的表現(xiàn)優(yōu)于最佳的去中心化并行 SGD（D-PSGD）、異構(gòu)并行 SGD（A-PSGD）和標(biāo)準(zhǔn)的數(shù)據(jù)并行 SGD（AllReduce-SGD）。AD-PSGD 在異構(gòu)環(huán)境中的表現(xiàn)往往能超出其它方法多個(gè)數(shù)量級(jí)。

下圖給出了在 ImageNet 數(shù)據(jù)集上基于 ResNet-50 模型得到的訓(xùn)練損失和每 epoch 訓(xùn)練時(shí)間情況?？梢钥吹?，AD-PSGD 和 AllReduce-SGD 的收斂情況接近，都優(yōu)于 D-PSGD。在使用 64 個(gè)工作器時(shí)，AD-PSGD 每 epoch 耗時(shí) 264 秒，而另外兩種方法每 epoch 耗時(shí)會(huì)超過(guò) 1000 秒。

下圖則展示了各種方法在 CIFAR10 上為 VGG（通信密集型）和 ResNet-20（計(jì)算密集型）模型帶來(lái)的加速情況?？梢悦黠@看到 AD-PSGD 一直都有最優(yōu)的表現(xiàn)。

AD-PSGD 是首個(gè)在超過(guò) 100 個(gè) GPU 的規(guī)模上達(dá)到接近 AllReduce-SGD 的 epoch 收斂速度的異步算法。

13、D2：在去中心化數(shù)據(jù)上的去中心化訓(xùn)練 D2: Decentralized Training over Decentralized Data

論文地址：https:///abs/1803.07068

以去中心化的方式訓(xùn)練機(jī)器學(xué)習(xí)模型近來(lái)得到了很大的研究關(guān)注。在使用多個(gè)工作器訓(xùn)練機(jī)器學(xué)習(xí)模型時(shí)（其中每一個(gè)都會(huì)從自己的數(shù)據(jù)源收集數(shù)據(jù)），從各個(gè)不同的工作器收集的數(shù)據(jù)也各不相同時(shí)這些數(shù)據(jù)是最有用的。但是，近期的很多去中心化并行隨機(jī)梯度下降（D-PSGD）研究都假設(shè)托管在不同工作器上的數(shù)據(jù)并沒(méi)有很大的差異——否則這些方法的收斂速度會(huì)非常慢。

研究者在這篇論文中提出了一種全新的去中心化并行隨機(jī)梯度下降算法 D2，該算法是為各工作器之間數(shù)據(jù)差異很大的情況（可以說(shuō)是“去中心化”數(shù)據(jù)）設(shè)計(jì)的。

D2 基于標(biāo)準(zhǔn)的 D-PSGD 算法，但添加了一個(gè)降低方差的組件。在這種 D2 算法中，每個(gè)工作器都會(huì)存儲(chǔ)上一輪迭代的隨機(jī)梯度和局部模型，并將它們與當(dāng)前的隨機(jī)梯度和局部模型線性地結(jié)合到一起。這能將收斂速度改善，其中 ζ2 是不同工作器上的數(shù)據(jù)差異，σ2 是每個(gè)工作器內(nèi)的數(shù)據(jù)方差，n 是工作器的數(shù)量，T 是迭代次數(shù)。

研究者在圖像分類任務(wù)上對(duì) D2 進(jìn)行了評(píng)估，其中每個(gè)工作器都僅能讀取一個(gè)有限標(biāo)簽集的數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明 D2 的表現(xiàn)顯著優(yōu)于 D-PSGD。下面給出了在無(wú)數(shù)據(jù)混洗（unshuffled）情況下（不同工作器之間的數(shù)據(jù)差異最大）的不同分布式訓(xùn)練算法的收斂性比較。

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

14、實(shí)現(xiàn)更高效的隨機(jī)去中心化學(xué)習(xí)：更快收斂和稀疏通信 Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication

論文地址：https:///abs/1805.09969

去中心化優(yōu)化問(wèn)題近來(lái)得到了越來(lái)越大的關(guān)注。大多數(shù)現(xiàn)有方法都是確定性的，具有很高的每次迭代成本，并且收斂速度與問(wèn)題條件數(shù)呈二次關(guān)系。此外，為了確保收斂還必需密集的通信，即使數(shù)據(jù)集是稀疏的也是如此。

在這篇論文中，研究者將去中心化優(yōu)化問(wèn)題泛化成了一個(gè)單調(diào)算子根查找問(wèn)題，并提出了一種名為去中心化隨機(jī)反向聚合（DSBA）的算法。

在 DSBA 的計(jì)算步驟，每個(gè)節(jié)點(diǎn)都會(huì)計(jì)算一個(gè)隨機(jī)近似的單調(diào)算子的預(yù)解式（resolvent），以降低對(duì)問(wèn)題條件數(shù)的依賴程度。這樣的預(yù)解式接受脊回歸等問(wèn)題中的閉式解。在 DSBA 的通信步驟，每個(gè)節(jié)點(diǎn)都接收連續(xù)迭代之間差異的非零分量，以重建其臨近節(jié)點(diǎn)的迭代。因?yàn)??2-relaxed AUC 最大化問(wèn)題等效于凸凹函數(shù)的極小極大問(wèn)題，其微分是一個(gè)單調(diào)算子，因此能無(wú)縫地適配 DSBA 的形式。

該算法具有以下優(yōu)勢(shì)：（1）能以與問(wèn)題條件數(shù)呈線性的速度以幾何方式收斂，（2）可以僅使用稀疏通信實(shí)現(xiàn)。此外，DSBA 還能處理 AUC 最大化等無(wú)法在去中心化設(shè)置中高效解決的學(xué)習(xí)問(wèn)題。研究者在論文中也給出了對(duì)該算法的收斂性分析。

研究者在凸最小化和 AUC 最大化上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明新提出的方法是有效的。下圖給出了 DSBA 與幾種之前最佳方法在 logistic 回歸上的結(jié)果比較。

可以看到，DSBA 的表現(xiàn)是最優(yōu)的，而且能以更低的計(jì)算成本更快地收斂。

15、誤差補(bǔ)償式量化 SGD 及其在大規(guī)模分布式優(yōu)化中的應(yīng)用 Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization

論文地址：https:///abs/1806.08054

這一輪機(jī)器學(xué)習(xí)熱潮的出現(xiàn)很大程度上得益于計(jì)算機(jī)處理能力的指數(shù)級(jí)發(fā)展以及出現(xiàn)了可用于訓(xùn)練模型的海量數(shù)據(jù)。為了有效地完成海量數(shù)據(jù)的訓(xùn)練，往往需要用到分布式優(yōu)化方法，其中包括數(shù)據(jù)并行化的處理方法。但在這樣的分布式框架中，各個(gè)節(jié)點(diǎn)之間的通信速度往往會(huì)成為整體性能的關(guān)鍵制約因素。目前的常見解決方法是對(duì)節(jié)點(diǎn)之間的通信信息進(jìn)行壓縮，但這會(huì)引入量化誤差。

為了解決這一問(wèn)題，這篇論文提出通過(guò)使用累積的所有之前的量化誤差的誤差反饋方案來(lái)補(bǔ)償當(dāng)前的局部梯度。研究者將該方法稱為“誤差補(bǔ)償式量化隨機(jī)梯度下降（ECQ-SGD）”。實(shí)驗(yàn)結(jié)果表明這種方法能實(shí)現(xiàn)比很多基準(zhǔn)方法更快更穩(wěn)定的收斂。下面是該算法的工作過(guò)程：

在量化完成之后，總體通信成本會(huì)降至 32+dr 比特（r ? 32），遠(yuǎn)少于原來(lái)的 32 位全精度梯度所需的 32d 比特；其中 d 是原向量的維度；其中 s 是非零量化級(jí)別的數(shù)量：s 越大，則量化越細(xì)粒度，通信成本也就越高。下圖給出了在 ILSVRC-12 數(shù)據(jù)集上訓(xùn)練 ResNet-50 模型時(shí)，使用不同數(shù)量的 GPU 的吞吐量情況比較：

在使用 512 個(gè) GPU 進(jìn)行訓(xùn)練時(shí)，ECQ-SGD 相對(duì)于普通 SGD 實(shí)現(xiàn)了 143.5% 的加速（每秒各 66.42k 與 27.28k 張圖像）。如果節(jié)點(diǎn)之間的帶寬更小，這樣的優(yōu)勢(shì)還會(huì)更加顯著。

研究者還在該論文中提供了該方法的理論保證：分析了其收斂行為并證明了其相對(duì)于其它之前最佳方法的優(yōu)勢(shì)。

16. 使用聯(lián)網(wǎng)智能體的完全去中心化多智能體強(qiáng)化學(xué)習(xí) Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents

論文地址：https:///abs/1802.08757

在多智能體強(qiáng)化學(xué)習(xí)（MARL）問(wèn)題中，多個(gè)智能體的聯(lián)合行動(dòng)會(huì)影響它們所處的共同環(huán)境。在每個(gè)狀態(tài)，每個(gè)智能體都會(huì)執(zhí)行一個(gè)動(dòng)作，這些動(dòng)作共同決定了環(huán)境的下一個(gè)狀態(tài)和每個(gè)智能體的獎(jiǎng)勵(lì)。此外，這些智能體可能針對(duì)的是不同的任務(wù)，會(huì)有不同的獎(jiǎng)勵(lì)函數(shù)；但每個(gè)智能體都只能觀察自己的獎(jiǎng)勵(lì)。每個(gè)智能體都會(huì)基于局部觀察到的信息以及從網(wǎng)絡(luò)中的臨近智能體接受到的信息各自做出決策。在這種設(shè)置內(nèi)，所有智能體的整體目標(biāo)是通過(guò)與其臨近智能體交換信息而最大化在整個(gè)網(wǎng)絡(luò)上的全局平均回報(bào)。

針對(duì)這一問(wèn)題的中心化方法存在可擴(kuò)展性和穩(wěn)健性等方面的問(wèn)題，因此，研究者在這篇論文中基于一種用于 MARL 的全新策略梯度定理提出了兩種去中心化 actor-critic 算法；結(jié)合函數(shù)近似，可應(yīng)用于狀態(tài)和智能體數(shù)量都非常大的大規(guī)模 MARL 問(wèn)題。

基于動(dòng)作-價(jià)值函數(shù)的聯(lián)網(wǎng)式 actor-critic 算法

基于狀態(tài)-價(jià)值 TD 誤差的聯(lián)網(wǎng)式 actor-critic 算法

具體來(lái)說(shuō)，actor 步驟是由每個(gè)智能體單獨(dú)執(zhí)行的，無(wú)需推斷其它智能體的策略。對(duì)于 critic 步驟，研究者提出了一種在整個(gè)網(wǎng)絡(luò)通過(guò)通信實(shí)現(xiàn)的共識(shí)更新（consensus update），即每個(gè)智能體都會(huì)與其網(wǎng)絡(luò)中的臨近智能體共享其價(jià)值函數(shù)的估計(jì)，從而得到一個(gè)共識(shí)估計(jì)。這個(gè)估計(jì)又會(huì)被用在后續(xù)的 actor 步驟中。通過(guò)這種方式，每個(gè)智能體的局部信息都能散布到整個(gè)網(wǎng)絡(luò)，從而最大化整個(gè)網(wǎng)絡(luò)層面的獎(jiǎng)勵(lì)。

這種算法是完全漸進(jìn)式的，可以以一種在線形式實(shí)現(xiàn)。研究者還提供了當(dāng)價(jià)值函數(shù)位于線性函數(shù)類別內(nèi)近似求取時(shí)的算法收斂性分析。

研究者使用線性和非線性函數(shù)近似執(zhí)行了大量模擬實(shí)驗(yàn)，對(duì)所提出的算法進(jìn)行了驗(yàn)證。下圖給出了當(dāng)使用神經(jīng)網(wǎng)絡(luò)進(jìn)行函數(shù)近似時(shí)，在協(xié)同導(dǎo)航任務(wù)上的全局平均獎(jiǎng)勵(lì)。其中 Central-1 和 Central-2 分別是算法 1 和算法 2 對(duì)應(yīng)的中心化方法。

研究者表示該研究是首個(gè)使用函數(shù)近似的聯(lián)網(wǎng)智能體的完全去中心化 MARL 算法研究。