背景

现在深度学习势头很猛，大模型在大规模数据下训练后，在线任务中已经越来越常见。效果好归好，但使用起来确实有些麻烦。大模型通常得靠大量语料和文本训练，迭代周期动不动就很长。尤其那些特定场景下的词语，在训练语料中间出现次数少，模型常常拟合不好。这篇文章要聊的，正是针对关键词这类特定场景语料，在序列到序列任务中，通过构建状态转移自动机来改善最终效果的方案。

生成模型即生成模型解码

序列到序列模型，像机器翻译、语音识别这类任务，2014年就有了它的架构 [1]。核心组件就两个：编码器和解码器。这里不展开训练过程，只关注它使用时的解码环节。

看这张图就明白了，每个时刻的生成结果，不仅和输入时刻序列有关，还和输出序列绑在一起。一个最直接的想法是，把每个时刻置信度最高的结果存下来，作为下一个时刻的输入。但这么干容易出问题：每个时刻缺乏全局视野，某个时刻的最优，不一定是全局最优。如果所有结果都存，数据量又是指数增长。所以，beam search这种方法就被提出来了。我们来用一个具体例子说明beam search的过程。

假设我们有这么一串拼音：

你可能会问：这串拼音到底什么意思？

下图展示了一个简单概率模型生成的文本。第零时刻有5个候选（编号④省略了）。到了第一时刻，每个候选又延伸出3个，总共15个候选。然后，用语言模型概率挑出top5保留，剩下的就丢掉。这样，搜索空间就从指数级增长变成了平方级增长——每个时刻只保留top N，不保留全部结果。

传统解码应用问题与改进

这种方法和全状态保存比，牺牲了准确度换时间，局限性不小。正常情况下，每个时刻的top N能覆盖90%以上的情况，但在关键词检测、风控词语检测这类任务里，会冒出两个问题：

1. 待检测关键字在日常语料里出现少，传统beam search很容易漏召回。

2. 时效性要求高，经常有新词要实时插入，立刻生效。

第一个问题，一个最直观的思路是用标注数据、弱标注数据重新训练模型。但显然，迭代周期长，预期还不稳定。

Google在2018年的一篇论文里 [2] 提出了一种方案，不重新训练模型，只在解码时通过追加模型重新打分，来改善对小众语料的拟合。

以上图的识别系统设计为例，除了传统声学识别模块，还加了个上下文模块。这个模块功能不少，包括标点、语言模型打分、文本归一。语言模型的使用方式是这样的：用beam Search对中间结果追加打分，更新top N，再把当前结果传给下一时刻解码。这种设计的好处是，不用更新语音识别模型，就能通过添加不同语境的语言模型影响beam search中的top N选取，从而改善结果。缺点呢？计算量明显上去。虽然语言模型计算量通常不高，但beam search过程中每个候选结果都要多次经过它，次数一多，耗时上升很明显。

为了提高计算效率，经典的wfst解码方案 [3] 被重新用在seq2seq模型里 [4]。这种方案注意到，重打分过程是在序列中进行，没必要在每个时刻都从头开始计算所有文本。具体做法是，把语言模型生成新的概率转移自动机 [5]，解码时，只维护beam search中当前top N的状态。看下 cat（音标：kæt）这个单词的状态转移图。当声学识别模块产出c对应的k音，系统就转移到状态1。接着，当a对应的æ出现时，不需要再从状态0计算k和æ一起的概率，而是直接看当前状态1的后继状态里有没有æ。没有的话，就计算回退到初始状态的概率。这样一来，在序列生成中，你只需要记录当前位置的状态，新识别结果出来时，对当前状态算可行的转移就行。和普通语言模型比，相当于省去了从状态0到当前状态的重复计算，复杂度大大降低。

这种浅融合方案很好地解决了训练语料不均衡的问题，缺点是不能实时改图，也缺对特定词的加权。所以，我们引入了前缀自动机来改进这个过程。

基于前缀自动机的解码加权方案

前缀自动机是个经典算法，常用于多模式串匹配。如果有一个字典，想检测输入文本是否命中字典中的词，这就是个多模式串匹配任务。一个明显的方案是遍历整个字典，但这复杂度过高。

那就开始优化。一种方式是优化字典结构：字典中字符有公共部分的词，比如 teach 和 teacher 都在字典里，那如果 teach 不匹配，teacher 也不需要再匹配了。这样就把顺序字典变成了前缀树的存储方式。

接下来，继续优化。如果一个词的前缀是另一个词的子串，比如上图的 she 和 her，检测字符串 sher 时，里面包含前缀树中多个词。当 she 在状态4匹配成功后，我们知道 he 也是待匹配串的一部分，所以不需要跳回状态1，直接跳到状态9，从 r 开始匹配就行。这就是前缀自动机的核心思想。

这种跳转关系的构建方法是个递归过程。一句话概括：一层一层来，如果父节点的跳转状态的子节点里有和我相同的，那就是我的跳转状态；否则，我的跳转状态就是根节点。按照这个思路，我们把上图的点按遍历顺序重新标号，方便理解。

有了这个前缀转移关系，就能高效处理热词构建和查询。一个带前缀自动机的解码流程如下：

对于每个beam search过程，我们不仅要维护结果，还要维护它在前缀自动机中的状态。这个状态维护起来很方便，只需要存一个状态指针。从性能看，执行时的额外计算量和内存使用量，都可以认为是常数级别。

前缀自动机实时增加新词方案

前面介绍了用前缀自动机的解码方案，但这还不能很好地解决“实时”这个要求。如果想实时向解码过程中添加热词，该怎么改进？

回顾上一节，前缀自动机构建分两步：前缀树的构建和状态转移的构建。前缀树保证算法正确，状态转移则大幅优化时间。同时，状态转移需要层次遍历整棵树，这意味着转移状态的构建不能随前缀树形态变化而自动更新，必须全量重新构建。

当插入一个新词时，由于前缀树的特性，可以用字符长度的时间复杂度完成插入。但构建新的转移状态得遍历所有节点。如果每次插入新词都要重新访问整棵树的全部节点，这种复杂度是难以接受的。相比之下，损失一些转移状态，相当于让部分词的查询复杂度变大，但和遍历全部词典的复杂度比，这种损失是可以接受的。

根据这个想法，我们把整体查询分成两棵树：一棵是带转移状态的前缀自动机，另一棵是普通字典树。新词插入时，先在普通字典树里操作。当普通字典树规模超过一个设定阈值后，再把它和前缀自动机合并，在合并后的树上构建转移状态。一次查询的复杂度，从词长变成小字典树的规模，但能省下构建转移状态时遍历全文的时间。

方案效果

这种解码方案在语音识别系统中进行了实际应用。从效果来看，评估主要从两个维度展开：一方面是针对标注了关键词语音的数据集，看关键词的准召情况。下表中，beam search代表普通方案，ac automation代表前缀自动机加权解码方案。结果显示，在识别结果中，关键词召回相对提升了4.6%。另一方面，在普通语音识别数据集上对比字错误率（CER）。由于对特殊词加了权重，整体准确率有一定下降，但影响在可接受范围内，远低于关键词召回带来的收益。

总结

本文主要围绕seq2seq类模型，通过追加状态转移自动机，来提升模型在专有领域语料上的识别准确率，同时让语料能实时生效，并对这个实时性流程的构建方法做了介绍。对于语音转录文本中的关键词检测，常见问题是语言模型不能实时调整，导致新词很难被识别出来。通过这套方案，可以实现秒级别的新词添加，显著缓解这个困扰。参考文献部分保留了原始引用，但需要注意，不包含任何第三方推广内容。

参考文献

[1] Sutskever, Ilya, Oriol Vinyals, and Quoc V. Le. "Sequence to sequence learning with neural networks." Advances in neural information processing systems 27 (2014).

[2] Zhao, Ding, et al. "Shallow-Fusion End-to-End Contextual Biasing." Interspeech. 2019.

[3] Hori T, Hori C, Minami Y, et al. Efficient WFST-based one-pass decoding with on-the-fly hypothesis rescoring in extremely large vocabulary continuous speech recognition[J]. IEEE Transactions on audio, speech, and language processing, 2007, 15(4): 1352-1365.

[4] Williams I, Kannan A, Aleksic P S, et al. Contextual Speech Recognition in End-to-end Neural Network Systems Using Beam Search[C]//Interspeech. 2018: 2227-2231.

[5] Hori T, Nakamura A. Speech recognition algorithms using weighted finite-state transducers[J]. Synthesis Lectures on Speech and Audio Processing, 2013, 9(1): 1-162.