揭开黑盒的面纱: 一种学习确定性加权自动机的新算法

在计算机科学和自然语言处理 (NLP) 领域，我们经常面对强大的“黑盒”模型。我们给它们一个输入，它们会给出一个输出——通常是一个概率分数或分类。但要理解它们 如何 得出这个结论却极其困难。这就是 自动机提取 的领域: 将复杂模型逆向工程为更简单、可解释的有限状态自动机 (FSA) 的过程。

几十年来，Dana Angluin 的 \(L^*\) 算法 (1987) 一直是学习正则语言的黄金标准。然而，最初的 \(L^*\) 是为布尔语言设计的——字符串要么“在”语言中，要么“不在”。现代 NLP 依赖于 加权 语言，其中字符串具有概率、成本或分数。

在这篇文章中，我们将深入探讨一篇最近的论文 “An \(L^*\) Algorithm for Deterministic Weighted Regular Languages” (一种用于确定性加权正则语言的 \(L^*\) 算法) , 它弥补了这一差距。作者提出了 Angluin 算法的一个忠实扩展，用于学习 确定性加权有限状态自动机 (WDFSA) 。 该方法在数学上非常优雅，适用于支持除法的代数结构 (半域) ，并保证能找到目标语言的最小自动机。

挑战: 从布尔到加权

为了理解这篇论文的贡献，我们首先需要了解我们要学习的对象。

加权正则语言

在标准的正则语言中，有限状态自动机接受或拒绝一个字符串。在 加权正则语言 中，自动机为宇宙 \(\Sigma^*\) 中的每个字符串分配一个值 (权重) 。

加权有限状态自动机 (WFSA) 由状态、转移和权重组成。当一个字符串穿过自动机的一条路径时，我们会组合转移的权重。

如下图所示，语言 \(\mathbf{L}_{\mathcal{A}}\) 对字符串 \(\boldsymbol{p}\) 的权重是所有有效路径 \(\pi\) 的总和 (\(\oplus\)) ，其中路径的权重是初始权重、转移权重和最终权重的乘积 (\(\otimes\)) 。

加权自动机生成语言的定义。

在这里，\(\lambda\) 代表初始权重函数，\(\rho\) 代表最终权重函数。路径仅仅是转移的序列:

自动机中路径的定义。

确定性的鸿沟

现有的学习加权自动机的算法通常使用称为“谱学习”的方法。然而，这些方法通常学习 非确定性 自动机 (同一个字符串可能存在多条路径) 。虽然功能强大，但非确定性模型更难解释和分析。

此外，以前的许多方法要求权重属于一个 域 (Field) (允许加、减、乘、除) 。本文将这一要求放宽到 半域 (Semifield) (不需要减法，但需要除法) 。这使得算法适用于更广泛的权重类别，如正实数或概率。

本文的目标是创建一个算法，能够:

  1. 学习 确定性 加权自动机 (WDFSA) 。
  2. 使用 主动学习 (查询预言机) ，类似于 Angluin 的原始方法。
  3. 在数学上保证找到 最小 自动机。

核心概念: 位似等价 (Homothetic Equivalence)

Angluin 原始 \(L^*\) 算法的精妙之处在于它如何决定何时两个前缀通向“同一个状态”。在布尔世界中，如果两个前缀 \(u\) 和 \(v\) 拥有相同的未来——即对于任何后缀 \(z\)，当且仅当 \(uz\) 在语言中时 \(vz\) 也在语言中，则这两个前缀通向同一个状态。

在加权世界中，我们不能要求未来的权重 完全相同。因为权重是沿路径相乘的，前缀 \(u\) 到达某个状态时的累积权重可能是 \(2\)，而前缀 \(v\) 到达同一状态时的累积权重可能是 \(4\)。它们的未来看起来会很相似，但 \(v\) 的一切都会相对于 \(u\) 缩放 \(2\) 倍。

作者引入了 位似等价 (Homothetic Equivalence) 来解决这个问题。如果两个函数 (或未来) 互为标量倍数，则它们是等价的。

位似等价的定义。

这种关系意味着，如果两个前缀 \(\mathbf{x}\) 和 \(\mathbf{z}\) 的“右语言” (它们的未来) 是位似等价的，则它们对应于底层确定性自动机中的同一个状态:

右语言的等价关系。

这一简单而强大的转变允许算法将行为上“成比例”相同的前缀归为同一个状态。

加权 \(L^*\) 算法

该算法使用一个 预言机 (Oracle) (一位教师) 。学习者可以问两类问题:

  1. 成员查询 (Membership Query) : “字符串 \(x\) 的权重是多少？”
  2. 等价查询 (Equivalence Query) : “这是我的假设自动机。它是正确的吗？” (如果不正确，预言机会提供一个反例) 。

学习者维护一个称为 经验 Hankel 矩阵 (\(\mathbf{H}\)) 的数据结构。

经验 Hankel 矩阵

可以将 Hankel 矩阵视为一个观测表。

  • 行 (\(P\)) : 代表前缀 (通向某个状态的字符串) 。
  • 列 (\(S\)) : 代表后缀 (未来的字符串) 。
  • 单元格: 值 \(\mathbf{H}(p, s)\) 是字符串 \(p \cdot s\) 的权重。

算法试图组织这个矩阵，以便代表相同状态的行被分组在一起。根据我们上一节的内容，如果两行 \(p\) 和 \(q\) 的行向量互为标量倍数，则它们代表同一个状态。

Hankel 矩阵中行的等价性。

从矩阵构建自动机

我们如何将矩阵变成机器？该算法直接从数据构建一个“朴素 Hankel 自动机”。

1. 状态: 状态是行索引 \(P\)。具体来说，它们是位似等价下的唯一行。

2. 转移: 为了计算从状态 \(p\) 在符号 \(a\) 上的转移权重，我们查看 \(pa\) 的未来的“总权重”与 \(p\) 的比率。作者将 \(d_{\mathbf{H}}(p)\) 定义为 \(p\) 行中条目的总和:

d_H 的定义，即 Hankel 矩阵中一行的和。

符号 \(a\) 的转移权重 \(w\) 是通过将目标行的总权重除以源行的总权重得出的:

通过除法计算转移权重。

这就是为什么代数结构必须是一个 半域——我们需要能够除 (或乘以逆元) 来归一化这些权重。

3. 初始和最终权重: 同样，初始和最终权重源自矩阵中的特定条目 (如空字符串 \(\varepsilon\)) ，并由行和进行归一化。

初始权重的定义。

最终权重的定义。

学习循环

算法迭代地优化 Hankel 矩阵，直到它代表一个有效的确定性自动机。这个过程涉及矩阵必须满足的两个主要属性: 一致性 (Consistency) 和 封闭性 (Closedness) 。

这是高层算法:

算法 1: 加权 L* 算法。

让我们分解内部循环:

1. 使其一致 (Making it Consistent)

一致性确保如果两行看起来是等价的 (是标量倍数) ，它们在每个字母表符号上的 转移 也必须指向等价的行。

在数学上，如果 \(p \sim_{\mathbf{H}} q\)，那么对于所有符号 \(a\)， \(pa\) 必须等价于 \(qa\)。

一致性条件。

如果矩阵违反了这一点 (即 \(p\) 和 \(q\) 现在看起来很像，但在看到符号 \(a\) 后分歧了) ，算法会调用 MAKECONSISTENT。这会向 \(S\) 添加一个新的后缀，以暴露 \(p\) 和 \(q\) 之间的差异，迫使它们进入不同的状态。

2. 使其封闭 (Making it Closed)

封闭性确保对于每个已知状态 (前缀 \(p\)) 和每个符号 \(a\)，结果状态 (前缀 \(pa\)) 都等价于我们在 \(P\) 中已经发现的某个状态。

如果系统通过转移发现了一种“新”类型的行，它会调用 MAKECLOSED 将该新前缀提升到集合 \(P\) 中。

3. 补全矩阵 (Completing the Matrix)

每当添加新的行或列时，算法会调用 COMPLETE (使用算法 2 中的子程序) ，通过向预言机询问新字符串的权重来填充空白单元格。

算法 2: 一致性、封闭性和补全的子程序。

从矩阵到最小自动机

一旦矩阵既封闭又一致，算法就会生成一个假设自动机 \(\tilde{\mathcal{A}}_{\mathbf{H}}\)。

这篇论文的一个关键理论贡献是证明了以这种方式推导出的自动机不仅仅是 一个 有效的自动机，而是该语言的 最小 确定性加权自动机。

作者定义了一个 转移正则等价关系 (transition-regular equivalence relation) 。 这确保了当我们把等价的行合并为单个状态时，转移权重保持一致。

转移正则性要求。

具体来说，转移权重必须在等价路径之间完美平衡:

转移正则性的权重相等。

该算法本质上计算了观测行为的商。结果自动机中的状态数量正好等于 Hankel 矩阵中唯一的“方向” (等价类) 的数量。

状态数等于 Hankel 矩阵中的等价类数量。

理论保证

论文为两个基本问题提供了严格的证明: 它会停止吗？它有多快？

终止性

作者证明了该算法总是会终止。在每一次假设不正确的情况下——无论是由于不一致、缺乏封闭性，还是来自预言机的反例——Hankel 系统的“维度”都会增加。

由于目标语言具有有限数量的状态 (假设为 \(N\)) ，矩阵的维度不可能永远增长。它的上限是最小目标自动机的大小。

相对于 Hankel 矩阵的状态复杂度界限。

复杂度

复杂度取决于 \(N\) (目标自动机中的状态数) 、\(M\) (最长反例的长度) 和 \(|\Sigma|\) (字母表大小) 。

运行时间复杂度的主要项推导如下:

算法的运行时间复杂度。

该算法相对于目标自动机的大小和字母表的大小在多项式时间内运行。这是 \(L^*\) 类型算法的标准结果，证实了这种加权扩展对于合理规模的正则语言在计算上是可行的。

结论与意义

本文成功地将 Angluin 的主动学习范式扩展到了半域上的 确定性加权自动机 领域。通过利用 位似等价 , 作者提供了一种将“成比例相似”的状态分组的方法，从而实现了对加权语言的精确学习，其中权重可以代表概率、持续时间或成本。

为什么这很重要?

  1. 可解释性: 我们可以使用此算法从在常规任务上训练的黑盒循环神经网络 (RNN) 或 Transformer 中提取确定性自动机。由于输出是确定性的，它比谱学习的非确定性输出更容易分析。
  2. 理论基础: 它弥合了代数自动机理论 (通过商最小化) 和机器学习 (通过查询进行主动学习) 之间的差距。
  3. 通用性: 通过使用半域 (需要除法但不需要减法) ，它支持现代 AI 应用中广泛使用的各种权重类型。

对于那些希望窥探现代神经模型黑盒内部，将复杂的连续向量空间转化为清晰、离散且可理解状态的人来说，这项工作是一个强有力的工具。