StackRNN的设计及可解释性研究

郭立鹏

StackRNN的设计及可解释性研究

郭立鹏

（清华大学计算机系，北京 100084）

针对循环神经网络的可解释性问题设计StackRNN，StackRNN在确定型上下文无关语言文法推测实验中可以预测最长8倍于训练样本的测试集样本，可视化实验表明StackRNN具有模拟确定型下推自动机的能力。该研究对将深度学习应用于自然语言处理尤其是与程序语言相关的任务具有重要的意义。

循环神经网络；可解释性；记忆网络；自动机理论

循环神经网络（Recurrent Neural Network，RNN）是神经网络中处理序列数据的重要模型，而可解释性是机器学习模型尤其是神经网络中存在的问题之一。目前，已有研究表明RNN中的简单循环网络（Simple Recurrent Network，SRN）、长短时记忆网络（Long-Short Term Memory，LSTM）、门控循环单元（Gated Recurrent Unit，GRU）与自动机之间存在密切的联系[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 优化栈操作

弹出栈顶符号即读取栈顶符号，本质是一个操作，所以取消Neural Stack中的读取常量并合并READ操作和原POP操作为 POP 操作。并且在时刻 StackRNN 先执行PUSH操作表示时刻压入栈符号，再执行POP操作表示弹出栈顶符号用于时刻+1的转移。

1.2 形式约束下推自动机

为了模拟确定型PDA，StackRNN的设计依据为自动机理论中的一个重要定理[5]。

定理1：对于任意的PDA都存在满足以下约束的等价PDA，即约束1是只有一个接受态f并且只有栈空时才进入该接受态；约束2是中产生式右部只能为（i，）或（i，）两种形式，即每次迁移栈的变化只能是增减一个符号，而不再是定义中的任意多个。此定理对于确定型PDA也有效，结合确定型上下文无关语言（Context-Free Language，CFL）与确定型PDA的关系，可以得到重要推论。

推论1：确定型CFL记为，总是存在一个满足两点约束的确定型PDA记为DPDA，使得=（DPDA）。

该推论是StackRNN设计的重要依据。根据推论，如果想实现确定型PDA，只需要实现结构满足在每次转移中能够压入2个或者压入0个栈符号的确定型PDA。所以，据此设计StackRNN，先压入确定程度为1t的栈符号1t，然后再压入确定程度为2t的栈符号2t。其中2t由1t经过克隆操作得到，克隆即1t与2t有独立的存储空间，但是共享后向传播路径。这样StackRNN的结构实现了在时刻可以压入0个或2个栈符号：当2t=1t=0时，压入0个栈符号；当2t=1t=1时，压入2个栈符号。此处改进满足了定理1中的约束2，约束1会在损失函数设计的改进中满足。当满足约束1以及约束2时，理论上StackRNN可以识别任意一种确定型CFL。

1.3 优化控制器内连接方式

由转移函数（­t-1，t，t-1）=（­t，t）可知，不仅当前状态­t，而且当前栈的变化即t，1t，2t，1t，2t也由­t-1，t，t共同决定。Neural Stack将t连接至控制变量及栈符号变量，这样会导致复杂的状态空间而且存在信息压缩损失的问题。因此，改变控制器内连接方式，由­t-1，t，t与t、1t，2t，1t，2t进行全连接。

1.4 优化损失函数

根据定理1的约束1，当判定输入为正样本时必须同时满足栈内容为空以及终态为接受态的条件。所以设置超参数并在原损失函数的基础上添加栈为空的损失函数lossstack以满足约束1。

2 实验

2.1 实验任务

准备进行确定型CFL文法推测实验和StackRNN可视化实验，文法推测实验的目标是测试不同RNN对确定型CFL的识别能力，可视化实验的目标是探究StackRNN与确定型PDA的关系。文法推测实验的数据集为Dyck2语言。Dyckn语言定义为由种括号对正确嵌套生成的语言，选择Dyck2语言代表确定型CFL的原因是由Chomsky-Schutzenberger表示定理可知，任何的CFL都可以由正则语言和Dyckn语言的同态交集表示，因此成功识别Dyck2语言是识别CFL的必要条件。为了测试模型的泛化能力，数据集划分为样本长度范围和深度范围为（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值定义为预测正确的样本与测试集所有样本之比。

预测正确样本的标准如下：样本预测正确当且仅当样本每一位都预测正确，第位预测正确当且仅当第位输入对应的所有可能情况都预测正确。模型能够识别长度为的语言，当且仅当能够正确预测长度小于等于的测试集中的样本。

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中样本的转移过程如表2所示。

2.3 结果分析

文法推测实验中SRN、GRU和LSTM在测试集P2上的Coarse值无法达到100%，说明其在训练过程中仅仅是在记忆已有的样本模式，而不同StackRNN在测试集P2上的Coarse值都达到了100%，并且在更复杂的测试集上Coarse值也可以达到100%，结果表明StackRNN可以准确预测最长8倍于训练集样本的测试集样本，由此得出StackRNN可以识别确定型CFL的结论。

表2 P2中样本转移过程

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（续）

在可视化实验中，对以SRN为控制器的StackRNN识别P2样本的模型进行可视化分析。从表2中可以看出，StackRNN学习到的栈符号单位长度约为0.4，在每次转移中都会首先弹出栈顶符号，然后当输入符号“（”时，PUSH操作中1t和2t取值0.4左右，即先压入原栈顶符号再压入栈符号a；当输入符号“）”时，PUSH操作中1t和2t取值0.1左右，即不压入栈符号；当输入符号“[”时，PUSH操作中1t和2t取值0.4左右，即先压入原栈顶符号再压入栈符号b；当输入符号“]”时，PUSH操作中1t和2t取值0.1左右，即不压入栈符号。

StackRNN一直处于状态A直到输入终止字符e并且栈内容空时，StackRNN的控制器内状态变为状态B，最终每次转移的预测结果与真实结果一致。可以看出，StackRNN是通过模拟确定型PDA来识别Dyck2语言，从而得出StackRNN可以模拟确定型PDA的结论。另外，从表2中可以看出由于StackRNN采用软决策机制，每一次转移中PUSH操作的1t、2t和POP操作的t都与期望取值之间存在误差，即在期望取值为0，取值约为0.1，在期望取值为单位长度0.4时，取值约为0.4，而误差被存储在栈中并向前传播，随着样本长度增加误差逐渐积累最终导致预测错误，这也StackRNN虽然可以识别Dyck2语言，但是存在最大泛化长度的原因。

3 结束语

本文设计了StackRNN并从自动机理论的角度对其进行可解释性研究得出StackRNN可以模拟非转移确定型PDA的结论。此外仍有问题值得研究，一个方向是使StackRNN模拟PDA中的转移功能；另一个方向是使StackRNN识别非确定型CFL，因StackRNN是前向计算模型，如果想解决非确定型CFL的识别问题，需要具有回溯功能的模型，初步设想是将StackRNN与启发式算法结合，有待进一步探索。

［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］.北京：机械工业出版社，2004.

TP391.1

A

10.15913/j.cnki.kjycx.2019.14.030

2095－6835（2019）14－0070－03

郭立鹏（1993—），男，河北衡水人，在读硕士研究生，研究方向为大数据与人工智能。

〔编辑：张思楠〕