正則表達式與神經網絡的深度融合

本文介紹了上海科技大學屠可偉研究組與樂言科技的一項合作研究，提出了將正則表達式規則與神經網絡深度融合的新思路。該論文已被 EMNLP 2020 接收為長文。

論文標題：

Cold-Start and Interpretability: Turning Regular Expressions into Trainable Recurrent Neural Networks

論文連結：

http://faculty.sist.shanghaitech.edu.cn/faculty/tukw/emnlp20reg.pdf

神經網絡發展至今，在很多自然語言處理任務上獲得了很大的成功。在有足夠多標註數據的情況下，神經網絡往往效果驚人。但是，當標註數據匱乏時，神經網絡的性能就會大打折扣。此外，神經網絡缺少可解釋性以及難以融入外部知識的問題也一直為人所詬病。與之對應的，基於符號主義的規則系統，如正則表達式（regular expression, RE），通常由人類專家基於領域知識構建，具備著良好的可解釋性，可用於沒有任何數據的冷啟動場景，並且可以通過規則的增刪和修改來快速應對目標任務的變化。因此，儘管神經網絡和深度學習如火中天，在工業界實際應用場景中，基於規則的方法仍然有著穩固的地位。規則系統的缺點在於完全依賴於人類專家，無法自動從數據中學習，因而在數據資源豐富的場景下難以達到和神經網絡相近的效果。為了結合兩者的優點，近年來如何將規則更好地融入神經網絡成為了一個重要的研究方向。現有的工作主要利用規則去約束神經網絡，通常使用多任務學習 （multitask learning）、知識蒸餾（knowledge distillation）等方法，或是根據規則的啟發設計新的神經網絡結構。然而，兩類方法仍然需要大量數據用於訓練，並且前者的神經網絡本身仍然是一個黑盒子，缺乏可解釋性，後者後者難以利用已有規則進行轉化或是通過專家手工構建。在這篇論文中，我們提出了直接由正則表達式轉化而來的神經網絡：FA-RNN （Finite Automata - Recurrent Neural Networks），將其使用在文本分類任務上，使得基於 FA-RNN 的系統在未經訓練的情況下與正則表達式文本分類系統有著相似的準確率。同時，FA-RNN 兼備神經網絡可訓練、可泛化的優點。我們發現，FA-RNN 在 zero-shot 以及 low-resource 場景下，由於人類知識的融入，與基於神經網絡的基線模型相比有著明顯的優勢；在全部數據的場景下，FA-RNN 與基線模型有著相當的性能。另外，經過訓練的 FA-RNNs 可以近似地表示成非確定性有限狀態自動機（non-deterministic finite automata, NFA）, 進而可以近似地轉化為正則表達式，因此有著更好的可解釋性。

正則表達式是在工業中最常用的規則之一。我們以意圖分類數據集 ATIS 中的一個類別 [distance] 為例：根據常識，如果問句裡面包含「how far」，「how long」或者 「distance」，那麼通常這句話就與[詢問距離]有關。因此我們可以對這個類別撰寫出下表第二行的正則表達式，去匹配如第三行所示的句子（其中 $* 表示任意詞出現任意次）。

▲ 表一

對計算理論有一定基礎的讀者可能會知道，任何正則表達式都能轉化為非確定性有限自動機（NFA），如上表的第四行，而任何 NFA 也可以表述成一個正則表達式。並且有以下重要的關係：如果讀完了一個句子，自動機能夠從開始狀態（s0）走到結束狀態（s2），那麼，該自動機接受了這個句子，並且其等價的正則表達式也匹配了這個句子。我們會發現，這個有限狀態自動機可以用一個三維張量，以及兩個向量表示，張量的三個緯度分別是詞表大小 V，自動機狀態數 S，以及狀態數 S，可以看成是由每個單詞對應的轉移矩陣 stack 起來組成。兩個向量分別表示了自動機的初始狀態以及結束狀態。如下圖所示，對於一個句子，我們可以得到每一個單詞的轉移矩陣，若該矩陣的第 i 行第 j 列為 1，則表示可以通過該單詞從狀態 si 轉移到 sj。因此，我們可以用前向算法（forward algorithm）或者維特比算法（viterbi algorithm）來計算句子被該自動機接受的分數。

▲ 圖一

我們以前向算法為例：讀完整個句子之後，從開始狀態到達任一結束狀態的路徑數可以表示為：

我們只要改換一下 notation 以及公式的形式，這個計算過程就可以被看成一個 RNN。其中 A 是指自動機（automata），x 為句子。

ht 類似 RNN 中的隱狀態向量，他的維度等於自動機狀態數。ht 的每一個維度就表示：在讀了 t 個單詞之後，有多少條路徑能夠從開始狀態到該維度對應的自動機狀態。接下來我們描述一個基於正則表達式的文本分類系統。如下圖的上半部分所示，我們針對輸入句子運行所有的正則表達式，得到匹配結果，然後通過一些邏輯操作，將匹配的結果整合。例如，如果一句話只被針對 A 類別的正則表達式匹配，那麼他的標籤是 A 類別；如果這句話被 A，B 兩個類別都匹配，那麼我們可以通過事先定義一個優先級關係來選出更可能的類別。這些都可以用邏輯操作來實現。所以，正則表達式的分類系統先匹配（matching），再整合匹配結果（aggregation）來得到句子的標籤。

如果直接由 RE 轉化而來，FA-RNN 的參數需要包括三維張量 (VxSxS)。這個三維張量相比於傳統的詞向量矩陣 (VxD) 過於大了，並且不包含詞向量中存在的語義信息。我們利用了張量秩分解（tensor rank decomposition，CP decomposition）的技術，用 ER, D1, D2 三個大小分別為 VxR, SxR 與 SxR 的矩陣來近似表示原來的張量，其中，S 為自動機狀態數，R 為 rank 數。原來公式 (1)  中的迭代公式由此變為了：

記 t 時刻的輸入為 x_t, 我們可以把 ER 看成一個只包含規則信息的詞嵌入矩陣，vt 則是 ER 矩陣的對應行選出的 R 維詞向量。由此，我們模型的參數量大大減少，相當甚至更少於 LSTM, GRU 等循環神經網絡。接下來我們介紹我們結合詞向量（如：glove）的方法。為了結合 D 維度的詞向量，我們利用一個 DxR 的矩陣 G 將詞向量從 D 映射到 R 維空間，這個矩陣 G 可以初始化為詞嵌入矩陣 Ew 的違逆乘上 ER。我們再引入一個 0，1 之間的超參數來結合 vt 與 G 映射後的兩個 R 緯詞向量，控制接受多少詞向量語義的信息，更新公式變為如下：

我們將這個模型稱之為 FA-RNN。經過了張量分解、詞向量結合之後，在 zero-shot 的場景中，FA-RNN 仍然能夠得到和規則系統接近的準確率。例如在 ATIS 數據集（Hemphill et al., 1990）中，規則系統的準確率為 87.01%，FA-RNN 仍然能夠達到 86.53% 的準確率，而大部分的神經網絡初始的準確率近似於隨機。另外，我們提出了 FA-RNN 的雙向以及門控變體，不過模型可解釋性相應下降了。有了 FA-RNN，我們就可以用它構造規則系統的「神經網絡版本」，如圖二的下半部分所示。FA-RNN 的最後一個「hidden state」包含了正則表達式的匹配信息，我們可以通過一個 MLP 來整合匹配結果。第一個 linear 層取出所有自動機的接收狀態（final state）的值，第二個 linear 層可以利用 soft logic 進行簡單的邏輯操作，並且最終得到每個類別的分數。這些分數的理想值為非負正數。可以看到，我們的模型結構非常類似於傳統的 RNN+MLP，同時模型輸出的結果完全與規則系統一致。與規則系統不同的是，我們可以直接將模型輸出的標籤分數利用 cross-entropy 損失函數進行訓練。

實驗以及實驗結果

我們比較了結構對應的傳統神經網絡。具體結構為 BiRNN / BiGRU / BiLSTM / CNN / DAN 給句子做 encoding，用 Linear 層輸出每個 label 的 score。除此之外，我們使用了一些已有方法將規則與傳統神經網絡結合。分別是 Luo et, al 提出的三種利用正則表達式匹配結果的方式（+i: 將正則表達式匹配結果作為額外的特徵輸入，+o: 利用 RE 結果直接改變輸出 logits, +io 前兩者結合），以及兩種基於知識蒸餾的方式，分別記為 +kd（Hinton et al., 2015）以及 +pr（Hu et al. 2016）。我們在三個文本分類數據集上實驗，分別是 ATIS (Hemphill et al., 1990), Question Classification (QC) (Li and Roth, 2002) 以及 SMS (Alberto et al., 2015). 我們使用了 glove 詞向量。下表顯示了數據集以及規則的統計信息以及樣例。

我們發現，FA-RNN 在 zero-shot 以及 low-resource 的場景下有著明顯的優勢，並且在 full-shot 上仍然能夠得到與傳統簡單神經網絡方法以及其經過規則加強後相似的準確率。結果如下：

▲ 表四：few-shot 、full dataset 準確率

3.3 模型可解釋性的探索

訓練過後的 FA-RNN 參數可以還原出 VxSxS 的三維的張量。不過不再是非零即一了，因此不再對應非確定性有限自動機 (NFA)，而對應了帶權有限狀態自動機(weighted finite automata, WFA)。由於 FA-RNN 與計算模型 WFA 的對應關係，我們認為他相比較傳統神經網絡有著更強的可解釋性。進一步地，我們可以設定一個閾值，將 WFA 中大於閾值的認為是 1，小於的認為是 0，從而將 WFA 轉化為 NFA，並將 NFA 轉化為人類可讀的正則表達式。下圖展示了 ATIS 數據集中在訓練前與訓練後針對 [aircraft] 類別的自動機變化。可以看到，新的自動機可以考慮更全面的情況，例如識別到句子中有 jet, 737(boeing) 的時候認為該句子在描述 aircraft。

我們發現，訓練過後的 FA-RNN 轉化為的正則表達式，雖然是有損的轉化，也能達到和訓練之前的系統相近甚至更高的準確率。在 QC 數據集上提升了 9.2% 的準確率，在 ATIS 上提升了 0.45%，在 SMS 上稍有下降 (-1.2%)。

我們提出了直接由正則表達式轉化而來的神經網絡：FA-RNN ，並將其應用在文本分類任務上，使得基於 FA-RNN 的系統在未經訓練的情況下與正則表達式文本分類系統有著相似的準確率。通過實驗發現，與基線模型相比，由於知識的融合，FA-RNN 的文本分類系統在 zero-shot 與 low-resource 場景下有著更好的效果，在全部數據的訓練場景下也有著不錯的競爭力。同時，FA-RNN 可以轉化為計算模型 WFA，甚至正則表達式，因此有著更好的可解釋性。

上海科技大學信息學院屠可偉老師研究組主要從事自然語言處理、機器學習等人工智慧領域的研究，目前側重於研究語言結構的表示、學習與應用。

研究組近幾年已發表頂會論文數十篇，其中三篇無監督句法解析的論文已被美國卡內基梅隆大學自然語言處理課程列為閱讀材料，另一篇論文是 ACL2018 句法領域的最高分論文。2020 年到目前為止，研究組已發表 ACL論文4篇，EMNLP 論文3篇，EMNLP Findings 論文4篇。

研究組現招收碩士研究生（推免生）、博士後和研究助理，歡迎有興趣的同學聯繫屠老師。

http://faculty.sist.shanghaitech.edu.cn/faculty/tukw/

如何才能讓更多的優質內容以更短路逕到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。 

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術乾貨。我們的目的只有一個，讓知識真正流動起來。

📝 來稿標準：

• 稿件確係個人原創作品，來稿需註明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向） 

• 如果文章並非首發，請在投稿時提醒並附上所有已發布連結 

• PaperWeekly 默認每篇文章都是首發，均會添加「原創」標誌

📬 投稿郵箱：

• 投稿郵箱：[e-mail] 

• 所有文章配圖，請單獨在附件中發送 

• 請留下即時聯繫方式（微信或手機），以便我們在編輯發布時和作者溝通

🔍

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關於PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報導人工智慧前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號後臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群裡。