无需机器模型：简洁轨迹实现语言识别新突破

背景

语言识别（Language Identification in the Limit）是 Gold 和 Angluin 提出的经典计算学习理论模型，其核心问题是：学习器能否在观察无限多字符串样本后，最终正确推断出目标语言（即该语言对应的语法或自动机）。该模型的原始设定在可学习性上存在许多负面结果，例如，任何超有限的语言类都无法在被呈现所有正例后收敛到一个唯一的语法。然而，随着大语言模型（LLM）展现出强大的学习能力，研究者重新审视这一经典模型，并探索通过引入计算轨迹（computational traces） 或注释（annotations） 来增强学习器的能力。这类思路源于实际观察：带有注释的源代码比裸代码更易学习，而用算法生成的链式思维（chain-of-thought）令牌标注的文本也比原始文本更易理解。最近的工作表明，当训练字符串附带这类计算轨迹时，语言识别可以取得正面结果。但已有的正面结果所依赖的轨迹来自显式的自动机理论机器模型（如有限自动机、下推自动机等），且轨迹使用的令牌字母表非常大。这留下了两个关键开放问题：（1）能否仅用很小的字母表来定义轨迹并实现正面结果？（2）能否不依赖底层机器模型，直接从语言本身定义轨迹？本文正是针对这两个问题展开研究。

核心内容

该论文（arXiv:cs.CL，2026年7月提交）聚焦于在 Gold-Angluin 语言识别模型中引入简洁且与机器无关的计算轨迹。作者指出，近期在带计算轨迹的语言识别方面取得的正面结果，所使用的轨迹都源自显式的自动机理论机器模型（如有限自动机、下推自动机等），并且这些轨迹的底层令牌词汇表（alphabet）非常大。这既限制了轨迹的普适性，也使得算法的复杂度依赖于特定机器模型。

本文的核心贡献是解决了上文提到的两个开放问题：

1. 小字母表轨迹：作者证明，即使使用仅包含与底层语言字母表大小成线性关系（即 O(|Σ|)）的令牌字母表，也能为任意语言集合定义计算轨迹，使得学习器能够在极限内实现语言识别。这意味着轨迹的符号集不再需要依赖特定机器模型的大型状态集合，而是可以用非常有限的标记表示。

2. 与机器无关的轨迹：作者进一步展示，可以直接从语言本身定义这些轨迹，而无需借助任何生成该语言的底层机器模型（如自动机、图灵机等）。这相当于将计算轨迹的概念从“机器执行的步骤”提升为“语言的结构性注释”，使得轨迹的构造不依赖于具体的计算模型，具有更强的通用性。

具体而言，对于任意的语言集合 L（定义在有限字母表 Σ 上），作者构造了一种映射，将每个字符串 x 映射为一个带注释的序列 τ(x)，该序列由两部分组成：原始字符串 x 加上一组来自一个小型辅助字母表 Δ 的令牌（∣Δ∣ = O(∣Σ∣)）。这些令牌编码了关于字符串 x 在语言中的“位置”信息（例如，通过某种枚举方式给出该字符串在语言中的索引，或者通过前缀树上的某种标记）。作者证明，在这样的注释下，存在一个学习器（算法）能够根据无限递增的带注释字符串序列，在极限内正确识别出目标语言。该结果不依赖于任何特定的自动机族，因此是“与机器无关”的。

论文的正式陈述为：对于任意语言集合 L ⊆ Σ*，都存在一个计算轨迹方案，使得学习器可以在极限内识别 L，且轨迹的字母表大小与 ∣Σ∣ 成线性关系。该构造是通用的，适用于所有可能的语言类（包括不可数无穷类），从而扩展了之前只能在特定自动机模型（如确定有限自动机、下推自动机等）上取得的正面结果。

关键要点

• 核心问题：能否用更小的令牌字母表（与底层语言字母表大小线性相关）以及不依赖底层机器模型的轨迹，在 Gold-Angluin 模型中实现语言识别？
• 主要结果：对于任意语言集合，都可以构造出满足上述条件的计算轨迹，使学习器能在极限内识别语言。
• 轨迹构造方法：轨迹的令牌字母表大小仅为 O(∣Σ∣)，且构造过程完全基于语言本身（例如利用字符串的某种枚举顺序或前缀结构），无需自动机等机器模型。
• 与先前工作的关系：先前正面结果依赖特定自动机模型且使用大型字母表（通常与自动机状态数有关），本文消除了这两种限制，使轨迹更简洁、更通用。
• 适用范围：该结果适用于所有语言类，包括非递归可枚举、甚至不可数无穷语言类，但主要关注的是可计算或可枚举的语言集合。

意义与影响

本文在语言识别理论方面迈出了重要一步。它表明，即使不使用复杂的机器模型，仅通过语言本身附加的少量信息（即一个小型字母表的注释），就能使极限识别成为可能。这为理解大语言模型为何能从带注释的文本（如包含思考链、注释代码等）中更有效地学习提供了理论支撑。此外，与机器无关的轨迹定义使得该框架可以应用于任何计算或学习场景，而不必假设特定的底层机器架构。这一结果也重新激发了人们对 Gold-Angluin 模型及其变体的兴趣，并可能启发更高效的语言学习算法设计——尤其是在处理大规模、带结构注释的数据时。从理论角度看，它缩小了“不可学习性”负面结果与实践中观察到的学习能力之间的鸿沟，为计算学习理论提供了新的思路。