WFST核心算法

论文参考经典之作“Speech Recognition With Weighted Finite-State Transducers”，网上随便就能搜到。

符号化：

在半环$\mathbb K(\oplus, \otimes, 0, 1)$之上定义一个WFST

$$def \quad T=(\mathcal A, \mathcal B, Q, I, F, E, \lambda, \rho)$$

其中

$$\begin{align} \mathcal A:& \text有限的输入字母表 \notag \\ \mathcal B:& \text有限的输入字母表 \notag \\ Q:& \text有限的状态集合 \notag \\ I,F:& \text始末状态 \ I,F \subseteq \ Q \notag \\ E:& 转移集合 \notag \\ \lambda:& 初始状态权值 \notag \\ \rho:& 结束状态权值 \notag \\ \end{align}$$

对于$e \in E$

$$\begin{align} p[e]:& \text起始状态 \notag \\ n[e]:& \text终止状态 \notag \\ i[e]:& \text输入标签 \notag \\ o[e]:& \text输出标签 \notag \\ w[e]:& \text转移权值 \notag \end{align}$$

对于多次转移形成的一个路径$\pi=e_1 \dots e_k$满足：

$$n[e_i]=p[r_{i+1}]\ i=2,\dots ,k$$

将$p,n,w$这些函数应用到path上,令

$$n[\pi]=n[e_k] \\ p[\pi]=p[e_1] \\ w[\pi]=w[e_1] \otimes \dots \otimes w[e_k]$$

若存在路径集合$R$，那么

$$w[R]=\bigoplus_{\pi \in R}w[\pi]$$

另做如下定义：

$$P(q,q'): \ q \to q'\ 的路径集合 \\ P(q,x,y,q'): \ q \to q',x \in \mathcal A, y \in \mathcal B \ 的路径集合 \\ P(q,x,q'): \ q \to q' \ input = x\ 的路径集合$$

上述定义拓展至$R,R’ \subseteq Q$

$$P(R,R')=\bigcup_{q \in R,\ q' \in R'}P(q,q') \\ P(R,x,y,R')=\bigcup_{q \in R,\ q' \in R'}P(q,x,y,q') \\ P(R,x,R')=\bigcup_{q \in R,\ q' \in R'}P(q,x,q')$$

定义一个transducer $T$在$input/output=(x,y)$时

$$T(x,y)=\bigoplus_{\pi \in P(I,x,y,F)}\ \lambda[p[\pi]]\otimes w[\pi] \otimes \rho[n[\pi]]$$

同理

$$T(x)=\bigoplus_{\pi \in P(I,x,F)}\ \lambda[p[\pi]]\otimes w[\pi] \otimes \rho[n[\pi]]$$

Composition操作

定义$T_1$，$T_2$的Composition操作如下：

$$T_1\circ T_2=\bigoplus_{z \in \mathcal B^*}T_1(x,z)\otimes T_2(z,y)$$

示例，详细操作见OpenFST

操作的伪代码如下：

算法设置一个队列，初始化两个操作数的$I$集合的笛卡尔积插入队列，之后进行BFS逻辑的流程。每一次迭代过程如下($e$表示一个状态节点的所有输出转移路径)

1. 从队列中取出一个state pair($p_1, p_2$)，这是一对状态节点，第一次pop时必然在$I$集合的笛卡尔集合中
2. 依次比较每个状态节点的输出的转移路径($e_1, e_2$)，若满足$o[e_1] = i[e_2]$又不存在于队列中，加入队列
3. 输出半群中加入一条新的转移路径，从$(p_1, p_2)$到$(n[e_1], n[e_2])$，路径标志为$(o[e_1], i[e_2], w[e_1] \otimes w[e_2])$

根据上述流程，输出半群的过程也是BFS逻辑的，一次操作可以扩展完节点$(p_1, p_2)$的所有后继。

Determination操作

对于一个FST中任意的状态$q$，如果从他出发的边没有着相同的输入，那么就可以说这个FST是deterministic的
定义若干符号表示如下

$$\begin{align} p &: \text{带权子状态集合} \notag \\ Q[p] &: p\text{中的状态集合} \notag \\ E\left[Q[p]\right] &: p\text{中的状态集合的出弧集合} \notag \\ i[E\left[Q[p]\right]] &: p\text{中的状态集合的出弧集合的输入集合} \notag \\ \end{align}$$

算法如下

注意，确定化之后的状态本身是未确定化之前的状态集合和权值的pair

• 算法采用BFS逻辑，将带权子状态集合$q$放在队列中依次处理，初始化该集合状态为所有initial状态，权值为1
• 对于每次拿到的$q$，在对应的$i[E\left[Q[p]\right]]$中的每一种输入，做如下操作

1. 拿到有该类输入的出弧累计权值最小的一个权值作为新建出弧的权值$w’$
2. 把这些出弧的目标状态和相应累计权值减去$w’$的集合，作为新建状态$q’$
3. 新建$E[q, x, w’, p’]$
4. 若新建状态$q’$为新，加入BFS队列中待处理

RemoveEps操作

RemoveEps去除FST中输入为$\varepsilon$的边，得到的FST和原FST等价，算法分为两步执行

• 对于每一个状态$p$，计算$\varepsilon$闭包，结果定义为 $$C(p) = \{(q, w): q \in \varepsilon(p), \; d[p, q] = w \in \mathbb{K} - \overline 0\}$$
• 对于每一个状态$p$，移除$\varepsilon$边，添加若干拓展边，这部分伪代码如下

在该算法中，有三个状态比较重要

• 当前正在处理的状态$p$
• 可以通过$p$的$\varepsilon$闭包到达的状态$q$
• 可以通过状态$p$到达的后继状态$r$

若$q$是终止节点，那么$p$肯定也是终止节点

举个栗子：