正则表达式与神经网络的深度融合

本文介绍了上海科技大学屠可伟研究组与乐言科技的一项合作研究，提出了将正则表达式规则与神经网络深度融合的新思路。该论文已被 EMNLP 2020 接收为长文。

论文标题：

Cold-Start and Interpretability: Turning Regular Expressions into Trainable Recurrent Neural Networks

论文链接：

http://faculty.sist.shanghaitech.edu.cn/faculty/tukw/emnlp20reg.pdf

神经网络发展至今，在很多自然语言处理任务上获得了很大的成功。在有足够多标注数据的情况下，神经网络往往效果惊人。但是，当标注数据匮乏时，神经网络的性能就会大打折扣。

此外，神经网络缺少可解释性以及难以融入外部知识的问题也一直为人所诟病。与之对应的，基于符号主义的规则系统，如正则表达式（regular expression, RE），通常由人类专家基于领域知识构建，具备着良好的可解释性，可用于没有任何数据的冷启动场景，并且可以通过规则的增删和修改来快速应对目标任务的变化。

因此，尽管神经网络和深度学习如火中天，在工业界实际应用场景中，基于规则的方法仍然有着稳固的地位。规则系统的缺点在于完全依赖于人类专家，无法自动从数据中学习，因而在数据资源丰富的场景下难以达到和神经网络相近的效果。

为了结合两者的优点，近年来如何将规则更好地融入神经网络成为了一个重要的研究方向。现有的工作主要利用规则去约束神经网络，通常使用多任务学习 （multitask learning）、知识蒸馏（knowledge distillation）等方法，或是根据规则的启发设计新的神经网络结构。

然而，两类方法仍然需要大量数据用于训练，并且前者的神经网络本身仍然是一个黑盒子，缺乏可解释性，后者后者难以利用已有规则进行转化或是通过专家手工构建。

在这篇论文中，我们提出了直接由正则表达式转化而来的神经网络：FA-RNN （Finite Automata - Recurrent Neural Networks），将其使用在文本分类任务上，使得基于 FA-RNN 的系统在未经训练的情况下与正则表达式文本分类系统有着相似的准确率。

同时，FA-RNN 兼备神经网络可训练、可泛化的优点。我们发现，FA-RNN 在 zero-shot 以及 low-resource 场景下，由于人类知识的融入，与基于神经网络的基线模型相比有着明显的优势；在全部数据的场景下，FA-RNN 与基线模型有着相当的性能。

另外，经过训练的 FA-RNNs 可以近似地表示成非确定性有限状态自动机（non-deterministic finite automata, NFA）, 进而可以近似地转化为正则表达式，因此有着更好的可解释性。

背景：正则表达式与有限状态自动机

正则表达式是在工业中最常用的规则之一。我们以意图分类数据集 ATIS 中的一个类别 [distance] 为例：根据常识，如果问句里面包含“how far”，“how long”或者 “distance”，那么通常这句话就与[询问距离]有关。

因此我们可以对这个类别撰写出下表第二行的正则表达式，去匹配如第三行所示的句子（其中 $* 表示任意词出现任意次）。

▲ 表一

对计算理论有一定基础的读者可能会知道，任何正则表达式都能转化为非确定性有限自动机（NFA），如上表的第四行，而任何 NFA 也可以表述成一个正则表达式。

并且有以下重要的关系：如果读完了一个句子，自动机能够从开始状态（s0）走到结束状态（s2），那么，该自动机接受了这个句子，并且其等价的正则表达式也匹配了这个句子。

1.1 有限状态机的向量化运行

我们会发现，这个有限状态自动机可以用一个三维张量，以及两个向量表示，张量的三个纬度分别是词表大小 V，自动机状态数 S，以及状态数 S，可以看成是由每个单词对应的转移矩阵 stack 起来组成。两个向量分别表示了自动机的初始状态以及结束状态。

如下图所示，对于一个句子，我们可以得到每一个单词的转移矩阵，若该矩阵的第 i 行第 j 列为 1，则表示可以通过该单词从状态 si 转移到 sj。因此，我们可以用前向算法（forward algorithm）或者维特比算法（viterbi algorithm）来计算句子被该自动机接受的分数。

▲ 图一

我们以前向算法为例：读完整个句子之后，从开始状态到达任一结束状态的路径数可以表示为：

我们只要改换一下 notation 以及公式的形式，这个计算过程就可以被看成一个 RNN。其中 A 是指自动机（automata），x 为句子。

ht 类似 RNN 中的隐状态向量，他的维度等于自动机状态数。ht 的每一个维度就表示：在读了 t 个单词之后，有多少条路径能够从开始状态到该维度对应的自动机状态。

1.2 规则的文本分类系统

接下来我们描述一个基于正则表达式的文本分类系统。如下图的上半部分所示，我们针对输入句子运行所有的正则表达式，得到匹配结果，然后通过一些逻辑操作，将匹配的结果整合。

例如，如果一句话只被针对 A 类别的正则表达式匹配，那么他的标签是 A 类别；如果这句话被 A，B 两个类别都匹配，那么我们可以通过事先定义一个优先级关系来选出更可能的类别。这些都可以用逻辑操作来实现。

所以，正则表达式的分类系统先匹配（matching），再整合匹配结果（aggregation）来得到句子的标签。

▲ 图二

方法：从RE到FA-RNN，从规则系统到神经网络

2.1 减少模型参数、结合词向量的FA-RNN

如果直接由 RE 转化而来，FA-RNN 的参数需要包括三维张量 (VxSxS)。这个三维张量相比于传统的词向量矩阵 (VxD) 过于大了，并且不包含词向量中存在的语义信息。

我们利用了张量秩分解（tensor rank decomposition，CP decomposition）的技术，用 ER, D1, D2 三个大小分别为 VxR, SxR 与 SxR 的矩阵来近似表示原来的张量，其中，S 为自动机状态数，R 为 rank 数。原来公式 (1)  中的迭代公式由此变为了：

记 t 时刻的输入为 x_t, 我们可以把 ER 看成一个只包含规则信息的词嵌入矩阵，vt 则是 ER 矩阵的对应行选出的 R 维词向量。由此，我们模型的参数量大大减少，相当甚至更少于 LSTM, GRU 等循环神经网络。

接下来我们介绍我们结合词向量（如：glove）的方法。为了结合 D 维度的词向量，我们利用一个 DxR 的矩阵 G 将词向量从 D 映射到 R 维空间，这个矩阵 G 可以初始化为词嵌入矩阵 Ew 的违逆乘上 ER。我们再引入一个 0，1 之间的超参数来结合 vt 与 G 映射后的两个 R 纬词向量，控制接受多少词向量语义的信息，更新公式变为如下：

我们将这个模型称之为 FA-RNN。经过了张量分解、词向量结合之后，在 zero-shot 的场景中，FA-RNN 仍然能够得到和规则系统接近的准确率。

例如在 ATIS 数据集（Hemphill et al., 1990）中，规则系统的准确率为 87.01%，FA-RNN 仍然能够达到 86.53% 的准确率，而大部分的神经网络初始的准确率近似于随机。另外，我们提出了 FA-RNN 的双向以及门控变体，不过模型可解释性相应下降了。

2.2 从规则系统到可以训练的神经网络

有了 FA-RNN，我们就可以用它构造规则系统的“神经网络版本”，如图二的下半部分所示。FA-RNN 的最后一个“hidden state”包含了正则表达式的匹配信息，我们可以通过一个 MLP 来整合匹配结果。

第一个 linear 层取出所有自动机的接收状态（final state）的值，第二个 linear 层可以利用 soft logic 进行简单的逻辑操作，并且最终得到每个类别的分数。这些分数的理想值为非负正数。

可以看到，我们的模型结构非常类似于传统的 RNN+MLP，同时模型输出的结果完全与规则系统一致。与规则系统不同的是，我们可以直接将模型输出的标签分数利用 cross-entropy 损失函数进行训练。

实验以及实验结果

3.1 baselines

我们比较了结构对应的传统神经网络。具体结构为 BiRNN / BiGRU / BiLSTM / CNN / DAN 给句子做 encoding，用 Linear 层输出每个 label 的 score。除此之外，我们使用了一些已有方法将规则与传统神经网络结合。

分别是 Luo et, al 提出的三种利用正则表达式匹配结果的方式（+i: 将正则表达式匹配结果作为额外的特征输入，+o: 利用 RE 结果直接改变输出 logits, +io 前两者结合），以及两种基于知识蒸馏的方式，分别记为 +kd（Hinton et al., 2015）以及 +pr（Hu et al. 2016）。

3.2 数据集

我们在三个文本分类数据集上实验，分别是 ATIS (Hemphill et al., 1990), Question Classification (QC) (Li and Roth, 2002) 以及 SMS (Alberto et al., 2015). 我们使用了 glove 词向量。下表显示了数据集以及规则的统计信息以及样例。

▲ 表二：数据集统计及规则样例

我们发现，FA-RNN 在 zero-shot 以及 low-resource 的场景下有着明显的优势，并且在 full-shot 上仍然能够得到与传统简单神经网络方法以及其经过规则加强后相似的准确率。结果如下：

▲ 表三：zero-shot 准确率

▲ 表四：few-shot 、full dataset 准确率

3.3 模型可解释性的探索

训练过后的 FA-RNN 参数可以还原出 VxSxS 的三维的张量。不过不再是非零即一了，因此不再对应非确定性有限自动机 (NFA)，而对应了带权有限状态自动机(weighted finite automata, WFA)。

由于 FA-RNN 与计算模型 WFA 的对应关系，我们认为他相比较传统神经网络有着更强的可解释性。进一步地，我们可以设定一个阈值，将 WFA 中大于阈值的认为是 1，小于的认为是 0，从而将 WFA 转化为 NFA，并将 NFA 转化为人类可读的正则表达式。

下图展示了 ATIS 数据集中在训练前与训练后针对 [aircraft] 类别的自动机变化。可以看到，新的自动机可以考虑更全面的情况，例如识别到句子中有 jet, 737(boeing) 的时候认为该句子在描述 aircraft。

我们发现，训练过后的 FA-RNN 转化为的正则表达式，虽然是有损的转化，也能达到和训练之前的系统相近甚至更高的准确率。在 QC 数据集上提升了 9.2% 的准确率，在 ATIS 上提升了 0.45%，在 SMS 上稍有下降 (-1.2%)。

总结

我们提出了直接由正则表达式转化而来的神经网络：FA-RNN ，并将其应用在文本分类任务上，使得基于 FA-RNN 的系统在未经训练的情况下与正则表达式文本分类系统有着相似的准确率。

通过实验发现，与基线模型相比，由于知识的融合，FA-RNN 的文本分类系统在 zero-shot 与 low-resource 场景下有着更好的效果，在全部数据的训练场景下也有着不错的竞争力。同时，FA-RNN 可以转化为计算模型 WFA，甚至正则表达式，因此有着更好的可解释性。

研究组介绍

上海科技大学信息学院屠可伟老师研究组主要从事自然语言处理、机器学习等人工智能领域的研究，目前侧重于研究语言结构的表示、学习与应用。

研究组近几年已发表顶会论文数十篇，其中三篇无监督句法解析的论文已被美国卡内基梅隆大学自然语言处理课程列为阅读材料，另一篇论文是 ACL2018 句法领域的最高分论文。2020 年到目前为止，研究组已发表 ACL论文4篇，EMNLP 论文3篇，EMNLP Findings 论文4篇。

研究组现招收硕士研究生（推免生）、博士后和研究助理，欢迎有兴趣的同学联系屠老师。

更多信息请访问屠可伟老师主页：

http://faculty.sist.shanghaitech.edu.cn/faculty/tukw/

更多阅读

#投 稿 通 道#

 让你的论文被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。

📝 来稿标准：

• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向） 

• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接 

• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志

📬 投稿邮箱：

• 投稿邮箱：[e-mail] 

• 所有文章配图，请单独在附件中发送 

• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

关于PaperWeekly

PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。