本文轉(zhuǎn)載自騰訊AI實驗室，微信號 tencent_ailab

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

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

第一部分：新模型與新框架

1、用于強化學(xué)習的基于反饋的樹搜索

Feedback-based Tree Search for Reinforcement Learning

論文地址：https://arxiv.org/abs/1805.05935

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

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

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

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

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

2、通過學(xué)習遷移實現(xiàn)遷移學(xué)習

Transfer Learning via Learning to Transfer

論文地址：

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

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

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

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

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

3、通過強化學(xué)習實現(xiàn)端到端的主動目標跟蹤

End-to-end Active Object Tracking via Reinforcement Learning

論文地址：https://arxiv.org/abs/1705.10561

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

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

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

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

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

4、使用局部坐標編碼的對抗學(xué)習

Adversarial Learning with Local Coordinate Coding

論文地址：https://arxiv.org/abs/1806.04895

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

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

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

研究者用 PyTorch 實現(xiàn)了 LCC-GAN 并通過大量基于真實世界數(shù)據(jù)集的實驗對該方法進行了評估。結(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 的泛化界限，并證明維度較小的輸入就足以實現(xiàn)優(yōu)良的泛化表現(xiàn)。

5、一種可變度量超松弛混合臨近外梯度方法的算法框架

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

論文地址：https://arxiv.org/abs/1805.06137

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

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

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

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

PADMM-EBB 算法

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

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

第二部分：分布式與去中心化

6、針對次模函數(shù)最小化的元素安全篩選算法

Safe Element Screening for Submodular Function Minimization

下載地址：https://arxiv.org/abs/1805.08527

次模函數(shù)可以看成是離散函數(shù)中的凸函數(shù)，其在眾多領(lǐng)域中有著重要應(yīng)用，比如：機器學(xué)習、計算機視覺和信號處理。然而，在大規(guī)模實際應(yīng)用中，次模函數(shù)最小化問題的求解依然是一個具有挑戰(zhàn)性的問題。在本文中，我們第一次嘗試將大規(guī)模稀疏學(xué)習中新興的篩選方法擴展到次模函數(shù)最小化中，以加快它的求解過程。通過仔細研究次模函數(shù)最小化問題和其對應(yīng)凸問題之間的關(guān)系以及該凸問題最優(yōu)解的估計，我們提出了一種新穎安全的元素篩選算法，能夠在優(yōu)化過程中迅速檢測出一定包含在最優(yōu)解中的元素（我們稱為活躍元素）以及一定不包含在最優(yōu)解中的元素（不活躍元素）。通過刪除不活躍元素和固定活躍元素，問題規(guī)模得以顯著減小，從而我們能夠在不損失任何精度的情況下大大減少計算量。據(jù)我們所知，我們的方法是次模函數(shù)最優(yōu)化領(lǐng)域乃至組合優(yōu)化領(lǐng)域中的第一個篩選算法。因此，我們的方法為加速次模函數(shù)最小化算法提供了一種新思路。在合成數(shù)據(jù)集和實際數(shù)據(jù)集上的實驗結(jié)果均證實我們的算法能夠顯著加速次模函數(shù)最小化問題的求解。

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

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

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

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

7、生成對抗網(wǎng)絡(luò)的復(fù)合函數(shù)梯度學(xué)習

Composite Functional Gradient Learning of Generative Adversarial Models

論文地址：https://arxiv.org/abs/1801.06309

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

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

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

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

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

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

8、用于高斯圖模型中最優(yōu)估計的圖非凸優(yōu)化

Graphical Nonconvex Optimization for Optimal Estimation in Gaussian Graphical Model

論文地址：https://arxiv.org/abs/1706.01158

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

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

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

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

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

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

9、用于大型多類分類問題的候選項與噪聲估計

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

論文地址：https://arxiv.org/abs/1711.00658

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

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

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

另外，研究者還使用了一種樹結(jié)構(gòu)（葉表示類別）來促進對候選項選擇的快速波束搜索（算法 2）。這種波束搜索具有更低的復(fù)雜度，能快速得到預(yù)測結(jié)果，還能自然地輸出最靠前的多項預(yù)測。

研究者實驗了 CANE 方法在有大量類別的多類分類問題和神經(jīng)語言建模任務(wù)中的應(yīng)用。下圖展示了各種方法在不同分類數(shù)據(jù)集上的測試準確度隨 epoch 的變化情況。可以看到，有更大候選項集的 CANE 在準確度方面基本優(yōu)于其它方法，有時甚至能超過 softmax 方法。而且 CANE 方法的收斂速度明顯勝過噪音對比估計（NCE）和 Blackout。

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

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

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

Policy Optimization with Demonstrations

論文地址：

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

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

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

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

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

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

11、邊密度屏障：組合推理中的計算-統(tǒng)計權(quán)衡

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

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

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

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

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

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

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

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

第三部分：機器學(xué)習優(yōu)化方法與理論研究

12、異步去中心化并行隨機梯度下降

Asynchronous Decentralized Parallel Stochastic Gradient Descent

論文地址：https://arxiv.org/abs/1710.06952

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

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

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

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

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

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

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

D2: Decentralized Training over Decentralized Data

論文地址：https://arxiv.org/abs/1803.07068

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

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

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

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

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

14、實現(xiàn)更高效的隨機去中心化學(xué)習：更快收斂和稀疏通信

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

論文地址：https://arxiv.org/abs/1805.09969

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

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

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

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

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

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

15、誤差補償式量化 SGD 及其在大規(guī)模分布式優(yōu)化中的應(yīng)用

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

論文地址：https://arxiv.org/abs/1806.08054

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

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

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

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

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

16、使用聯(lián)網(wǎng)智能體的完全去中心化多智能體強化學(xué)習

Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents

論文地址：https://arxiv.org/abs/1802.08757

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

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

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

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

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

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

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

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

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。