在语音识别系统中，有限加权状态转换机（Weighted Finite State Transducers, WFST）扮演着重要角色。本文主要介绍发音词典、语言模型和WFST的原理，以及在实践过程中的一些优化方法。
目前的实际场景中的语音识别系统更多是基于HMM的传统语音识别框架，如：DNN-HMM，这种框架是由声学模型、发音词典、语言模型和解码器构成的pipeline结构，其中声学模型建模粒度为比音素还小的三音素状态，而语言模型和WFST在其中扮演着重要的角色。本文将主要围绕三个问题展开：（1）如何实现从HMM状态到句子的映射；（2）WFST如何优化解码效率；（3）在实际应用时，如何使用Lattice Rescore等方法适应不同的业务场景。首先，我们会回顾一下语音识别的背景知识，介绍传统语音识别的架构和基本概念，以及发音词典和语言模型的原理。进而，介绍WFST的定义和基本操作，以及WFST在语音识别中发挥的作用。最后，我们将以实际场景为例，从解码图的角度介绍一些语音识别的优化方法。语音识别（Automatic Speech Recognition, ASR）的目标是将人类的语音内容转换为相应的文字。系统的输入通常是一段完整的长录音（或语音流），录音需要先经过语音端点检测（Voice Activity Detection, VAD）将人声的片段截取出来，语音识别会将语音中的内容转写为文字，其中会包含大量口语、重复、语法错误等情况，且语音识别不会为句子添加标点。这时，系统需要一个后处理模块，使用顺滑技术将明显的口语问题“整理”为通顺的句子，并为句子加上标点。同时，说话人分离、说话人识别、语音情绪识别等模块，会为每段语音打上说话人、性别、情绪等标签，与转写的文字一同作为下游NLP模块的输入，进而转化为意图、情感、槽位等可用信息。语音识别系统通常分为基于HMM的传统系统和端到端系统。传统系统分为声学模型、发音词典、语言模型和解码器，其结构从最开始的GMM-HMM，过渡到DNN/GMM-HMM混合系统。端到端系统的输入为声学特征序列，输出对应的单词/字序列，以CTC和Seq2Seq两种结构为主。语言模型在两种系统中都起着很大的作用，而WFST则主要应用于传统的系统。本文内容将基于HMM的传统语音识别展开介绍。语音识别问题通常可以用以下公式描述，其中W为单词序列，X为声学特征序列，如公式所示，语音识别的目的是在当前的声学特征序列下，找出让该条件概率最大的单词序列。根据贝叶斯定理，可以将公式变形，变形后的公式中包含两个部分，即给定W下X的条件概率和W的概率。对于p(X|W)我们使用声学模型（Acoustic Model, AM）建模，对于P(W)则由语言模型（Language Model, LM）来建模，这也是传统语音识别的建模基础。语音识别的过程如下图所示。首先，声音信号经过分帧加窗后，计算每帧的声学特征，如：MFCC、Fbank或PLP，该序列即前面提到的X。X作为HMM的观测序列，使用声学模型去拟合发射概率，即p(X|S)，这里S为HMM的状态，当使用GMM建模时，每个状态会对应一个模型，当使用DNN建模时，状态数即DNN的输出层维度。现实生活中，一个音节通常会持续一段时间，所以帧与HMM状态之间会呈现多对一的关系，因此声学模型的另一个作用是实现帧与状态的对齐（alignment）。此时，在HMM中已知了观测序列和模型参数，则语音识别的过程即是给定声学特征序列的条件下在HMM状态上解码的过程。此外，我们的识别目标是单词序列（句子的分词结果），每个单词由提前构造好的发音词典（lexicon）转为对应的音素序列（中文的音素通常指拼音中的声母和韵母），即将单词序列转为音素序列。人们在说话时，某音素的发音是会受到前后音素影响的，这种现象为协同发音，为了解决这一现象，将当前音素与其前后的音素拼起来组成新的音素，称为三音素（triphone）。在传统的语音识别系统中，通常使用三个状态去表示一个三音素，分别表示一个音素的发音初始态、稳定态和结束态，因此，一个音素又可以表示为三个状态。但这里会有个问题，中文有200多个音素，按照现在的方法，最后的状态类别数为200*200*200*3 = 24000，也就是说我们需要使用24000个GMM或者输出层维度为24000的DNN去建模，正常的训练数据很难支持如此大的模型，很容易过拟合。而在现实中不是所有的三音素都会出现，且某些三音素的发音会有近似的情况，因此在传统语音识别系统中，会将所有的三音素放在一起进行聚类，发音相似的三音素会使用同一个模型，这个方法称为状态绑定（State Tying），这里的聚类通常使用决策树来实现。至此，我们知道使用声学模型可以拟合HMM状态到声学特征序列的发射概率，也知道了状态与单词之间层层对应的关系，接下来我们需要一个模型，使其输入一个状态序列，即可高效的输出对应的单词序列，并给出相应的打分以供解码其使用，这就是WFST解决的问题。在介绍WFST之前，先来熟悉一下语言模型与发音词典的概念。
1、语言模型
语言模型表示一个句子出现的概率，对于下图中的四句话来说，第四句“火腿吃猫喜欢”明显是一句不通顺的句子，因此，我们希望语言模型可以给前三句话较高的分数，给最后一句话很低的分数。语言模型的公式化表达为P(W)，因为句子是千变万化的，所以将句子分词后再建模。分词后，一句话出现的概率就表示为其中每个单词在当前上下文中出现的概率之积。使用马尔科夫假设，每个单词的概率只与前N个单词有关，基于这样思想构造的语言模型为ngram。举例来说，假设训练集就是前面给出前三句话，那么“猫 喜欢 吃 火腿”出现的概率计算过程如下图所示，其中<s>表示句子开始符号，</s>表示句子结尾符号。
2、语言模型的平滑
还是上节的例子，试着计算 “老鼠 喜欢 吃 火腿”的概率，因为“老鼠”从来没有作为句子的开始，且“老鼠”后面从来没有出现过“喜欢”，所以P(老鼠|<s>)和P(喜欢|老鼠)都是0，这会导致整个句子的得分为0，但是这明显是一句通顺的句子，只是因为这样的组合在语料中没有出现过就让整句的概率为0是不合理的，为了解决这一问题，提出了平滑算法（Smoothing）[1][6]。平滑算法主要有两种思想，插值法（Interpolation）和回退法（Backoff），以上面的句子为例，插值法是将高阶的单词（老鼠 喜欢）与对应低阶的单词（喜欢）进行插值，而回退法，是在高阶词存在时，使用高阶词的概率，高阶不存在时，使用对应低阶的概率乘以回退概率。常用的平滑算法为Kneser Ney Smoothing [1]，这个方法既有插值版本，也有回退版本，在计算高阶的原始概率时，会加一个打折因子（discount）以保证所有单词的概率和为1，而其打折因子和回退概率由当前词的上下文统计得出，以下为对应的计算公式。
3、困惑度
语言模型的评价方法为困惑度（perplexity, ppl），表示为每个单词概率倒数的几何平均数，经过取log变换后，与交叉熵的形式相同，其大小表示当前句子的“通顺”程度，通常相对值更加有意义。
4、语言模型工具
在使用kaldi[10]语音识别框架时，需要把语言模型表示为ARPA格式，如下图所示，主要分为头部以及各阶ngram的单词和分数，包含三列，分别为当前单词出现概率的log10、单词和回退概率的log10。进而，使用kaldi中的arpa2fst工具将语言模型转化为WFST图的形式。基于ngram的语言模型工具通常为SRILM[11]、IRSTLM[12]，除此之外，还可以使用深度学习语言模型建模，常见的有rnnlm[2]工具，可以通过重打分等方式应用于语音识别系统。注意，此处的语言模型本质与NLP中的概念相同，但在NLP中更关注语言模型的输出语义向量，而在语音识别中则更加关注单词之间的转移概率。
5、发音词典
发音词典则给出了每个单词对应的音素序列，如下图所示。目前，常用的开源中文词典有thchs30和CC-CEDICT，英文词典有CMU-dict。词典中的单词决定了这个词在解码时出现的概率，所以通常需要根据业务需求挖掘词典，并生成音素序列，这个功能称为g2p (Grapheme-to-Phoneme)，目前有Sequitur G2P、g2p-seq2seq等工具可以用来训练发音词典生成模型。语言模型与发音词典通过WFST组合在一起后，才可以用于语音识别的，下面将介绍WFST的定义和基本操作。
1、WFST的定义
有限加权状态转换机（Weighted Finite State Transducers, WFST）是有限自动机（Finite Automaton, FA）家族中的一员，FA由（A, Q, E, I, F）五个元素组成，其中Q为状态集合，表示图中的节点，A为Label集合，表示边上的符号， E为转移函数集合，两个状态节点和他们之间的边以及边上的label和weight构成了一次转移（transition），I为初始状态，在图中使用较粗的圆圈表示，为搜索的起点，F为终止状态，在图中使用双环形圆圈表示，为搜索的终点。FA家族有四个成员，如上如所示。有限状态接收机（Finite-State Acceptor, FSA）边上的label只有输入，或者说输入与输出相同，有限状态转录机（Finite-State Transducer, FST）边上既有输入又有输出，加权有限状态接收机（Weighted Finite-State Acceptor, WFSA）在FSA的基础上多了边上的权重，加权有限状态转录机（Weighted Finite-State Transducer, WFST）在FST的基础上多了边上的权重，如a:z/1.2表示在0状态时，输入为a则输出为z，且可以得到1.2的权重。在语音识别中经常使用WFST结构[3][4][5]，前面介绍的语言模型和发音词典都可以表示为WFST的形式，下图中，（a）为语言模型的WFST表示，其每条边上的输入为word，输出也是word，权重为在当前路径中出现某单词的概率（即ngram概率），可见其本质是一个WFSA。（b）为发音词典的WFST表示，其每条边上的输入为phone，输出为word，权重为当前单词的发音概率，因为一个word会对应一个phone序列，所以通常将word作为第一个phone的输出。至此，我们已经知道了语言模型和发音词典的WFST表示，回到最初的问题上，我们希望用WFST建立从HMM状态到单词的映射，并且尽可能的优化解码搜索效率，这就取决于WFST的特点与操作。
2、半环
WFST中的操作是基于半环（Semiring）理论构建的[4]，半环是抽象代数的概念，简单来说就是对集合、加法和乘法等概念的抽象。如下图所示，列举了四种常见的半环，其中SET表示定义域，加法可以理解为并联操作，乘法可以理解为串联操作，单位0表示加单元，单位1表示乘单元。这里主要介绍两种半环结构，左图所示为Probability Semiring，其节点为状态，边上的权重为概率值，则从状态0到状态3的得分可以理解为，
和
两条路径的概率之和，即p1*p2+p3*p4。右图所示为Tropical Semiring，其节点为状态，边上的权重为概率的-log值，在Tropical Semiring中，我们关注的是最佳路径问题，即最短路径搜索，则从状态0到状态3的得分表示为
和
中的加权最短路径。WFST在语音识别中主要是扮演解码图的角色，所以在ASR中经常使用Tropical Semiring。
WFST的操作是基于当前Semiring中加和乘的定义的，这些操作可以被分为两类，组合（Composition）与优化（Optimization），优化操作中又可以分为Determinization、Weight Pushing、Epsilon Removal、Minimization。其中组合操作实现了不同level的WFST的组合，而优化主要是为了优化解码效率的。接下来主要介绍组合（Composition）与确定化（Determinization）。
3、组合（Composition）
组合操作通过连接两个图的输入与输出，将两个不同level的WFST组合为一个WFST，通常使用空心圆圈表示组合的符号，如下面公式中所示，表示T1和T2两个图的组合。首先，分别列出图a和图b的所有transition，如：图a的初始状态表示0A，图b的初始状态表示为0B。组合操作的精髓在于将图a中的输出与图b中输入相同的transition进行组合，如图a的transition a:b/0.1 就可以和图b中的b:b/0.1进行组合。从图a的初始状态和图b的初始状态（0A,0B）开始迭代，如下图所示，图中QueueT表示当前处理的状态组合，QueueT+1表示下一次将要处理的状态组合。先将0A和0B状态“出来”的所有边列出来，因为0A的transition输出为b，为0B的transition输入为b，因此可以将两个transition组合，组合后的transition的输入为图a中的输入，输出为图b中的输出，weight则为两个transition的weight之积（这里weight表示概率），下一跳节点表示为（1A,1B），这样就得到了一个组合后的新transition，下一次迭代将从（1A,1B）开始。当再次迭代到（1A,1B）时，因为已经处理过该节点，所以后续不再放入QueueT+1中。迭代一直到所有transition处理完成，将得到的组合后的transition表示为图的形式，即可得到下图所示的组合后的WFST，这个WFST的输入为原来图a的输入，输出为图b的输出。
4、 确定化（Determinization）
如果一个图是确定化的，给定一个输入序列，在图中只能找到一条路径与其对应。如下图所示，左图为未确定化的图，右图为确定化后的图，当输入序列为“ab”时，左图的路径有两个，而右图的路径只有一个。下面用一个例子来说明确定化的作用，下图为一句经过语音识别的话，我们在Lattice（一种特殊的WFST）中用beam search得到top5的音素序列。在未确定化的图中得到的top5音素序列是相同的，而在确定化的图中搜索可以得到5个不同的序列，这说明如果想在未确定化得到和确定化上相同的效果，必须要增加beam的值，因此，确定化提高了解码搜索效率。对于前面两张图来说，确定化的过程如下。首先，找到有相同输入的path（0à1和0à2），因为两者权重不同，将其中一个path的权重表示为另一个path的权重加上一个“差值”（a/1+1），将两条路径合并，同时在目标节点的括号中将“差值”表示出来，即（1,0）,（2,1）表示原始节点1差值为0，原始节点2差值为1，即完成了一个transition的确定化。
1、HCLG解码图
回到文章最初提出的问题，我们希望用WFST建立从HMM状态到单词的映射，并且尽可能的优化解码搜索效率。根据组合操作的定义，图a的输出与图b的输入相同时，即可进行组合。在传统语音识别的流程中，使用H表示HMM拓扑结构，输入为HMM状态（state），输出为三音素（triphone），权重为HMM的转移概率；使用C表示三音素到单音素的映射，输入为三音素，输出为单音素（上下文无关音素，CI phone）；L表示发音词典，输入为音素，输出为单词，权重为发音概率；G表示语言模型，输入为单词，输出为单词，权重为语言模型打分。根据WFST的组合操作，可以将上面四张图进行组合，组合后的图称为HCLG，其输入为HMM状态序列，输出为单词序列，则HCLG就是我们希望的模型，通常被称为解码图。现实中，优化与组合交替进行，如下公式所示[4]。其中，空心圆圈表示组合，det表示确定化，min表示最小化，rds表示去掉消歧符号（为了让L可以确定化，对有相同音素前缀的单词后面添加消歧符号）。前面说语音识别的过程相当于HMM的解码过程，发射概率由声学模型表示，而解码状态从原来在HMM状态空间上搜索，改为在解码图上搜索，则解码可以直接得到单词序列，经过了优化变换的解码图也实现了优化搜索性能的效果。
2、Lattice
为了保证解码效率，对解码图的剪枝是一个必要的步骤，常见的就直接使用beam search。另外，在传统语音识别系统中，声学模型的训练通常会占较多资源，因此声学模型不会频繁的更新，这就造成语音识别系统较难快速的针对特定场景优化。考虑这两个问题就有了Lattice的概念。在解码时，采用一些剪枝方法，使得最后获得N-best的路径，由这N-best的路径重新进行确定化等操作后得到的WFST就是Lattice，因此与HCLG一样，Lattice的输入为HMM状态，输出为单词序列。但在kaldi中，对Lattice的生成和存储做了优化[8]，使其输入输出都是单词序列，并将HMM状态等信息存在transition中，因此，也通常称Lattice为词图或词格。这样语音识别的解码过程就分为两步（two-pass），第一遍解码得到Lattice，第二遍解码在Lattice中进行最短路径搜索得到1-best的解码结果。使用Lattice的好处，一方面，在原来的模型上得到Lattice后，可以在新的语言模型和词典上进行重新打分（Rescore），在重打分时可以使用更大的语言模型，或者与业务相关性更强的模型，这保证了在声学模型不变的情况下，优化解码效果。另一方面，在DNN/GMM-HMM混合模型中，经常会用到区分性训练，通常我们训练目标是让1-best句子与标注的句子尽可能接近，但区分性训练在这个基础上，还希望与1-best相似的其他句子与标注句子尽可能的远，为了减轻计算复杂度，区分性训练通常会在Lattice上进行。在实际场景中，Lattice的使用要更加广泛。例如：Seq2Seq模型decoder的输出，序列标注任务中CRF的输出等都可以视为在Lattice上的解码过程，其重打分、融合等思想在这些场景中也同样适用。至此，我们清楚了传统语音识别系统是在基于WFST构造的解码图上进行解码的，由独立构造的语言模型、发音词典等完成了构图，并通过WFST的一系列操作优化搜索空间。接下来，我们重点讨论在实际场景中如何在声学模型不动的情况下优化识别效果。语音识别系统在落地时往往同时应用在多个场景和领域，说话人也遍布全国各地，其对话内容、说话环境、口音等都会有很大的差别。在新场景接入时，往往要快速的优化其识别效果，这可以从语言模型、发音词典和解码图的角度实现。
1、语言模型的适应
通常在数据充足的条件下，训练数据分布与真实数据越接近，识别效果越好。而如果针对每个场景都做一套语音识别系统可能会因为数据较少导致过拟合问题。对于传统语音识别系统，可以让声学模型在所有场景数据上训练，再使用不同场景数据训练的语言模型对应的解码。下表均使用了同样的声学模型，且该声学模型没有使用业务相关数据训练，我们使用不同的语言模型，在三个不同的业务上验证识别效果（字错率，cer）。可以发现在声学模型不变的情况下，语言模型的训练数据与原始场景越接近，在对应场景下的识别效果就越好。此外，我们计算了语言模型在三个测试数据文本上的ppl，可以发现，在声学模型不变的情况下，测试文本上的ppl的表现与对应的cer基本呈正相关，因此，在优化语言模型时，可以优先在测试集文本上计算ppl，与原始的ppl对比，如果有提升则表示新模型在测试集上表现会好一些。此外，训练声学模型时的发音词典和解码词典是独立的，解码图的输出序列由词典和语言模型共同决定，与语言模型的适应同理，解码词典也可以根据场景重新设计，如：裁剪或新词挖掘。这里的一个小技巧是，使用分字语言模型和词典分字语言模型与原始模型融合会在一定程度上丰富输出内容，避免无法输出集外词，从而提高识别效果。
2、Lattice Rescore
根据前面的介绍可知，更新了语言模型通常要更新整个解码图，然后在新解码图上解码。这样的操作是比较复杂的，重新解码的效率也比较低。一种替代的方法是，只在Lattice上面更新语言模型的打分，然后重新在Lattice找出1-best路径即可大大减小重新识别的复杂度。Lattice Rescore[9]可以用两种思路，一是重新构图，即使用新语言模型的G.fst与Lattice重新构图，这种方法效率比较低，而且识别效果并没有提升。使用较多的方式是“先减后加”，我们先看kaldi中Lattice的存储格式。如下图所示，为使用Lattice计算TopN后的一部分，其中包含四列（最后三列是本质是一列由逗号分开的），其中，前两列的序号表示状态，第三列表示边上的单词，最后一列有三个部分，分别是graph cost、acoustic cost和transition-id序列。Acoustic cost为声学得分，graph cost为图固得分。graph cost包含三部分，lm cost为语言模型得分，pronunciation cost为发音概率的分数，transition cost为HMM转移概率分数。“先减后加”的rescore方法，首先加载原来的语言模型，将lm cost从对应的graph cost中减掉，然后再加上新的语言模型的lm cost即可得到更新后的Lattice，注意每次更新后通常需要重新确定化。我们对比了Lattice Rescore（因为主要是对语言模型重打分，所以也可以叫lmrescore）和使用新语言模型重新构图解码的结果（直接解码），可以发现，rescore的方法相比直接解码会有1个点左右的误差，这个误差可能来自于第一遍解码过程。因此，最好的方式还是更新HCLG解码图，但在线上环境不方便时，或者为了离线实验节省时间时，可以使用rescore的方法。此外，在线识别的过程中也可以加载热词词典，在解码时实时判断当前beam中的单词是否在词典中，及时将不符合要求的路径剪掉，也可以快速的优化线上识别效果，不过这会大大降低解码器的通用性，词典选择不当可能会带来一些识别问题。
3、语言模型的融合
与平滑的原理相似，多个语言模型之间是可以融合的[7]，融合方式就是简单的插值，即给某个模型一个scale（0<=scale<=1），与另外一个模型中对应单词的分数乘以1-scale相加。通常可以使用一个业务相关小模型和一个预训练的大模型融合，即保证了业务相关性，又可以尽量避免OOV的情况。本文主要从原理的角度介绍了WFST和语言模型在传统语音识别系统中的作用，并结合场景实例介绍了一些优化方法。在实际应用中，随着场景的增加和解码服务的不断成熟，声学模型会趋向于适应更加通用的场景，此时解码图的优化会越来越重要。通常在新增业务场景或者修复badcase时，优化语言模型和词典是比较有效的方法，这也是pipeline结果相比端到端的优势之一。后续将会从典型badcase出发探索传统语音识别系统中解码图相关的优化方法。[1] Goodman, S. F. C. a. J. (1999). 'An empirical study of smoothing techniques for language modeling.'[2] Toma ́sˇ Mikolov1, Martin Karafia ́t (2010). 'Recurrent neural network based language model.'[3] Mehryar Mohri1, F. P. a. M. R. (2002). 'Weighted Finite-State Transducers in Speech Recognition.'[4] Mohri1, M. (2008). 'SPEECH RECOGNITION WITH WEIGHTED FINITE-STATE TRANSDUCERS.'[5] Dixon, P. R. O., Tasuku; Iwano, Koji; Furui, Sadaoki (2009). 'Recent Development of WFST-Based Speech Recognition Decoder.'[6] Goodman, J. T. (2001). 'A Bit of Progress in Language Modeling Extended Version.'[7] X. Liu1, M. J. F. G., J.L. Hieronymus2, P.C. Woodland1 (2010). 'LANGUAGE MODEL COMBINATION AND ADAPTATION USING WEIGHTED FINITE STATE TRANSDUCERS.'[8] Povey, D. (2012). 'GENERATING EXACT LATTICES IN THE WFST FRAMEWORK.'[9] H.Abdulla, A. A. A. a. W. (2013). 'Speech Decoding Using Lattice Rescoring.'[10] Daniel Povey1, A. G. (2011). 'The Kaldi Speech Recognition Toolkit.'[11] Abrash, A. S. J. Z. W. W. V. (2011). 'SRILM at Sixteen: Update and Outlook.'[12] Marcello Federico, N. B., Mauro Cettolo (2016). 'IRSTLM: an Open Source Toolkit for Handling Large Scale Language Models.'周维，58同城AI Lab算法资深开发工程师，2018年5月加入58，先后从事智能客服、语音机器人、写稿机器人和语音识别项目的算法工作，目前主要从事语音识别算法开发。
