[NAACL16]RNN文法

09-06

[NAACL16]RNN文法

來自專欄自然語言處理與深度學習3 人贊了文章

原文鏈接：

Recurrent Neural Network Grammars?

godweiyang.com

論文地址：Recurrent Neural Network Grammars

代碼地址：github

今天要介紹的這篇論文是來自NAACL16的Recurrent Neural Network Grammars，主要貢獻點就是提出了一種新的文法RNNG，不同於傳統的PCFG之類的文法，RNNG使用RNN來對句子和它的句法樹的聯合概率進行建模，因此它是一個生成模型。但是稍稍修改就可以改為判別模型，也就是大家熟悉的基於轉移的成分句法分析系統，並且轉移系統是採用top-down方法的，也就是利用了句法樹的前序遍歷。

RNNG在語言模型任務上取得了當時的state-of-the-art結果，成分句法分析任務上，生成模型取得了媲美最好結果的F1值，而判別模型就差了點。本文最大的貢獻點就是提出了生成式模型RNNG，說明了在數據量不是很大的時候，利用生成式模型可以提高成分句法分析的準確率。

摘要

RNN在語言模型和其他許多NLP任務上面都已經取得了非常不錯的效果，但是RNN只能捕捉到句子的序列特徵，例如句子的句法結構等遞歸嵌套的結構信息無法用RNN捕捉到。

因此本文提出了一種利用RNN建模出來的全新文法RNNG，建立在句子的句法結構之上，消除了PCFG的上下文無關假設。並提出了兩種變體，一種是生成模型，可以用來句法分析和訓練語言模型，另一種是判別模型，可以用來句法分析。

RNNG建立在top-down轉移系統之上，top-down轉移系統相比於bottom-up轉移系統有一個好處，就是不需要二叉化，因為如果bottom-up轉移系統不二叉化的話，REDUCE的狀態就會有很多種可能，不知道到底歸約棧里的幾個結點。而top-down轉移系統就不存在這個問題，直接歸約到第一個父結點為止就行了。本文應該也是第一個提出用RNN來實現top-down轉移系統的，之前的方法都是用top-down的文法，或者是bottom-up的，例如Sochar2013的CVG，也是用二叉化後的RNN學習結點的語義表示。

RNN文法

RNNG定義為三元組 $(N, Sigma, Theta)$ ，其中 $N$ 是非終結符集合， $Sigma$ 是終結符集合，並且 $N cap Sigma = emptyset$ ， $Theta$ 就是神經網路的參數集合。RNNG和傳統的PCFG的一個明顯區別就是它沒有顯式地指出語法規則是什麼，而是蘊含在了神經網路中，在句法轉移的時候動態的生成。

Top-down句法分析和生成

這部分主要介紹RNNG的兩個變體，一個是top-down的句法分析系統，還有一個是稍稍修改後的生成系統。

判別式系統

這個判別式模型之前也已經介紹過很多次了，和普通的基於轉移的句法分析系統一樣，輸入是一個句子 $x$ ，輸出是它的句法分析樹 $y$ 。主要組成部分有句法樹棧、句子單詞buffer、動作集合，每一步的動作有三種：

NT(X)：將一個父結點X移進棧里。
SHIFT：從buffer中移一個單詞到棧里。
REDUCE：將棧頂的若干個結點歸約為它們的父結點，並且出棧。

圖1就是每個動作的狀態變化過程，圖2是判別式模型進行句法分析的示例：

當然得給動作添加一些限制，首先記當前狀態為三元組 $(B, S, n)$ ，分別表示buffer、棧、當前棧里未歸約的父結點數量，這個之前的博客沒有提及過：

NT(X)動作只有當buffer不為空並且 $n < 100$ 的時候才能進行。因為buffer空了的話就沒有單詞了，此時不可能移進新的非終結符了，並且要限制 $n < 100$ 防止一元產生式無限生成下去。
SHIFT動作只有當buffer不為空並且 $n ge 1$ 時才能進行。前者不用解釋了，後者的話因為是top-down的，所以棧里至少要有一個父結點才能移進新的單詞。
REDUCE只有當棧頂不是沒有歸約的父結點才能進行。
REDUCE只有當 $n ge 2$ 或者buffer為空時才能進行。這裡要解釋一下為什麼 $n ge 2$ ，因為如果buffer不為空同時 $n=1$ ，那麼這時候如果REDUCE的話，棧里就只剩一個非終結符了，只可能是根節點S，而buffer里還有單詞，所以這是不可能的。

記當前狀態的可能動作集合為 $mathcal{A}_D(B, S, n)$ 。

生成式系統

將上面的top-down轉移系統稍稍修改即可得到生成式系統。區別有兩點：

首先沒有了輸入的buffer，取而代之的是輸出的buffer $T$ 。
其次因為沒有輸入單詞了，所以在需要輸入單詞的時候採用GEN(x)動作來產生一個新的單詞 $x$ ，然後移進棧里，取代SHIFT動作。

圖3就是每個動作的狀態變化過程，圖4是生成式模型進行句法分析的示例：

同樣也要對其採取一些限制：

GEN(x)動作只有當 $n ge 1$ 時才能進行，上面SHIFT限制已經解釋過了。
REDUCE只有當 $n ge 1$ 或者buffer為空時才能進行。這裡再次解釋一下，上面判別式模型限制條件是 $n ge 2$ ，為什麼這裡就變成了 $n ge 1$ ？因為生成模型沒有輸入buffer，所以即使 $n=1$ 時REDUCE了，以後不要再GEN(x)即可，直接結束分析

記當前狀態的可能動作集合為 $mathcal{A}_G(T, S, n)$ 。

轉移序列

因為一棵句法樹的前序遍歷是唯一的，所以不管用判別式模型還是生成式模型，得到的動作序列也都是唯一的。對於句子 $x$ 和句法樹 $y$ ，記生成式模型動作序列為 $a(x, y)$ ，判別式模型動作序列為 $b(x, y)$ 。

生成式模型

本文最重要的就是上面提到的生成式模型，因為GEN(x)動作的存在，所以模型同時對句子 $x$ 和句法樹 $y$ 的聯合分布進行了建模。記當前狀態的向量表示為 $u_t$ ，那麼聯合分布可以表示為：

$p(x,y) = prodlimits_{t = 1}^{left| {a(x,y)} ight|} {p({a_t}|{a_{ < t}})} = prodlimits_{t = 1}^{left| {a(x,y)} ight|} {frac{ {exp r_{ {a_t}}^T{u_t} + {b_{ {a_t}}}}}{ {sum olimits_{a in {mathcal{A}_G}({T_t},{S_t},{n_t})} {exp r_{a}^T{u_t} + {b_{a}}} }}}$

其中 $r_a$ 表示動作 $a$ 的向量表示， $b$ 表示偏移向量，都包含在了RNNG參數集合 $Theta$ 裡面，通過訓練得到。

而當前狀態的向量表示 $u_t$ 由三部分得到，輸出buffer的LSTM輸出 $o_t$ 、棧的LSTM輸出 $s_t$ 、歷史動作序列的LSTM輸出 $h_t$ ，然後經過一個前饋神經網路得到：

$u_t = anh (W[o_t; s_t; h_t] + c)$

$W$ 和 $c$ 同樣也包含在了RNNG參數集合 $Theta$ 裡面，下圖是三個LSTM的示例圖：

句法成分組合

在REDUCE操作時，需要將若干個子結點歸約為一個父結點，為了得到父結點的向量表示，再次利用一個LSTM對子結點序列進行編碼，同時在首尾加上父結點，結構圖如下所示：

單詞生成

單詞生成採用softmax尋找概率最大的單詞，但是單詞數量可能十分巨大，所以採用分層softmax的思想，首先預測當前動作是不是GEN，如果是GEN，記單詞總數為 ${left| { sum } ight|}$ ，再將單詞平均分成 ${sqrt {left| sum ight|} }$ 個類別，用softmax預測屬於哪個類別，然後在那個類別里再用softmax預測輸出哪個單詞。這樣時間複雜度就從 $Oleft( {left| sum ight|} ight)$ 降到了 $Oleft( {sqrt {left| sum ight|} } ight)$ 。