nlp - 如何执行 FST（有限状态传感器）合成

Question

考虑以下 FST：

T1 

0 1 a : b
0 2 b : b
2 3 b : b
0 0 a : a
1 3 b : a

T2

0 1 b : a
1 2 b : a
1 1 a : d
1 2 a : c

我如何对这两个FST（即T1 o T2）执行合成操作我看到了一些算法但不太了解。如果有人能以简单的方式解释它，那将是一个很大的帮助。

请注意，这不是家庭作业。该示例取自给出解决方案的演讲幻灯片，但我不知道如何解决。

score 20 · Accepted Answer

由于您没有指定输入格式，我假设 0 是初始状态，出现在第二列但不是第一列的任何整数都是接受状态（T1 为 3，T2 为 2），每一行是转换关系的一个元素，给出前一个状态、下一个状态、输入字母和输出字母。

对 FST 的任何操作都需要产生一个新的 FST，因此我们需要状态、输入字母表、输出字母表、初始状态、最终状态和转换关系（以下 FST A、B 和 W 的规格按此顺序给出）。假设我们的 FST 是：

A = (Q, Σ, Γ, Q ₀ , Q _F , α)
B = (P, Γ, Δ, P ₀ , P _F , β)

我们想找到

W = (R, Σ, Δ, R ₀ , R _F , ω) = A ∘ B

请注意，我们不需要确定 W 的字母；组合的定义就是这样做的。

想象一下串联运行 A 和 B，A 的输出磁带作为 B 的输入磁带馈送。组合 FST 的状态只是 A 和 B 的组合状态。换句话说，组合的状态是各个 FST 状态的叉积。

R = Q × P

在您的示例中， W 的状态将是整数对：

R = {(0,0), (0,1), ... (3, 2)}

尽管我们可以重新编号并获得（例如）：

R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}

类似地，组合 FST 的初始状态和接受状态是组件 FST 中的叉积。特别是，当 A 和 B 都接受字符串时，R 接受字符串。

R ₀ = Q ₀ × P ₀ 
R _F = Q _F × P _F

在示例中，R ₀ = {00} 和 R _F = {32}。

剩下的就是确定过渡关系ω。为此，将 A 的每个转换规则与 B 可能适用的每个转换规则结合起来。即，将 A的每个转移规则与 B 的每个以“γ”作为输入字符的规则组合。(q_i, σ) → (q_j, γ)

ω = { ((q _i ,p _h ), σ) → ((q _j , p _k ), δ) : (q _i , σ) → (q _j , γ) ∈ α,
                                     (p _h , γ) → (p _k , δ) ∈ β}

在该示例中，这意味着将（例如）0 1 a : bT1 与0 1 b : aT2的和组合1 2 b : a以获得：

00 11 一个：一个
01 12 一个：一个

同样，您可以将0 2 b : bT1 与相同的0 1 b : a和1 2 b : aT2 组合，0 0 a : a将 T1 与1 1 a : dT2 1 2 a : c&c 的和组合起来。

请注意，您可能有无法到达的状态（那些永远不会出现为“下一个”状态的状态）和永远不会发生的转换（那些来自无法到达的状态）。作为优化步骤，您可以删除这些状态和转换。但是，将它们留在里面不会影响构造的正确性；这只是一个优化。

score 4 · Accepted Answer

如果您更愿意接受图形解释，下面的一组幻灯片提供了实践中组合算法的增量图形示例，还包括对分量传感器中 epsilon 转换的讨论。Epsilon 转换使合成过程复杂化，并且在这种情况下，outis answer 中描述的算法可能不会生成正确的结果，具体取决于所使用的半环。

有关一些图形示例，请参见幻灯片 10~35：

score 1 · Accepted Answer

T1 和 T2

T1 和 T2 的组成

组合物T的状态是T1状态和T2状态的对。T 满足以下条件：

它的初始状态是T1的初始状态和T2的初始状态的对
它的最终状态是 T1 的最终状态和 T2 的最终状态的对
对于从 q1 到 r1 和 T2 从 q2 到 r2 的每一对转换 T1，存在从 (q1, q2) 到 (r1, r2) 的转换 t，使得 T1 的输出标签与 T2 的输入标签匹配。转换 T 从 T1 获取其输入标签，从 T2 获取其输出标签，其权重是 T1 和 T2 的权重的组合，该操作通过沿路径组合权重的相同操作完成。

由于没有权重，我们可以忽略这一点。上面是从下面一张漂亮的纸上摘下来的。链接在这里

3 回答 3