上篇简单介绍了FSA、FST、WFSA、WFST、半环的概念和区别,本篇将介绍WFST的基本操作和转移器的合并。
文章目录
自动机理论中包含3个基本操作:Kleene闭包、并联、串联,对于给定的两个WFST为 \(T_{A}\) 见图1(a), \(T_{B}\) 见图(b),有:
Kleene闭包:重复自动机内部的符号序列集合0次或多次,以改变整个自动机的结构,则 \(T_{A}\) 的Kleene闭包可表示为 \(T_{A}^{*}\) ,见图1(c);
并联:将自动机并联,使之具有相同的起始状态,不同的终止状态,可表示为 \(T_{A} + T_{B}\) ,见图1(d);
串联:将自动机串联,可表示为 \(T_{A} \times T_{B} \) ,见图1(e)。
图1. 自动机的基本操作
对于转移器有3个重要的操作:投影、翻转、合并,如图1(a),图1(b)分别为 \(T_{A}\) 和 \(T_{B}\) 的表示形式。
投影:通过省略转移器的输入或者输出标签达到从转移器到接收器的转变的操作,见图2(a);
翻转:在每次状态转移时都将输入标签和输出标签对调的反转操作,见图2(b);
合并:将两个原始转移器级联组合为一个转移器表示,合并算法比较复杂,见下面。
图2. 投影、翻转
合并操作的算法比较复杂,这里单独拿出来解释,如图3(a)和图3(b)的转移器,假设(a)中的转移器是将一个小写字母序列从小写转为大写,而(b)中的转移器是将一个的大写字母转为一个包含这些字母的单词序列。这两个转移器的组合结果见图3(c),将一个字母序列转为单词序列。事实上,从头开始构建这样结果的转移器是很困难的,因为我们需要考虑每个单词进来时的大小写问题,然而,复杂的转移器常常可以被分解为更多简单的转移器进行级联。
图3. 合并算法
这里给出算法1,这是一种合并两个WFST的 \(\varepsilon-free\) 合并算法,以使得第一个转移器没有任何的 \(\varepsilon \) 输出,第二个转移器没有任何的 \(\varepsilon \) 输入。
注: \(\varepsilon\) 代表空字符串。
对于转移器 \(T_{1}=(\Sigma _{1},\Delta _{1},Q_{1},I_{1},F_{1},E_{1},\lambda _{1},\rho _{1})\) 和 \(T_{2}=(\Sigma _{2},\Delta _{2},Q_{2},I_{2},F_{2},E_{2},\lambda _{1},\rho _{1})\) 合并为 \(T=(\Sigma _{1},\Delta _{2},Q,I,F,E,\lambda,\rho)\) , \(T\) 中的每个状态都是由 \(T_{1}\) 和 \(T_{2}\) 中的状态组合而成。因此,一个复合状态原始的状态对 \((q_{1},q_{2})\) 定义,其中 \(q_{1}\in Q_{1}\) , \(q_{2}\in Q_{2}\) 。每一次从复合状态 \((q_{1},q_{2})\) 进行转移时,也可以从 \(e_{1}\) 和 \(e_{2}\) 得到,使得 \(e_{1}\in E[q_{1}]\) , \(e_{2}\in E[q_{2}]\) ,且 \(o[e_{1}]=i[e_{2}]\neq \varepsilon\) ,这样在一次转移中得到的结果为输入 \(i[e_{1}]\) ,输出 \(o[e_{2}]\) ,且权重为 \(w[e_{1}]\otimes w[e_{2}]\) 。用这种方法, \(T\) 就变成了一个可以从 \(T_{1}\) 和 \(T_{2}\) 级联得到的可直接运行的转移器,且计算复杂度为 \(O(|T_{1}||T_{2}|)\) ,其中 \(|T_{i}|=|Q_{i}|+|E_{i}|\) , \(i\in [1,2]\) 。
首先,该算法在1-4行对状态进行初始化,得到 \(I_{1}\) 和 \(I_{2}\) ,每一个初始化状态 \((i_{1}, i_{2})\) 的权重设为 \(\lambda (i_{1})\otimes \lambda (i_{2})\) ,第5行将该初始化状态放入队列中。接下来是将每个复合状态 \((q_{1},q_{2})\) 放入队列中,其中,9-12行是当 \(q_{1}\) 和 \(q_{2}\) 分别是 \(T_{1}\) 和 \(T_{2}\) 的终止状态时则 \((q_{1},q_{2})\) 是 \(T\) 的终止状态,并且终止权重 \(\rho ((q_{1}, q_{2}))\) 可由 \(\rho (q_{1})\otimes \rho (q_{2})\) 计算得到。13-19行,对每一次的转移对 \((e_{1},e_{2})\in E[q_{1}\times E[q_{2}]]\) 使得 \(o[e_{1}]=i[e_{2}]\) ,并且 \((n[e_{1}],n[e_{2}])\) 作为 \(e_{1}\) 和 \(e_{2}\) 的下一个状态转移对,在16行将其插入队列中,为下一次的合并做准备。由此可得到以下符合转移结果: \(((q_{1},q_{2}),i[e_{1}],o[e_{2}],w[e_{1}]\otimes w[e_{2}],(n[e_{1}],[e_{2}]))\) ,其中在第19行通过连接操作符得到 \(E\) ,由于 \(E\) 是一种多重集合,转移时将允许出现多次。通常合并的时候对 \(\varepsilon \) 需要做特殊的处理,可看做是通过模拟 \(\epsilon \) 转移而对 \(varepsilon-free\) 算法进行的扩展,这种扩展可以通过FST级别的操作进行解释。首先修改 \(T_{1}\) 和 \(T_{2}\) 为 \(T^{'}_{1}\) 和 \(T^{'}_{2}\) ,进行合并时,需要考虑两个case,也就是当 \(T_{1}\) 使用一个 \(\varepsilon \) 输出进行转移时和当 \(T_{2}\) 使用一个 \(\varepsilon \) 输入进行转移时。前者是 \(T_{1}\) 只进行 \(\varepsilon\) $转移而不输出任何东西,且 \(T_{2}\) 保持当前的状态。后者是 \(T2\) 进行 \(\varepsilon\) 转移时没有任何输入,而 \(T_{1}\) 保持当前状态。为了模拟这个状态转移过程,可用图4来展开 \(T_{1}\) 和 \(T_{2}\) 到 \(T^{'}_{1}\) 和 \(T^{'}_{2}\) 。
图4. 包含 \(\varepsilon \) 的转移器及其转变
对于 \(T_{1}\) , \(\varepsilon \) 输出用 \(\varepsilon o\) 代替,并且通过自循环来匹配 \(\varepsilon i\) 将其添加到每个状态中。对于 \(T_{2}\) , \(\varepsilon \) 输入用 \(\varepsilon i\) 代替,并且通过自循环来接收 \(\varepsilon o\) 并将其添加到每个状态。通过这样的扩展, \(\varepsilon -free\) 的合并可看做是 \(T^{'}_{1}\circ T^{'}_{2}\) ,其中 \(\varepsilon i\) 和 \(\varepsilon o\) 可被认为是一种由规律的符号。合并算法的结果如图5所示:
图5. \(T^{'}_{1}\circ T^{'}_{2}\) 合并结果
然而图5中的转移器包含了额外的路径,此外对于非幂等半环(如概率半环和对数半环)的权重求和路径实际上是不正确的。为了解决这个问题,一种叫做"滤波器"的特殊转移器将会在合并操作中使用。假设 \(F\) 是一个滤波器,我们用 \(T^{'}_{1}\circ F\circ T^{'}_{2}\) 来代替 \(T^{'}_{1}\circ T^{'}_{2}\) 。例如,图6(1)展示了一种2-state filter(epsilon-sequencing filter)就是一种" \(F\) ",图中 \(x\in \Sigma _{2}\bigcap \Delta _{1}\) 。
图6. 滤波转换器
图7(a)展示了 \(T^{'}_{1}\circ F\circ T^{'}_{2}\) 的合并结果,已经消亡的状态和转移用灰色表示,这个算法就是通过这些状态和转移组合而成,消亡的状态和转移将会在后面通过剪枝操作移除掉。在使用2-state filter进行合并期间, \(T_{1}\) 中的 \(\varepsilon o\) 转移是不允许直接跟在 \(T_{2}\) 的 \(\varepsilon i\) 后面的,因为“滤波器”的状态是通过 \(T_{2}\) 的 \(\varepsilon o\) 从0到1进行改变的,但是不能从状态1中接收 \(T_{1}\) 的 \(\varepsilon o\) 。因此,每当一个 \(T_{1}\) 的 \(\varepsilon o\) 和 \(T_{2}\) 的 \(\varepsilon i\) 转移时, \(T_{1}\) 的转移总是位于复合转移器的第1个,最后,这些冗余的路径将被成功的过滤掉。
图7. \(T^{'}_{1}\circ F\circ T^{'}_{2}\) 的结果
图7(b)是3-state filter的合并过程,类似2-state filter。
本篇简单介绍了自动机的基本操作,包括闭包、并联、串联、投影、翻转和合并,并详细介绍了最麻烦的合并算法,下一篇将会介绍在语音识别解码中如何使用WFST对发音字典(L)、语言模型(G)、上下文(C)和声学模型(H)进行模型合演,敬请期待。
Speech Recognition Algorithms Using Weighted Finite-State Transducers.
来源: http://x-algo.cn/index.php/2017/05/29/2380/