WeNet 热词增强 2.0 强势来袭
继《WeNet 更新：支持热词增强》两年后，WeNet 近期更新了热词增强 2.0。本次更新内容是使用 AC 自动机 (Aho-Corasick automaton) 对热词进行构图，解决热词之间存在的重叠问题[1]。
早在 2022 年 5 月份，@victor45664 就在 Github 上 Pull Request 了相关的代码实现[2]（非 OpenFST 版本）。
巧的是，当时 WeNet 也正在开发 OpenFST 版本的 AC 自动机热词增强。更巧的是，K2 近期也开源了相关的实现，感兴趣的同学可以参考《新一代 Kaldi 热词识别功能》[2]。
热词增强原理
我们来回顾一下语音识别解码和热词增强的原理：
我们可以简单地认为 WeNet 训练出来的声学模型是一个多分类器，例如对于常用的 5000 个汉字，每输入一帧音频，模型输出一个 5000 维的向量。解码就是要在多帧音频对应的多个 5000 维向量中，剪枝掉概率较小的文字序列，保留概率较大的文字序列。
热词增强则是在剪枝的过程中，不仅考虑声学模型输出的概率，也考虑匹配热词得到的奖励，最终提高包含热词的文字序列的概率。
热词增强 1.0
我们再来回顾一下 WeNet 热词增强 1.0 的原理：
假如我们有以下热词列表：
人民大会堂
中国人民大学
中国人民银行
代码解读构建热词图后，“中国人民银行”可以完全匹配热词，而“中国人民大会堂 ”却无法完全匹配热词。匹配的过程如下：
虽然也可以在每次跳转的时候，都把开始状态 0 作为热词的状态，但是在包含较多热词状态时，计算复杂度会大大提升。
热词增强 2.0
当热词数量增加后，热词和热词之间存在上述前缀重叠的情况非常常见，最终我们决定使用 AC 自动机完成热词的构图（构图过程有点像字符串匹配的 KMP 算法），改善热词前缀重叠的问题。
基于 AC 自动机的热词构图过程，主要包含以下两个步骤：
根据热词列表，构建热词前缀树
给热词前缀树添加回退弧，得到 AC 自动机
前缀树
前缀树 (Trie)：一个节点的所有子孙都有相同的前缀（充分必要条件）。
前缀树可以看作是做了确定化 (Deterministic) 的有限状态接收器 (FSA, Finite State Acceptor)，也叫 DFA。因此我们可以借助 OpenFST 工具来完成构图。
FSA
DFA
AC 自动机
在前缀树的基础上，添加一些失配的回退弧即可得到 AC 自动机，算法原理参考论文：Local Grammar Algorithms[4]。
“中国人民大会堂”在匹配“中国人民大学”失败后，回退到状态 6 继续匹配“人民大会堂”，回退的同时需要减去“中国”两个字共 6 分的奖励。
举例
假如我们热词列表中有两个热词 A 和 B，它们之间可能存在以下几类重叠关系：
无前缀重叠
A：中国人民大学
B：北京大学
无需特殊操作，即使热词增强 1.0 也能处理。
A 包含 B 的前缀
A：中国人民 大学
B：人民 大会堂
AC 自动机可以处理回退的问题。
A 的前缀是 B
A：中国人民 大学
B：中国人民
如果需要记录完整匹配了哪些热词，需要在构图时记录每个结束状态对应的热词；同时，在匹配的过程中需要记录到达过哪些结束状态。
A 的后缀是 B 的前缀
A：中国人民大学
B：大学 之路
“中国人民大学之路”应该包含两个热词。需要注意的是，状态 4 和状态 6 的回退分数在构图的时候是无法确定的，需要在实际解码的过程中统计（当前代码尚未处理这种情况，欢迎大家 PR）。
A 的后缀是 B
A：中国人民大学
B：人民大学
这种情况需要保留结束状态的回退弧。状态 10 可以回退到状态 8，因此到达状态 10 时，即可认为完全匹配了两个热词。
A 包含 B
A：中国人民 大学
B：人民
状态 6 可以回退到结束状态 4，因此到达状态 8 时，即可认为完全匹配了两个热词。需要注意的是，状态 7 的回退分数只包含“中国”和”大“三个字的分数。
优化：SortedMatcher
完成了构图后，我们可以使用 SortedMatcher 对每个状态上的出弧进行排序，使用二分搜索优化在热词匹配过程中的搜索时间。
WFST Beam Search & 热词增强
使用 WFST Beam Search 时，我们有两种方式实现热词增强：
作用在 TLG 的 ilabel：相当于先应用热词增强，再对热词增强的结果使用语言模型
作用在 TLG 的 olabel：相当于先应用语言模型，再对语言模型的输出使用热词增强
热词增强 1.0 作用在 TLG 的 olabel 上：
语言模型的输出是词，导致只能在词的级别上回退。由于在分词的时候，使用的是最长匹配策略，可能会产生下述热词图，令“中国人民大学校长”无法正常回退。
这次我们将热词增强作用在 ilabel 上，可以解决上述问题。但是带来的新问题是：增强出来的热词，有可能被语言模型剪枝掉。
实验指标
测试数据是在 LibriSpeech 和 AIShell1 中抽取的，将其中的专有名词，例如人名作为热词。分别统计含热词和不含热词的词错率。
WER：词错误率
U-WER：词错误率（标注不含热词）
B-WER：词错误率（标注含热词）
LibriSpeech
| librispeech | WER | U-WER | B-WER |
|---|---|---|---|
| 热词增强 1.0 | 8.14% | 5.63% | 30.19% |
| 热词增强 2.0 | 8.13% | 5.61% | 30.26% |
AIShell1
| aishell1 | U-WER | B-WER |
|---|---|---|
| 热词增强 1.0 | 5.42% | 12.86% |
| 热词增强 2.0 | 5.42% | 12.99% |
在不含热词的测试数据上，热词增强 1.0 和热词增强 2.0 指标几乎没有变化，因为热词没有匹配成功，不影响最终识别结果。
在含热词的测试数据上，热词增强 2.0 的指标略有下降，分析是因为热词增强后，语言模型又把正确的结果剪枝掉了。
感兴趣的同学可以找一些热词具有重叠关系的数据来测试一下，欢迎贡献和分享测试结果。
热词增强 3.0
基于 OpenFST 构图和人工设计分数的热词增强还是会存在不少局限，例如具体每个字应该奖励多少分，也是需要结合测试集去调的。现在有很多基于深度学习的热词增强算法，WeNet 也会持续探索，敬请期待。
特别鸣谢
特别感谢这些在热词增强 2.0 开发过程中助力过的同学，@吕航博士提供了 AC 自动机的算法支持，@黄凯勋提供了英文分词的部分代码和 librispeech 的测试指标。
Reference
[1] https://github.com/wenet-e2e/wenet/pull/1937
[2] https://github.com/wenet-e2e/wenet/pull/1163
[3] https://mp.weixin.qq.com/s/d7Ab9u1_OAGLF76V1ymHmg
[4] https://web.stanford.edu/group/cslipublications/cslipublications/koskenniemi-festschrift/9-mohri.pdf