AAAI 2018最佳論文出爐，中國留學生再下一城

02-15

本文由「AI前線」原創，原文鏈接：AAAI 2018最佳論文出爐，中國留學生再下一城
編輯｜Natalie
譯者｜馬卓奇
消息來源｜AAAI 官網，Twitter

AI 前線導讀： 」人工智慧頂級會議 AAAI 2018 於今天（2 月 2 日）在美國路易斯安那州新奧爾良正式開幕。然而，在大會開始前，最佳論文獲獎信息就已經在網上傳播開了，加拿大阿爾伯塔大學的兩名中國留學生斬獲這一獎項。1 月 31 日，最佳論文作者 Martin Müller 教授搶先在推特上公開了他們的這篇獲獎論文，AI 前線將簡要介紹這篇獲獎論文的內容。」

去年的 AAAI 大會上華人學者的名字刷屏了整個接收論文名單，但最佳論文獎和最佳學生論文獎均沒有出現華人的名字。這一次，霸屏還在繼續，而最佳論文獎也終於再度被華人學者收入囊中。根據 jeffhuang 統計的獲獎論文清單（http://jeffhuang.com/best_paper_awards.html），這應該是自 1996 年以來華人學者第五次獲得 AAAI 最佳論文獎。

AAAI 最佳論文獎獲獎論文體現了技術貢獻和闡述的最高標準。這個獎通常是獎勵給在計算機科學領域兼具廣度和獨特性的研究者，這些研究通常構建了不同科系和學科之間的橋樑。

Martin Müller 教授 Twitter 消息

AAAI 官方程序手冊節選

本屆獲得 AAAI「最佳論文獎」的是加拿大阿爾伯塔大學的 Martin Müller 教授與他的兩位學生 Chenjun Xiao、Jincheng Mei 的論文：「Memory-Augmented Monte Carlo Tree Search」（記憶增強的蒙特卡洛樹搜索）。

AI 前線趣聞：
該論文的導師，阿爾伯塔大學教授 Martin Müller 是計算機圍棋頂級專家，主要研究領域包括：博弈樹搜索和規劃的蒙特卡洛方法、大規模並行搜索和組合博弈論。實際上，2016 年揭開人工智慧火熱大戲序幕的 AlphaGo 的設計研發主導人物 David Silver 和黃士傑（Aja Huang）（他們分別是發表於 Nature 的 AlphaGo 論文的一作和二作）都曾師從於他。甚至有知乎網友將 Martin Müller 教授稱為「王背後的男人——AlphaGo 背後的祖師爺」。
Chenjun Xiao 於 2014 年加入 Martin Müller 教授的研究小組，攻讀碩士學位，2016 年開始攻讀博士學位。
Jincheng Mei 本科畢業於華南理工大學，碩士畢業於上海交通大學，於 2015 年進入加拿大阿爾伯塔大學攻讀博士學位，師從 Dale Schuurmans 教授。

以下是 AI 前線對論文內容的簡要編譯：

摘要

這篇論文提出了記憶增強的蒙特卡洛樹搜索演算法（Memory-Augmented Monte Carlo Tree Search，M-MCTS），為在線實時搜索提供了一個新的利用泛化性的方法。M-MTCS 的核心思想是為 MCTS 增加了一個記憶結構，該結構的每一個入口都含有一個特殊狀態信息。記憶結構結合相似狀態的估計產生一個近似的值估計。作者發現，基於記憶的值估計結果比溫和條件下高概率的普通蒙特卡洛演算法估計結果更好。作者在圍棋遊戲中評測了 M-MCTS 的性能。實驗結果表明，在相同模擬次數下，M-MCTS 優於原來的 MCTS。

論文介紹

MCTS 的核心思想是根據快速蒙特卡洛模擬對狀態的估計值構建搜索樹。給定當前棋面狀態，通過隨機的自我博弈模擬上千場棋局，直到遊戲結束。隨後，根據模擬結果的平均值估測狀態值。同時，搜索樹通過 bandit 演算法對於探索（exploration）和利用（exploitation）進行權衡，導引模擬的方向。然而，對於巨大的狀態空間，值估計的準確率不能得到有效保證，因為在有限的搜索時間內，平均值估計容易呈現較高方差。這種不準確的估計會誤導搜索樹的構建方向，從而嚴重影響演算法的性能。

近期提出了幾個新的機器學習演算法，旨在解決 MCTS 的這一缺點。例如，使用深度神經網路來學習域知識，並近似狀態值函數。它們與 MCTS 的結合為實踐中提高搜索樣本效率帶來了啟發式演算法。

機器學習方法的成功絕大部分可以歸結於其強大的泛化能力，例如相似狀態共享信息。廣義的域知識通常由函數近似來表示，例如深度神經網路，通過專門的數據集或自我生成的模擬進行離線訓練。

目前已有大量的研究從離線學習中發現泛化能力，相比之下很少有人關注在線實時搜索時如何利用演算法泛化帶來的好處。這篇論文提出了記憶增強的 MCTS 演算法，為利用在線泛化提供了一個不一樣的方法。作者設計了一個記憶結構（memory），每一個入口包含某一個特定狀態的信息，作為構建在線值近似的基礎。論文從理論和實踐（圍棋遊戲實驗）上證實了該基於記憶的框架對 MCTS 性能的提升。

圖 1：M-MCTS 演算法解釋。

當葉子狀態 s 被搜索到時，特徵表示?(s) 隨之產生，隨後用於搜索基於記憶的值近似

。值近似用於更新 s 和所有的父節點，這一過程由圖中紅色箭頭表示。

實驗

作者在中國圍棋遊戲中對 M-MCTS 演算法進行了測試。

基準實驗

演算法實現基於開源圍棋項目 Fuego，但是增加了深度卷積神經網路（DCNN）來提升性能。DCNN 在狀態節點剛被添加入搜索樹時調用，來初始化模擬數據。演算法以一種同步方式在 MCTS 中加入 DCNN，即當 DCNN 返回估測結果時，搜索會繼續進行。基準實驗在 Fuego 中取得了 97% 的勝利率，每一步進行 10000 次模擬。

實驗結果

演算法主要有 3 個參數，記憶結構中的近鄰數量 M：{20，50，100}、溫度參數τ：{0.05，0.1，1}，及每步模擬運行次數：{1000，5000，10000}。作者在實驗中測試了這 3 個參數對 M-MCTS 演算法性能的影響。

圖 2（a）-（c）顯示了不同 M 值的實驗結果。

當 M 和τ分別取{50，0.1}時，演算法得到了最好結果：每步運行模擬次數為 10000，與基準實驗進行圍棋遊戲中取得了 70% 的勝利率，每一次結果的標準差大約在 2.5%。

在同等參數情況下，作者對記憶結構的大小進行了實驗。記憶結構的大小取值為{1000,5000,10000}。一般情況下，記憶結構越大，演算法性能越好，因為搜索中能包括更多的候選狀態。圖 2（d）顯示，記憶結構大小為 10000 時演算法取得最佳性能。

作者也對比了在每走一步所需計算時間相同的情況下（每步 5 秒），M-MCTS 在與基準實驗進行圍棋遊戲中取得了 61% 的勝利率。

未來工作

作者計劃未來探索以下兩個方向：

1）是否可以通過將離線學習的近似值與所提出的在線基於記憶的框架結合，得到更好的泛化效果。

2）M-MCTS 中利用了為預測行為而設計的神經網路進行特徵表示，未來將探索如何將特徵表示學習與 M-MCTS 整合，成為端到端的演算法。

M-MCTS 更加詳細的演算法實現請參見論文原文（點擊閱讀原文可直接打開）：

http://webdocs.cs.ualberta.ca/~mmueller/ps/2018/Chenjun-Xiao-M-MCTS-aaai18-final.pdf

AAAI 官方資料：

https://aaai.org/Conferences/AAAI-18/wp-content/uploads/2018/01/AAAI18Program.pdf

小彩蛋： 如果你平常有閱讀論文的習慣，並且願意做一些論文編譯整理的工作，或者有國際頂會的論文解讀稿件尋求發布，歡迎關注 AI 前線（ai-front），在後台留下聯繫方式，我們將與你聯繫，並進行更多交流！