Gold定理被打破！新方法仅凭正数据就能识别语言，样本复杂度多项式级
A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners
📖 AI 总结
这篇论文提出并证明了一个与Gold定理方向相反的正面结果。Gold定理表明，仅凭正例无法识别超有限类中的任意语言；作者则证明，在给定一个递归对比算子（将任意字符串映射为其结构受限扰动的有限集合）和一个有界容量的判别评分器、并通过InfoNCE式对比估计在自生成扰动上训练的条件下，只要算子、评分器与目标之间满足忠实性条件，评分器就能仅从正数据实现PAC条件识别：以高概率将除ε比例外的所有正例排在其自身轨道内的所有语言外扰动之上，样本复杂度与容量、轨道大小、分数界及1/ε成多项式关系。负例由学习器自行构造而非外部提供，且无需计算全局归一化常数。误排序界由对比损失的几何性质推出，速率为ε的负二次方，并给出量化语言内碰撞扰动代价的显式近似间隙，该间隙在轨道纯算子下消失。排序保证在间隔条件下可提升为全局成员分类器，同一算子与学习评分器组合还可构成免归一化的Metropolis-Hastings生成器。作者在可替换上下文无关语言和次正则类上实例化了假设，并提出一个开放猜想以定位该构造在轻度上下文敏感层级中的位置。
🔑 关键词速览
| Gold定理 | 语言识别理论中的经典结果，指出仅从正例无法识别超有限类中的任意语言。 |
| 递归对比算子 | 一种将字符串映射到其结构有界扰动有限集的函数，用于生成对比学习中的正负样本。 |
| InfoNCE | 一种对比估计损失函数，通过区分正样本和负样本训练评分器。 |
| PAC条件识别 | 在可能近似正确框架下，以高概率对正例进行条件性识别，允许ε比例的错误。 |
| Metropolis-Hastings生成器 | 一种马尔可夫链蒙特卡洛采样方法，此处结合学习到的评分器实现无归一化的生成。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅