Contrastive Identification and Generation in the Limit

技术摘要：极限下的对比识别与生成

问题定义
本文开启了极限下对比识别与生成的学习理论研究。作者弥补了经典极限学习模型（Gold, 1967; Angluin, 1980）与近期生成模型（Kleinberg and Mullainathan, 2024）之间的空白，后者依赖于正例流（文本）或完全标记的数据（信息源）。在许多自然场景中——例如 A/B 测试、对比实验以及相似性 - 相异性标注——数据以无序对 $\{x, y\}$ 的形式到达，学习者知道这些示例在目标假设 $h$ 下不一致（即 $h(x) \neq h(y)$），但不知道哪个元素是正的（$h(x)=1$），哪个是负的（$h(x)=0$）。

学习者观察到一系列此类对比对，这些对最终覆盖每一个正例（正侧覆盖），但从不显式标记单个点。目标是确定学习者在何种条件下能够：

1. 识别来自已知类 $\mathcal{H}$ 的目标假设 $h$（收敛至正确的假设）。
2. 生成 $h$ 的新正例（输出流中尚未出现的 $\text{supp}(h)$ 中的元素）。

方法论与技术框架
核心的技术贡献是引入了公共交叉图，记为 $\Gamma(h, g) = \Delta(h) \cap \Delta(g)$，其中 $\Delta(h)$ 是所有跨越由 $h$ 定义的割的集合。该图编码了假设之间的成对模糊性：如果某一对是 $h$ 和 $g$ 的有效观测，则 $\Gamma(h, g)$ 中存在一条边。

作者将该几何对象应用于三个尺度：

• 成对：分析两个假设之间的可消除性。
• 有限族：通过共享呈现分析生成障碍。
• 无限缺陷集：分析对对抗性破坏的鲁棒性。

本文利用了一种图论翻译，其中成对对比模糊性被简化为覆盖问题：假设 $g$ 无法从 $h$ 中被消除，当且仅当 $h$ 的支持集被 $\Gamma(h, g)$ 中边所关联的顶点所覆盖。

主要贡献与结果

1. 对比识别 (CtrId) 的精确刻画
本文提供了类 $\mathcal{H}$ 可从对比数据中识别的必要且充分条件。一个类属于 CtrId 当且仅当：

• 它是文本可识别的（满足 Angluin 的“特征线索”条件）。
• 重叠覆盖条件：$\mathcal{H}$ 中每一对不可比的假设必须形成“重叠覆盖”。这意味着它们的支持集必须相交（$\text{supp}(h) \cap \text{supp}(g) \neq \emptyset$），且它们的并集必须覆盖整个示例空间（$\text{supp}(h) \cup \text{supp}(g) = X$）。
• 推论：对比数据引入了新的障碍：如果两个假设不可比、不相交，或者相交但未覆盖整个空间，则无法区分它们。

2. 对比生成与闭包维数
作者引入了对比闭包维数 ($C^\Delta$)，这是一个与正数据的闭包维数（Raman et al., 2025）类似的组合维数。

• 定义：$C^\Delta(\mathcal{H})$ 是有限“空心”边集大小的上确界（这些边集强制在观测顶点之外不产生新的正元素）。
• 结果：一个类 admit 一个统一对比生成器，当且仅当 $C^\Delta(\mathcal{H}) < \infty$。紧致的样本复杂度为 $C^\Delta(\mathcal{H}) + 1$。
• 非统一生成：如果一个类可以分解为具有有限对比闭包维数的子类链，则该类是非统一可生成的。
• 障碍：本文识别了“有限族障碍”，即一组假设 admit 一个共享的对比呈现，其支持集交集有限，从而阻碍了新元素的生成。

3. 钻石层级
在具有均匀无界支持 (UUS) 的可数类上，四个学习族形成了一个严格的钻石层级，而非线性链：

• 严格包含：$\text{CtrId} \subsetneq \text{CtrGen}$ 且 $\text{CtrId} \subsetneq \text{TxtId}$。$\text{CtrGen}$ 和 $\text{TxtId}$ 均被严格包含在 $\text{TxtGen}$ 中。
• 不可比性：$\text{CtrGen}$ 和 $\text{TxtId}$ 是相互不可比的。
  • TxtId $\not\subseteq$ CtrGen：具有不相交支持的类是文本可识别的，但受限于有限交集障碍，无法进行对比生成。
  • CtrGen $\not\subseteq$ TxtId：具有“穿孔支持”（从无限集中移除一个元素）的类可以通过最终核心进行对比生成，但缺乏用于文本识别的有限特征线索集。

4. 对抗性破坏下的鲁棒性反转
本文证明了在有限对抗性破坏下，识别模式之间关系的急剧反转：

• 文本脆弱性：单个被污染的正例就足以使一个类在文本设置中变得不可识别。
• 对比鲁棒性：作者定义了一个缺陷数 $\kappa(h \to g)$，计算在 $h$ 的任何有效呈现中，假设 $g$ 被强制违反的最小次数。如果 $\kappa(h \to g) = \infty$，则任何有限破坏都无法掩盖这些违反。
• 共单例类：每个假设将所有示例标记为正，仅有一个“空洞”的类，在对比设置下（使用“缺失计数”算法）对于任何有限破坏预算都是可识别的，但在文本设置下，即使仅一次破坏也是不可识别的。
• 结果：对于每个 $k \ge 1$，$k$-污染对比识别与 $k$-污染文本识别是相互不可比的。

意义与主张
本文主张，公共交叉图作为一个统一的技术对象，用单一语言编码了成对模糊性、族级生成障碍以及破坏缺陷。作者认为，虽然对比数据中方向的缺失在干净设置中是一个弱点（相比文本引入了新的障碍），但在对抗性破坏下却成为一种优势，因为被污染的成对数据会产生结构上可检测的“非边”，从而违反异或 (XOR) 约束。

这项工作表明，当观测值非单点时，经典极限学习范式可以得到富有成效的细化，揭示了一种双向图论结构：在干净环境下相对于标记数据成本高昂，但在对抗性扰动下具有保护性。本文明确指出，其针对识别和非统一生成的构造是信息论层面的（依赖于特征线索族或维数链的存在性），并将更广泛类的有效构造过程问题留作开放问题。