两个维度主导不可知多类转导学习

# 两个维度支配不可知多类转导学习  
来源：https://arxiv.org/html/2608.25326  

###### 摘要  
在转导分类中，对手固定一个带标签群体，其中一个标签被均匀隐藏，学习者看到所有剩余标签。对于二分类问题，不可知转导学习与PAC学习具有相同的极小极大速率。这一结论是否能推广到多类学习，尤其是在标签空间无界（此时一致收敛可能失效）的情况下，仍是一个开放性问题。我们将该问题解决至对数因子误差范围内。对于任意多类假设类H，其DS维度为d_DS，Natarajan维度为d_N，则最优的不可知转导超额误差满足 Θ̃(d_DS/n + √(d_N/n))。该结果对任意标签空间均成立。两项缺一不可：DS伪立方体提供了可实现情况下的d_DS/n阻碍，而带有重复点及公平标签的Natarajan立方体则提供了不可知情况下的√(d_N/n)阻碍。上界证明使用了随机预留原理：学习者刻意忽略可见标签中的一个固定比例，使真实测试点在一个大块未见区域中均匀分布。我们结合了可实现压缩、标签空间缩减以及跨有限群体划分的菜单内不可知压缩。一个无放回乘法权重引理保留了快速收敛的d_DS/n项。因此，不可知多类PAC学习与转导学习在对数因子内服从相同的二维法则。  

## 1 引言  
转导模型聚焦于数据相关情况下最简单的预测问题之一。对手选择n个带标签样本，其中一个索引被均匀随机隐藏。学习者观察完整的无标签群体及除隐藏标签外的所有标签，随后预测该标签。其损失与基准假设类中最佳固定假设的经验损失进行比较。对于可实现分类，转导学习与单包含图及PAC学习紧密相关（Haussler 等, 1994; Daniely 与 Shalev-Shwartz, 2014; Asilis 等, 2024）。不可知情形更为微妙：学习者必须在每个对抗性群体上与最佳假设进行加法竞争。从PAC学习器到转导学习器的通用转换会在样本复杂度上损失1/ε因子（Asilis 等, 2024）。另一方面，从转导到PAC学习的最新转换仅产生与类别无关的验证成本（Dughmi 等, 2025）。对于二分类问题，不可知单包含图的对称化完成了逆向证明，并给出最优速率Θ(√(d/n))，其中d为VC维度。相应的多类问题则悬而未决。  

多类学习在任意标签空间上还面临一个额外困难：没有单一维度能控制其不可知样本复杂度。DS维度刻画了可实现可学习性（Daniely 与 Shalev-Shwartz, 2014; Brukhim 等, 2022）。近期研究表明，Natarajan维度在小超额不可知情形下再次出现（Cohen 等, 2026）。随后的精确密度定理消除了DS项中剩余的多项式差距（Pabbaraju, 2026）。综合这些结果，不可知PAC样本复杂度（忽略对数因子）为 d_DS/ε + d_N/ε²。但这些进展本身并未给出转导学习器。PAC证明对独立样本取平均，而转导保证必须对每个固定群体成立。特别是，在有限重构族上进行经验最小化时，即使族仅含n个成员，其留一误差也可能为常数。这正是该开放问题背后的不稳定性。  

我们证明，两个模型仍具有相同的多类速率（忽略对数因子）。记ε_tr_H(n)为最优的不可知转导超额误差。主定理表明：  
c·min{1, d_DS/n + √(d_N/n)} ≤ ε_tr_H(n) ≤ C·min{1, d_DS·log²(en)/n + √(d_N·log³(en)/n)}。  

该结果允许标签空间无限或不可数。上界基于对可见样本使用方式的简单调整：给定隐藏索引后，学习者从n-1个可见样本中选取三个不相交的随机块，并忽略所有其他可见标签。等价地，可先从未见部分中均匀选择隐藏索引。被忽略的点将单个隐藏标签转化为一个大未见块中的均匀随机点，从而在无需留一稳定性的前提下实现有限群体泛化。随后，我们改编了Cohen等（2026）的三阶段标签空间缩减方法：第一阶段通过可实现压缩创建有限覆盖；第二阶段使用乘法权重缩减逐点标签空间；第三阶段执行菜单内不可知压缩。两个标准压缩论证可转移到随机划分中，而关键的新要素是有限群体乘法权重引理。尽管样本是无放回抽样，但被采样专家获得的期望奖励数为常数，因为每个专家只能覆盖群体中一个互不相交的部分。这保留了1/n逼近项。  

下界揭示了为何两个维度在转导模型中均不可或缺。对于Natarajan项，我们复制每个被破碎的点并独立分配其两个见证标签之一，隐藏标签为独立公平比特位，而最佳假设在观察整个群体后选择各块多数标签。对于DS项，我们定向伪立方体的坐标纤维：即使群体通过重复填充，每个定向的平均出度仍与伪立方体维度成正比。  

我们的结果解决了Dughmi等（2025）提出的多类开放问题实例。它足够具体以利用多类学习的结构，但并未给出针对任意有界损失的通用PAC到转导的黑箱转换。不过，随机预留论证可能在任何PAC构造通过有限重构族分解时都有用。  

#### 贡献  
1. 我们通过独立的DS和Natarajan项，将不可知多类转导误差刻画至对数因子误差范围内，适用于任意标签空间。  
2. 我们引入一种随机预留缩减方法，将结构化的三阶段PAC学习器转移到每个固定有限群体。  
3. 我们证明了一个无放回乘法权重菜单引理，其错过概率为O(log|F|/n)。  
4. 我们基于Natarajan立方体和DS伪立方体给出了直接的转导下界。  

## 2 设定与主结果  
记X为实例空间，Y为任意标签空间，H⊆Y^X非空。一个带标签群体为S=(z₁,…,zₙ)∈(X×Y)ⁿ，其中zᵢ=(xᵢ, yᵢ)。允许重复实例和重复带标签样本。记 L_S(h) = (1/n)Σᵢ₌₁ⁿ 𝟙{h(xᵢ)≠yᵢ}。  

一个随机化转导学习器接收完整实例序列x₁:n、索引i及带标签序列S₋ᵢ，输出xᵢ的标签。其在S上的不可知超额误差为：  
ℰ_S(A) = (1/n)Σᵢ₌₁ⁿ ℙ_A{A(x₁:n, S₋ᵢ, i) ≠ yᵢ} - min_{h∈H} L_S(h)。  

最坏群体下的最优误差为 ε_tr_H(n) = inf_A sup_{S∈(X×Y)ⁿ} ℰ_S(A)。这与Asilis等（2024）及Dughmi等（2025）的不可知转导准则一致。  

我们回顾两个维度。序列x₁:d被称为Natarajan破碎的，若存在对aⱼ≠bⱼ使得H|_{x₁:d}包含∏ⱼ{aⱼ, bⱼ}中的所有向量。最大d即为Natarajan维度d_N（Natarajan, 1989）。一个有限非空集F⊆Y^d称为d维伪立方体，若每个f∈F都有一个仅在坐标j处不同的邻居，对所有j∈[d]成立。H的迹包含此类伪立方体的最大d即为DS维度d_DS（Daniely 与 Shalev-Shwartz, 2014; Brukhim 等, 2022）。  

###### 定理1（二维转导法则）  
存在普适常数c, C>0，使得对所有非空H⊆Y^X及n≥2，有：  
ε_tr_H(n) ≥ c·min{1, d_DS/n + √(d_N/n)}，  
ε_tr_H(n) ≤ C·min{1, d_DS·log²(en)/n + √(d_N·log³(en)/n)}。  

约定：当d_DS=∞时上界无效；Natarajan维度为零的类具有零转导超额误差。  

定义 m_tr_H(ε) = min{n : sup_{N≥n} ε_tr_H(N) ≤ ε}。逆速率为：  

###### 推论2（PAC与转导速率）  
忽略多项对数因子，有 m_tr_H(ε) = Θ̃(d_DS/ε + d_N/ε²)。  

这与不可知PAC学习的双参数法则相同，由Cohen等（2026）与Pabbaraju（2026）组合得到。  

#### 为何通用ERM转换失效  
假设学习器在n-1个可见标签上训练一个有限族上的经验最小化器。即使有一个完美比较器且仅添加n个假设，通过打破平局，对每个留出索引i，可选择一个除在i处外处处正确的假设，其留一误差为1。有限基数界限仅在测试点位于未用于选择输出的大块中时有效。随机预留恰好创建了这样的块。  

## 3 三个有限群体引理  
我们陈述上界所用的工具。以下所有群体均为带索引样本的有限多重集。均匀样本在索引上进行，因此重复值不会引起歧义。  

### 3.1 可实现压缩覆盖  
一个确定性选择方案A=(κ, ρ)，其大小k(m)选择最多k(m)个输入样本（允许重复），并从该元组重构预测器。若其重构实现每个可实现输入序列，则它是可实现压缩方案。近期的单包含与提升结果隐含以下事实：对于损失ℓ，ℓ-样本压缩方案还要求其在每个输入序列上的经验ℓ-损失不超过H中任何比较器的经验ℓ-损失。因此，经验最优性是保证的一部分，而非重构的额外性质。  

###### 命题3（压缩成分）  
若H具有有限DS维度d_DS，则存在大小k₁(m) ≤ C·d_DS·log(em)的确定性可实现压缩方案。对于大小至多p的菜单μ:X→2^Y，H存在一个用于ℓ_μ(g,(x,y))=𝟙{y∈μ(x), g(x)≠y}的确定性样本压缩方案，其大小k₂(m) ≤ C·d_N·log(ep)·log(em)。  

以上结论对任意标签空间成立。第一个陈述结合了Pabbaraju（2026）的密度定理与David等（2016）的弱学习到压缩构造。具体构造也由Cohen等（2026，推论C.2）给出。第二个陈述来自Cohen等（2026，命题3.6）。附录A记录了该缩减及无限标签点的情况。  

对于固定比较器h，记A(h)为A中被h正确标注的样本。将第一个方案应用于A(h)产生一个预测器，它可能与h不一致，但不会在A中h正确的任何点上不一致。  

###### 引理4（有限群体压缩覆盖）  
设R为固定大小N的群体，A为大小m的均匀子集（m≤N/2），A=(κ, ρ)为大小至多k的确定性可实现压缩方案。对固定h，令f_{h,A}=A(A(h))。则：  
𝔼_A [1/(N-m) Σ_{(x,y)∈R\A} 𝟙{h(x)=y≠f_{h,A}(x)}] ≤ C·[(k+1)·log(eN)]/m。  

证明是压缩联合界，但针对未见的有限群体而非分布。每个可能输出由至多(k+1)Nᵏ个元组重构。若其在R\A上的不良比例为u，则A避免所有不良点的概率至多为e^{-um/2}。详细证明见附录B。  

### 3.2 无放回菜单引理  
设F⊆Y^X有限，Z₁,…,Z_T为从固定大小N的群体R中无放回随机有序样本。乘法权重从均匀权重开始。在观察Z_t=(X_t,Y_t)之前...