WFST相关学习

2019-01-14 本文已影响0人习惯了千姿百态

知识准备

群
$G$ 非空， $G$ 上定义二元运算 $*$ :满足已下条件：
(1)封闭性 $\forall a,b \in G$ 有 $a*b \in G$
(2)结合律 $\forall a,b,c\in G$ 有 $(a*b)*c=a*(b*c)$
(3)幺元 $\exists e,\forall a\in G$ 有 $a*e=e*a=a$
(4)逆元 $\forall a\in G,\exists a^{-1}$ 使得 $a^{-1}*a=a*a^{-1}=e$
则称 $(G,*)$ 为群
若只满足条件(1)(2)则 $(G,*)$ 为半群
环
具有两个二元运算 $+,\centerdot$ 的非空集合 $S$ ,满足：
(1) $(S,*)$ 是阿贝尔群
(2) $(S,\centerdot)$ 为半群
(3) $\forall a,b,c\in S$ 有 $(a+b)+c=ac+bc, c(a+b)=ca+cb$
语音处理常用的半环

常见环
WFST符号化表示

composition algorithm

$Q$ ：记录composition之后的状态集
$S$ ：是一个队列，保存遇到的所有状态
代码1-2：初始化 $Q,S$ ，都初始为 $I_1,I_2$ 的笛卡尔乘积
代码3-16：对队列 $S$ 中的状态进行遍历操作
　　代码4-5：从 $S$ 中取出一个状态对 $(q_1,q_2)$
　　代码6-8：判断这个状态对是不是初始状态，如果是，则更新composition之后的初始状态 $I$ ,更新初始状态的权重
　　代码9-11：判断是否是终止状态
　　代码12-16：遍历所有从 $q_1,q_2$ 出发的转移，如果这两条的转移满足 $e_1$ 的输出等于 $e_2$ 的输入，那么就可以合并
　　　　代码13-15：判断合并后的转移的终点状态 $(n[e_1],n[e_2])$ 是不是新的状态（不在 $Q$ 里面），如果是新的状态则加入 $Q$ ，并插入队列 $S$ 中
　　　　代码16：产生新的转移，加入composition之后的转移集合 $E$

determination

首先定义了一个weighted subset：

weighted subset
大概的意思是：

determination algorithm

代码1-3：将(初始状态， $\bar{1}$ )对（即，带权状态）插入队列 $S$
代码5-6：从 $S$ 中取出一个带权状态集合 $p'$
代码7-16：对 $p'$ 中各个带权状态对应状态出发转移的所有输入 $x$ 进行操作
　　代码8：更新新的状态的权值，把 $p'$ 中每一个状态对的权值与该状态对出发转移上的权值做 $\otimes$ ，然后再进行 $\oplus$
　　代码9：更新状态， $E[Q[p']]$ 是 $p'$ 中的状态对应的所有转移
　　代码10：产生新的转移，加入集合 $E'$
　　代码11：判断这个状态 $q'$ 是不是新的状态
　　　　　代码12：把 $q'$ 加入新的状态集 $Q'$
　　　　　代码13：判断这个状态对集合 $q'$ 中的状态有没有终止态
　　　　　　　代码14-15：将这个状态 $q'$ 加入终止态集合 $F'$ 中，并更新其权值
　　　　　代码16：把状态 $q'$ 插入队列 $S$ 中
WFST-determination例子演示

weight-pushing

主要分两步，第一步：计算potential值，第二步：更新权值，起始，终止状态的权值
计算potential：

计算potential

代码1-7：初始化V[q]，如果是终止状态就赋值终止状态的权值，否则赋值 $\bar 0$
代码14：从终止状态开始往前， $E^{-1}[q]$ 表示以 $q$ 为终点的转移（个人理解...）
代码15：比较当前状态 $p[e]$ 到终点的最短路径与 $w[e]\otimes R$ 哪个小（tropical semiring下），R表示从 $q$ 到终点的最短路径
代码18：如果是出现新的状态插入队列 $S$ 中
（ $r$ 不知道有啥用。。。没看懂，这个算法解读仅供参考吧）
第二步更新：