析取范式屠可伟:正则表达式的神经 *** 化

分享嘉宾：屠可伟上海科技大学长聘副教授

编辑整理：Gary DT Dream

出品平台：DataFunTalk

导读：今天分享的内容是如何把正则表达式做神经 *** 化。这是基于我们过去两年发表在 EMNLP 2020 和 2021 上的两篇论文。

我们的 *** 兼具了符号系统和神经 *** 的优点：不需要训练，可以直接根据规则构造出来，所以可以用于冷启动的场景；当有了数据之后，可以通过训练去提升效果。

正则表达式介绍

我们很多落地的系统里面都会用到规则，其中非常具有代表性的一类规则是正则表达式 regular expression，用来表示文本中的 pattern。下面给了一个例子。

$* 表示任意字符串，竖线表示 or 关系。所以这个 pattern 表示的是 how far 或者是 how long 或者是 distance 三种可能性。

可以用正则表达式来做很多任务，如文本分类。如果一个输入的句子能够匹配这个正则表达式，那么我们可以给它一个分类的标签。

正则表达式简单，而应用广泛，因为它具有如下优点：

可解释性，规则易懂支持细粒度的诊断和操控

一个系统一般是由很多表达式构成的，一旦系统出错，可以非常方便地定位到底是哪一条规则出错了，就可以去修改这个规则或者删除它，或者是增加一些额外的规则，这样就可以很快地修正这个错误，所以用规则可以做这种非常细粒度的诊断和操控。

不用训练，不需要任何的数据，只要有规则就可以去上线系统了，所以非常适用于冷启动的场景。

但是正则表示也有它的缺点：

需要有专家来写，但是对于某些领域可能找不到这样的专家；即使专家来写规则，也难以做到面面俱到，可能导致这个基于规则的系统的precision比较高，但是 recall 比较低。无法利用有标注的数据改善系统。当我们的系统运行了一段时间，积累了数据并且有了标签，系统无法基于标签数据训练进化。所以这也是为什么在高资源的场景下，当有了足够多的资源，足够多的数据，神经 *** *** 的效果往往比基于符号的系统的表现会更好一些。

正则表达式系统有优点也有缺点，所以我们想把正则表达式和神经 *** *** 相结合。具体而言，把正则表达式转化成一种神经 *** ，使得这个神经 *** 和原始的正则表达式几乎是等价的。也就意味着只要有了正则表达式，就可以构造出一个相应神经 *** ，可以用于冷启动场景。当我们有了数据的时候，也可以训练这个神经 *** ，从而使这个系统的表现超越原先基于规则的系统。

最后还有一点，就是这个系统在训练之后，还可以还原出正则表达式，从而有可能支持细粒度的诊断和操控。

正则表达式变成神经 ***

具体分为如下几个步骤。

1. 正则表达式转变成等价的有限状态自动机

这个转化过程有非常经典的算法，得到的自动机里有若干个状态（state），有一个起始状态，一个或多个终止状态和若干中间状态。状态之间会有 transition，每一个 transition 有一个对应的输入单词。有限状态自动机和正则表达式是完全等价的。如果一句话可以被正则表达式所匹配，那么它也必然可以被有限状态自动机所匹配，也就是说，从起始状态开始依次接收这句话里的每个单词进行状态转移，最终会到达一个终止状态。反之亦然，如果一句话可以被有限状态自动机所接收，那么它也可以被原始的正则表达式所接收，所以两者是等价的。

有限状态自动机可以用三组参数来表示：

Binary transition tensor T

Binary start vector α0‍

Binary final vector α∞

这三组参数的值都是非零即一的。Transition tensor 的维度是词表大小乘以 state 个数的平方。给定一个单词，我们可以从 Transition tensor 中提取出一个 Transition matrix，表示我们可以从哪些状态跳转到哪些下一个状态。另外两个参数是 start vector 和 final vector，分别表示哪些状态是起始和终止状态。通过这三组参数就可以唯一地表示一个有限状态自动机。

2. 有限状态自动机作为循环神经 ***

那么，有限状态自动机是如何用来推理的？假设给定一个输入的句子，可以计算 forward score，表示这句话被自动机接受的状态转移路径有多少条，0表示不被接受，大于0表示被接受。这个 score 是一个连乘的形式：之一项是 start vector, 最后一项是 final vector，中间是 transition matrix 的乘积。

这个 score 的计算可以从左到右进行，每个时刻计算一个 hidden vector。最开始这个 hidden vector 等于 start vector。接下来在每个时刻，新的 vector 根据前一时刻的 hidden vector 和当前时刻的单词输入来计算。这相当于一个 recurrent step。这和循环神经 *** 的更新公式非常类似，都是在每个时刻用前一时刻的 hidden vector 和当前时刻的输入去计算一个新的 hidden vector。

3. 参数分解

二者区别在于有限状态自动机会涉及到一个很大的参数T，是一个三阶的张量，所以参数量和计算复杂度高于 RNN 或者 LSTM。接下来我们要做的事情就是降低复杂度。我们可以做张量分解来降低T的复杂度，即Tensor Rank Decomposition。把三阶的张量分解成三个矩阵，对这三个矩阵做外积，就可以还原出这个张量。

之一个矩阵大小是 V‍xR ，其中 R 是 rank 。该矩阵的每一行对应的是一个单词，可以看成一个词向量。后面两个矩阵的维度是 KxR，其中 K 是状态的个数。所以后面两个矩阵每一行可以看作一个状态向量 state embedding。根据这个分解，recurrent step 更新公式可以写成一个如上图的新形式。

4. 集成预训练的词向量

刚才我们所得到的词向量是从 T 分解出来的，而 T 是从正则表达式转化而来的。所以它只包含了这个正则表达式的信息。但是我们知道，现在有很多外部的现成的词向量，比如 GloVe，BERT。怎么把这些带有额外 lexical knowledge 的外部embedding引进来？

我们把上一步得到的 word embedding 矩阵 ER 再分解成两个矩阵。之一个矩阵 Ew 表示外部的 word embedding。第二个矩阵 G 初始化成是 Ew 的伪逆与 ER 的乘积。这样一来，两个矩阵相乘就近似等于 ER。这么做的意义是引入了外部的 word embedding，同时在初始化这个模型的时候，依然可以还原出正则表达式所对应的 word embedding，从而使得这个系统依然等价于最初的正则表达式。

在实践当中，我们发现构造出来的 word embedding 和外部的 word embedding做加权平均效果会更好。

这样我们就得到了一种新型的循环神经 *** ，我们把它命名为 FA-RNN。这个神经 *** 和一般 RNN 的区别在于它是完全构造出来的，不是训练出来的。我们不需要任何数据训练，完全是根据最初的正则表达式，通过刚才的四个步骤，构造出了这个神经 *** 的所有参数，并且它的表现和我们最初的正则表达式几乎是等价的。

我们也做了一些扩展了，比如可以加入类似于 GRU 的门控，以及可以把两个方向结合起来，得到类似于 bidirectional RNN 的变种。

接下来我们看一下怎么把 FA-RNN 用于分类任务。

文本分类

我们先来看一下原先的正则表达式系统是怎么做分类的。对于一个分类任务，我们会写很多规则。输入一句话，每个规则都会有一个匹配结果，如果匹配就是1，不匹配就是0，所以我们会有一个0/1的向量。

接下来会有一个逻辑层。逻辑层的作用是做 aggregation，因为这些匹配结果里面可能会有矛盾。比如同时有两条规则匹配了，但是这两条规则对应的 class label 不一样，就会有矛盾。我们一般会通过逻辑层在不同规则之间排一个优先级，用命题逻辑来实现，最终输出唯一的label。

我们把这些正则表达式并联，通过前述 *** 变成了一个 FA-RNN。它对应的自动机依然有一个单独的 start state，但会有很多 final state，这些 final state 对应原先不同的规则，所以也对应的是不同的 class label。原先正则表达式匹配的结果都是 0/1 的，但现在 FA-RNN 输出的是接近于 0/1 的实数，原因在于我们构建 FA-RNN 的时候，使用的 tensor decomposition、门控等都引入了一些近似。所以匹配结果可以是任意实数，但是会比较接近于0/1。这个实数的向量会过一个 MLP，输出 label 上的一个分布。这个 MLP 和逻辑层是相对应的，所以MLP也是根据逻辑层所构造出来的。逻辑层使用的是命题逻辑，涉及的操作就是与、或、非，可以用这三个操作去等价表示任意的命题逻辑表达式。我们使用 soft logic，把与或非改成加减操作和 0-1 之间的 truncate，如下图所示。我们可以把这种操作看成一层的神经 *** ：权重是 1 或 -1，常数就是 bias，0-1 之间的 truncate 对应的就是 ReLU 激活函数。命题逻辑的任何的一个表达式都可以写成合取范式或者析取范式，所以对应到 MLP 就是一个两层的神经 *** 。

给定输入的一句话，经过 FA-RNN 输出一系列匹配的分数，然后再过两层的MLP，最终得到各个标签上的分数，这样就构造了一个神经 *** 系统。它完全是根据正则表达式系统所构造出来的，没有经过任何的训练，但是它和上面的正则表达式系统几乎是等价的，所以不需要训练，可以用于冷启动的场景。另一方面，这个神经 *** 当有了数据时也可以训练，从而进一步提升这个系统的效果。我们可以看一下实验结果。

Zero-shot 就是没有任何数据，完全冷启动的场景。我们 *** 的表现与原始的正则表达式相近，同时远高于神经 *** baseline。

上图是低资源和高资源的场景。首先在 1% 的数据上，我们的效果远远超过所有的 baseline。在 10% 的数据上，我们的效果依然比 baseline 更好。在100% 的数据这个高资源的场景下，我们的效果和baseline不相上下。

总结一下，FA-RNN 既有正则表达式系统的优点，可以用于冷启动，同时，当我们有了数据，也可以和神经 *** 系统一样训练。

神经 *** 还原为正则表达式

当我们训练完 FA-RNN 系统之后，还可以还原出一个正则表达式。前面所说的 FA-RNN 转换 *** 最主要是做了 tensor decomposition，把 transition tensor 分解成了三个矩阵，这三个矩阵是FA-RNN的参数。训练了之后，这三个矩阵更新了，但还是可以把这三个矩阵再乘起来还原出原来的 transition tensor，只不过现在它的值是任意实数，而原始 tensor是 binary 的。所以，我们需要把现在的实数 tensor 做二值化。做完二值化之后，就还原出了一个有限状态自动机。任何一个有限状态自动机都等价于一个正则表达式，所以可以抽取出它所对应的正则表达式。

经过训练再抽取出的正则表达式和原始的正则表达式相比效果怎么样？我们的实验发现在两个数据上有提升，在第三个数据上略有下降，下降的原因是在这个数据上，原始的正则表达式系统的效果已经非常高了，所以很难再进一步提升。

用于Slot filling的正则表达式

我们再来看另外一个正则表达式非常常用的场景 slot filling。给定一句话，找出这句话里的某个信息。比如，在下图例子中，我们想知道航班的起点，所以需要把 San Francisco 标成 from city。可以用下面的带 capturing group 的正则表达式来做这个slot filling。

我们希望把这一类带 capturing group 的正则表达式变成一个神经 *** 。

1. 正则表达式变成有限状态转换器FST

Finite state transducer和finite state automaton一样有很多的state，state 之间有 transition，但是 automaton 的每个 transition 对应的是一个输入单词，而在 transducer 里，不仅有一个输入单词，还有一个输出的标签。我们所使用的标签是经典的 BIO scheme。

通过 BIO scheme 可以找出所需要抽取出的信息。

Transducer也可以用三个参数来表示：

transition tensorstart vectorfinal vector

和前面类似，只不过现在 transition tensor 多了一个维度，因为现在每个 transition 多了一个输出标签，也就是说对于每个输入单词和每个输出标签都会有一个 transition matrix。我们可以给任意一句话及其输出标签序列打分，打分的方式和 forward score 类似。

2. FST作为BiRNN

给定一句话，我们希望去找出分数更高的一个 label sequence。但是这个推理任务是 NP-hard。所以我们用如下的近似算法，在每个位置独立地预测该位置上分数更高的输出 label。

从左到右去读每个单词，然后在每个位置计算 forward score vector α。计算的方式和我们前一个工作类似，根据前一时刻的 vector 和当前时刻的输入来计算当前时刻的 vector。从右到左，根据右边前一时刻的 hidden vector 和当前时刻的输入计算当前的 hidden vector ‍β。把每个位置算出的 α 和 β 这两个 vector 结合起来算出这个位置上的 label 分布。

可以看到这个过程和双向 RNN 的形式非常相似，都是前向后向各算一遍，再把每个位置前向后向的 vector 整合起来。但是，面临的问题是复杂度比较高。所以接下来要做的依然是降低复杂度。降低复杂度我们用了两个技巧。

3. FST变为iFST

首先，我们把 transducer 变成一个所谓的 independent transducer。可以看下面这个表，原先的四阶的 tensor，每个维度对应的是输入的单词、输出的标签，from state 和 to state。

现在我们做一个假设，当给定第二个 state，输出标签和输入单词及之一个 state 是条件独立的。这样就可以把原来的四阶 tensor 分解成两个 tensor ——一个是三阶的 tensor，一个是二阶的矩阵。我们设计了一套算法把任意 transducer 转化为 independent transducer。在这个算法的转换过程中，会增加一些新的 state。在实验中发现增加 state 的个数不超过原有 state 个数的50%。这样我们得到了一个 independent transducer，它的参数量会降低，但是依然有一个三阶的 tensor。我们需要进一步降低这个三阶 tensor 的复杂度。

4. 张量分解与预训练词向量

和前一个工作类似，我们通过 rank decomposition 把三阶的 tensor 分解成三个矩阵，从而把复杂度降到标准的循环神经 *** 的复杂度。

同样，我们引入外部的 word embedding，像 GloVe 或者 BERT。外部的 word embedding 会和我们所构造出来的 embedding 做加权平均，得到最终的更新公式。我们把更新公式所对应的这个 *** 模型叫做 FST-RNN。

Slot filling 任务上的实验表明，FST-RNN 同样具有 FA-RNN 的优点，即 zero-shot 时等价于原始的正则表达式，低资源场景表现远超神经 *** baseline，高资源时的表现与神经 *** baseline 不相上下。

总结

我们在两个任务上研究怎么把正则表达式变成神经 *** ，FA-RNN 在分类任务上，FST-RNN 在 slot filling 任务上。我们的 *** 兼具了符号系统和神经 *** 的优点，不需要训练，可以直接根据规则构造出来，适用于冷启动的场景；当有了数据之后，可以通过训练去提升效果。

今天的分享就到这里，谢谢大家。

阅读更多技术干货文章，请关注微信公众号“DataFunTalk”。

分享嘉宾：

关于我们：

DataFun：专注于大数据、人工智能技术应用的分享与交流。发起于2017年，在北京、上海、深圳、杭州等城市举办超过100+线下和100+线上沙龙、论坛及峰会，已邀超过2000位专家和学者参与分享。其公众号 DataFunTalk 累计生产原创文章700+，百万+阅读，14万+精准粉丝。

欢迎转载分享评论，转载请私信。