基于简洁机器无关轨迹的语言识别

# 基于紧凑机器无关迹的语言识别 来源: https://arxiv.org/html/2607.12443 \\coltauthor\\Name Moses Charikar\\Emailmoses@cs\.stanford\.edu \\addrStanford University and\\NameJon Kleinberg\\Emailkleinberg@cornell\.edu \\addrCornell University and\\NameChirag Pabbaraju\\Emailcpabbara@cs\.stanford\.edu \\addrStanford University ###### 摘要 受大语言模型能力的驱动，Gold-Angluin 的语言极限识别模型重新引起关注，研究者着眼于可能克服原始模型否定结果的变体。近期关于此问题的论文提出将**计算迹** 和**标注** 作为学习器的额外能力来源，这反映了经验规律：例如，带有注释的源代码比任意源代码更容易学习，而带有算法生成的链式思维令牌的文本比原始文本本身更容易学习。这些近期工作在存在此类计算迹的情况下取得了语言识别的正面结果，但这些正面结果中的迹来自生成该语言的显式自动机理论机器模型，且迹的底层令牌词汇规模非常大。在本文中，我们解决该研究方向留下的两个基本问题：我们能否使用仅含小字母表的迹取得正面结果？我们能否直接从语言本身定义迹，而无需依赖生成它的底层机器模型？我们对这两个问题都建立了正面结果：对于任意语言集合，我们展示了如何定义计算迹，使其能够实现极限识别，使用的令牌字母表大小与语言定义所用字母表大小呈线性关系，且独立于语言的任何其他属性。 ###### 关键词: 语言模型，极限识别，计算迹 ## 1 引言 大语言模型成功激励了多条近期研究方向，探索可能揭示其如何从所用训练数据和训练管道中实现强性能的理论模型。其中一条研究路线从 Gold 关于**语言极限识别** 的经典模型出发（Gold, 1967 (https://arxiv.org/html/2607.12443#bib.bib5)），在该模型中，语言学习任务被视为对手与算法之间的博弈：对手选择一个秘密语言 KKK，已知它仅来自可数候选列表 L1,L2,L3,…L\_\{1\},L\_\{2\},L\_\{3\},\\ldots；对手以任意顺序111KKK 的有效枚举 x1,x2,…x\_\{1\},x\_\{2\},\\dotsc 满足：(1) xi∈Kx\_\{i\}\\in K，对所有 i；且 (2) ∀x∈K\\forall x\\in K，存在 i 使得 xi=xx\_\{i\}=x。枚举 KKK 的字符串；在每一步 ttt，算法猜测真实语言的索引 iti\_\{t\}；若存在某个时刻 t∗t^\{\*\}，使得对所有 t≥t∗t\\geq t^\{\*\}，有 Lit=KL\_\{i\_\{t\}\}=K——即算法从 t∗t^\{\*\} 开始的每一步都正确——则算法获胜（它已**在极限内识别** 了 KKK）。Gold 框架中的主要结果，始于 Gold 关于其模型的原始定理，都是否定的（Gold, 1967 (https://arxiv.org/html/2607.12443#bib.bib5)）；对于除高度受限语言族之外的所有情况（远低于正则语言类），算法无法赢得博弈（Angluin, 1980 (https://arxiv.org/html/2607.12443#bib.bib1)）。然而，真实语言模型似乎比这些广泛的否定结果所暗示的强大得多，因此问题转向寻找该模型上合理的变体，使我们在其中能够获得与实践成功更一致的正面结果。 #### 计算迹。近期一条有前途的研究方向探索了**标注** 或**计算迹** 在帮助解决语言极限识别问题中的能力（Papazov and Flammarion, 2025 (https://arxiv.org/html/2607.12443#bib.bib7)；Bhattamishra et al., 2026 (https://arxiv.org/html/2607.12443#bib.bib2)；Peng et al., 2026 (https://arxiv.org/html/2607.12443#bib.bib8)）。这些模型受以下观察的驱动：训练语料库通常包含通过某种元数据、思维痕迹或领域相关标注而丰富了的文本或序列数据。这包括数据本身具有此类支持信息的情况，例如从带有注释的源代码语料库学习比任意源代码更有效，或者从数学证明包含逐步论证的语料库学习更有效。它还包括数据经算法标注的情况，例如**链式思维** 及相关方法的成功（Wei et al., 2022 (https://arxiv.org/html/2607.12443#bib.bib10)）。这一系列例子表明，如果训练数据标注有某种计算迹，学习器在该语料库上可以更有效。这些近期模型从假设候选语言具有自动机理论基础开始——例如，它们由未知的有限状态机、下推自动机或图灵机生成——并且所讨论的标注由机器自身的计算迹产生。先前的工作用这种方法获得了可能性结果。然而，该研究方向留下了两类基本问题。首先，他们所描述的标注是细粒度且庞大的：一种情况下用底层机器的状态表示（Peng et al., 2026 (https://arxiv.org/html/2607.12443#bib.bib8)），另一种情况下用词汇的幂集表示，导致指数级膨胀（Bhattamishra et al., 2026 (https://arxiv.org/html/2607.12443#bib.bib2)）。其次，这些模型的前提是标注直接与产生该语言的自动机相关联；它留下了以下问题：当我们无法访问底层机器模型时，如何有效标注以助识别？相比之下，我们在实践中看到的标注或计算迹往往并非来自底层机器模型，而是更多地作为独立客体设计，自带词汇，且比机器架构的完整状态集粗糙得多。例如，在注释代码中，正是注释形成了帮助学习语料库的额外令牌；而链式思维中，正是思考令牌提供了这种帮助。这两者都不对应于产生训练数据的底层机器的状态，即便存在这样的机器。如果我们把迹中的令牌视为具有这种粗粒度结构，且独立于任何特定机器模型，那么计算迹的理论会是什么样子？我们还能获得语言极限识别的可能性结果吗？ #### 本文工作：紧凑、机器无关的迹。在本文中，我们发展这样的理论，并展示使用一小套令牌——独立于底层机器状态集大小——的标注足以实现语言极限识别。此外，我们构建标注的方式在语言本身层面操作，不假定了解产生该语言的任何底层机器。我们将在后续章节详细描述模型，但这里先给出一个高层次概述。作为起点，考虑早期基于机器的模型如何在有限自动机情况下定义计算迹：当自动机从左到右逐符号处理字符串时，迹报告每个符号处的自动机状态。这种迹具有性质：若 x=x1x2...xnx=x\_\{1\}x\_\{2\}\\ldots x\_\{n\} 是输入字符串，则迹用标注符号 cic\_\{i\}（对应此时自动机的状态）标注每个输入符号 xix\_\{i\}；并且由于 cic\_\{i\} 是状态，它只取决于直到该点的前缀 x1x2...xix\_\{1\}x\_\{2\}\\ldots x\_\{i\}，而非任何后续符号。我们将其用作迹的定义性质：我们说一个**迹着色函数** cc 定义在有限颜色集合 PP（“调色板”）上，是将有限字符串映射到 PP 元素的函数，并定义字符串 x=x1x2...xnx=x\_\{1\}x\_\{2\}\\ldots x\_\{n\} 的**颜色迹** 为 cc 应用于其每个前缀的值： tracec(x):=(c(ε),c(x≤1),c(x≤2),...,c(x≤n))\\displaystyle\{\\mathrm\{trace\}\}\_\{c\}\(x\):=\(c\(\\varepsilon\),c\(x\_\{\\leq 1\}\),c\(x\_\{\\leq 2\}\),\\dots,c\(x\_\{\\leq n\}\)\)\(1\) 其中 x≤ix\_\{\\leq i\} 表示前缀 x1x2...xix\_\{1\}x\_\{2\}\\ldots x\_\{i\}，ε\\varepsilon 表示空串。用产生它的有限自动机的状态对 xx 进行着色，是产生这种迹着色的方式之一，但此处的定义表明，我们可以将其定义为任何语言的标注方案，即使我们不知道底层机器模型，甚至根本不存在这样的机器。（这与注释或思考令牌可以标注训练语料库中的字符串，尽管它们与最初产生该字符串的生成机制毫无对应关系，是同一个道理。） #### 利用迹进行识别。我们希望使用这些迹实现极限识别，并且进一步，使用小的调色板，这样我们就不需要像细粒度状态集那样庞大的字母表来提供标注。形式上，给定一个极限识别实例，其候选语言为 L1,L2,L3,…L\_\{1\},L\_\{2\},L\_\{3\},\\ldots，我们考虑一个过程：首先，每个语言 LiL\_\{i\} 由其自身的迹着色函数 cLic\_\{L\_\{i\}\} 标注，然后对手枚举字符串 x∈Kx\\in K，每个字符串以标注对 (x,tracecK(x))(x,\\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\)) 出现。这是否足以实现极限识别，即使没有底层机器模型？我们证明是足够的：存在一个算法 A\\mathcal\{A\}，使得对于任何候选语言集合 L1,L2,L3,…L\_\{1\},L\_\{2\},L\_\{3\},\\ldots，存在迹着色函数 cL1,cL2,cL3,…c\_\{L\_\{1\}\},c\_\{L\_\{2\}\},c\_\{L\_\{3\}\},\\ldots 的选择，使得 A\\mathcal\{A\} 在接收到来自对手语言 KKK 枚举的有序对 (x,tracecK(x))(x,\\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\)) 时，能够实现极限识别。此外，所需的迹着色可以使用非常少的颜色构建：对于字母表大小为 kk 的问题实例，存在一种算法使用最多 k+1k\+1 大小的调色板实现这一点。即使在语言来自底层机器模型的情况下，这也是一个独立于这些机器状态数的界，而对于无穷语言族，状态数必然无界增长。因此，与早期方法提出的计算迹相比，这是一种资源高效得多的计算迹构建——并且适用范围更广。我们通过建立迹着色允许极限识别时的一个精确组合刻画来证明这一结果，然后将其松弛为一个相关的充分条件，并展示如何实现该条件。这一充分条件本身具有有趣的组合解释，我们在二元字母表（k=2k=2）情况下证明了该条件的匹配上下界：我们的结果显示如何用 k+1=3k\+1=3 种颜色实现所需条件，并证明 2 种颜色不足。我们进一步探索了结果的扩展，包括当迹可被有限程度破坏时，极限识别仍然可能（使用更大的调色板）；以及当候选语言 L1,L2,L3,…L\_\{1\},L\_\{2\},L\_\{3\},\\ldots 是正则语言时，我们可以使用仅含两种颜色的迹着色函数实现极限识别。 ### 1.1 主要结果 给定一个语言集合222假设集合中所有语言非空。C\\mathcal\{C\}，我们的目标是将 C\\mathcal\{C\} 中的每个语言 LL 与一个合适的迹着色函数 cLc\_\{L\} 相关联，使得当每个 x∈Lx\\in L 都伴随 tracecL(x)\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\) 时，集合 C\\mathcal\{C\} 变为极限可识别的。为此，作为我们的第一个贡献，我们推导了使用颜色迹实现极限识别可能性的精确刻画。该刻画在结构上类似于 Angluin 的条件（Angluin, 1980 (https://arxiv.org/html/2607.12443#bib.bib1)）用于极限识别，但额外考虑了输入中看到的颜色迹；证明见\\Crefsec:characterization\-appendix。 ###### 定理 1.1（带颜色迹的极限识别刻画）。设 C\\mathcal\{C\} 是一个可数语言集合。那么，C\\mathcal\{C\} 在给定迹着色函数族 {cL}L∈C\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\} 的颜色迹下是极限可识别的，当且仅当对每个语言 L∈CL\\in\\mathcal\{C\}，存在一个有限“告密”子集 TL⊆LT\_\{L\}\\subseteq L，使得对每个是 LL 真子集的语言 L′∈CL^\{\\prime\}\\in\\mathcal\{C\}，要么 (1) L′L^\{\\prime\} 不包含 TLT\_\{L\}，要么 (2) 存在 x∈L′x\\in L^\{\\prime\} 使得 tracecL′(x)≠tracecL(x)\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)。 上述刻画为构建迹着色函数 {cL}L∈C\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\} 给出了精确的目标。或许令人惊讶的是，我们的下一个结果——这也是本文的主要结构结果之一——表明，对于每个语言集合，我们可以构建使用小调色板的迹着色函数，并且这些函数**总是** 满足上述要求 (2)。 ###### 引理 1.2（着色引理）。设 C\\mathcal\{C\} 是有限字母表 Σ\\Sigma（大小为 kk）上的一个语言集合。存在迹着色函数 {cL}L∈C\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}，映射到大小为 k+1k\+1 的调色板 PP，并满足以下“可区分着色条件”：对于满足 L⊊L′L\\subsetneq L^\{\\prime\} 的任意 L,L′∈CL,L^\{\\prime\}\\in\\mathcal\{C\}，存在 x∈Lx\\in L 使得 tracecL(x)≠tracecL′(x)\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)。 我们还证明，我们的迹着色函数对于二元字母表达到满足可区分着色条件所需的最优调色板大小（\\Crefprop:2\-coloring\-lower\-bound\-for\-sufficient\-condition）：即，存在一个（有限的）二元字母表上的语言集合，任何满足可区分着色条件的迹着色函数集必然需要三种颜色。鉴于我们的迹着色函数确保了 \\Crefthm:characterization\-identification\-with\-traces 中刻画条件的要求 (2) 总是成立，告密集不再是必要的，我们得到主要结果： ###### 定理 1.3（识别