強化學習＋樹搜索：一種新型程序合成方法

選自arXiv

作者：Riley Simmons-Edler、Anders Miltner、Sebastian Seung

機器之心編譯

參與：Panda

程序合成一直都是計算機科學領域內一大重要研究方向。近日，普林斯頓大學的研究者提出了一種結合強化學習與樹搜索實現程序合成的方法，為程序合成開啟了一個新研究方向。這項研究目前仍在繼續進行，機器之心對該研究的預印本論文進行了摘要編譯。

在編程語言和機器學習領域，程序合成方面的研究都已經出現了復興，該任務要做的是根據用戶提供的規格（specification）自動生成計算機代碼。由於計算能力的增長和深度神經網路的興起，這個曾經無力解決的問題現在已經可以攻克了，並且也已經在很多領域得到了使用 [1]，其中包括通過自動執行常式任務來提高程序員的效率 [2]、為沒有編程知識的非專家人員提供直觀的界面 [3]、為性能很關鍵的代碼減少漏洞和提升運行效率 [4]。

在編程語言（PL）領域，程序合成通常使用枚舉搜索來解決——通過簡單直接地枚舉候選項直到找到滿足條件的程序來尋找滿足給定規格的合適程序 [5,6,7]。通過將演繹組件集成進搜索過程來收窄搜索空間 [8,9,10]，或通過將相關語言修改成具有更窄搜索空間的同等語言並在該空間中搜索 [11,12,13]，這種方法可以得到解決。另一種常用方法是將合成任務約簡成通過 SAT 求解器尋找一個滿足條件的布爾公式配置 [14,15]，但這只是將枚舉搜索放進了求解器進行處理。

機器學習（ML）領域的研究者則在從另一個方向解決這個問題——不是單純地全面搜索一個有限定的空間，而是使用一個學習了規格到程序的映射方式的模型，通過智能地搜索或採樣搜索空間，從而在更大的搜索空間中有效地找到正確的程序。這些方法大都使用了監督學習方法——在一個大型的輸入/輸出樣本和對應滿足規格的程序的合成數據集上訓練，然後給定一個相應的輸入/輸出示例集合 [16,17,18,19,20]，使用基於循環神經網路（RNN）的模型依次輸出目標程序的每一行。從概念上看，這種方法應該能與編程語言技術很好地結合起來——在小型搜索空間中進行智能搜索比在大型搜索空間中進行智能搜索要容易得多。那麼，為什麼這些技術通常沒有一起使用呢？

機器學習領域內的大部分已有工作都嚴重依賴於被合成的領域特定語言（DSL）的結構來實現優良的表現，而且也不能輕鬆地泛化到新語言上。這些方法通常需要語言特徵，比如語言的全可微分性 [19,20] 或規格和滿足規格的程序對構成的大型訓練集 [16,17,18]。這些要求使其難以將已有的基於機器學習的方法與編程語言社區開發的技術結合起來，它們在使用一種 DSL 進行有效合成時所需要的性質差異非常大。此外，大多數已有方法都主要注重以「一步式」的方式求解出程序，要麼通過單次或少數幾次嘗試成功輸出滿足給定規格的程序，要麼就無法得到這樣的結果；隨著程序空間變大，這種方法的擴展能力會變得更糟。相比之下，當基於搜索的方法枚舉所有程序時，它們最終能解決任何合成任務，但所需的時間可能會超出可行範圍。

強化學習引導的樹搜索

我們的方法是強化學習引導的樹搜索（RLGTS：reinforcement learning guided tree search），如圖 1 所示。該方法旨在將基於搜索的方法和基於機器學習的方法的優勢結合起來，並且讓來自這兩個研究領域的技術結合起來進一步提升效果。我們提出了一種程序合成新方法：將合成程序的過程表示成一個馬爾可夫決策過程（MDP）[21] 並使用強化學習（RL）來學習求解程序，僅需給定該程序的一組輸入/輸出示例、一個語言規格和一個用于衡量給定程序的質量的獎勵函數。在我們的基於強化學習的方法中，我們將程序狀態和當前的部分程序看作是環境，並將該語言的代碼行看作是尋求實現獎勵函數最大化的動作。更進一步，我們還將我們的強化學習模型與一種基於樹的搜索技術結合到了一起，這能極大提升該方法的表現。這種組合有助於解決很多強化學習應用中都會出現的局部極小值和高效採樣的問題。

圖 1：我們提出的系統的示意圖。我們的程序合成方法將該問題看作是一個可用強化學習解決的馬爾可夫決策過程，並且將其與一種優先搜索樹組合起來通過避免局部極小值來加速求解過程，這能提升在固定數量的嘗試次數內求解的程序的數量。給定一個輸入記憶狀態和對應的輸出記憶狀態集合，這種方法能使用一個為部分正確的解定義的獎勵函數來引導學習過程，從而學習到一個策略——該策略能輸出可將每個輸入樣本映射到對應的輸出樣本的代碼行序列。

RLGTS 不依賴給定語言的訓練數據的可用性，並且不對語言的結構做任何假設——只要求該語言允許執行和評估不完整的部分程序。此外，我們的基於強化學習的方法可以輕鬆且自然地與其它程序合成方法結合起來，這讓用戶可以受益於某些領域在基於搜索的合成上的大量研究成果。

總體而言，我們有以下貢獻：

我們引入了強化學習引導的樹搜索（RLGTS），這是一種將程序生成作為強化學習任務處理的程序合成方法。

我們描述了 RLGTS 在 RISC-V 彙編語言的一個子集上的實現，並且通過結合一個基於 Q 網路的策略與簡單的樹搜索方法為該任務創建了一個強化學習智能體。

研究表明，在隨機程序構成的一個合成數據集上，相比於僅使用強化學習和僅使用枚舉搜索的基準方法，我們的方法可求解的程序的比例分別提升了 100% 和 800%。此外，我們還比較了 RLGTS 與基於馬爾可夫鏈蒙特卡洛（MCMC）的方法（該方法已經在 x86 代碼的超優化上取得了很大的成功，並且也是合成彙編語言代碼的當前最佳方法 [4]），結果表明我們的方法在更有難度的基準程序上有更優越的表現，在固定的程序評估限制內可求解的程序多出 400%；即使當該限制在 MCMC 看來增大了 50 倍時，我們的方法依然能在總體表現上保持競爭力。

圖 2：我們的 Q 函數神經網路的示意圖

圖 3：我們的 Q 函數與優先搜索樹組合方法的示意圖

圖 5：RLGTS 與基準方法的表現比較，左圖展示了求解出的非凸程序的比例，右圖展示了求解出的凸程序的比例。儘管 RLGTS 能有效求解凸程序，但它們也可以通過最佳優先搜索（Best-First Search）輕鬆解決，因此我們將它們從我們的其它實驗中移除了，因為它們不能很好地代表該方法的表現。對於長度最多到 6 的程序，最大程序長度為 6；對於長度為 10 的程序，最大程序長度為 10。

圖 6：RLGTS 和 MCMC 作為程序長度函數（左圖）和允許的指令數（右圖）的表現比較。隨著程序長度和搜索上限之間的差異的增大，RLGTS 一直都有更好的表現。讓人驚訝的是，隨著程序長度的增大，MCMC 的表現僅略有甚至沒有下降。隨著搜索的指令數的增大，MCMC 樣本效率下降得快得多。MCMC-1m 給出了當 MCMC 的超時時間增加到 100 萬次嘗試時的表現，其它情況都使用了 20000 次嘗試的限制。

論文：Program Synthesis Through Reinforcement Learning Guided Tree Search

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

摘要：程序合成是根據提供的規格生成程序的任務。傳統上該任務被編程語言（PL）社區看作是一個搜索問題，近期則被機器學習（ML）社區視為一個監督學習問題。我們在這裡提出另一種方法，將合成給定程序的任務當作是可通過強化學習（RL）解決的馬爾可夫決策過程。根據對部分程序的狀態的觀察，我們試圖找到一個程序，且該程序在程序和狀態對上依據所提供的一個獎勵度量是最優的。我們在操作浮點數的 RISC-V 彙編語言的一個子集上實例化了該方法；並且受編程語言社區使用基於搜索的技術來進行優化的啟發，我們將強化學習與一種優先搜索樹組合到了一起。我們評估了這個實例，並且表明了我們的組合方法相比於各種基準方法的有效性，其中包括僅保留強化學習的方法和一種在該任務上當前最佳的馬爾可夫鏈蒙特卡羅搜索方法。

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

------------------------------------------------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！