WFST加权有限状态转换机-下

2025/7/10 算法算法加权有限状态转换机 WFST

在学习WFST，搜集了一些资料，加上自己的理解，如果有错误欢迎评论！

上一篇太长了，分成第二篇

顺便补充一下HMM，看下面的链接：

HMM的小知识

再来看看FSA和FST的区别：

特性	FSA(Finite-State Automaton)	FST(Finite-State Transducer)
输入/输出	仅处理输入，判断是否接受	处理输入并生成输出
转移标签	仅输入符号（如 `a`）	输入输出对（如 `a:b`）
用途	语言识别，正则匹配	字符串转换，语音识别，机器翻译

ps：下面这图和话均是欧阳盆栽大佬的原画，hhhh

下面这张图，介绍了集中FA的具体转换方式（腹诽一句，这个图画的差点累岔气）：

几种FA之间的关系

讲完了FA相关的知识，我们可以看到，一个普通的FA可以通过加输入输出、加权，转化为WFST，而在语音识别领域，往往是由 [HCLG] 这四个小网络通过一定的“操作”组合在一起，成为了一个大的WFST网络的，也就是说WFST是网络的结构，而HCLG代表了网络的四部分“内容”：

H(声学模型)：

H是把声学观察序列变成上下文相关因子序列的WFST。这个WFST代表声学模型，它的输入是观察序列，输出是上下文相关因子序列及其概率。([HMM]）模型。

C(跨词三音子模型) ：

C 是把上下文相关的因子序列转换成上下文无关的因子序列的WFST。

L(发音词典)：

它的输入(上下文无关的)因子序列，输出是词序列。

G(语言模型)：

它是一个WFSA，它的输入是一个词序列，然后G可以判断这个词序列是否符合语法以及它的概率。(n-gram)

加权有限状态转换器(WFST)

WFST之中，Tropical semiring是最常用的一个半环，而在一些WFST优化步骤中也会用到

Log半环。

复合操作

复合操作的前提是，前一个WFST的输出属于后一个WFST的输入
（有点像向量加法哈：AC+CB=AB
你别说，还真挺像
如图下所示
找到a：b，a输入b输出，
和b：a，b输入a输出，
就变成了
a:a，a输入，a输出，然后概率相乘

（对于1B节点，考虑所有可能组合，0A，1B 然后2A1B，然后3A1B，对于每个节点遍历的考虑）

注意：组合可能会舍弃掉某些边。

可以动手算一下：c为AC复合得到的，注意但是原文中的这个权重计算不太对，应该是相乘。而博客的示例可能是为了说明另一种权重系统（比如Tropical半环，其中权重为负对数概率，则组合时权重相加）而设计的。但是他没有转成负对数，有点奇怪。

图：WFST复合操作的例子

转移消除（[ε-removal]操作

半环（Semiring）框架在加权自动机（WFSA/WFST）中的应用

操作(⨂ 和 ⨁) 的定义与作用：
• 路径累积操作 ⨂：定义了如何将一条路径上边的权重组合成该路径的总权重。例如，在一条路径上依次经过边权 w1, w2, ..., wn，该路径的总权重为 w1 ⨂ w2 ⨂ ... ⨂ wn。
• 路径合并操作 ⨁：定义了如何合并具有相同输入序列（到达相同或不同状态）的多条路径的权重，得到一个代表这些路径集合的总体权重。
• 符号约定：使用 ⨂ 表示权重累积操作，⨁ 表示权重合并操作，是处理加权自动机的标准数学框架。
常见半环组合及其物理意义：
• 概率半环 (Probability Semiring)： (⨁, ⨂) = (+, *)
◦ 意义：权重直接表示概率 (或代价)。
◦ 应用：总路径权重 = 边权乘积 (*)，相同输入序列的总权重 = 所有路径权重求和 (+)。常用于需要计算所有路径概率之和的场景。
• 最大-概率半环 (Max-Probability / Viterbi Semiring)： (⨁, ⨂) = (max, *)
◦ 意义：权重表示概率 (或代价)。
◦ 应用：总路径权重 = 边权乘积 (*)，相同输入序列的总权重 = 最大路径权重 (max)。用于寻找最可能路径（Viterbi解码）。
• 热带半环 (Tropical Semiring)： (⨁, ⨂) = (min, +)
◦ 意义：权重表示概率的负对数 (-log(prob)) 或一般化的代价/距离。代价越低（min）对应概率越高。
◦ 应用：总路径权重 = 边权之和 (+)，相同输入序列的总权重 = 最小路径权重 (min)。用于寻找最低代价（最高概率）路径。名称由来：其发现者系巴西（热带国家）数学家 Imre Simon。
• 对数半环 (Log Semiring)： (⨁, ⨂) = (-log(e^{-x} + e^{-y}), +)
◦ 意义：权重表示概率的负对数 (-log(prob))。
◦ 应用：总路径权重 = 边权之和 (+)，相同输入序列的总权重 = -log(e^{-w1} + e^{-w2} + ... + e^{-wn})。这是概率半环在负对数空间下的精确等价形式。用于在负对数空间精确计算所有路径的总概率。
• 核心见解：在语音识别中，前两种（(+, *) 和 (max, *)）通常直接作用于概率值，后两种（(min, +) 和 (-log(e^{-x}+e^{-y}), +)）作用于概率的负对数值。
Viterbi 近似 (Viterbi Approximation) 的解释：
• 当权重表示概率时，如果使用 max 作为合并操作 (⨁)，代替概率求和 (+)，这意味着我们只保留概率最大的那条路径，忽略其他路径。这就是 Viterbi 近似（或 Viterbi 解码）。
• 负对数空间下的对应：如果权重表示概率的负对数 (-log(prob))，则：
◦ 概率求和 (+) 的对应操作是 -log(e^{-x} + e^{-y}) (Log半环的 ⨁）。
◦ 取最大值 (max) 的对应操作变成了取最小值 (min) (Tropical半环的 ⨁)。因为较小的负对数权重对应较大的原始概率。
WFSA/WFST 确定化 (Determinization) 的核心挑战：
• 与普通 NFA 确定化（子集构造法）类似：给定输入字符串，找到所有可到达的状态集合。
• 关键区别 (核心价值点)：在 WFSA/WFST 中，相同的输入字符串可能通过多条具有不同权重的路径到达不同的状态。确定化过程不仅需要合并这些状态，还必须合并这些路径的权重。
• 合并权重的操作：合并后的权重必须由所选的 ⨁ 操作决定！这是确定化算法的精髓和主要挑战。
◦ 正确表述： “但是状态 0 到状态 <1,2> 的 weight 是由 ⨁ 操作决定的（例如在 Tropical Semiring 下是 min(1, 2) = 1，在 Probability Semiring 下是 1 + 2 = 3）。”
• “剩余权重（Remaining Weight）”/“残差（Residual）”的概念引入：在确定化过程中需要记录额外信息以处理非确定性的权重分布。它触及了标准 WFSA 确定化算法（如 Mohri 提出的权重推送算法）的核心思想——跟踪每个状态在合并子集内的权重偏差，以便正确地组合后续路径权重。
半环的普适性：
• ⨁ 和 ⨂ 操作不限于列举的几种，只要它们满足半环的公理要求（结合律、分配律、存在零元和单位元等），这种代数结构（半环）就可以用来定义加权自动机的行为。这是理论框架的核心抽象。-

实际计算示例

场景：两条路径权重为 w₁ = -log(0.3) ≈ 1.20, w₂ = -log(0.5) ≈ 0.69
（对应概率 P₁=0.3, P₂=0.5）。

• 概率半环：

总概率 = 0.3 + 0.5 = 0.8
• 对数半环：

总权重 = -log(e⁻¹˙²⁰ + e⁻⁰˙⁶⁹) ≈ -log(0.3 + 0.5) = -log(0.8) ≈ 0.22
• 热带半环：

结果 = min(1.20, 0.69) = 0.69（仅对应 max(0.3, 0.5)=0.5，漏掉 0.3）。

ps：只有满足半环公理的系统，才能通过动态规划（如前向算法）高效计算所有路径之和。

WFST构建过程中，ε的状态转移对整体输入输出序列没有贡献，存在一个算法(ε-消除算法)把一个ε-NFA转换成与之等价的没有ε-跳转的NFA。

前期优化过程中留下、生成或引入空弧标记，最后进行去空弧操作减少整体复杂度。

下图来源于知乎

确定化操作（Determinization）

ps：跟NFA到DFA的相似，但是不相同

特征	NFA到DFA确定化 (标准子集构造)	WFST确定化
核心对象	FSA (输入单轨)	WFST (输入-输出双轨 + 权重)
主要不确定性	输入转移状态不确定性	输入转移状态不确定性 + 输出不确定性
核心合并操作	合并状态集合 (Q-subset)	合并状态、计算输出LCP、管理输出残差、组合权重
新状态	原始状态集合 (e.g., {q0, q1})	元组集合 (e.g., { (q0, ε), (q1, "y") })
边标签	输入标签	输入标签 + 输出标签 (LCP) + 权重
权重处理	无	必须（依赖半环）
输出标签处理	无	必须（LCP提取与残差管理）
对 ε-transitions 的要求	算法本身可直接处理输入ε	通常需要输入ε-自由或先进行 ε-移除
功能等价目标	接受相同的输入语言	具有相同的输入->输出+权重映射关系
算法复杂度	相对较低 (状态空间爆炸)	显著更高 (状态复杂 + LCP/权重计算)

虽然 WFST 的确定化借鉴了 NFA 到 DFA 的子集构造法（幂集构造）的基本理念来解决 输入转移的不确定性，但它是一个显著更复杂的过程。其核心区别和额外复杂性来源于必须同时、正确地处理输出标签的合并（通过LCP提取和残差管理）以及权重的组合与传播（根据半环语义），以维持原始WFST的输入-输出-权重映射关系。输出序列的管理，尤其是公共前缀的抽取和剩余后缀的延迟处理，是WFST确定化独有的、最核心的区别点。权重则需要依据所选代数结构（半环）进行符合语义的合并。

可以说，NFA到DFA的确定化是WFST确定化的一个特例（当权重不影响路径选择且输出标签不存在或等同于输入标签时）。但在实践中，正是因为WFST处理了权重和双轨映射，它的确定化才如此关键且算法复杂。

如果从一个状态遇到一个字母会有两条及其以上的边，那么它就是非确定的

确定化的算法就是把一个非确定的WFST转换成等价的确定的WFST的算法，确定化后，网络将变为唯一输入和唯一输出。（与FSA相同）

（这个佬画的太好了Orz，（直接偷了
（但是这个大佬，好像不写文章了

在每个final state之中，输出必定被替换为ε。优点：提高计算效率

ps：上图的计算流程示例：

公式解析

\(W_{r} ( e_{i} )= W_{r} (e_{i}^{n})^ {-1} \otimes W(p[ e_{i} ]) \otimes W( e_{i})\)

在热带半环 (min, +) 语境下，符号 ⊗ 实际对应加法 (+)，符号 ⁻¹ 表示加法逆元（即取负值）。公式中的符号含义如下：

变量定义：
• \(e_{i}\): 原始WFST中的一条转移边（待合并的边）
• \(W_{r}(e_{i})\): 计算结果 → 原始边 \(e_{i}\) 的路径预估代价
例：这个最后的结果用于下次的新状态的权重（也就是下一次的剩余权重
• \({W_{r}(e_{i}^{n})^{-1}}\): 当前确定化状态（S）权重的加法逆元
◦ 即 \(-W_r(S)\)（状态权重的相反数）
例：在上图来说这个值是新弧的权重的相反数： 1 到 -1
• \(W\left(p[e_{i}]\right)\): 原始边起点的分量残差权重（新状态中存储的）
例：这个值是上一个权重的状态所以是0，0
• \(W\left(e_{i}\right)\): 原始边 \(e_{i}\) 的边权重
例：这个值是0输入a到1的权重，0输入a到2的权重