ICLR2019 | 表示形式语言：比较有限自动机和循环神经网络

本文对ICLR2019论文《REPRESENTING FORMAL LANGUAGES：A COMPARISON BETWEEN FINITE AUTOMATA AND RECURRENT NEURAL NETWORKS》进行了解读。

这篇论文通过将RNN的内部状态映射为自动机状态，研究RNN在正则语言识认时所采用的内部结构。通过实验证实了RNN状态与自动机状态间确实存在解码函数。不过这种解码函数不能将RNN状态直接映射到正则语言的MDFA状态，而是映射到它的超状态 。研究显示RNN与自动机在结构上存在较强的关联关系，并解释了RNN在形式语言识认方面所具备的较强学习能力的原因。

关注文章公众号

对话框回复“paper10”获取本篇论文

本文作者：Joshua J. Michalenko， Ameesh Shah， Abhinav Verma， Richard G. Baraniuk， Swarat Chaudhuri， Ankit B. Patel(Rice University)

论文地址：https://arxiv.org/abs/1902.10297

研究背景

循环神经网络（RNN）对真实世界中带噪声的序列数据具有不可思议的建模效果。它似乎能够识认序列数据的文法，因为RNN可以生成文法基本正确的结构化数据，像C++和Latex源码。然而，关于RNN识认形式语言的能力方面的研究却很少。本文通过对比RNN与有限自动机的内部结构，提出一种理解RNN在表示形式文法方面所使用的内部结构的新方法。

由于正则语言可以采用无限多的有限自动机定义，所以本文只考虑最小确定有限自动机MDFA（minimal deterministic finite automaton），即定义某项正则语言的自动机集合中包含状态最少的自动机。

在实验过程中，我们首先选择一个自动机，并随机生成一组符合该自动机的正负样本序列，然后将样本数据喂给RNN进行训练。最后将训练得到的RNN的隐层状态与自动机状态进行对比，分析两种状态间是否存在某种映射关系。

我们一共选择了大约500个自动机进行实验，结果显示这种映射关系确实存在。图1展示了用正则语言[（（[4-6]{2}[4-6]+）？）3[4-6]+]生成的样本训练得到的RNN网络的t-SNE嵌入。虽然，右侧的MDFA包含6个状态，我们发现左侧的RNN状态呈现出5个点簇。实际上这种现象在实验中普遍存在， 而且可以用经典系统理论中的抽象概念进行很好地解释。

图1：右侧是刻画正则语言[（（[4-6]{2}[4-6]+）？）3[4-6]+]的自动机，左侧是对应的RNN的隐层状态空间可视化的结果。该图用不同的颜色区分DFA状态。训练得到的RNN将DFA中的状态1（绿色）和状态2（蓝色）合并为一个状态。状态1和状态2均可独立地表示[4-6]*。

一个自动机M的抽象A也是一个自动机，其状态是由M的状态聚类生成的超状态。通常，抽象自动机A与原自动机M相比损失了一定的语言分辩能力，因此A接受的语言是M接受语言的超集。在正则语言识认过程中，我们观察到训练得到的RNN R通常表现出这种抽象行为。这些状态可以解码为MDFA的某个抽象机器A，使得A能够以极高的概率接受R接受的任何字符序列。

相关研究

现有研究主要采用状态抽取的方式从RNN隐层状态中得到DFA，主要包括4类方法。（1）早期的状态抽取方法采用动态状态划分过程从二阶循环神经网络抽取DFA。（2）基于聚类的抽取方法。首先对内部状态空间采样，然后对状态向量的采样结果进行聚类（如K-means、基于密度的聚类或KNN），生成包含指定数量状态的自动机。（3）基于频谱算法抽取方法。利用频谱分析算法从RNN中抽取带权重自动机。基于L*算法的抽取方法。（4）将RNN看作经典文法推断中先知，利用L*算法的查询问题构建DFA。

本文没有采用状态抽取的方式，而是将RNN状态与DFA状态间建立直接的映射关系。与本文研究思路最接近的是Tino发表于1998的论文。他们也在RNN与DFA的状态间建立关联关系。然而Tino的RNN要求精确模拟DFA，而且其研究对象也仅限定于包含2-3个状态的小规模自动机。

相反，本文不需要在RNN与DFA间建立精确的行为对应关系。DFA状态允许通过抽象合并成大粒度的超状态。本文在RNN与自动机的状态建立近似映射关系，映射的精确性可定量地评估。这允许我们在处理更大规模的自动机时可以在RNN和DFA间建立状态的映射关系。

相关定义

1.自动机的抽象化

2.状态解码

3.抽象状态解码

本文将抽象状态的解码精度定义为：

4.抽象状态的转移关系解码

本文将转移关系的解码精度定义为：

实验及结果分析

针对以下4个基本问题，本文针对大约500个正则语言对比分析了RNN及自动机的状态映对应关系。

(1)如何选择一个合适的抽象编码函数f ̂？

(2)什么导致抽象函数α必然存在？

(3)能否事先评估高精度细粒度的编码函数f ̂？是否存在？

(4)如何用抽象函数α和编码函数f ̂？更好地理解RNN？

通过实验本文得到以下结论。

1.解码器学习。

实验显示非线性解码器与线性解码器相比不具备更高的精确性。在本文的实验中随着自动机阶数提高，非线性解码器的精度与线性解码器一样下降。实验发现，（1）表达能力较强的非线性解码器并没有产生更高精度的解码效果。（2）对MDFA的解码精度普遍不高。因此，我们认为对本文的解码任务来说，线性解码器的表达能力是足够的；但对RNN内部知识组织结构还需要其他的解释方式。

图2：左图是线性解码器的精度随DFA阶数上升变化趋势。右图是非线性解码器（蓝色）和线性解码器（绿色）解码精度的对比，该图反映出非线性解码器的精度并不比线性解码器高。

2.为什么RNN只能模拟抽象化的自动机？

本文认为RNN在识认正则语言时只能模拟抽象化的MDFA，而不是MDFA本身。为验证该观点，本文设计了一个简单的贪婪算法来选择抽象函数α。（1）给定一个包含n个状态NFA A_L^n，枚举所有两状态合并为一个超状态的方案。（2）选择解码精确度最高的状态合并方案生成新的NFA。（3）重复这个过程直到NFA仅剩下2个状态 。虽然该贪婪算法并不能保证找到全局最优的状态合并方案，并比随机状态合并要好很多。

图3 左图展示SIMPLE EMAILS语言识认任务中线性解码器的解码精度随粒度上升的变化情况。右图展示DATES语言识认任务中线性解码器的解码精度随粒度上升的变化情况。

图4 左图是对所有解码精度和粒度的AUC标准化后的平均值。右图展示要达到90%的正确率所需的抽象粒度的平均比率。

图5 左图展示状态的线性解码精度随粒度变化情况。右图展示转移关系的线性解码精度随粒度变化的情况。

3.抽象状态和转移关系的解码

对于任何抽象α，我们都要评估解码函数是否具有高准确率和低抽象粒度。如图5所示，解码正确率受原始MDFA的复杂度影响。MDFA越复杂，准确率越低。原因有两个：（1）当MDFA规模变大时，解码问题的难度自然增加；（2）R_L总是将自动机多个状态合并为一个隐层状态。

4.用MDFA解释RNN隐层状态空间

采用两个真实世界的正则语言的例子解释RNN内部知识表示的方式。RNN在学习SIMPLE EMAILS时呈现出位置无关性，即忽略了模式[a-d]*出现的位置。而在学习长度固定的DATES时又呈现出位置相关性，即将相同位置的状态抽象为一个超状态。

图6 上图是SIMPLE EMAILS语言的MDFA，用系统树图描述线性解码器对该自动机的抽象化顺序。第一次抽象合并两个代表[a-d]*的状态。下图是DATE语言MDFA，用系统树图描述线性解码器对该自动机的抽象化顺序。第一次抽象合并两个相同位置的状态。

结论

本文提出的RNN结构解释方法使我们对RNN有了新的认识。虽然本文采用的解码器不能将RNN的状态映射到MDFA状态，只能映射到抽象后的超状态。但本研究仍然证明了RNN的内部结构与有限自动机的结构间存在很强的关联关系，并解释了众所周知的RNN识认形式语法的能力。后续将采用该研究扩展到上下文无关语言、递归可枚举语言及它们对应的神经网络上。