Facebook田淵棟：NeurIPS 2020中了兩篇，感覺還算不錯！

點擊上方“CVer”，選擇加"星標"置頂

重磅干貨，第一時間送達

本文轉載自：AI科技評論

作者 |?田淵棟

編輯 |?陳大鑫?

做理論需要的基礎知識多，困難，周期長，沒有直接經濟效益，還只能一兩個人單打獨斗且無法使用大量計算資源，每個因素都和現(xiàn)在的主流發(fā)展方向（強調團隊合作，強調速度和新聞性，代碼開源，大數(shù)據(jù)，大量計算資源）背道而馳。

而且，理論研究論文大多艱深、晦澀難懂，結論依賴不現(xiàn)實的假設，難免令人望而卻步乃至失望。相比之下，實驗研究效果立竿見影，傳播快。

田淵棟如此說道。

理論研究要讓少數(shù)的、有情懷的人去做，遠離市場噪雜和競爭，慢慢地鉆研?！耙蝗f個碩士博士里有一個懷著這個理想，那遲早有一天會做出來的，大部分人不用費這個力氣的?！?/span>

田淵棟又道。

昨日，NeurIPS 2020放榜，9454篇論文提交，1900篇接收，錄取率僅為20.09%。

上海交通大學本碩、卡耐基梅隆大學機器人系博士，現(xiàn)任 Facebook 人工智能研究院（FAIR）研究員和研究經理的田淵棟這次投稿了三篇主打文章（一作或者最后一作），中了兩篇。

田淵棟表示：還算不錯。

得知自己中了兩篇論文之后，作為知乎上的熱愛分享、傳播知識的大V，田淵棟第一時間寫了兩篇小博客各自介紹了這兩篇篇論文：

第一篇設計了一個新的算法，來試圖解決多智能體合作時聯(lián)合優(yōu)化策略的問題。

第二篇提出了一種新的黑盒優(yōu)化的方法：LaMCTS (Latent Action Monte Carlo Tree Search)，這個方法基于蒙特卡羅樹搜索，但在這上面有改進。

AI科技評論第一時間聯(lián)系到了田淵棟博士，經授權，現(xiàn)把內容整理如下。

在介紹兩篇論文工作之前先把田淵棟博士的NeurIPS后感想轉述如下：

這篇一作文章的理論在deadline前四天才被發(fā)現(xiàn)，在理論被發(fā)現(xiàn)之前，對策略變化的得分計算一直用的是一個極其復雜的方案，考慮各種狀態(tài)進入和離開信息集的情況，光代碼本身就寫了一周，修理各種corner case修到頭都禿了。最后實驗上的效果也確實是單調上升，但一直證明不出來其正確性。

直到某一天晚上意識到根本不需要這么復雜，推出了非常簡單的公式之后不敢相信自己的眼睛，立即重寫代碼，從晚上十點半寫到十點四十分，跑出來的結果是一樣的，速度還快。

數(shù)學的美，可能正是美在這里。?

另一篇最后一作的中稿文章基本上我從頭到尾都重寫過一遍，包括abstract，introduction，方法還有實驗部分。反觀第三篇沒中的，其實整體思路及實驗效果都非常好，但因為寫作只把關了abstract和intro，導致方法論的描述部分出現(xiàn)了低級失誤，給reviewers造成了巨大的誤解，可惜了。

做研究，文章其實貴精不貴多，現(xiàn)在鋪天蓋地的AI論文，每天看arXiv都看不完，但留下印象的，給領域提供實質性貢獻的，其實并不多。

我每次向別人介紹FAIR內部的評價體系，都會說“我們不看論文數(shù)量”，每半年打績效，只問有沒有Top-3的工作，在每篇工作里的具體貢獻是什么：思路是誰提出的？代碼是誰寫的？實驗是誰跑的？效果是誰調上去的？定理是誰證的？文章是誰寫的？其它的各種掛名文列上去就行，也沒人會在意。這樣算下來，花大力氣發(fā)一篇好工作是正分，發(fā)一百篇毫無關聯(lián)的水文是零分甚至是負的印象分，這樣也可以鼓勵大家多出成果少搭便車。

我也在向這方面一直繼續(xù)努力。曾經挺羨慕那些文章列表上百的朋友們，但后來才明白什么才是自己想要走的道路。

之后的ICLR還會延續(xù)同樣的模式，除開被拒轉投的文章，還會有兩篇新的文章出來，還是老樣子，一篇一作，一篇最后一作。兩篇文章都非常不錯，而教師-學生的神經網絡理論分析也將回歸，用在一個大家想不到卻正是極其適合的地方，得到極其有趣的結果，敬請期待。

接下來田淵棟博士對兩篇中獎論文的介紹。

1

論文一

論文鏈接：https://arxiv.org/abs/2008.06495.pdf

論文作者：Yuandong Tian, Qucheng Gong, Tina Jiang

這篇文章設計了一個新的算法，來試圖解決多智能體合作時聯(lián)合優(yōu)化策略的問題。

對于不完美信息兩人零和游戲，比如說兩人德州撲克。

用現(xiàn)用的一些算法（比如說CFR）可以在理論上保證當?shù)螖?shù)足夠時一定收斂到納什均衡點。但不完美信息多智能體合作的策略優(yōu)化則要困難很多，并且往往會陷入局部極小值。

比如說有兩個玩家合作，玩家1抽一張暗牌紅桃A或黑桃A，然后向玩家2發(fā)一個紅桃A或黑桃A或方塊A的信號，讓玩家2猜A手上的牌是什么，猜中得1分，猜不中則得0分。

顯然在這種情況下，存在?種協(xié)議，這6種協(xié)議是完全對稱的，采用任何一種玩家2都可以猜中得1分。但如果規(guī)則稍微改一下，比如說發(fā)送黑桃A有0.1的附加分，那若玩家1和玩家2采用“抽紅桃A發(fā)紅桃A, 抽黑桃A發(fā)方塊A”的協(xié)議，就賺不到這個附加分，是局部極小策略。但玩家1和玩家2單方面都不想改變自己的策略，因為單方面改變的結果是對方不理解自己策略的改變，導致得分的下降。

那在這種情況下，要如何去優(yōu)化各自的策略呢？很多策略優(yōu)化方案采用就是按坐標優(yōu)化（Coordinate Descent），即假設其它人的策略不變，然后優(yōu)化自身的策略。這顯然在這里不太可行。而同時優(yōu)化多個智能體的策略，在不完美信息的條件下，又是比較困難的，見下圖：

假設帶陰影的這些信息集（Information Set）上的策略需要優(yōu)化，但問題在于如果改變了上游的策略，則下游信息集內各狀態(tài)的可到達概率就會發(fā)生各種變化，從而隱含地改變下游的期望得分；而下游策略的改變，又會改變上游的期望得分。

這就使得策略與收益得分相互間的影響變得非常復雜，而且存在“牽一發(fā)而動全身”的關系，讓聯(lián)合優(yōu)化變得非常困難——如果我們只想修改1000個信息集中的3個信息集的策略，那其它997個信息集上的期望得分也會發(fā)生變化，即便它們之上的策略并沒有發(fā)生任何改變。

這篇文章的一個主要貢獻，就是找到了一個”策略變化密度“（policy-change density）這樣一個量，滿足以下兩個條件：

1、 不管上下游的策略是否發(fā)生了變化，如果一個狀態(tài)的當前策略沒有變化，那策略變化密度就為0。

2、策略變化密度在所有狀態(tài)上的總和，就是整個游戲得分因策略變化后的改變量。

如果一個狀態(tài)的當前策略沒有變化，那么策略變化密度（policy-density change) 正好等于零。這個和周圍的策略有沒有變化無關。

有了這兩個性質之后，得分因策略變化后的改變量就可以分解成局部項了：如果只修改了3個信息集的策略，那么總的期望得分的增加就完全由這3個信息集上的策略變化密度的和來決定。這樣就極大簡化了計算。

? ? ? ?

策略變化后，整個游戲的得分改變量在每個信息集上的局部分解。

有了這個公式之后，再要聯(lián)合優(yōu)化策略就變得相對容易了。

這篇文章采用的是簡單的深度優(yōu)先搜索，從上游策略出發(fā)，先改變上游策略，然后給定上游策略，再改變下游策略，如此往復，然后看最后整個游戲的得分改變量的大小，最終選出最好的新策略組合。

這樣就能達到聯(lián)合策略搜索（Joint Policy Search）的目的，并且這樣的算法得到的策略性能一定是單調上升的。

運用這個方法，我們先在一些小規(guī)模的非完美信息合作游戲（主要是橋牌叫牌階段的簡化版）上進行了測試。我們從CFR得到的聯(lián)合策略開始，用搜索算法對當前的聯(lián)合策略進行改進（CFR1k+JPS），直到陷入局部極大值為止。結果發(fā)現(xiàn)確實有用，新的策略都改進了得分，而且越復雜的游戲，改進越大。

這部分代碼已經開源:

https://github.com/facebookresearch/jps

聯(lián)合策略搜索在四個不同的小游戲上都改進了游戲得分。

最后當然是在真的橋牌叫牌環(huán)境下進行測試。

們先用A2C自對弈訓練了一個還不錯的基線策略，然后用上文提到的聯(lián)合策略搜索（JPS）來改進隊友間的叫牌約定，并且和目前較好的橋牌AI軟件（WBridge5）進行了一千局開閉室比賽。

比賽是JPS和JPS一隊，WBridge5和WBridge5一隊。最后發(fā)現(xiàn)和基線策略相比，我們的效果確實變好了。

注意這里的兩階段訓練沒有用到任何人類對局，為的是能夠無監(jiān)督地學到全新的叫牌約定——讓機器學到人類所不知道的新東西永遠是很有意思的。

當然這里有個問題是我們只做了叫牌，沒有做打牌，叫牌完了之后游戲就結束了，并以雙明手（double-dummy）的分數(shù)，即所有牌攤開來打，來定勝負。

WBridge5是以正常叫牌加打牌的模式來優(yōu)化的，并且事先也沒有領教過我們學出來的新叫牌約定，所以這個比較不是特別公平（也被reviewer們使勁狂噴），但目前只有這個辦法（這部分代碼暫不開源，因為各種小trick比較多，之后等全部搞完了再說）。

?IMPs/b (平均每桌的國際比賽分）這個應該算是目前最好的結果了（State-of-the-Art）。

?

2

論文二

論文鏈接：https://arxiv.org/abs/2007.00708

論文作者：Linnan Wang, Rodrigo Fonseca, Yuandong Tian

（我們相關的工作還有一篇叫LaNAS，主要是將這個方法用在神經網絡架構搜索（NAS）上：Sample-Efficient Neural Architecture Search by Learning Action Space https://arxiv.org/abs/1906.06832。Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, Yuandong Tian）

這篇主要是提出了一種新的黑盒優(yōu)化（Black-box optimization）的方法。這個新的方法叫LaMCTS (Latent Action Monte Carlo Tree Search)，顧名思義這個是基于蒙特卡羅樹搜索（Monte Carlo Tree Search）的，但在這上面有改進。

傳統(tǒng)的MCTS的目標是在給定狀態(tài)空間（state space S）、行動空間（action space A）及狀態(tài)轉移函數(shù)（transition matrix, S, A -> S') 之后，通過搜索找到最優(yōu)的行動序列，以獲得最大的獎勵。

MCTS搜索是通過增量構建一棵以初始狀態(tài)?為根的樹來實現(xiàn)的，樹中的每個狀態(tài)結點都有一個簡單的模型，描述如果選擇行動，根據(jù)過去的經驗會有多少獎勵。新葉子結點的構建則權衡了過去的經驗（exploitation）和探索新的結點（exploration）這兩個目標，隨著搜索的進行，新葉子會更多集中在有希望的區(qū)域里面。

乍一看，MCTS和規(guī)劃有關，和黑盒優(yōu)化似乎無關，那它們之間是如何建立聯(lián)系的呢？

一般來說，黑盒優(yōu)化都是從一個初始解出發(fā)，通過不停迭代來改進當前解，直到無法再改進為止。

其主要性能指標是：達到同樣的函數(shù)值，需要多少次黑盒函數(shù)的調用，越少越好。因為在實際問題中，需要用黑盒優(yōu)化的場景，往往是函數(shù)調用開銷非常大且沒有導數(shù)信息的場景，比如說函數(shù)值是一個復雜系統(tǒng)運轉一天后的平均效率，或者是耗費巨資才可獲得的一個實驗結果，等等。

這個黑盒優(yōu)化的迭代過程可以用各種方案去刻劃：比如說從一個還不錯的起始點開始的局部搜索，一個從粗到細的逐步精化，或者說局部漸進和長程跳躍的組合（例如進化算法的演化和突變），等等，每種方案都對應不同的行動空間。

但從本質上來說，優(yōu)化和“下棋打游戲”等問題很大的不同點在于，優(yōu)化本身沒有”行動空間“的概念，對它而言，行動空間如何定義都無所謂，只要最終解質量好就行。

與其使用各種人工定義，自然的想法就是學一個行動空間出來。這就是這一系列文章的貢獻。?

我們以“解空間的切分”作為廣義上的行動空間，而具體的切分方式，則是在每個MCTS的樹結點上，用過去獲得的樣本點學一個最好的切分函數(shù)出來——我們希望這個切分函數(shù)能將好的和差的樣本點盡量分開，這樣一刀切下去，如果能將質量差的解空間統(tǒng)統(tǒng)切掉，以后少分配些搜索資源，那就是最理想的了。

而MCTS兼顧exploitation和exploration的特性，使得即便一開始切得不夠好，以后也有扳回來重新劃分空間的余地。而每個葉節(jié)點的空間，就是它的所有祖先節(jié)點的切分的交集。

以下是一個神經網絡架構搜索（NAS）上的簡單例子。

假設我們要搜索一個一至五層的卷積網絡，每層的filter數(shù)是32或是64，filter大小可以是3x3或者5x5?？紤]兩個不同的行動空間，一個是逐層確定每層的參數(shù)(filter數(shù)及filter大小)，另一個是先確定網絡層數(shù)，再確定每層的參數(shù)。

從圖上可以看到，明顯是先確定網絡層數(shù)的方案效率更高（同樣樣本下準確率更高），因為相對其它參數(shù)，層數(shù)對最后網絡準確率的影響更大，如果先按層數(shù)切分搜索空間，那搜索效率自然就提高了。

神經網絡架構搜索（NAS）上的簡單例子，先按層數(shù)切分搜索空間（藍線），搜索效率得到了提高。

洞察到了這些問題之后，我們提出了LaNAS和LaMCTS。

LaNAS采用線性函數(shù)切分空間，對于葉節(jié)點的函數(shù)值估計則采用簡單的隨機采樣法，及最近比較流行的one-shot supernet。

LaMCTS做了改進，采用非線性函數(shù)切分空間，并且在葉節(jié)點上用了已有的黑盒優(yōu)化的方法比如說Bayesian Optimization（BO）來找到葉節(jié)點的子區(qū)域里的最優(yōu)解。

通過這個方式，特別對于高維問題達到同樣性能，我們發(fā)現(xiàn)LaMCTS可以達到更低的樣本復雜度。這里我們在Mujoco的任務上做了測試，和各種已有的黑盒算法進行了比較，藍線是我們的方法：

LaMCTS在高維空間搜索中有優(yōu)勢，縱軸是獎勵，越高越好。

當然LaMCTS和基于梯度的方法相比，在Mujoco的高維問題上還是有差距（因為Mujoco其實并不需要太多探索）。我們指出了自身的局限性，出乎意料地被reviewers們開口稱贊。

因為每個葉結點采用了已有算法，LaMCTS也可以套在任何已知的黑盒優(yōu)化算法上，作為一個元算法（meta-algorithm），讓整個系統(tǒng)達到更好的效果。

為什么能提高呢？

主要原因是，傳統(tǒng)方法像Bayesian Optimization (BO）在參數(shù)空間維數(shù)很大（比如上百維）的情況下，由于維數(shù)災難的問題，高斯過程（GP）的建模效率就會大打折扣。

而LaMCTS通過切分空間，讓GP的建模局限在一個比較小的范圍內，從而提高了它的效率。

LaMCTS可以套在任何已知的黑盒優(yōu)化算法上，一定程度上提高它們的性能。

田淵棟博士知乎鏈接：

https://www.zhihu.com/people/tian-yuan-dong/posts

---

NeurIPS 2020錄用結果已出，歡迎各位作者投稿

推薦閱讀：

NeurIPS 2020 放榜！投稿破萬，收錄1900篇，史上最低錄取率！你中了么？

NeurIPS 2020 | 一種嶄新的長尾分布下分類問題的通用算法

重磅！CVer-NeurIPS 2020?中獎群成立了

CVer 建了一個NeurIPS 2020 中獎群，方便后續(xù)線上開會交流（注冊、視頻制作等），歡迎中獎的同學加入（非中勿擾），目前群已滿100+人。添加CVer小助手微信，一定要備注：NeurIPS 2020 中獎+學校+姓名+研究方向，即可拉你入群。

▲長按加微信群

▲長按關注CVer公眾號

整理不易，請給CVer點贊和在看！