大漠孤烟原创Joshua J. Michalenko, Ameesh Shah, Abhinav Verma, Richard G. Baraniuk, Swarat Chaudhuri, Ankit B. Patel(Rice University)本文作者

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

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

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

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

研究背景

循环神经网络(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识认形式语法的能力。后续将采用该研究扩展到上下文无关语言、递归可枚举语言及它们对应的神经网络上。

AMiner学术头条
AMiner学术头条

AMiner平台由清华大学计算机系研发,拥有我国完全自主知识产权。系统2006年上线,吸引了全球220个国家/地区800多万独立IP访问,数据下载量230万次,年度访问量1000万,成为学术搜索和社会网络挖掘研究的重要数据和实验平台。

https://www.aminer.cn/
专栏二维码
理论有限自动机循环神经网络ICLR 2019
1
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

推荐文章
暂无评论
暂无评论~