Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision

01-27

轉載請註明出處：https://zhuanlan.zhihu.com/c_178715855
來源:ACL 2017
文章鏈接:Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision

Abstract

這篇文章提出了一個Neural Symbolic Machine(NSM),它包含了：

(a)一個neural "programmer"，也就是一個seq2seq模型，把語言表達映射成程序並且使用key-variable memory解決語義合成性

(b)一個符號的"computer"，也就是一個Lisp interpreter完成程序執行，並且通過減少搜索空間找到好的程序

我們應用REINFORCE直接優化任務reward。為了用若監督學習訓練並且提高REINFORCE的穩定性,我們增加了一個iterative maximun-likelihood。當只通過quetion-answer對學習，不需要特徵工程和領域知識時，NSM在WEBQUETIONsSP的表現超過了state-of-the-art。

Introduction

近幾年問答系統受到了廣泛關注，問答系統中關鍵的部分就是語義解析，語義解析就是把自然語言表達映射成可執行的邏輯形式(LFs，logic forms）或程序(program)。深度學習已經在監督學習的分類和結構預測問題比如speech recognition和機器翻譯中取得了突出的表現。然而，通過弱監督學習訓練神經網路對於語義解析和程序歸納仍然是有挑戰的。這是因為模型必須通過不可微分的操作與符號執行器交互來查找一個大的程序空間。

圖一：語義解析過程

圖2：基於語義解析的KBQA

Motivation

近期關於語義解析的工作訓練是通過人工注釋的程序所以在訓練的時候避免了程序執行的過程。然而，注釋程序的代價非常昂貴並且可擴展性差。在程序歸納中，現有的工作或者使用了low-level的記憶(memory)或者要求memory可微，使得模型可以用反向傳播訓練。這使得不能使用有效的離散操作和傳統計算機的記憶，並且把應用限制在合成的或者小的知識庫。所以，我們提出使用傳統計算機的記憶和離散操作在一個新的Manager-Programmer-Computer(MPC)的框架下去做神經程序歸納。

Model

一.模型結構

Neural Symbolic Machines:

1. "Manager" : 通過獎勵機制來進行弱監督。

2. "Programmer" : 輸入自然語言並且輸出一個程序。

3. "Computer" : 用high-level的程序語言執行程序。它的不可微的記憶使得能夠進行抽象的，可擴展的，精確的操作，但這使得訓練面臨更大的挑戰。

圖3：Neural Symbolic Machines

接下來分別介紹模型的各個組成部分。

二.Computer:有代碼幫助的Lisp Interpreter

我們使用Lisp Interpreter作為computer，一個程序是一個表達的列表 $(c_{1}...c_{N})$ ,每一個表達或者是特殊的token"Return"代表程序的結束，或者是一系列的由小括弧括起來的tokens" $(FA_{1}...A_{K})$ ", $F$ 是一個函數，有 $K$ 個特殊類型的參數。Table1定義了每一個函數的語義和它們的參數類型(或者是一個屬性 $p$ 或者是一個變數 $r$ ）。當一個函數執行的時候，它返回一個實體列表並且把它存入一個新的變數。

通過引入變數來存儲執行的中間結果，程序能夠自然地建模語言的語意合成性。

什麼是code assistance？

為了創造一個有好的神經計算機介面，解釋器為語法提供代碼幫助。它在每一步產生一系列有效tokens。tokens應該滿足以下條件:

1.一個有效的token不能引起語法錯誤：例如，如果前面的token是"("，那麼下一個token一定是一個函數名字，如果前面的token是"Hop"，那麼下一個token一定是一個變數。

圖4：語法限制

2.一個有效的token不能引起語義錯誤：這由存儲在變數中的符號來檢測。例如，如果前一個生成的token是"(Hop r",那麼下一個可用的tokens被限制在屬性 $p$ $left{ p|exists e,e^{}:ein r,(e,p,e^{})in K ight}$ 。

圖5：語義限制

三.Programmer:Seq2seq model with Key-Variable Memory

給了"computer"，"programmer"需要把自然語言映射成程序。我們的programmer是基於標準的帶有attention的seq2seq模型，並且帶有key-variable memory使得模型能夠表達和查閱程序變數。

Seq2seq模型包含兩個RNNs，對於encode和decoder我們都使用一層的GRU。給定一個詞序列 $w_{1},w_{2}...w_{m}$ ,每個單詞映射到一個embedding $q_{t}$ ，那麼GRU讀取這些embeddings並且更新它們的hidden states使用 $h_{t+1}=GRU(h_{t},q_{t}, heta_{Encoder})$ 。decoder更新它的隱變數使用 $u_{t+1}=GRU(u_{t},c_{t}, heta_{Dncoder})$ 。程序的tokens $a_{1},a_{2}...a_{n}$ 用一個在所有由"computer"產生的有價值的tokens上做softtmax生成。

簡單的seq2seq模型是不夠的，為此：

圖6：簡單的seq2seq是不夠的

為了得到語意合成性(圖7)，decoder要學會表示和查閱中間變數，中間變數的值在執行後被保存在"computer"中。因此，我們用一個key-variable memory擴展模型，每一個entry有兩個組成部分:一個連續的embedding鍵 $v_{i}$ 和一個對應的變數token $R_{i}$ 。在encoding的時候，我們用一個實體鏈接把文本範圍(例如，"US")鏈接到知識庫實體。對於每一個鏈接實體我們增加一個memory entry，鍵為文本範圍內GRU的hidden states的平均，值為變數token( $R_{1}$ )即為在computer中變數的名字。在解碼過程中，當一個表達全部生成(也就是生成了")")，那麼它將被執行，其結果被存儲為computer中一個新的變數的值，鍵為在那個step下GRU的hidden states(圖8)。當新的變數 $R_{i}$ 被加入key-variable memory中， $R_{i}$ 也被加入了decoder的詞典里。最後programmer生成的答案是最後一個計算的變數的值。

圖7：Key-Variable Memory語意合成

圖8：Key-Variable Memory: 保留中間值

圖9：Key-Variable Memory:重用中間值

四.Manager:Training NSM with Weak Superation

NSM對KB執行不可微的操作，因此end-to-end的反向傳播訓練是不可能的，因此我們的訓練過程是基於REINFORCE的。

1.REINFORCE

問題形式化:給定一個問題x,state,action,reward在一個時間 $tinleft{ 0,1,...,T ight}$ 是 $(s_{t},a_{t},r_{t})$ 。由於環境是確定的，state是由問題x和動作序列決定的: $s_{t}=(x,a_{0:t})$ , $a_{0:t}=(a_{0},...,a_{t})$ 是歷史的actions。在時刻t有效的actions是一系列由computer給出的有效的tokens。reward $r_{t}=I[t=T]cdot F_{1}(x,a_{0:T})$ 只有在decoding的最後一步不是0，並且reward是計算比較執行程序 $a_{0:t}$ 得到的答案與gold answers所得到 $F_{1}$ score。因此，一個程序 $a_{0:t}$ 的累積reward是：

$R(x,a_{0:T})=sum_{t}{r_{t}}=F_{1}(x,a_{0:T})$

agent的決策過程由策略定義， $pi_{ heta}(s,a)=P_{ heta}(a_{t}=a|x,a_{0:t})$ , $heta$ 是模型的參數。由於環境是確定的，那麼生成一個程序 $a_{0:t}$ 的概率為 $P_{ heta}(a_{0:T}|x)=prod_{t}P_{ heta}(a_{t}|x,a_{0:T})$ 。

我們定義目標函數為累積獎勵的期望並且使用策略梯度方法訓練，目標函數和梯度是：

$J^{RL}( heta)=sum_{x}{E_{P_{ heta}(a_{0:T}|x)}[R(x,a_{0:T})]}$

$B(x)=sum_{a_{0:T}}{P_{ heta}(a_{0:T}|x)R(x,a_{0:T}})$ 是一個基線，為了減小梯度估計的方差。

我們用beam search做梯度估計，對比常用的梯度估計從模型中採樣，我們使用beam中top-k的動作序列(programs)使用歸一化的概率。經驗上來說，REINFORCE收斂慢經常陷入局部最優。訓練的困難是由於在大的搜索空間下，reward信號的稀疏，這使得非零reward程序的模型概率在開始時非常小。如果beam size k小，好的的程序將落在beam之外，導致beam中所有的所有程序零梯度。如果beam size k大，訓練非常慢，而且當模型沒訓練的時候好的程序的歸一化概率仍然非常小，導致了(1)接近0基線，因此不好的程序接近0梯度(2)好的程序接近0梯度。

圖10：REINFORCE Training

2.Iterative ML

如果我們有gold grograms，我們可以直接優化它們的likelihood。由於我們沒有gold programs，我們可以執行一個迭代的過程(類似於hard EM)，給定固定的參數我們查找好的程序，然後優化目前為止找到的最好的程序的概率。我們在一個例子上以大的beam size做decoding，然後稱在之前所有迭代中得到最高rewar並且最短長度的 $a_{0:T}^{best}(x)$ 為perseudo-gold program,那麼接下來我們可以優化ML目標:

$J^{ML}( heta)=sum_{x}{logP_{ heta}(a_{0:T}^{best}(x)|x)}$

用iterative ML訓練快因為每一個例子至多有一個程序而且梯度權重不是模型概率，iterative ML只用了perseudo-gold program，沒有直接優化目標。這有兩個反效果:(1)最好的程序可能是個假程序偶然產生了正確的答案,但是不能泛化到其他問題上(2)訓練不能觀察到全部的負例，模型不能夠區別相關的tokens。

圖11：Iterative Maximum Likelihood Training (Hard EM)

3.Augmented REINFORCE

為了bootstrap REINFORCE,我們可以使用iterative ML去找到pseudo-gold programs並且把這些程序以一個合理的大概率添加到beam。Algorithm1描述了我們的全部訓練過程。我們首先運行itarative ML $N_{ML}$ 個迭代，並且記錄每一個例子 $x_{i}$ 的最好的程序。然後我們運行REINFORCE，歸一化一個beam中的程序中的概率為 $(1-alpha)$ 並且添加 $alpha$ 為找到的最好的程序 $C^{ast}(x_{i})$ 的對的概率。結果是，這個模型在訓練時總是給高reward的程序以一個合理的概率。

實驗和分析

1.數據集：The WEBQUESTIONSSP dataset，包括3098個訓練問答對，和1639個測試問答對。實體鏈接的質量和STAGG相似，我們把命名實體替換成一個特別的token"ENT"

2.模型細節：使用300維的GloVe詞向量。encoder hidden states,decoder hidden states和鍵embedding都是50維。函數和special tokens的embedding都是隨機初始化的。dropout rate是0.5

3.訓練細節：更新pseudo-gold programs時beam size k=100,每個decoding步驟結束之後模型迭代20次。對於REINFORCE訓練，decoding的beam size k=5， $alpha$ 為0.1.由於decoding需要query KBs，訓練速度的瓶頸是decoding。我們解決這個問題通過劃分數據集，用平行的不同decoders去解決每一個劃分。我們使用100個decoders，queries 50 KG servers。

圖12：Distributed Architecture

4.結果：和state-of-art STAGG對比

可以看出我們的模型在弱監督下擊敗了STAGG，沒有依賴特徵工程和人工規則。

四個主要的組成導致了最後的表現：(1)neural computer interface：提供了代碼幫助檢驗了語法和語義錯誤。(2)Augmented REINFORCE：REINFORCE陷入了局部最優表現差，Iterative ML沒有直接優化目標F1。(3)curriculum learning (4)reducing overfitting。

圖片13：Augmented REINFORCE

總結：本篇論文提出了一個Manager-Programmer-Computer的程序推斷框架，包含了key-variable memory的seq2seq模型。一個Lisp interpreter。為了解決解釋器的不可微問題使用了Augmented REINFORCE進行訓練。達到了state-of-art對的表現，並且彌補了弱監督和監督學習之間的差距。它是端到端訓練的，不需要特徵工程和領域知識。