郭立鵬

StackRNN的設(shè)計(jì)及可解釋性研究

郭立鵬

（清華大學(xué)計(jì)算機(jī)系，北京 100084）

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

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

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

1 設(shè)計(jì)StackRNN

StackRNN是在Neural Stack的基礎(chǔ)上為了模擬確定型PDA而設(shè)計(jì)的，具體改進(jìn)包括4個(gè)方面。

1.1 優(yōu)化棧操作

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

1.2 形式約束下推自動(dòng)機(jī)

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)任務(wù)

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

預(yù)測(cè)正確樣本的標(biāo)準(zhǔn)如下：樣本預(yù)測(cè)正確當(dāng)且僅當(dāng)樣本每一位都預(yù)測(cè)正確，第位預(yù)測(cè)正確當(dāng)且僅當(dāng)?shù)谖惠斎雽?duì)應(yīng)的所有可能情況都預(yù)測(cè)正確。模型能夠識(shí)別長(zhǎng)度為的語(yǔ)言，當(dāng)且僅當(dāng)能夠正確預(yù)測(cè)長(zhǎng)度小于等于的測(cè)試集中的樣本。

2.2 實(shí)驗(yàn)結(jié)果

2.2.1 文法推測(cè)實(shí)驗(yàn)

SRN、GRU、LSTM和以其為控制器對(duì)應(yīng)的StackRNN在Dyck2語(yǔ)言上的文法推測(cè)實(shí)驗(yàn)結(jié)果如表1所示。

表1 確定型CFL文法推測(cè)實(shí)驗(yàn)結(jié)果

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 可視化實(shí)驗(yàn)

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

2.3 結(jié)果分析

文法推測(cè)實(shí)驗(yàn)中SRN、GRU和LSTM在測(cè)試集P2上的Coarse值無(wú)法達(dá)到100%，說(shuō)明其在訓(xùn)練過(guò)程中僅僅是在記憶已有的樣本模式，而不同StackRNN在測(cè)試集P2上的Coarse值都達(dá)到了100%，并且在更復(fù)雜的測(cè)試集上Coarse值也可以達(dá)到100%，結(jié)果表明StackRNN可以準(zhǔn)確預(yù)測(cè)最長(zhǎng)8倍于訓(xùn)練集樣本的測(cè)試集樣本，由此得出StackRNN可以識(shí)別確定型CFL的結(jié)論。

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

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ù)）

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

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

3 結(jié)束語(yǔ)

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

［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］林茨.形式語(yǔ)言與自動(dòng)機(jī)導(dǎo)論（英文版）［M］.北京：機(jī)械工業(yè)出版社，2004.

TP391.1

A

10.15913/j.cnki.kjycx.2019.14.030

2095－6835（2019）14－0070－03

郭立鵬（1993—），男，河北衡水人，在讀碩士研究生，研究方向?yàn)榇髷?shù)據(jù)與人工智能。

〔編輯：張思楠〕