arXiv cs.CL· Rakesh Sengupta·· 12 小时前AI 评分20
逆向 Gold 定理：受基底约束的对比学习器如何仅凭正数据实现识别
A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners
AI 导读
研究者提出"逆向 Gold 定理"，证明在递归对比算子 R 与有界容量判别打分器满足忠实性条件时，仅用自生成扰动做 InfoNCE 式对比学习即可实现 PAC 条件识别，样本复杂度与容量、轨道大小、分数界及 1/ε 呈多项式关系。
正文 · AI 翻译
摘要：Gold 定理表明，仅凭正例呈现，没有任何学习器能够识别一个超有限类中的任意语言。我们证明了一个不同形式的正面结果。固定一个内在的\emph{递归对比算子} $R$，它将任意字符串映射为其结构上有界扰动的有限集合，以及一个容量有界的判别性评分器，该评分器通过 InfoNCE 风格的对比估计 \citep{vandenoord2018,macollins2018} 在自生成的扰动上训练。在关联算子、评分器和目标的忠实性条件下，训练后的评分器仅凭正数据即可实现 \emph{PAC 条件识别}：以高概率，它将除 $\varepsilon$ 比例之外的所有正例排在其自身轨道中每个语言外扰动之上，样本复杂度在容量、轨道大小、分数界和 $1/\varepsilon$ 上均为多项式。负例由学习器构造，而非由预言机提供，且从不计算字符串上的全局归一化常数。错误排序界来自对比损失的几何结构——逐样本损失下界加上错误排序下的确定损失增量——产生 $\varepsilon^{-2}$ 速率，以及一个显式近似间隙，该间隙量化了语言内（“碰撞”）扰动的代价，并在轨道纯算子下消失。在间隔条件下，排序保证可提升为全局成员分类器，且同一算子与学习到的评分器复合后是一个无需归一化的 Metropolis--Hastings 生成器。我们为可替换上下文无关语言 \citep{clarkeyraud2007} 和次正则类 \citep{heinz2010,hayashikamigaito2025} 实例化了这些假设，并提出了一个开放猜想，将该构造定位于轻度上下文敏感层级中。
| 学科： | 机器学习（stat.ML）；计算与语言（cs.CL）；机器学习（cs.LG）；神经元与认知（q-bio.NC） |
| MSC 分类号： | 68Q32 |
| ACM 分类号： | I.2.6 |
| 引用为： | arXiv:2610.28747 [stat.ML] |
| （或 arXiv:2610.28747v1 [stat.ML] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.28747 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Rakesh Sengupta [查看电子邮件]
[v1]
2026年10月20日星期二 18:00:47 UTC（28 KB）
来源：arXiv cs.CL · arxiv.org