WFST中的代数半环

概览

包括：半环定义、例行证明、完备半环定义和解释；先把这几个半环摆出来吧：

表1）剪切自Mohri weighted automata algorithms

为什么WFST要基于半环构建呢？我的理解是：一方面环这样的代数结构是比我们熟知的域（ $\mathbb {Q ,R, C, Q(\sqrt2)}$ ）更加普遍的、实用性更广的结构，可以让WFST更加普适。另一方面，WFST库的设计只需考虑面向这些代数结构编程，只要WFST框架内的运算模块符和环的定义，无需考虑具体的任务相关知识；而使用者则需根据业务设计具体的适当的权重环就能直接利用WFST框架，不同环对应的功能；换句话说，这是个很棒的接口，例如kaldi中的代码WeightType::Zero()，WeightType::One()就代表了环的加法中性元和乘法中性元。

我们先来简单介绍一下基本的代数结构：

环（ring）

设 $R$ 是一个集合，其上定义了两个二元运算，分别称为“加法”和“乘法”，分别使用 $\oplus$ 和 $\otimes$ 作为记号，定义为 $\oplus : R \times R \to R$ ， $\otimes : R \times R \to R$ ，并且满足下面的条件：

1） $R$ 关于 $\oplus, \otimes$ 运算封闭

2） $R$ 关于 $\oplus$ 运算构成Abelian群

3） $R$ 关于 $\otimes$ 运算构成幺半群

4）乘法运算 $\otimes$ 关于加法运算 $\oplus$ 满足左分配律和右分配律

我们说 $(R, \oplus, \otimes,\overline{0},,\overline{1})$ 构成了一个环，为了强调这里的0和1是抽象环的“加法中性元”和“乘法中性元”，遵循Mohri的文章，我们特意使用上加bar来表示，下面也称”中性元“是”单位元“或”幺元“。

注：不同的书上对环的定义会有些许的不同，比如有人喜欢把上面条件（3）改为“ $R$ 关于 $\otimes$ 运算构成半群semi-group“，而不是上面的幺半群monoid，这无非只是更倾向于是否把乘法中性元（即”幺“）放到乘法半群中去；当你需要环的性质时，你把它称述清楚即可；这里我们还是遵循Mohri的定义。

半环（semi-ring）

有了上面的环的定义，那么什么叫半环呢？“半”的性质肯定来自环的子结构（即“群”），自然 $R$ 已经关于 $\otimes$ 运算构成半群，那么“半环”的“半”字肯定就来自加法群了；即将上面“环”的定义做个剪裁：

1）、3）、4）保持不变；

2） $R$ 关于 $\otimes$ 构成幺半群，当然交换性依然满足（即上面的abelian修饰词），也就是不是所有的元素都有加法逆元了。

显然，半环比环的条件更加弱，因此更加普适。

以下我们用五元组 $(S, \oplus, \otimes,\overline{0},,\overline{1})$ 来代表半环结构，并且我们既使用 $S$ 来表示进行运算的元素所在集合，也用 $S$ 表示这个半环的五元组定义。

简单的形式证明

下面我们来证明一下上面表格（1）中的各个集合在对应的运算下的确构成半环，证明过程非常的形式化和简单，我们权当做个练习。

Boolean Semiring

$S=(\{0,1\}, \vee, \wedge, 0, 1)$

verbose proof:

1） $0\oplus0 = 0 \vee0=0,\ 0\oplus1=0\vee1=1, \ 1\oplus0=1\vee0=1,\ 1\oplus 1=1\vee1 =1$ ，显然关于加法封闭，而且“交换性”可以直接看出来，不过也可以由逻辑运算的交换性来保证。“幺元”显然就是0，因为它与其它元素作加法运算，结果还是其它元素自己；最后可以发现元素1的确不存在加法逆元。

2）加法结合率： $x\oplus(y\oplus z) = (x\oplus y)\oplus z$ 显然成立，因为只要 $x,y,z$ 中有一个是1，则两边均为1；全为0的时候，两边显然都是0。

3） $0\otimes0=0\wedge0=0,0\otimes1=0\wedge1=0,1\otimes0=1\wedge0=0,1\otimes1=1\wedge1=1$ ，可见关于乘法运算封闭，存在乘法单位元 $\overline{1} = 1$ 。

4）乘法结合律： $\oplus,\otimes$ 显然成立，因为只要 $x,y,z$ 中有一个为0，则两边全为0；全为1的时候，两边都是1。

5）分配律： $x\otimes(y\oplus z) = \begin{cases}1, x 和 y\oplus z 均为1 \\0,x和y\oplus z至少一个为0\end{cases}$

在case1中，当 $y\oplus z=1 \iff y=1\ \text {or} \ z=1$ ，这意味着 $x\otimes y=1\ \text{or}\ x\otimes z=1$ ，进而有 $(x\otimes y )\oplus (x\otimes z) =(x\otimes y )\vee(x\otimes z)= 1$ ，即此时分配律成立；

在case2中，若 $x=0$ ，则 $(x\otimes y )\oplus (x\otimes z) =0 \vee 0= 0$ ；若 $y \oplus z =0$ ，则 $y=0\ \text{and} \ z=0$ ；显然case2中分配律也成立；

由于这里的环是交换的，所以我们没有刻意强调左右分配律。

Probability Semiring

$S=({\mathbb R_{+}}\cup \{ +\infty\}, +, \times, 0,1)$

verbose proof:

1）由于这里的半环运算 $\oplus,\otimes$ 就是实数域中的加法和乘法运算，因此由实数公理，可知 $\mathbb R_{+}$ 关于加法和乘法封闭；

2）再由无穷大运算相关性质：

$\begin{aligned}a+(+\infty) &= +\infty \\ (+\infty)+(+\infty) &= +\infty \\a \cdot (+\infty) &= +\infty \\(+\infty)\cdot (+\infty) &= +\infty \end{aligned} ;\quad \forall a \in {\mathbb R}_{+}$

可知集合 ${\mathbb R_{+}}\cup \{ +\infty\}$ 的确关于加法和乘法封闭；

3）加法、乘法结合率，加法、乘法交换律，以及乘法关于加法的分配律都继承自实数的运算律；

4）显然加法幺元 $\overline 0_{S} = 0_{\mathbb R}$ ，乘法幺元 $\overline 1_{S} = 1_{\mathbb R}$ 都存在；

5）再次，除了0都不存在加法逆元，所以是半环。

Log Semiring

$S=({\mathbb R} \cup \{ -\infty,+\infty\}, \oplus_{\rm log}, +, +\infty,0)$ ，其中加法运算定义为： $x \oplus_{\rm log} y = -\log(e^{-x} + e^{-y})$

verbose proof:

1）显然对于任意实数 $x,y$ ，都有 $x \oplus_{\rm log} y$ 是一个实数；下面考虑几个特殊情况， $\forall y \in \mathbb R$ ：

$(+\infty) \oplus_{\rm log} y = -\log(e^{-\infty} + e^{-y}) = -\log(e^{-y}) =y$

$\begin{aligned}(-\infty) \oplus_{\rm log} y & = -\log(e^{\lim_{x\to+\infty}x} + e^{-y})\\& = -\lim_{x\to +\infty}\log(e^{x}(1+e^{-x-y})) \\&=-\lim_{x\to +\infty}(x + \log(1+e^{-x-y})) \\&= -\lim_{x\to +\infty} x \ - \log(1+\lim_{x\to \infty}e^{{-x-y}})\\&= -\infty -0 = -\infty\end{aligned}$

2）显然，由于满足交换性，我们只要验证下面表格中的情况：

$\begin{array}{c|ccc}x & +\infty &+\infty & -\infty \\y & +\infty & -\infty & -\infty \\\hlinex\oplus y &+\infty &-\infty &-\infty\\\end{array}$

$(+\infty) \oplus_{\rm log} (+\infty) = -\log(e^{\lim_{x\to\infty}-x} + e^{\lim_{y\to\infty}-y}) = -\lim_{x,y\to \infty}\log(e^{-x}+e^{-y}) =- (-\infty )=+\infty$

$(+\infty) \oplus_{\rm log} (-\infty) = -\log(e^{\lim_{x\to+\infty}-x} + e^{\lim_{y\to-\infty}-y}) = -\lim_{x,y\to \infty}\log(e^{-x}+e^{y}) =- \lim_{y\to+\infty}\log e^{y}=-\infty$

$(-\infty) \oplus_{\rm log} (-\infty) = -\log(e^{\lim_{x\to +\infty}x} + e^{\lim_{y\to +\infty} y}) = -\lim_{x,y\to +\infty}\log(e^{x}+e^{y})$ ，令 $z = -\log(e^x+e^y)$ ，则 $e^z=\frac{1}{e^x+e^y}$ ，所以 $e^z \to 0 \ \text{as}\ x,y\to +\infty$ ，即 $z \to -\infty$

3）显然，通过观察上面的（1）和（2）可以发现 $+\infty$ 的确是“加法中性元”；

4）由于Log-半环的乘法运算只是实数域的加法运算，显然也满足封闭性、交换性、结合性等等；

5）并且满足 $(+\infty) \otimes x=(+\infty) + x = \infty$ , $(-\infty) \otimes x = (-\infty) + x = -\infty$ , $(+\infty)\otimes(+\infty)=(+\infty)+(+\infty)=(+\infty)$ , $(-\infty)\otimes(-\infty) = (-\infty)+(-\infty)=(-\infty)$ ；

6）最后，在拓展的实数域中 $(+\infty)\otimes(-\infty)=(+\infty)+(-\infty)$ 不是一个数，这样的运算是无意义的；但是Mohri的文章中似乎没提到这点，如果这条封闭性不满足，那么严格意义上并不构成半环；不过是否可以参考积分学中的“主值意义下的积分”思路，定义 $(+\infty)\otimes(-\infty)\equiv \lim_{x\to+\infty}x+\lim_{x\to-\infty}x=\lim_{x\to+\infty}(x - x)=\lim_{x\to+\infty}0 =0$ 呢？这样就算封闭了；但是如果实际中，并不会出现这样的运算，那么这一点也是无关紧要的。

7）Log-半环的乘法运算关于加法运算的分配律，也很好验证，比如：

$\begin{aligned}x\otimes (y\oplus z)&\equiv x + (-\log(e^{-y}+e^{-z}))\\&=-\log e^{-x} -\log(e^{-y}+e^{-z})\\&=-\log e^{-x}(e^{-y}+e^{-z}) \\&=-\log e^{-(x+y)}+e^{-(x+z)} \\&\equiv (x\otimes y) \oplus (x\otimes z)\end{aligned}$

其中符号“ $\equiv$ ”是“by definition“的意思，并且 $x,y,z\in \mathbb R$ ；

显然上式说明Log-半环的分配律在实数中成立，再来看看一些边界case：

$+\infty\otimes (x\oplus y)=+\infty -\log(e^{-x}+e^{-y})=+\infty, \forall x,y\in \mathbb R$ ，另一方面 $(+\infty) \otimes x \oplus (+\infty) \otimes y=-\log(e^{-(+\infty+x)}+e^{-(\infty+y)}) =+\infty, \forall x,y\in \mathbb R$ ，所以分配律此时也成立；

$\begin{aligned}(+\infty)\otimes[(+\infty)\oplus (+\infty)] &= (+\infty) -\log(e^{-\infty}+e^{-\infty})\\&=(+\infty) +(+\infty)\\&=+\infty \in S\end{aligned}$

$\begin{aligned}(-\infty)\otimes[(-\infty)\oplus (-\infty)] &= (-\infty) -\log(e^{+\infty}+e^{+\infty})\\&=(-\infty) +(-\infty)\\&=-\infty \in S\end{aligned}$

但是这里出现一个例外情况： $(+\infty) \otimes [(+\infty) \oplus (-\infty)]$

$\begin{aligned}(+\infty)\otimes[(+\infty)\oplus(-\infty)]&=(+\infty) + (-\log(e^{-\infty}+e^{+\infty}))\\&=(+\infty) -\log e^{+\infty} \\&=(+\infty) +(-\infty)\\&=0\quad (\text {主值意义下})\end{aligned}$

而 $\begin{aligned}(+\infty)\otimes(+\infty)=+\infty, (+\infty) \otimes (-\infty)&= -\log(e^{-\infty}+e^{+\infty})=-\infty\\\end{aligned}$ ，因此有 $[(+\infty)\otimes(+\infty) ] \oplus [(+\infty)\otimes(-\infty)]=-\log(e^{-\infty} + e^{+\infty})=-\infty$ ；我们发现此时若使用主值意义下的无穷大加法，则不满足分配律！

所以，前面的讨论是欠考虑了（ok，这些随笔都是我想到哪写到哪，只要不是低级错误就不改了）；看来我们需要定义 $(+\infty)+(-\infty)=(-\infty)$ ，因为取主值是没什么明显道理的；而让运算满足分配律则是明确的动机；不过回过头来，以Log-半环的乘法运算视角来看，上面新的定义就是： $(+\infty)\otimes(-\infty)=-\infty$ ，这的确是相当自然的（联想一下实数域的平行case： $(+\infty)\cdot (-\infty) = -\infty$ ）。

8）Log-半环的乘法单位元显然是0，显然有 $0\otimes x = 0+x=x,\ \forall x \in \mathbb R\cup \{+\infty,-\infty\}$ 成立。

Tropical Semiring

$S=({\mathbb R}\cup \{ -\infty,+\infty\}, \min, +, +\infty,0)$

插曲

说到Tropical Semiring，这个名字很特别，我特意查了一下Tropical Semiring的含义：这个半环起初是由巴西的一个数学家提出来的，而那些主导学术和技术的西方国家因为懒得去了解这位数学家，于是就凭着“巴西就是某个处于赤道上的国家”这一刻板印象，随意地为这个半环取了这样的一个名字；在我看来，这真切地体现了西方国家一贯的傲慢形象。

说到这里，我又想起来西方人起的另一个名字“中国余数定理”，虽然（大概）所有的书上都是这么写的，并且一些老师可能也是这么介绍的，但我真的很反感这样的名字。不得不说，虽然我一直在吐槽“百度文库”，但是这次它给这个定理用了中国人应该用的名字“孙子定理”。

proof:

1）显然有 $\min(x,y) \in S ,\ \forall x,y \in\mathbb R\cup \{+\infty, -\infty\}$ 成立，因此关于半环加法封闭；

2）和Log-半环一样， $x\otimes y = x+y \in S, \ \forall x,y \in S$ 成立，因此关于半环乘法也封闭；

3）结合率、交换律仍然是继承自实数域；

4）显然有 $\min(+\infty, x) = x,\ \forall x \in S$ 成立，因此 $+\infty$ 的确是半环S的加法单位元；

5）显然有 $0\otimes x = 0 + x = x, \ \forall x \in S$ 成立，因此0的确是半环S的乘法单位元；

6）最后验证以下分配律，不妨设 $y<z$ ，则 $x \otimes (y\oplus z) = x+\min(y, z)=x + y$ ，而 $(x\otimes y) \oplus (x\otimes z) =\min( x+y, x+z) =x+y$ ，所以分配律对 $x,y,z\in \mathbb R$ 成立；根据Log Semiring中的讨论结果，亦可验证这里当 $x,y,z \in \mathbb R \cup \{+\infty,-\infty\}$ 都成立。

半环的其它属性

交换性（commutative）

注意，在环的定义中，并没有要求乘法运算满足交换性，例如一个矩阵环就是不交换的，当一个半环的乘法运算满足交换律的时候，我们称其为“交换半环”；显然，有上面的讨论，可知上面的四个环均满足交换性。

幂等性（idempotent）

若半环S满足 $x\oplus x=x,\ \forall x \in S$ 都成立，则称其满足幂等性；由 $1\vee1=1,0\vee0=0$ 可知Boolean Semiring是幂等的；由 $x\oplus x = \min(x, x) = x,\ \forall x \in \mathbb R \cup \{-\infty, +\infty\}$ 成立可知Tropical Semiring也是幂等的。

完备半环（Complete Semiring）

设 $(S, \oplus, \otimes, 0_R, 1_R)$ 为半环，设 $I$ 为任意索引族（有限或无穷），和任意由 $S$ 中的元素构成的集合 $\{a_i\}_{i\in I}$ ，都有 $S$ 关于累加运算 $\bigoplus_{i\in I}a_i$ 封闭；并且 $\bigoplus_{i\in I}a_i$ 的结果不依赖于求和运算中元素的顺序；则我们称其为“完备半环”，若还满足下面几个条件：

$\begin{aligned}&\bigoplus_{i\in I} a_i = 0_R \quad \quad \quad &\text{if}\ |I|=0\quad (2)\\&\bigoplus_{i\in I} a_i = a_i \quad \quad \quad &\text{if}\ |I|=1\quad (3)\\&\bigoplus_{i\in I} a_i = \bigoplus_{j\in J}\bigoplus_{i\in I_j}a_i \quad \quad \quad &\text{对}I\text{的任意一个不交并} I=\cup_j I_j\quad (4)\\&a \otimes ( \bigoplus_{i\in I} a_i) = \bigoplus_{i\in I} (a\otimes a_i )\quad \quad \quad &\forall a\in S \quad (5)\\&( \bigoplus_{i\in I} a_i)\otimes a = \bigoplus_{i\in I} (a_i \otimes a )\quad \quad \quad &\forall a\in S \quad (6)\\\end{aligned}$

星半环（Starsemiring）

在半环 $(S, \oplus,\otimes, 0_R, 1_R)$ 上增加了星运算（即一元闭包运算） $\ast$ ，其定义为： $a^{\ast} = \bigoplus_{n=0}^{+\infty} a^n, \ \forall a \in S$ ，并且对无穷级数满足结合率、交换律、分配律。

显然一个完备半环是一个星半环，因为对于任意n，有 $a^{n} \in S$ ，再由完备半环关于无穷级数的封闭性，和性质（5）（6）分配性即可得。

布尔半环是个完备半环，且 $0^{\ast} = \bigoplus_{n=0}^{+\infty} 0^n = 1\vee0\vee 0\vee\cdots = 1 \in \{0,1\}$ ， $1^{\ast} = \bigoplus_{n=0}^{+\infty} 1^n = 1\vee1\vee 1\vee\cdots = 1\in \{0,1\}$ ；

热带半环也是一个完备半环，且有：

$a^* = \begin{cases} 0 \quad & \text{若 }a \in \mathbb R_+\\-\infty \quad & \text{其它}\end{cases}$

以上两个半环都是幂等半环，也有非幂等半环满足完备性，例如概率半环 $(\mathbb R_+\cup \{+\infty\}, +, \times, 0, 1)$ ，且有：

$a^* =\sum_{n=0}^{+\infty} a^n = \begin{cases}\frac{1}{1-a}\quad &\text{若} 0\leq a< 1;\\+\infty \quad & \text{若} a\geq1;\end{cases}$

我们已经对WFST引入了半环结构，使得在WFST上的相关运算是良定的；那么，为什么还要引入“完备半环”和“星半环”的概念呢？

虽然在实际中WFST中只能处理有限个顶点，和有限多个转移弧，即有限的图；但是别忘了，我们在图中会出现循环连接，比如：自循环（self-loop），那么这样就会出现无穷条路径，而我们在WFST中经常会遇到一族路径的权重的累加运算。

比如，当有限长度的路径 $\pi$ 中出现一个自循环，则会出现可数无穷条路径到达终点；当出现两个自循环时则会可数多个可数条路径，再次仍是可数的，因此在图中出现有限多个循环时，总是可数无穷条路径。

不管怎样，我们的确需要考虑无穷的情况，即我们不仅需要半环对加法、乘法封闭，还需要对极限运算封闭；因此我们需要引入完备性概念，确保我们在WSFT中的相关运算都是良定的。

参考：Mohri, Weighted Automata Algorithms

最后编辑于：2022.11.28 17:34:25

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,793评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,567评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,342评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,825评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,814评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,680评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,033评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,687评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,175评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,668评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,775评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,419评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,020评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,206评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,092评论 2赞 351
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,510评论 2赞 343

WFST中的代数半环

概览

环（ring）

半环（semi-ring）

简单的形式证明

Boolean Semiring

Probability Semiring

Log Semiring

Tropical Semiring

半环的其它属性

完备半环（Complete Semiring）

星半环（Starsemiring）

推荐阅读更多精彩内容