事實證明，擴散模型不僅能用於生成圖像和視頻，也能用於合成新程式。
假設我們給模型一張手繪的「5」狀圖形，它就能透過不斷突變來修改程序，最終得到能輸出目標圖形的程式。 
該模型來自加州大學柏克萊分校的研究團隊，他們提出的這種程式合成新方法使用了神經擴散模型來直接操作句法樹。 論文一作為該校博士生 Shreyas Kapur，其導師為該校計算機科學教授 Stuart Russell。
- 論文標題：Diffusion On Syntax Trees For Program Synthesis
- 論文地址：https://arxiv.org/pdf/2405.2051905.2051905.2051905.20519. github.io/
- 程式碼庫：https://github.com/revalo/tree-diffusion
擴散模型之前已經在圖像生成領域取得了巨大成功。而團隊發現，透過利用擴散機制，讓模型學會迭代地優化程序，同時確保句法有效性（syntactic validity）。這種新方法的關鍵在於可讓模型觀察程式在每個步驟的輸出，從而實現有效的調試流程。
迭代的能力已經在 AlphaZero 等系統中得到了體現，而擴散機制的迭代性質也就很自然地會被用於基於搜索的程序合成。
該團隊發現，透過在訓練擴散模型的同時訓練一個價值模型，就可以引導其中的去噪過程得到能輸出所需結果的程序。這樣一來，便能有效率地探索程式空間，在生成過程中的每一步都做出更明智的決策。
為了實現該方法，該團隊選擇了逆向圖形任務（inverse graphics task），即假定使用特定領域的語言來繪製圖像。
該團隊表示：「逆向圖形任務天然就適合我們的方法，因為代碼中的一點微小變化就能導致所得圖像出現有意義的語義變化。」
舉個例子，如果影像中出現了一個放置錯誤的圖形，那就能被輕鬆看見並定位到程式空間中。圖 1 給出了一些範例。
這項研究的主要貢獻包括：
1. 提出一種在句法樹上使用擴散的全新方法
2. 針對逆向圖形任務實現了該方法，並發現新方法於之前的方法。 方法
簡而言之，該方法的核心思想是：為句法樹開發一個去噪擴散模型，類似於為視覺任務開發的圖像擴散模型。
首先來看一個來自 Ellis et al. 論文《Write, execute, assess: Program synthesis with a repl》中的任務範例：根據影像產生一個建構實體幾何（CSG2D）程式。使用CSG2D，我們可以使用加法和減法等布林運算將圓和四邊形等簡單的原語組合起來，從而能使用下面的上下文無關語法（CFG）創建出更複雜的形狀：
在圖2中，z₀ 是目標程序，x₀ 是z₀ 渲染過的版本。
任務就是逆轉 x₀，從而恢復得到 z₀。首先，去噪過程將 y=16 隨機突變為 y=10。然後再將左邊有兩個形狀的子樹轉換成只有一個形狀的新子樹。這裡的目標是基於影像 x₀，從 z₃ 和 x₃ 開始，訓練一個能逆向該去噪過程的神經網絡，從而得到 z₀。
下面首先將介紹如何將“噪聲”添加到句法樹中，然後將詳細描述如何訓練逆向該噪聲的神經網絡，最後將描述如何使用該神經網絡來執行搜索。 令 z_t 為時間 t 時的程序。令 p_N (z_{t+1}|z_t) 為將程式 z_t 隨機突變成 z_{t+1} 所依據的分佈。這裡希望 p_N 突變滿足兩點：(1) 很小，(2) 能得到句法有效的 z_{t+1}。 為此，該團隊探究了大量有關基於語法的模糊測試的電腦安全文獻。為了確保突變很小，他們先定義了一個函數 σ(z)，其能給出程式 z 的「大小」。在實驗中，則是將 CFG 中的一組端點（terminal）定義為原語。 舉個例子，如果用他們的 CSG2D 語言來寫，上述原語就為 {Quad, Circle}。使用該語言時，團隊的做法是讓 σ(z) = σ_primitive (z)，這能統計出原語的數量。 σ(z) 也可能包含深度、節點數量等選項。 然後，基於精確的約束條件 σ_min 為了讓給定程序z 發生突變，首先可在其句法樹中產生一個在某個σ_small 範圍內的候選節點集合：由於能讀取整個句法樹和CFG，因此知道了哪條生成規則能得到m，並由此可以確保得到句法有效的突變。舉個例子，如果 m 是數值，那麼替代它的也應該是數值。如果 m 是一個一般子表達式，那就可以把它替換成任何一般子表達式。因此，可採樣出 m'，這是 m 的替代：該團隊將程序合成問題視為一個推理問題。令 p (x|z) 為觀察模型，其中 x 可以是任意類型的觀察。任務是逆轉這個觀察模型的方向，即給定某個觀察值 x 得到一個程式 z。 首先，從一個資料集 D 取出某個程式 z₀，或這裡的做法是從 CFG 隨機取樣一個程式。即取樣一個滿足 σ(z₀) ≤ σ_max 的 z₀。然後透過下式描述的過程向z₀ 添加噪聲，執行s 步，其中s ∼ Uniform [1, s_max]，而s_max 是一個超參數：其中 ϕ 是該神經網路的參數，z_t 是目前的程序，x_t 是該程式目前的輸出，x₀ 是需要求解的目標輸出。 由於能夠獲取基本真值突變，因此可以簡單地通過前向過程馬可夫鏈z₀ → z₁ →... 來逆向採樣的軌跡，從而生成用以逆向採樣的軌跡，從而生成用以逆向採樣的軌跡，從而產生用以逆向採樣的軌跡，從而產生用以逆向採樣的軌跡，從而產生用以逆向採樣的軌跡，從而產生用以逆向採樣的軌跡，從而產生用以逆向採樣的軌跡，從而產生用以逆向採樣的軌跡，從而產生用以逆向採樣的軌跡，從而產生用以逆向採樣的軌跡，從而產生用以逆向取樣訓練神經網路的目標。乍一看，這或許是個合理選擇。但是，直接訓練模型逆向最後一次突變有可能為神經網路創造出遠遠更有雜訊的訊號。 舉個例子，在一個大得多的句法樹中，一種顏色的突變路徑為：目標圖像 x₀ 的顏色是 Red，而突變後圖像 x₂ 的顏色是 Green。如果只是簡單教導模型逆向上述馬可夫鏈，則可能會訓練網路將 Green 變成 Blue，即便可以直接訓練網路將 Green 變成 Red。 因此，為了創造更好的訓練訊號，可以計算目標樹與突變樹之間的編輯路徑。團隊使用了一個大體上基於樹編輯距離（tree edit distance）的樹編輯路徑演算法。廣義的樹編輯距離問題允許插入、刪除和替換任意節點。但這裡的設定不同，樹的編輯只能在一個只允許小突變的動作空間實現。 對於兩個樹 z_A 和 z_B，可以線性方式比較它們的句法結構。對於已經滿足 ≤ σ_small 的改變，就將其加入突變清單中。對於 > σ_small 的改變，則尋找能降低兩棵樹之間距離的首個突變。因此，對於任兩個程式 z_A 和 z_B 而言，可以在 O (|z_A| + |z_B|) 時間內計算出突變路徑的第一步。 該團隊另外也訓練了一個價值網絡v_ϕ (x_A, x_B)，其輸入為經過的圖像x_A 和兩個，x_A 和兩個，張影像的底層程式之間的編輯距離。由於在訓練期間已經計算出了樹之間的編輯距離，因此對於任意一對經過渲染的圖像，都能直接獲得它們的基本真值程序編輯距離，這就可以用於以監督式方法訓練該價值網路。 使用該團隊提出的上述新策略和新價值網絡，就可以為任意目標影像 x₀ 和隨機初始化的程式 z_t 執行波束搜尋。在每一次迭代中，都要維護搜尋樹中一組有最有希望值的節點，並且僅擴展這些節點。 
他們的去噪模型q_ϕ (z_{t−1}|z_t, x_t; x₀) 使用的是Tsimpoukelli et al. 在論文《Multimodal few-shot learning with frozen simpoukelli et al. 在論文《Multimodal few-shot learning with frozen simlanguage models》中所描述的視覺語言模型。至於影像編碼器，他們使用的是現成可用的 NF-ResNet-26 的實作；這是一種無歸一化器的捲積架構，可避免使用 Batch-Norm 時的時間不穩定問題。 該團隊實現了一種定制化的 token 化器，其中使用了他們的 CFG 的端點為 token。這個編輯模型的其餘部分是一個小型的僅解碼器 Transformer。 他們還添加了另外兩種類型的 token：用作該模型的句子起點 token 的 以及允許模型在其上下文中引用位置的 token 。 給定一張當前圖像，一張目標圖像，和當前一個已 token 化的程序，訓練該 Transformer 模型使之能以自回歸方式預測編輯位置和替換文本。在進行預測時，解碼過程受到語法的約束。團隊對預測 logit 進行了掩蔽，使其僅包含能表示句法樹節點的編輯位置，以及僅得到對於所選編輯位置句法上有效的替換。 這裡設定 σ_small = 2，這表示只允許網路產生少於兩個原語的編輯。對於訓練數據，他們的做法是從 CFG 採樣一個無限的隨機表達式流。對於噪音步數 s，他們是從 [1, 5] 中隨機選取一個。樣本中有一定的比例 ρ 是完成隨機取樣新表達式作為突變表達式。他們使用單台英偉達 A6000 GPU 訓練了三天時間。 他們在 4 種特定領域的圖形語言上進行了實驗：CSG2D、CSG2D-Sketch、TinySVG、Rainbow。 所選用的基準方法為 Ellis et al. 提出的《Write, execute, assess: Program synthesis with a repl》以及 Sharma et al. 提出的《CSGNet: Neural shape parser for constructive solid omeNettry》。 可以看到，在 CSG2D 和 TinySVG 環境中，新提出的樹擴散策略明顯優於先前方法的策略。如果組合使用波束搜索，該策略的性能還能進一步提升，在解決問題時相比其它方法可以更少地調用渲染器。 下圖給出了新系統的一些成功範例以及基準方法的輸出。可以看到，新系統能修復其它方法遺漏的較小問題。 如下影片展示了兩個使用 CSG2D-Sketch 語言基於草圖恢復程序的範例，其表明觀察模型並不一定需要確定性的渲染；它也可由隨機的手繪圖像構成。 
為了理解這些新設計的影響，該團隊也在簡化的 Rainbow 環境中使用一個更小的 Transformer 模型進行了消融實驗，結果見圖 5。總體而言，這些設計選擇的效果得到了證明。 以上是看張手繪草圖就能合成圖形程序，加州柏克萊讓擴散模型掌握新技能的詳細內容。更多資訊請關注PHP中文網其他相關文章！
