引用
Thakoor S, Shah S, Ramakrishnan G, et al. Synthesis of Programs from Multimodal Datasets[C]//Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
摘要
MultiSynth 是一個基於樣本多模態數據集的、用於合成領域特定程序的框架。給定一個領域特定語言（DSL），如果 DSL 中沒有一個通用於所有樣本的程序，那麼數據集是多模態的。此外，即使用一組程序概括數據集中的樣本，這些程序的域也可能不相交，這將導致合成具有二義性。MultiSynth 是一個框架，它以最小泛化概念推動程序合成，滿足了精確預測的需要。我們從以下三方面展示框架的實現過程：
（1）數據集的轉換驅動分區
（2）輸入和輸出的廣義規範的最小一般普化
（3）學習排序，估計特徵權重，以便在二義性的情況下將輸入映射到最合適的模式。
結果表明我們的框架能夠有效應用於兩種情況：在第一種情況下，我們擴展了現有的將 XML 樹轉換程序合成為模糊多模態數據集的方法；在第二種情況下，MultiSynth 通過學習源端句的分析樹的結果排列，對機器翻譯中的單詞進行預排序。
1. 預備工作
我們考慮給定領域特定語言（DSL）上下文中的程序合成問題。DSL 使我們能夠表示輸入輸出空間中的元素，並提供了讓輸入輸出元素相互轉換的機制。特別地，DSL 提供了表示輸入（或輸出）空間子集的語法。當輸入（或輸出）空間的子集可以用 DSL 表達式表示時，該表達式稱為子集的泛化，子集的元素是泛化的實例。
設 E 表示輸入或輸出空間的子集，泛化 g 是輸入（或輸出）空間的一組子集的最小一般普化，如果(i)每個 Ei 都包含在 g 中，(ii)對任何 DSL 表達式 g‘，每個 Ei 都包含在 g‘中，同時 g 也包含在 g‘中。
MultiSynth 對 DSL 提供的泛化機制作出如下假設：
(i)可歸納性是自反、對稱和傳遞的，
(ii)一組 DSL 表達式的泛化屬於相同的等價類。
(iii)可歸納的兩個 DSL 表達式 x 和 y 必須具有最小一般普化（LGG）。
程序 P 是一個泛化對（g，G）。P 的域是它輸入泛化 g 的實例集。如果 g 包含 i，我們就說 P 包含一個輸入 i。對於輸入 i，程序 P 的輸出是通過將 g 和 i 匹配，獲得 g 中變量的綁定，並用這些綁定實例化 G 而獲得的。我們還定義了程序通用性度量(GM)的概念，其中當 g 包含 g‘且 G 包含 G‘時，有 GM((g,G))>GM((g‘,G‘))。
給定數據集 D 和一組程序 S={P1…Pk}，我們將 sat(S)定義為樣本 e=(I,o) ∈D 的部分，這樣就存在一個程序 Pj∈S 使得 Pj(i)=o。顯然，sat 是一個單調子模函數。如果 sat(S)=1，就稱 S={P1…Pk}是數據集的候選集。
(i)通常只有 k>=1 的候選集存在，那麼這個數據集是多模態的。在存在 k=1 的候選集的情況下，那麼這個數據集是單模態的。
(ii)給定 θ∈[0,1]，如果 sat(S)>=θ，則 S 是一個 θ 候選集
2.MultiSynth 框架
為了處理數據集的多模態特性，MultiSynth 將程序與每個模式相關聯，並使用函數將每個輸入映射到最合適的模式上。MultiSynth 綜合了一組程序和映射函數。
我們的目標是在混亂性和不確定性間取得平衡。混亂性是多模態設置的核心，而不確定性可以應用於單模態。大多數數據集是多模態的，因此對於給定的點存在許多潛在的轉換，這導致了混亂性。另一方面，不確定性是一個點對應於所有可用模式的問題，這是多模態程序合成的核心問題。因此，我們在權衡中激發一種偏好，以最小化混亂性而不是不確定性。
我們將 S∗ 限制為 θ 候選集，此外，出於最小化混亂性的考慮，我們限制 S∗ 具有一般性測度 GM 的最小值。
我們使用加權線性組合對排序函數f建模。我們的優化公式表述為：
確定最優可行集：
考慮到泛化機制的假設，我們注意到創建的分區必須由所有屬於同一等價類的點組成（見第 1 節）。在 θ=1 的特殊情況下，D 中每個點必然屬於某個分區。
引理：設 θ=1，基於廣義關係將數據集劃分為等價類，得到最優可行集。
確定排序函數：
(i)設計和計算特徵向量：領域特定特徵可以是輸入或單獨分區的屬性，或者是輸入和分區之間“匹配”程度的度量。
(ii)學習排序：我們通過利用 RankSVM 公式的現有切割平面算法來學習上述特徵的權重。
3.XML 轉換的程序合成
現在，我們將描述我們框架中在 XML 轉換領域使用的部分。其中包括 DSL、泛化機制以及排序所需的特徵。
樹通過以下兩個操作達成泛化：
(i)允許樹中某些節點稱為迭代器，迭代器表示特定樹表達式的任意數量的實例。
(ii)允許將字段名映射到由變量表示的無關值。
如果可以通過用具體樹替換變量和用其它替換替換迭代器的方法得到，則稱具體樹與樹表達式匹配。
一旦對數據集進行分區並將每個分區的輸入輸出泛化為各自的 LGG，合成算法便會推斷輸入和輸出樹表達式的變量和迭代器之間的關係。如果輸出樹表達式僅包含輸入樹表達式中的變量和迭代器，則程序成功合成。
特徵：給定輸入下，決定程序使用的特徵如下：
(i)分區中數據點的數量
(ii-v)在對輸入進行泛化之前/之後分區 LGG 中迭代器/變量的數量
(vi，vii)LGG 和輸入之間匹配的迭代器和變量的數量
4.機器翻譯的程序合成
我們通過學習轉換輸入句子分析樹的規則，將預排序問題作為一個樹轉換問題來研究。我們將預排序規則提取問題看作是一個使用 MultiSynth 的程序合成問題。
雖然這種預排序涉及多種樹轉換，但為了證明 MultiSynth 在 MT 預排序中的有效性，我們將問題的範圍限制在學習分析樹產生級的轉換上，即源端分析樹的每個節點的子樹排列上。這樣的程序以給定分析樹的產生式作為輸入，以產生式的 RHS 排列作為輸出。
使用標準的源端語法分析器對訓練數據進行預處理，得到源端和目標端句子的語法樹，並以源樹為參考自下而上構造目標樹。此外，所有產生式，它們的特徵和對應的理想排列都作為合成器的訓練數據集。
DSL&泛化：使用產生式級排列的語法樹轉換的 DSL 包括以下內容：
(i)終結符，非終結符和變量。一個產生式在 LHS 中有一個非終結符，在 RHS 中有一個終結符/非終結符序列，該產生式還定義了語言的語法規則。語法樹的根是表示句子的非終結符。對於任何父節點及其有序的子節點列表，必須存在包含作為 LHS 的父節點和作為 RHS 的子節點的一個有效產生式。
(ii)泛化樹是一個語法樹，其葉子是終結符或變量
(iii)原始操作的集合，這些操作時不同產生式的所有可能排列
我們的泛化機制如下：給定兩棵樹 t1,t2，設 G(t1,t2)表示 t1 和 t2 的泛化。設 r（c1…c
n）表示以 r 為根節點的樹，其子節點和子樹用 c1…cn 表示。接著 G(r1(C1…Cn),r2(d1…dm))，由以下遞歸定義給出：
(i)如果 r1=r2 且 n=m，r1(G(c1,d1)…G(cn,dn))
(ii)否則，則為能從{r1,r2}中取值的變量 X
上述定義也可以擴展到對一組樹的泛化。
節點是語法樹中的非終端或終端。我們將樹中節點的子樹定義為該節點的內容。節點的內容是一個元組，由其父節點，父節點的子節點列表和一個表示列表中節點索引的整數組成。節點的深度是它和語法樹根節點的距離。
特徵：將給定測試輸入與候選分區之間匹配程度的度量作為特徵：
（f1）包容指示：一個二進制值，指示測試輸入產生式的內容是否被候選分區中點內容的 LGG 包含
(f2)匹配分數：介於 0-1 之間的值，指示測試輸入內容在候選分區中點的 LGG 內容中的包含程度
(f3)相對頻率：候選分區的大小與所有候選分區總大小的比值
(f4)給定輸入產生式下候選分區的數量
(f5)輸入分析樹中輸入產生式的相對深度
(f6)內容指示：二進制值，指示內容是否在候選產生式的內容列表中
(f7)內容頻率：與測試輸入含有相同內容的候選分區中訓練實例的數量
5.結論與未來工作
本文的具體貢獻是(1)結合 LGG，實現多模態數據集泛化程序的有效合成。(2)以兩個應用領域為例，證明在混亂數據點上學習排序的有效性。在以後的工作中，我們可以考慮在 θ<1 時多模態程序的合成問題。
致謝
國家重點研發計劃課題：基於協同編程現場的智能實時質量提升方法與技術（2018YFB1003901）和國家自然科學基金項目：基於可理解信息融合的人機協同移動應用測試研究（61802171）
本文由南京大學軟件學院 2020 級碩士袁博翻譯轉述。
閱讀更多 慕測科技 的文章
