StackRNN的設計及可解釋性研究

郭立鵬

StackRNN的設計及可解釋性研究

郭立鵬

（清華大學計算機系，北京 100084）

針對循環(huán)神經(jīng)網(wǎng)絡的可解釋性問題設計StackRNN，StackRNN在確定型上下文無關語言文法推測實驗中可以預測最長8倍于訓練樣本的測試集樣本，可視化實驗表明StackRNN具有模擬確定型下推自動機的能力。該研究對將深度學習應用于自然語言處理尤其是與程序語言相關的任務具有重要的意義。

循環(huán)神經(jīng)網(wǎng)絡；可解釋性；記憶網(wǎng)絡；自動機理論

循環(huán)神經(jīng)網(wǎng)絡（Recurrent Neural Network，RNN）是神經(jīng)網(wǎng)絡中處理序列數(shù)據(jù)的重要模型，而可解釋性是機器學習模型尤其是神經(jīng)網(wǎng)絡中存在的問題之一。目前，已有研究表明RNN中的簡單循環(huán)網(wǎng)絡（Simple Recurrent Network，SRN）、長短時記憶網(wǎng)絡（Long-Short Term Memory，LSTM）、門控循環(huán)單元（Gated Recurrent Unit，GRU）與自動機之間存在密切的聯(lián)系[1-2]。基于存儲的RNN是通過外顯存儲增強RNN，其典型代表是Memory Network，而棧是一種特殊的存儲結構，因此基于棧的RNN是基于存儲RNN的研究分支。其最早的嘗試是DAS于1992年提出的NNPDA[3]，但是其無法泛化到更長樣本。GREFENSTETTE于2015年設計出可微分棧Neural Stack[4]，但其模擬下推自動機仍有不足。本文主要基于Neural Stack設計可以模擬確定型下推自動機（PushDown Automata，PDA）的StackRNN。

1 設計StackRNN

StackRNN是在Neural Stack的基礎上為了模擬確定型PDA而設計的，具體改進包括4個方面。

1.1 優(yōu)化棧操作

彈出棧頂符號即讀取棧頂符號，本質(zhì)是一個操作，所以取消Neural Stack中的讀取常量并合并READ操作和原POP操作為 POP 操作。并且在時刻 StackRNN 先執(zhí)行PUSH操作表示時刻壓入棧符號，再執(zhí)行POP操作表示彈出棧頂符號用于時刻+1的轉(zhuǎn)移。

1.2 形式約束下推自動機

為了模擬確定型PDA，StackRNN的設計依據(jù)為自動機理論中的一個重要定理[5]。

定理1：對于任意的PDA都存在滿足以下約束的等價PDA，即約束1是只有一個接受態(tài)f并且只有棧空時才進入該接受態(tài)；約束2是中產(chǎn)生式右部只能為（i，）或（i，）兩種形式，即每次遷移棧的變化只能是增減一個符號，而不再是定義中的任意多個。此定理對于確定型PDA也有效，結合確定型上下文無關語言（Context-Free Language，CFL）與確定型PDA的關系，可以得到重要推論。

推論1：確定型CFL記為，總是存在一個滿足兩點約束的確定型PDA記為DPDA，使得=（DPDA）。

該推論是StackRNN設計的重要依據(jù)。根據(jù)推論，如果想實現(xiàn)確定型PDA，只需要實現(xiàn)結構滿足在每次轉(zhuǎn)移中能夠壓入2個或者壓入0個棧符號的確定型PDA。所以，據(jù)此設計StackRNN，先壓入確定程度為1t的棧符號1t，然后再壓入確定程度為2t的棧符號2t。其中2t由1t經(jīng)過克隆操作得到，克隆即1t與2t有獨立的存儲空間，但是共享后向傳播路徑。這樣StackRNN的結構實現(xiàn)了在時刻可以壓入0個或2個棧符號：當2t=1t=0時，壓入0個棧符號；當2t=1t=1時，壓入2個棧符號。此處改進滿足了定理1中的約束2，約束1會在損失函數(shù)設計的改進中滿足。當滿足約束1以及約束2時，理論上StackRNN可以識別任意一種確定型CFL。

1.3 優(yōu)化控制器內(nèi)連接方式

由轉(zhuǎn)移函數(shù)（-t-1，t，t-1）=（-t，t）可知，不僅當前狀態(tài)-t，而且當前棧的變化即t，1t，2t，1t，2t也由-t-1，t，t共同決定。Neural Stack將t連接至控制變量及棧符號變量，這樣會導致復雜的狀態(tài)空間而且存在信息壓縮損失的問題。因此，改變控制器內(nèi)連接方式，由-t-1，t，t與t、1t，2t，1t，2t進行全連接。

1.4 優(yōu)化損失函數(shù)

根據(jù)定理1的約束1，當判定輸入為正樣本時必須同時滿足棧內(nèi)容為空以及終態(tài)為接受態(tài)的條件。所以設置超參數(shù)并在原損失函數(shù)的基礎上添加棧為空的損失函數(shù)lossstack以滿足約束1。

2 實驗

2.1 實驗任務

準備進行確定型CFL文法推測實驗和StackRNN可視化實驗，文法推測實驗的目標是測試不同RNN對確定型CFL的識別能力，可視化實驗的目標是探究StackRNN與確定型PDA的關系。文法推測實驗的數(shù)據(jù)集為Dyck2語言。Dyckn語言定義為由種括號對正確嵌套生成的語言，選擇Dyck2語言代表確定型CFL的原因是由Chomsky-Schutzenberger表示定理可知，任何的CFL都可以由正則語言和Dyckn語言的同態(tài)交集表示，因此成功識別Dyck2語言是識別CFL的必要條件。為了測試模型的泛化能力，數(shù)據(jù)集劃分為樣本長度范圍和深度范圍為（0，32]（（0，8]）的訓練集I以及樣本長度范圍和深度范圍分別為（0，32]（（0，8]）、（32，64]（（8，16]）、（64，128]（（16，32]）、（128，256]（（32，64]）、（256，512]（（64，∞））的測試集1至5。評測指標Coarse值定義為預測正確的樣本與測試集所有樣本之比。

預測正確樣本的標準如下：樣本預測正確當且僅當樣本每一位都預測正確，第位預測正確當且僅當?shù)谖惠斎雽乃锌赡芮闆r都預測正確。模型能夠識別長度為的語言，當且僅當能夠正確預測長度小于等于的測試集中的樣本。

2.2 實驗結果

2.2.1 文法推測實驗

SRN、GRU、LSTM和以其為控制器對應的StackRNN在Dyck2語言上的文法推測實驗結果如表1所示。

表1 確定型CFL文法推測實驗結果

Coarse控制器I/（%）P1/（%）P2/（%）P3/（%）P4/（%）P5/（%） StackRNNSRN10010010010023.800.00 GRU10010010078.700.000.00 LSTM10010010090.580.000.00 SRN—94.4396.605.400.000.000.00 GRU—98.4197.3514.880.000.000.00 LSTM—99.9199.9045.000.200.000.00

2.2.2 可視化實驗

StackRNN在P2中樣本的轉(zhuǎn)移過程如表2所示。

2.3 結果分析

文法推測實驗中SRN、GRU和LSTM在測試集P2上的Coarse值無法達到100%，說明其在訓練過程中僅僅是在記憶已有的樣本模式，而不同StackRNN在測試集P2上的Coarse值都達到了100%，并且在更復雜的測試集上Coarse值也可以達到100%，結果表明StackRNN可以準確預測最長8倍于訓練集樣本的測試集樣本，由此得出StackRNN可以識別確定型CFL的結論。

表2 P2中樣本轉(zhuǎn)移過程

thtitrtht+1Stackd1td2tutv1tv2typtyt 1AsaAλ0.100.100.91bbe([e([ 2A(bAba0.360.360.44ba()[()[ 3A[aAab0.310.310.32ab([]([] 4A[bAbb0.330.330.35bb([]([] 5A(bAba0.390.390.5ba()[()[ 6A)aAλ0.070.070.41bb([]([] 7A[bAbb0.330.330.35bb([]([] 8A]bAλ0.110.110.52bb([]([] 9A(bAba0.390.390.5ba()[()[ 10A(aAaa0.380.380.47aa()[()[ 11A)aAλ0.060.060.43bb()[()[ 12A(aAaa0.380.380.47aa()[()[ 13A[aAab0.320.320.34ab([]([] 14A[bAbb0.340.340.37bb([]([] 15A]bAλ0.110.110.53bb([]([] 16A(bAba0.390.390.51ba()[()[ 17A[aAab0.330.330.33ab([]([] 18A[bAbb0.340.340.38bb([]([] 19A]bAλ0.110.110.53bb([]([] 20A(bAba0.390.390.52ba()[()[ 21A)aAλ0.070.070.4bb([]([] 22A(bAba0.390.390.52ba()[()[ 23A)aAλ0.070.070.4bb([]([] 24A]bAλ0.110.110.54bb()[()[

表2（續(xù)）

在可視化實驗中，對以SRN為控制器的StackRNN識別P2樣本的模型進行可視化分析。從表2中可以看出，StackRNN學習到的棧符號單位長度約為0.4，在每次轉(zhuǎn)移中都會首先彈出棧頂符號，然后當輸入符號“（”時，PUSH操作中1t和2t取值0.4左右，即先壓入原棧頂符號再壓入棧符號a；當輸入符號“）”時，PUSH操作中1t和2t取值0.1左右，即不壓入棧符號；當輸入符號“[”時，PUSH操作中1t和2t取值0.4左右，即先壓入原棧頂符號再壓入棧符號b；當輸入符號“]”時，PUSH操作中1t和2t取值0.1左右，即不壓入棧符號。

StackRNN一直處于狀態(tài)A直到輸入終止字符e并且棧內(nèi)容空時，StackRNN的控制器內(nèi)狀態(tài)變?yōu)闋顟B(tài)B，最終每次轉(zhuǎn)移的預測結果與真實結果一致。可以看出，StackRNN是通過模擬確定型PDA來識別Dyck2語言，從而得出StackRNN可以模擬確定型PDA的結論。另外，從表2中可以看出由于StackRNN采用軟決策機制，每一次轉(zhuǎn)移中PUSH操作的1t、2t和POP操作的t都與期望取值之間存在誤差，即在期望取值為0，取值約為0.1，在期望取值為單位長度0.4時，取值約為0.4，而誤差被存儲在棧中并向前傳播，隨著樣本長度增加誤差逐漸積累最終導致預測錯誤，這也StackRNN雖然可以識別Dyck2語言，但是存在最大泛化長度的原因。

3 結束語

本文設計了StackRNN并從自動機理論的角度對其進行可解釋性研究得出StackRNN可以模擬非轉(zhuǎn)移確定型PDA的結論。此外仍有問題值得研究，一個方向是使StackRNN模擬PDA中的轉(zhuǎn)移功能；另一個方向是使StackRNN識別非確定型CFL，因StackRNN是前向計算模型，如果想解決非確定型CFL的識別問題，需要具有回溯功能的模型，初步設想是將StackRNN與啟發(fā)式算法結合，有待進一步探索。

［1］ELMANl J L.Finding structure in time［J］.Cognitive Science，1990，14（2）：179-211.

［2］GERS F A，SCHMIDHUBER E.Lstm recurrent networks learn simple context-free and contextsensitive languages［J］.IEEE Transactions on Neural Networks，2001，12（6）：1333-1340.

［3］DAS S，GILES C L，SUN G.Learning context-free grammars：capabilities and limitations of a recurrent neural network with an external stack memory［C］//Conference of The Cognitive Science Society，San Francisco：Morgan Kaufmann Publishers，1992：791-795.

［4］GREFENSTETTE E，HERMANN K M，SULETMAN M，et al.Learning to transduce with unbounded memory［J］.Computer Science，2015（6）：1828-1836.

［5］林茨.形式語言與自動機導論（英文版）［M］.北京：機械工業(yè)出版社，2004.

TP391.1

A

10.15913/j.cnki.kjycx.2019.14.030

2095－6835（2019）14－0070－03

郭立鵬（1993—），男，河北衡水人，在讀碩士研究生，研究方向為大數(shù)據(jù)與人工智能。

〔編輯：張思楠〕