加权有限状态机

概述

基于加权有限状态机（Weighted Finite-State Transducers，WFST）生成的解码图，配合声学模型进行维特比解码是语音识别中基础的解码方法。

有限状态机（Finite-State Transducers，FST）和WFST的区别在于后者转移路径上带有权重，加权有限状态接收器（Weighted Finite-State Acceptor，WFSA）和WFST的区别在于前者的状态转移上只有一个标签，可以看作是string->double的字典，而后者既有输入标签又有输出标签。

WFST存在一个有限的状态集合以及状态间的跳转，如果存在一条从初始状态到终止状态的路径，使得路径上的标签序列正好等于输入序列，则输出一个新的序列和对应的权值。如下图所示，输入“ac”，匹配到0-1，1-2这条路径，则输出“qs”，对应的权值为\(1+0.63=1.63\)。

OpenFST是WFST及其相关算法的开源实现。

复合（Composition）操作

复合操作用来把两个不同层级的WFST“复合”成一个WFST。比如发音词典会告诉一个单词对应的因子（比如音素等），因此可以构造一个WFSTL来把因子的序列转换成单词的序列以及对应的概率，如上图b。此外有一个文法（或者统计语言模型）告诉单词序列概率，因此也可以构造一个WFSTG来表示该文法或者统计语言模型，如上图a，不过WFSTG的特点是：输入和输出是一样的，因此实际只需要其权值。这样通过复合操作\(L\circ G\)来得到一个新的WFST，该WFST的输入是一个因子的序列，输出是单词序列及其对应概率。

如上图所示，WFSTC由WFSTA和WFSTB复合而来，C可以看作是A、B的级联。

确定化（Determinization）操作

如果WFST有空转移的边，或者从一个状态遇到一个字母会有两条及其以上的边，那么它就是非确定的。非确定的WFST/WFSA/FSA相比于确定的WFST/WFSA/FSA会更加难于判定某个字符串是否可以接受。确定化算法就是把一个非确定的WFST转换成等价且确定的WFST的算法。两个WFST等价的定义是：如果第一个WFST接受输入x并且可以把它映射成y且权重是w，那么第二个WFST也一定接受输入x并且能把它映射成y，权重也是w；反之亦然。

如上图所示，图a是非确定的WFSA，图b是与之等价且确定的WFSA。

最小化（Minimization）操作

WFST可以通过最小化操作来进一步压缩空间和提高识别速度。

如上图所示，图c为图a经过最小化之后的WFSA。

TLG解码图

近年来，端到端声学模型常常与TLG解码图搭配使用，而Kaldi中的解码图由HCLG构成。

	输入	输出
T(token)	帧级别的CTC标签序列（声学建模单元）	lexicon建模单元
L(lexicon)	lexicon建模单元（文本建模单元）	词
G(grammer)	词	词