论文分享_07_31

Synthesizing Context-free Grammars from Recurrent Neural Networks

摘     要

        本文提出了一种从训练过的递归神经网络(RNN)中提取上下文无关文法(CFG)的算法。本文通过在L算法中提取的近似于非正则语言的确定性有限自动机(DFA)序列中提取pattern rule sets(PRSs),再将PRS转换为CFG,最终完成从RNN提取CFG。

背景介绍

        递归神经网络(RNN)是一类适用于序列输入的神经网络模型,广泛应用于各种序列任务,如自然语言处理等。由于它们的内部过程不透明,因此提取RNN模型学习的语言对于促进理解RNN和验证其正确性是非常重要的。现有的工作集中于从训练的RNN中提取有限自动机(DFAs和WFAs)

本文贡献

       本文的贡献在于提出了一种从经过训练的RNN中提取的DFA序列进一步提取CFG的算法,并进行实验。
       首先,从RNN中提取CFG对于促进对RNN的理解和验证其正确性非常重要。
       其次,学习的CFG可用于扩充或推广RNN学习的规则:由于固定精度RNN只能学习固定深度字符串的语言,因此若能找到CFG,就而且可以将其推广到无限的字符串。

算法内容

       本文提出了一种算法:通过对 L*算法[1]提取的不断扩张的DFA序列,进行解析,通过定义两种合成方式 Serial Composition 和 Circular Composition ,在DFA序列中相邻的两个DFA中提取其扩张作为模型(pattern),进一步解析其扩张的规则(rule),然后制作pattern rule sets(PRSs),再将PRS转换为CFG,最终完成从RNN提取CFG。       下面是两种合成方式的示例:        在制作过程中,由于L*算法本身的噪音和RNN训练不完全的可能性,算法可能不能在理想状态下运行,因此作者进一步对算法进行改进:

  1. vote:对PRSs中的规则使用次数建立阈值,对小于阈值的规则不予采纳
  2. simultaneous rule applications :由于L*算法中相邻DFA一次扩张可能使用多个规则,所以对规则使用进行了同步化处理

实验结果

        本文对15种语言进行了测试,其中 L1-L6为 XnYn(n为其指数),L7-L9为Dyck和RE-Dyck语言,L10-L15为其它语言的变种。

       表格第2列为从RNN中提取的DFA序列中元素的个数;第3列和第4列显示了算法在应用vote消除噪声前后发现的模式数。第5列给出了最后所有模式的最小和最大的投票数。第6列记录了算法是否找到了正确的CFG。其中,对于算法只遗漏或包含1或2个有效/无效结果的语言,我们将其标记为部分正确(partial)。

参考文献

[1] Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput.75(2),87–106(1987).https://doi.org/10.1016/0890-5401(87)90052-6