相对智能 II：可处理的或半监督的实例最优学习

# 可处理或半监督的实例最优学习  
来源：https://arxiv.org/html/2609.10886  

## 相对智能 II：可处理或半监督的实例最优学习  
Shaddin Dughmi††注：[email protected]。由NSF基金CCF-2432219支持。作者在西北大学担任Carter和Tania Neild客座教授以及芝加哥大学数据科学研究所客座教授休假期间完成了部分工作。  
Alireza F. Pour††注：[email protected]。由David Cheriton奖学金和Vector研究所研究基金支持。  
隶属关系：滑铁卢大学  

###### 摘要  
我们继续研究文献[10 (https://arxiv.org/html/2609.10886#bib.bib3)]中提出的“相对智能学习”，该概念要求监督学习器能够逐边际地与每一个可从无标签数据可靠验证的分布固定误差保证进行竞争。他们表明，单一包含图学习器在样本复杂度二次放大的条件下是相对智能的，并且不存在更优的相对智能学习器。然而，经验风险最小化或其他自然或可处理的学习器是否能获得类似保证仍属未解之谜。此外，样本复杂度的放大是否可以限制在无标签数据上——从而实现相对智能的半监督学习——也是一个极具吸引力的可能性。我们的第一个结果肯定地解决了第一个问题：我们证明了在无分布设定下，经验风险最小化（实际上任何适当的一致学习器）对于二元分类都是相对智能的。我们的证明表明，当允许使用\(m\)个样本时，一个小的可验证误差意味着在大小为\(O(m^2)\)的随机样本的均匀分布上存在一个大小至多为\(2^{m+1}\)的覆盖，这足以控制任何一致学习器在给定\(O(m^2)\)个样本时的误差。随后我们探讨了半监督问题：仅添加无标签数据是否足以实现相对智能学习，以及这如何影响学习的可处理性/简易性。我们在信息论问题上得到了一个正面结果：存在一种半监督相对智能学习器，其无标签样本复杂度仅有二次放大，而标签样本复杂度则没有放大。该学习器基于单一包含图向“留下大部分”传导问题的自然推广，其中揭示有限池中一个子集的标签，学习器预测剩余点的标签。最后我们表明——与我们在经验风险最小化上的第一个结果形成对比——这种信息论上的标签效率是以学习器的简易性和可处理性为代价的：当学习器只能通过调用不可知经验风险最小化预言机来访问假设类时，我们证明任何标签样本复杂度显著次二次放大的半监督相对智能学习器必须进行超多项式数量的预言机调用。即使边际分布被显式给出，这也成立，因此意味着对于分布固定学习的类似难解性结果，这可能具有独立价值。  

## 1 引言  
经典PAC模型寻求*全监督*学习保证，该保证在无标签数据的边际分布和标记假设上均一致成立，因此在所有可接受实例上以最坏情况衡量性能。然而，学习的难度可能因边际分布的不同而显著变化，即使假设仍然由对手选择。文献[5 (https://arxiv.org/html/2609.10886#bib.bib21)]研究的*分布固定*学习模型通过赋予学习器对边际分布\( \mathcal{D} \)的完全知识来捕捉这一点，允许其学习策略专门为\( \mathcal{D} \)量身定制。因此，分布固定学习可以被视为一种理想化的半监督学习形式，其中学习器不仅可以访问额外的无标签样本，还可以访问边际本身[4 (https://arxiv.org/html/2609.10886#bib.bib7)]。人们可能会问，是否可以在不给予学习器边际分布完整知识的情况下恢复分布固定学习的优势。文献[7 (https://arxiv.org/html/2609.10886#bib.bib14)]引入的*智能PAC学习*，寻求一个单一的监督学习器，其对每个边际的错误率接近该边际的最优分布固定学习器的错误率，尽管未被赋予边际分布本身。从这个意义上说，智能学习寻求关于边际分布的实例最优保证。文献[7 (https://arxiv.org/html/2609.10886#bib.bib14)]表明，对于“大多数”边际，存在这样的学习器，其中“大多数”是根据一个预先已知的任意固定先验分布来量化的。然而，这种限定通常无法被移除：文献[6 (https://arxiv.org/html/2609.10886#bib.bib24)]（强化了文献[9 (https://arxiv.org/html/2609.10886#bib.bib23)]的结果）表明，存在假设类和边际分布族，其中最优分布固定错误率快速一致地收敛到零，但对于每一个未被赋予边际的监督学习器和每一个有限样本大小，都存在一个边际使其错误率本质上仍是随机猜测。在最近的工作中，文献[10 (https://arxiv.org/html/2609.10886#bib.bib3)]将这种不可能性背后的障碍识别为一种不可区分性现象：为边际\( \mathcal{D} \)量身定制的学习器\( \mathcal{A}_{\mathcal{D}} \)在另一个与\( \mathcal{D} \)使用无标签数据不可区分的边际\( \mathcal{D}' \)上可能表现差得多。在这种情况下，学习器无法可靠地识别观察到的数据是否来自其特定分布学习策略仍然有效的边际，或者来自该策略失败的另一个统计上相似的边际。因此，无标签数据可能不足以确定与\( \mathcal{D} \)相关的有利错误保证是否确实可信。受此启发，文献[10 (https://arxiv.org/html/2609.10886#bib.bib3)]引入了*相对智能学习*。他们不要求学习器与任意的分布固定错误率竞争，而是要求学习器仅与可*从无标签数据可靠验证*的错误保证竞争。非正式地，为\( \mathcal{D} \)量身定制的学习器\( \mathcal{A}_{\mathcal{D}} \)与一个验证器\( \mathcal{C} \)配对，该验证器观察一个无标签样本并估计其错误。尽管\( \mathcal{A}_{\mathcal{D}} \)可能专为\( \mathcal{D} \)设计，但可靠性要求验证器的期望值在*每个*可接受的边际\( \mathcal{D}' \)上都是\( \mathcal{A}_{\mathcal{D}} \)错误的上界。因此，如果\( \mathcal{D} \)与另一个\( \mathcal{A}_{\mathcal{D}} \)错误显著更大的边际难以区分，验证器就必须考虑到这种模糊性。由此产生的*可验证错误率*恰好捕捉了可从无标签数据证明的依赖分布的保证，而相对智能学习则要求一个单一的逐边际地与所有此类保证竞争的学习器。在无分布设定中，文献[10 (https://arxiv.org/html/2609.10886#bib.bib3)]建立了本质上紧的信息论表征。他们表明，单一包含图学习器在误差常数放大和样本复杂度二次放大的条件下是相对智能的。他们进一步证明，每个相对智能学习器都必须承受近二次的样本复杂度放大。文献[10 (https://arxiv.org/html/2609.10886#bib.bib3)]的积极结果依赖于单一包含图学习器，更具体地说，依赖于它在“留一”传导问题上的逐数据集最优性。标准学习规则如经验风险最小化不具有此性质：存在一些数据集，在这些数据集上经验风险最小化和单一包含图具有非常不同的“留一”行为，尽管它们在PAC学习中的保证密切相关。因此，自然要问，支撑单一包含图分析的传导最优性对于具有二次（甚至有界）放大的相对智能学习是否至关重要，或者更简单、更标准的学习规则是否可以获得可比较的保证。  

###### 问题 1.1（文献[10 (https://arxiv.org/html/2609.10886#bib.bib3)]中的开放问题 3.3）。  
经验风险最小化或其他自然且通常可处理的学习器是否是相对智能的？  

第二个问题涉及无标签数据在相对智能学习中的作用。由于分布固定学习可以被视为一种理想化的半监督学习形式，自然要问，访问额外的无标签样本是否能帮助学习器与可验证错误率竞争。文献[10 (https://arxiv.org/html/2609.10886#bib.bib3)]的下界适用于全监督学习器，因此并未确定一旦无标签样本可用，所需的样本复杂度放大中有多少必须保留在标签数据中。这留下了一种可能性，即无标签数据可能大幅减少所需的标签数量，甚至可能完全消除标签样本复杂度的放大。  

###### 问题 1.2。  
无标签数据能否显著减少相对智能学习的标签样本复杂度？更具体地说，是否存在没有标签样本复杂度放大的半监督相对智能学习器？  

我们的第一个问题询问相对智能学习是否可以通过简单且通常可处理的监督学习规则（如经验风险最小化）实现。上述半监督问题提出了另一种可能性：使用无标签数据减少标签样本复杂度可能需要显著更复杂的学习过程，即使相应的信息论保证是可实现的。因此，除了询问无标签数据能否减少标签数量外，自然还要问这种改进是否可以通过可处理的学习器实现。  

###### 问题 1.3。  
具有显著改进的标签样本复杂度的半监督相对智能学习器是否可被可处理地实现？  

第二个问题的肯定答案与第三个问题的否定答案结合，将揭示无标签数据在信息论价值和算法价值之间的分离。这意味着，虽然无标签数据可能足以消除标签样本复杂度的放大，但利用这一优势可能需要显著更复杂的学习程序。具体来说，障碍将不再是获得关于边际的信息，而是将该信息转化为有效的学习策略。  

### 1.1 结果与技术  
我们肯定地回答了前两个问题，并在自然的预言机模型中对第三个问题给出了强烈的否定回答。  

#### 经验风险最小化是相对智能的。  
我们的第一个结果解决了文献[10 (https://arxiv.org/html/2609.10886#bib.bib3)]中关于经验风险最小化的开放问题。我们表明，在无分布设定下，经验风险最小化在样本复杂度二次放大的条件下是相对智能的。事实上，对于每个适当的一致学习器，相同的保证都成立：使用二次更多的标签样本，任何此类学习器都可以在原始样本大小的最佳可验证错误保证上近似竞争，损失常数因子。其原因与支撑单一包含图结果的原因根本不同。在文献[10 (https://arxiv.org/html/2609.10886#bib.bib3)]中，可靠验证意味着可验证错误率相对于随机有限样本的均匀分布上的最优学习错误有一个下界。单一包含图的逐数据集“留一”最优性提供了直接竞争此下界的方法。经验风险最小化没有可比的传导最优性；事实上，存在一些有限样本，在这些样本上其“留一”行为比单一包含图差得多。因此，我们的结果表明，“留一”最优性对于相对智能学习是充分的，但不是必要的。我们的证明反而推导出了小可验证错误率的另一个推论。与原始论证类似，对于边际\( \mathcal{D} \)和样本大小\( m \)，我们首先证明在大小为\( O(m^2) \)的随机样本\( S \)上的平均而言，\( \mathcal{D} \)固定学习器\( \mathcal{A}_{\mathcal{D}} \)在\( S \)上的均匀分布（记为\( \mathcal{D}_S \)）上的错误不会比可验证错误率大很多。然后我们证明，如果\( \mathcal{A}_{\mathcal{D}} \)在\( \mathcal{D}_S \)上实现了小错误，那么假设类就不能包含太多在\( \mathcal{D}_S \)下两两良好分离的假设。等价地，\( \mathcal{D}_S \)上的相关填充数很小，这导致了假设类的一个小覆盖。最后，一个双重抽样论证表明，要限制一个一致学习器在\( \mathcal{D} \)上的错误，只需证明任何与\( S \)的一半随机一致的假设在另一半上具有小错误。\( \mathcal{D}_S \)的覆盖足够小，以至于覆盖中的任何假设在两半上都具有相似的错误，我们利用覆盖来表明这扩展到了类中的每个假设。  

#### 没有标签样本复杂度放大的半监督相对智能学习。  
我们的第二个结果以最有力的形式回答了半监督问题。我们引入了相对智能半监督学习的概念，分别跟踪无标签和标签样本复杂度，并表明整个样本复杂度的放大可以转移到无标签数据上。具体来说，我们展示了一个半监督学习器，它可以在给定样本大小下近似地与最佳可验证错误保证竞争，同时仅使用相同数量的标签样本，再加上二次更多的无标签样本。因此，与全监督设置不同，相对智能半监督学习根本不需要标签样本复杂度的放大。该构造再次建立在可验证错误率与在大随机样本的均匀分布下学习之间的联系之上。给定无标签样本、标签样本和一个测试点，我们形成它们的并集\( T \)并考虑\( T \)上的均匀分布\( \mathcal{D}_T \)。然后学习器使用一个仅在可用标签样本上训练的最优\( \mathcal{D}_T \)固定学习器\( \mathcal{A}^*_T \)来预测测试点。设\( \mathcal{A}_{\mathcal{D}} \)是见证\( \mathcal{D} \)上可验证错误率的\( \mathcal{D} \)固定学习器。我们证明，在\( T \)上的平均而言，\( \mathcal{A}_{\mathcal{D}} \)在给定\( m \)个标签样本时在\( \mathcal{D}_T \)上的错误可作为可验证错误率的下界。\( \mathcal{A}^*_T \)对于\( \mathcal{D}_T \)的最优性则表明我们的学习器的错误与可验证错误率具有竞争力。  

半监督构造也允许一个自然的传导解释。上述学习器引发了一个问题，其中有限池中只有一个小子集被标记，学习器必须预测剩余点的标签。我们将其称为*留下大部分*问题。