无标签数据深度网络自训练的理论分析

摘要

自训练算法训练模型以适应另一个先前学习的模型预测的伪标签，在使用神经网络学习未标记数据方面非常成功。 然而，目前对自训练的理论理解仅适用于线性模型。 这项工作为半监督学习、无监督领域适应和无监督学习的深度网络自训练提供了统一的理论分析。 我们分析的核心是一个简单但现实的“扩展”假设，它指出数据的低概率子集必须扩展到相对于该子集具有大概率的邻域。 我们还假设不同类中的示例邻域具有最小的重叠。 我们证明，在这些假设下，基于自我训练和输入一致性正则化的人口目标最小化将在地面实况标签方面实现高精度。 通过使用现成的泛化边界，我们立即将此结果转换为神经网络的样本复杂性保证，该神经网络的边际和 Lipschitzness 为多项式。 我们的结果有助于解释最近提出的使用输入一致性正则化的自训练算法的经验成功。

1简介

尽管神经网络的监督学习已成为标准且可靠，但它仍然经常需要大量标记数据集。 由于标签可能昂贵或难以获得，因此在深度学习中利用未标记数据已成为一个活跃的研究领域。 半监督学习近期研究成果(Chapelle 等人, 2010; Kingma 等人, 2014; Kipf & Welling, 2016; Laine & Aila, 2016; Sohn 等人, 2020; Xie 等人, 2020) 和无监督域适应 (Ben-David 等人, 2010; Ganin & Lempitsky, 2015; Ganin 等人, 2016; Tzeng 等人, 2017; Hoffman 等人, 2018; Shu 等人, 2018; Zhang 等人，2019） 利用大量未标记数据以及来自相同分布或相关分布的标记数据。 无监督学习或表征学习的最新进展(Hinton 等人, 1999; Doersch 等人, 2015; Gidaris 等人, 2018; Misra & Maaten, 2020; Chen 等人, 2020a, b; Grill 等人, 2020) 在不使用任何标签的情况下学习高质量的表示。

自训练是一种常见的算法范例，用于利用深度网络的未标记数据。 自训练方法训练一个模型来拟合伪标签，即通过先前学习的模型对未标记数据进行预测（Yarowsky，1995；Grandvalet & Bengio，2005；Lee，2013）。 最近的工作还扩展了这些方法，以增强输入转换下预测的稳定性，例如对抗性扰动（Miyato等人，2018）和数据增强（Xie等人，2019）。 这些被称为输入一致性正则化的方法已在半监督学习（Sohn等人，2020；Xie等人，2020）、无监督域适应（French等人，2017）方面取得了成功; Shu 等人, 2018)，以及无监督学习(Hu 等人, 2017; Grill 等人, 2020)。

尽管取得了实证上的成功，但理解如何使用未标记数据的理论进展仍然滞后。 尽管监督学习相对容易理解，但用于推理未标记数据的统计工具却并不容易获得。 大约 25 年前，Vapnik (1995)提出了针对无标签数据的转导 SVM，这可以被视为自我训练的早期版本，但很少有工作表明该方法提高了样本复杂度（Derbeko等人，2004）。 使用未标记的数据需要对输入分布进行适当的假设（Ben-David 等人，2008）。 最近的论文（Carmon 等人，2019；Raghunathan 等人，2020；Chen 等人，2020c；Kumar 等人，2020；Oymak & Gulcu，2020）分析了各种环境下的自我训练，但主要是对于线性模型，通常要求数据是高斯或接近高斯的。 Kumar 等人 (2020) 还分析了在多个时间步上发生逐渐域转移的情况下的自我训练，但假设连续时间步之间的转移有一个小的 Wasserstein 距离界限。 另一种研究方法是使用非参数方法利用无标记数据，要求无标记样本的复杂度为指数维度（Rigollet，2007 年；Singh 等人，2009 年；Urner & Ben-David，2013 年）。

本文为半监督学习、无监督领域适应和无监督学习的深度网络自训练提供了统一的理论分析。 在数据分布的简单而现实的扩展假设下，我们表明，使用深度网络进行输入一致性正则化的自我训练可以在真实标签上实现高精度，使用未标记的样本大小（模型的边际和 Lipschitzness 为多项式）。 我们的分析为最近经验上成功的依赖输入一致性正则化的自训练算法提供了理论直觉（Berthelot 等人，2019；Sohn 等人，2020；Xie 等人，2020）。

我们的扩展假设直观地表明数据分布在每个类内具有良好的连续性。 具体来说，令 $P_i$ 为以类 $i$ 为条件的数据分布，扩展表明对于类 $i$ 的示例的小子集 $S$ ,

$P_i(\text{neighborhood of}S)\ge c{P}_i(S)$ (1.1)

其中 $c>1$ 是扩展因子。 邻域将被定义为包含数据增强，但目前可以将其视为与 $S$ 距离较小的 ${\mathrm{\ell }}_2$ 点的集合。这个概念是 Cheeger 常数（或等周或膨胀常数）的扩展（Cheeger，1969），它在图论中得到了广泛的研究（Chung & Graham，1997） 、组合优化(Mohar & Poljak, 1993; Raghavendra & Steurer, 2010)、抽样(Kannan 等人, 1995; Lovász & Vempala, 2007; 张等人, 2017)，甚至在早期版本的自我训练中（Balcan等人，2005）用于协同训练设置（Blum＆Mitchell，1998）。 扩展表示每个类的流形具有足够的连通性，因为每个子集 $S$ 都有一个大于 $S$ 的邻域。我们在3.1节中给出了满足扩展的分布的示例。 我们还需要一个分离条件，表明来自不同类别的相邻对很少。

我们的算法通过使用输入一致性正则化（Miyato等人，2018；Xie等人，2019）来利用扩展来鼓励分类器$G$的预测与相邻示例保持一致：

$R(G)={𝔼}_x[\underset{\text{neighbor}{x}^{\prime }}{\max }\mathrm{𝟏}(G(x)\ne G(x^{\prime }))]$ (1.2)

对于无监督域适应和半监督学习，我们分析了一种算法，该算法使 $G$ 适合未标记数据上的伪标签，同时规范输入一致性。 假设扩展和分离，我们证明拟合模型将对伪标签进行去噪，并在真实标签上实现高精度（定理4.3)。 这解释了这样的经验现象：尽管无法获得真实标签，但对伪标签的自我训练通常会比伪标签器有所改进。

对于无监督学习，我们考虑找到一个分类器$G$，该分类器可以最小化输入一致性正则化器，并限制为每个标签分配足够的示例。 在定理 3.6 中，我们表明，假设扩展和分离，学习的分类器在预测真实类别方面将具有很高的准确性，直到标签的排列（没有真实标签就无法恢复）。

定理的主要直觉如下：输入一致性正则化确保模型局部一致，扩展性质将局部一致性放大为同一类内的全局一致性。 在无监督域适应设置中，如图1（右）所示，错误伪标记的示例（红色区域）逐渐被正确伪标记的邻居（绿色区域）去噪，其概率质量为不平凡（至少 $c-1$ 倍于扩展错误集的质量）。 我们注意到，仅需要对总体分布进行扩展，但对经验样本进行了自我训练。 由于参数方法的外推能力，扩张的局部到全局一致性效应隐含地发生在总体上。 相比之下，最近邻方法需要在经验样本上显式进行扩展，从而遭受维数灾难。 我们在下面提供更多详细信息，并在图 1（左）中可视化此效果。

图1： 左：证明扩张假设。 验证扩展假设需要访问总体分布，因此我们使用 BigGAN （Brock 等人，2018）生成的分布。 我们展示了错误分类图像及其正确分类邻居的典型示例，这些图像是通过搜索整个 GAN 流形（而不仅仅是训练集）找到的。 作为对比，我们还在 100K GAN 图像的训练集中显示了它们的最近邻居，这些图像距离更远。 这支持了扩张适用于人口集但不适用于经验集的直觉和假设。 （更多详细信息请参见第 D.1 节。） 右：伪标签的假设和设置。 对于使用伪标签进行自我训练，正确伪标签示例的区域（绿色）将用于对具有错误伪标签的示例（红色）进行去噪，因为通过扩展，绿色区域将具有至少 $c-1$ 乘以红色区域的质量。 正如简介中所解释的，这确保了分类器适合伪标签并且与w.r.t.一致。 输入转换将在真实标签上实现高精度。

据我们所知，本文首次对用于无监督学习、半监督学习和无监督域适应的深度神经网络模型进行了多项式样本复杂性保证的分析。 之前的工作（Rigollet，2007；Singh 等人，2009；Urner & Ben-David，2013）分析了非参数方法，这些方法基本上用未标记的数据精确地恢复了数据分布，但要求样本复杂度在维度上呈指数级。 我们的方法优化了参数损失函数和正则化器，因此涉及总体损失的保证可以使用现成的泛化界限转换为有限样本结果（定理3.7)。 当神经网络能够以较大余量分离真实类别时，这些边界的样本复杂度可以很小，即维度为多项式。

最后，我们注意到我们的正则化器 $R(\cdot )$ 对应于强制一致性。 对抗性示例，经证明对半监督学习 （Miyato 等人，2018；Qiao 等人，2018） 和无监督领域适应 （Shu 等人，2018）. 此外，我们可以扩展(1.1)中的邻域概念以包括示例的数据增强，这将增加邻域大小，从而改善扩展。 因此，我们的理论可以帮助解释经验观察，即基于积极数据增强或对抗性训练的一致性正则化可以提高未标记数据的性能（Shu 等人，2018；Xie 等人，2019；Berthelot 等人，2019；Sohn 等人，2020；谢等人，2020；陈等人，2020a)。

总之，我们的贡献包括：1）我们提出了一个简单而现实的扩展假设，该假设表明数据分布在真实类别的流形内具有连通性2）使用此扩展假设，我们为 self 提供真实准确度保证-训练算法对未标记数据的输入一致性进行正则化，3）我们的分析可以通过现成的泛化边界轻松应用于具有多项式未标记样本的深度网络。

1.1 其他相关工作

通过伪标签（Lee，2013）或最小熵目标（Grandvalet & Bengio，2005）进行自我训练已广泛应用于半监督学习（ Laine & Aila, 2016; Iscen 等人, 2019; Berthelot 等人, 2020) 和无监督域适应（Long 等人，2013；French 等人，2017；Saito 等人，2017；Shu 等人，2018；Zou 等人，2019）。 我们的论文研究了输入一致性正则化，它增强了未标记数据的预测的稳定性。 在实践中，这些转换包括对抗性扰动，被提议为增值税目标（Miyato等人，2018），以及数据增强（Xie等人，2019） 。

对于无监督学习，我们的自我训练目标与 BYOL (Grill 等人，2020) 密切相关，这是一种最近最先进的方法，可训练学生模型以匹配由基于输入的强增强版本的教师模型。 对比学习是另一种流行的无监督表示学习方法，它鼓励“正对”的表示（理想情况下由同一类的示例组成）接近，同时将负对推得较远（Mikolov 等人，2013；Oord 等人，2018；阿罗拉等人，2019）。 最近的对比学习工作通过使用强大的数据增强形成正对（Chen 等人，2020a，b）来实现最先进的表示质量。 数据增强在这里的作用在本质上类似于我们使用输入一致性正则化。 与我们的设置不太相关的是通过解决自监督借口任务来学习表示的算法，例如修复和预测旋转（Pathak等人，2016；Noroozi＆Favaro，2016；Gidaris等人，2018） 。 Lee 等人 (2020) 从理论上分析了自监督学习，但他们的分析适用于与我们不同类别的算法。

先前的理论工作通过假设访问根据特定主题建模设置（Tosh等人，2020）或同一类中的独立样本对（Arora等人）分布的文档数据来分析对比学习，2019）。 然而，这些分析所需的假设并不一定适用于视觉，其中正对对同一图像应用不同的数据增强，因此具有很强的相关性。 其他论文分析了表征学习的信息论特性（Tian 等人，2020；Tsai 等人，2020）。

先前的工作分析了半监督学习的连续性或“集群”假设，这与我们的扩展概念相关（Seeger，2000；Rigollet，2007；Singh 等人，2009；Urner & Ben-David，2013）. 然而，这些论文使用非参数方法利用未标记的数据，需要在维度上呈指数级的未标记样本复杂性。 另一方面，我们的分析是针对参数方法的，因此当神经网络可以大范围地分离真实类别时，未标记样本的复杂性可能会很低。

协同训练是自我训练的经典版本，需要两个不同的数据“视图”（即特征子集），每个视图都可以用于预测其自身的真实标签 （Blum 和 Mitchell， 1998；达斯古普塔等人，2002；巴尔坎等人，2005）。 例如，为了预测网页的主题，一个视图可以是传入链接，另一个视图可以是页面中的单词。 最初的协同训练算法（Blum＆Mitchell，1998；Dasgupta等人，2002）假设两个视图在真实标签上是独立的，并利用这种独立性来获得未标记数据的准确伪标签。 相比之下，如果我们通过将示例和随机采样的邻居视为数据的两个视图来将我们的设置放入协同训练框架中，则这两个视图是高度相关的。 Balcan 等人 (2005) 放宽了对协同训练的独立观点的要求，同样通过使用“扩展”假设。 我们的假设与他们的假设密切相关，并且如果我们通过将相邻示例视为两种视图来将我们的设置放入协同训练框架中，那么在概念上是等效的。 然而，他们的分析要求可信的伪标签都是准确的，并且没有严格考虑其算法中潜在的错误传播。 相反，我们的贡献是提出并分析一个涉及输入一致性正则化的目标函数，其最小化去噪来自潜在不正确伪标签的错误。 我们还为神经网络假设类提供有限样本复杂性界限并分析无监督学习算法。

无监督域适应的替代理论分析假设源域和目标域之间的差异有界测量（Ben-David 等人，2010；Zhang 等人，2019）。 Balcan & Blum (2010) 提出了一种用于分析半监督学习的 PAC 式框架，但其界限要求用户指定包含数据先验知识的兼容性概念，并且不适用到域适应。 Globerson 等人 (2017) 证明半监督学习在标记样本复杂性方面可以优于监督学习，但假设完全了解未标记分布。 (Mobahi 等人, 2020) 表明，对于核方法，自蒸馏（自训练的一种变体）可以有效地放大正则化。 他们的分析适用于核方法，而我们的分析适用于数据假设下的深层网络。

2 预备知识和符号

我们让 $P$ 表示输入空间 $𝒳$ 上未标记示例的分布。 对于无监督学习，$P$ 是唯一相关的分布。 对于无监督域适应，我们还定义了源分布 $P_{\text{src}}$ 并让 $G_{\text{pl}}$ 表示在从 $P_{\text{src}}$ 采样的标记数据集上训练的源分类器。 为了将这些定义转化为半监督学习，我们将 $P_{\text{src}}$ 和 $P$ 设置为相同，但 $P_{\text{src}}$ 允许访问标签。 我们分析仅依赖于$P_{\text{src}}$到$G_{\text{pl}}$的算法。

我们考虑分类，并假设数据被划分为 $K$ 类，其中 $x\in 𝒳$ 的类由 $G^{\star }:𝒳\to [K]$ 的地面实况 $G^{\star }(x)$ 给出。 我们让 $P_i$ 表示以 $G^{\star }(x)=i$ 为条件的 $x$ 的类条件分布。 我们假设每个示例 $x$ 都有一个唯一的标签，因此 $P_i$、$P_j$ 对 $i\ne j$ 具有不相交的支持。 让 $\widehat{P}\triangleq \{x_1,\mathrm{\dots },x_n\}\subset 𝒳$ 表示 $n$ i.i.d. 来自 $P$ 的未标记训练示例。我们还使用 $\widehat{P}$ 来指代这些示例的均匀分布。 我们让$F:𝒳\to {ℝ}^K$表示学习的评分函数（例如神经网络输出的连续logits），$G:𝒳\to [K]$表示由$F$引起的离散标签：$G(x)\triangleq {\arg \max }_{i}F{(x)}_i$（按字典顺序断开关系）。

伪标签。 伪标签方法是半监督学习和领域适应的一种自我训练形式，其中源分类器 $G_{\text{pl}}:𝒳\to [K]$ 用于预测未标记目标数据上的伪标签 （Lee，2013） 。 然后，这些方法训练一个新的分类器来适应这些伪标签，例如，使用标准交叉熵损失：$L_{\text{pl}}(F)\triangleq {𝔼}_{\widehat{P}}[{\mathrm{\ell }}_{\text{cross-ent}}(F(x),G_{\text{pl}}(x))]$。 我们的理论分析适用于基于伪标签的目标。 其他形式的自我训练包括熵最小化，它是密切相关的，并且在某些设置中相当于伪标签，其中伪标签每次迭代都会更新（Lee，2013；Chen等人，2020c）。

3 无监督学习的扩展属性和保证

在本节中，我们将首先介绍关于扩展的关键假设。 然后我们研究扩展对无监督学习的影响。 我们证明，如果分类器与 w.r.t 一致。 输入转换并以适当的概率预测每个类，学习到的标签将与真实类对齐，直到类索引的排列（定理3.6)。

3.1 扩展属性

我们引入了扩展的概念。 当我们的理论研究强制输入转换稳定性的目标时，我们将首先通过下面定义的集合 $ℬ(x)$ 对输入 $x$ 的允许转换进行建模。 我们让 $𝒯$ 表示通过数据增强获得的某个 Transformer 集合，并定义 $ℬ(x)\triangleq \{x^{\prime }:\exists T\in 𝒯\text{such that}\Vert x^{\prime }-T(x)\Vert \le r\}$ 为与 $x$ 的某个数据增强的距离为 $r$ 的点集合。 我们可以将 $r$ 视为比 $x$ 的典型范数小得多的值，因此 $P(ℬ(x))$ 的概率在维度上呈指数级小。 我们的理论很容易适用于 $ℬ$ 的其他选择，尽管为了简单起见我们将此定义设置为默认值。 现在我们定义$x$的邻域，用$𝒩(x)$表示，作为其变换集与$x$的变换集重叠的点的集合：

$𝒩(x)=\{x^{\prime }:ℬ(x)\cap ℬ(x^{\prime })\ne \mathrm{\varnothing }\}$ (3.1)

对于$S\subseteq 𝒳$，我们将$S$的邻域定义为其元素的邻域的并集：$𝒩(S)\triangleq {\cup }_{x\in S}𝒩(x)$。 我们现在定义分布 $P$ 的扩展属性，它降低了低概率集的邻域大小并捕获输入空间中分布的连通性。

Definition 3.1 ($(a,c)$-扩展）。

如果对于具有 $P_i(V)\le a$ 的所有 $V\subseteq 𝒳$ 来说，以下条件成立，我们就说类条件分布 $P_i$ 满足 $(a,c)$ 展开：

$P_i(𝒩(V))\ge \min \{c{P}_i(V),1\}$ (3.2)

如果$P_i$满足所有$\forall i\in [K]$的$(a,c)$扩展，那么我们说$P$满足$(a,c)$扩展。

我们注意到，这个定义考虑了总体分布，并且扩展预计不会在训练集上成立，因为所有经验示例彼此相距很远，因此训练示例的邻域不会重叠。 这个概念与Cheeger常数密切相关，它用于限制连续分布采样的混合时间和命中时间（Lovász & Vempala, 2007；Zhang 等人, 2017） 和小集扩展，量化图的连通性（Hoory 等人，2006；Raghavendra & Steurer，2010）。 特别是，当邻域被定义为与集合的 ${\mathrm{\ell }}_2$ 距离至多 $r$ 的点的集合时，则扩展因子 $c$ 的界限如下通过 $\exp (\eta r)$，其中 $\eta$ 是 Cheeger 常数 (Zhang 等人, 2017)。 在D.1节中，我们使用GAN来证明扩展是视觉中的现实属性。 对于无监督学习，我们需要使用 $a=1/2$ 和 $c>1$ 进行扩展：

Assumption 3.2 （无监督学习的扩展要求）。

我们假设 $P$ 满足 对 的展开，而 $c>1$ 满足 $(1/2,c)$ 对 $𝒳$ 的展开。

我们还假设真实类别在输入空间中是分离的。 我们将总体一致性损失 $R_{ℬ}(G)$ 定义为 $G$ 对输入转换不稳健的示例的分数：

$R_{ℬ}(G)\triangleq {𝔼}_P[\mathrm{𝟏}(\exists x^{\prime }\in ℬ(x)\text{such that}G(x^{\prime })\ne G(x))]$ (3.3)

我们假设地面真值类远离输入空间：

Assumption 3.3 （分离）.

我们假设 $P$ 被 $ℬ$ - 由真实分类器 $G^{\star }$ 以概率 $1-\mu$ 分隔，如下所示： $R_{ℬ}(G^{\star })\le \mu$。

我们在定理 4.3 和 3.6 中的准确性保证将取决于 $\mu$。 我们期望 $\mu$ 很小或可以忽略不计（例如维度的逆多项式）。 分离要求要求两个类之间的距离大于$2r$，即$ℬ(\cdot )$定义中的${\mathrm{\ell }}_2$半径。 然而，$r$可能比典型示例的范数小得多，因此我们的扩展要求可能比典型的“聚类”概念弱，后者要求类内距离小于类间距离。 我们从高斯的混合开始定量地证明了这一点。

Example 3.4 （各向同性高斯的混合）.

假设$P$是具有各向同性协方差的$K$高斯$P_i\triangleq 𝒩({\tau }_i,\frac{1}{d}{I}_{d\times d})$和的混合，对应于$K$单独的类。 假设变换集$ℬ(x)$是一个${\mathrm{\ell }}_2$球，半径为$\frac{1}{2\sqrt{d}}$，围绕$x$，因此没有数据增强，并且$r=\frac{1}{2\sqrt{d}}$。 那么$P$满足$(0.5,1.5)$扩展。 此外，如果均值之间的最小距离满足${\min }_{i,j}{\Vert {\tau }_i-{\tau }_j\Vert }_2\gtrsim \frac{\sqrt{\log d}}{\sqrt{d}}$，则$P$以$ℬ$概率$1-1/\text{poly}(d)$分隔。

在上面的例子中，人口分布满足展开，但经验分布不满足。 任意两个经验例子之间的最小距离为$\mathrm{\Omega }(1)$的概率很高，因此当$r=\frac{1}{2\sqrt{d}}$时它们不能是彼此的邻居。 此外，类内距离 $\mathrm{\Omega }(1)$ 远大于均值之间的距离（假设为 $\gtrsim 1/\sqrt{d}$)。 因此，基于经验样本的简单的基于距离的聚类算法不适用。 3.2节中的无监督学习算法可以近似地恢复具有多项式样本的混合分量，误差高达$O(1/\text{poly}(d))$。 此外，这几乎是信息理论上最优的：通过总变化距离，需要均值之间的 $\mathrm{\Omega }(\frac{1}{\sqrt{d}})$ 距离来恢复混合分量。

该示例通过更一般的等周不等式扩展到对数凹分布（Bobkov 等人，1999）。 因此，我们的分析适用于先前工作（Chen等人，2020c）的设置，该工作研究了高斯或对数凹分布混合的线性模型的自我训练。

然而，我们分析的主要好处是，与之前仅考虑高斯或近高斯分布的自我训练工作相比，它适用于比高斯分布更丰富的分布族（Raghunathan 等人，2020；Chen等人，2020c；库马尔等人，2020）。 我们在以下流形混合示例中演示了这一点：

Example 3.5 （流形混合）.

假设环境空间 ${ℝ}^{d^{\prime }}$ 上的每个类条件分布 $P_i$（其中 $d^{\prime }>d$)由某个 $\kappa$-bi-Lipschitz 生成 潜在变量 $z\in {ℝ}^d$ 上的生成器 $Q_i:{ℝ}^d\to {ℝ}^{d^{\prime }}$：

$x\sim P_i\iff x=Q_i(z),z\sim 𝒩(0,{\displaystyle \frac{1}{d}}\cdot I_{d\times d})$

我们将变换集$ℬ(x)$设置为${\mathrm{\ell }}_2$球，半径为$\frac{\kappa }{2\sqrt{d}}$，围绕$x$，因此没有数据增强并且$r=\frac{\kappa }{2\sqrt{d}}$。 那么，$P$满足$(0.5,1.5)$扩展。

图1（右）提供了流形上展开的图示。 请注意，只要$\kappa \ll d^{1/4}$，半径$\kappa /(2\sqrt{d})$就比数据点的范数小得多（至少在$1/\kappa$的数量级）。 这表明生成器可以不平凡地打乱空间，并且仍然以小半径保持有意义的扩展。 在B.2节中，我们证明了示例中的主张。

3.2无监督学习的群体保证

我们设计了一个利用扩展和分离特性的无监督学习目标。 我们的目标是总体分布，但它是参数化的，因此我们可以将其扩展到第 3.3 节中的有限样本情况。 我们希望仅使用未标记的数据来学习分类器 $G:𝒳\to [K]$，以便预测的类别与真实类别保持一致。 请注意，在不观察任何标签的情况下，我们只能学习基本事实类直至排列，从而导致为分类器 $G$ 定义以下排列不变错误：

$${\text{Err}}_{\text{unsup}}(G)\triangleq \underset{\text{permutation}\pi :[K]\to [K]}{\min }𝔼[\mathrm{𝟏}(\pi (G(x))\ne G^{\star }(x))]$$

我们研究了分类器 $G:𝒳\to [K]$ 上的以下无监督总体目标，它鼓励输入一致性，同时确保预测的类别具有足够的概率。

$\underset{G}{\min }{R}_{ℬ}(G)\text{subject to}\underset{y\in [K]}{\min }{𝔼}_P[\mathrm{𝟏}(G(x)=y)]>\max \{{\displaystyle \frac{2}{c-1}},2\}{R}_{ℬ}(G)$ (3.4)

这里$c$是假设3.2中的膨胀系数。 该约束确保任何预测类别的概率大于输入一致性损失。 让 $\rho \triangleq {\min }_{y\in [K]}P(\{x:G^{\star }(x)=y\})$ 表示最小真实类别的概率。 下面的定理表明，当$P$满足扩展和分离时，目标的全局极小值(3.4)将具有较低的误差。

Theorem 3.6.

假设假设 3.2 和 3.3 对于某些 $c,\mu$ 成立，使得 $\rho >\max \{\frac{2}{c-1},2\}\mu$ 成立。 那么 (3.4) 的任何最小化器 $\widehat{G}$ 满足

${\text{Err}}_{\text{unsup}}(\widehat{G})\le \max \{{\displaystyle \frac{c}{c-1}},2\}\mu$ (3.5)

在B节中，我们提供了定理3.6的证明以及该定理的一个变体，该变体适用于较弱的可加性展开概念。 通过应用 3.3 节的泛化界限，我们可以将定理 3.6 转换为有限样本保证，该保证是模型的边际和 Lipschitzness 的多项式（参见定理 C.1)。

我们的目标让人想起最近在无监督表示学习中取得最先进结果的方法：SimCLR (Chen 等人, 2020a)、MoCov2 (He 等人, 2020; Chen等人，2020b)，以及 BYOL (Grill 等人，2020)。 与我们的算法不同的是，这些方法并不预测离散标签，而是直接预测在输入 Transformer 条件下保持一致的表征。不过，我们的分析仍然可以解释为什么输入一致性正则化对这些方法如此重要：假设数据满足扩展性，它将鼓励表征在 整个类中具有相似性，因此表征将捕捉到地面实况的类结构。

Chen 等人 (2020a) 还观察到，使用更积极的数据增强来规范输入稳定性可以显着提高表示质量。 我们指出，我们的理论提供了一个潜在的解释：在我们的框架中，加强增强会增加邻域的大小，从而产生更大的扩展因子 $c$ 并提高准确度范围 (3.5 ）。

3.3深度学习模型的有限样本保证

在本节中，我们表明，如果真实类别可以通过具有大鲁棒余量的神经网络进行分离，那么泛化效果会很好。 与之前的工作相比，定理 3.6 和定理 4.3 的主要优点是它们分析参数目标，因此有限样本保证通过现成的泛化边界立即成立。 先前关于与扩展相关的连续性或“集群”假设的工作需要非参数技术，其样本复杂度在维度 上呈指数增长（Seeger, 2000; Rigollet, 2007; Singh 等人, 2009; Urner & Ben-David, 2013） 。

我们基于全层裕度的概念应用（Wei & Ma，2019b）的泛化界限，尽管任何其他界限都可以。 全层裕度衡量神经网络对每个隐藏层同时扰动的稳定性。 正式地，假设 $G(x)\triangleq {\arg \max }_{i}F{(x)}_i$ 是某个前馈神经网络 $F:𝒳\to {ℝ}^K$ 的预测，该网络计算以下函数：带有权重矩阵 ${\{W_i\}}_{i=1}^p$ 的 $F(x)=W_p\varphi (\mathrm{\cdots }\varphi (W_{1}x)\mathrm{\cdots })$。 让 $q$ 表示任何隐藏层的最大尺寸。 让 $m(F,x,y)\ge 0$ 表示示例 $x$ 中标签 $y$ 的所有层边距，在 C.2 节中正式定义。 现在，我们只需注意 $m$ 具有以下属性：如果 $G(x)\ne y$，则 $m(F,x,y)=0$，因此我们可以通过对所有阈值进行阈值化来限制 0-1 损失的上限-层边距：$\mathrm{𝟏}(G(x)\ne y)\le \mathrm{𝟏}(m(F,x,y)\ge t)$ 对于任何$t>0$。 我们还可以定义一个测量输入转换稳健性的变体：$m_{ℬ}(F,x)\triangleq {\min }_{x^{\prime }\in ℬ(x)}m(F,x^{\prime },{\arg \max }_{i}F{(x)}_i)$。 以下结果表明，大的全层裕度意味着输入一致性损失具有良好的泛化性，这出现在目标 (3.4) 中。

Theorem 3.7 (定理3.1的扩展（Wei & Ma, 2019b）)。

训练集 $\widehat{P}$ 的抽取概率为 $1-\delta$，所有 $F(x)\triangleq W_p\varphi (\mathrm{\cdots }\varphi (W_{1}x))$ 形式的神经网络 $G={\arg \max }_i{F}_i$ 将满足

$R_{ℬ}(G)$ $\le {𝔼}_{\widehat{P}}[\mathrm{𝟏}(m_{ℬ}(F,x)\le t)]+\tilde{O}\left({\displaystyle \frac{{\sum }_i\sqrt{q}{\Vert W_i\Vert }_F}{t\sqrt{n}}}\right)+\zeta$ (3.6)

对于所有 $t>0$ 的选择，其中 $\zeta \triangleq O\left(\sqrt{(\log (1/\delta )+p\log n)/n}\right)$ 是低阶项，而 $\tilde{O}(\cdot )$ 隐藏了 $n$ 和 $d$ 中的多对数因子。

对于 (3.4) 中的其他量，可以表达类似的界限，并在 C.2 节中提供。 在第 C.1 节中，我们将边界插入定理 3.6 和定理 4.3 中，以提供依赖于未标记训练集的准确性保证。 我们在 C.2 节中提供了证明概述，在 C.3 节中，我们提供了全层裕度的数据相关下界，该下界与模型的 Lipschitzness，通过训练数据的雅可比行列式和隐藏层规范来测量。 这些数量已被证明通常表现良好（Arora 等人，2018；Nagarajan & Kolter，2019；Wei & Ma，2019a）。 在D.2节中，我们凭经验证明，显式正则化全层边距可以提高自训练的性能。

4 用于半监督学习和领域适应的去噪伪标签

我们研究半监督学习和无监督领域适应设置，在这些设置中我们可以访问未标记的数据和伪标记器 $G_{\text{pl}}$。 这种设置需要比无监督学习设置更复杂的分析，因为伪标签可能不准确，并且学生分类器可能会放大这些错误。 我们设计了一个总体目标来衡量输入转换的一致性和伪标签的准确性。 假设扩展和分离，我们表明该目标的最小化器在ground-truth标签上将具有高精度。

我们假设可以访问伪标签$G_{\text{pl}}(\cdot )$，它是通过域适应设置中的标记源数据或半监督设置中的标记数据上的分类器获得的。 通过访问伪标签，我们可以准确地恢复真实标签，而不是像 3.2 节中那样进行排列。 对于$G,G^{\prime }:𝒳\to [K]$，将$L_{\text{0-1}}(G,G^{\prime })\triangleq {𝔼}_P[\mathrm{𝟏}(G(x)\ne G^{\prime }(x))]$定义为$G$和$G^{\prime }$之间的不一致。 错误度量是真实标签上的标准 0-1 损失：$\text{Err}(G)\triangleq L_{\text{0-1}}(G,G^{\star })$。 让 $ℳ(G_{\text{pl}})\triangleq \{x:G_{\text{pl}}(x)\ne G^{\star }(x)\}$ 表示一组错误的伪标签示例。 我们需要对扩展做出以下假设，直观地表明 $ℳ(G_{\text{pl}})$ 的每个子集都有足够大的邻域。

Assumption 4.1 ($P$ 在小于 $ℳ(G_{\text{pl}})$ 的集合上展开）。

将 $\overline{a}\triangleq {\max }_i\{P_i(ℳ(G_{\text{pl}}))\}$ 定义为任何类中错误伪标签示例的最大比例。 我们假设 和 $P$ 满足 $\overline{c}>3$ 的 $(\overline{a},\overline{c})$ 展开。 我们用 $c\triangleq \min \{1/\overline{a},\overline{c}\}$ 来表达我们的界限。

请注意，上述要求$c>3$比无监督学习设置中所需的条件$c>1$要求更高（假设3.2)。 较大的 $c>3$ 说明伪标签中的错误可能会以最坏情况的方式对学习的分类器产生不利影响。 这种担忧不适用于无监督学习，因为不使用伪标签。 对于示例 3.4 和 3.5 中的玩具分布，我们可以将邻域半径增加 3 倍以获得 (0.16, 6) 扩展，这已经足够了满足假设4.1中的要求。

另一方面，假设4.1比假设3.2严格，因为仅对于质量小于$\overline{a}$的小集合才需要扩展，伪标记器在类上的最坏情况错误，该错误可能比假设 3.2 中所需的 $a=1/2$ 小得多。 此外，无监督目标(3.4)具有输入一致性正则化器不能太大的约束，而此设置不需要这样的约束。 我们注意到，假设 4.1 也可以放宽，直接考虑错误伪标签示例子集的扩展，同时对扩展因子 $c$ 的要求更宽松（参见第 A.1)。 我们在分类器 $G$ 上设计了以下目标，它使分类器适合伪标签，同时规范输入一致性：

$\underset{G}{\min }ℒ(G)\triangleq {\displaystyle \frac{c+1}{c-1}}{L}_{\text{0-1}}(G,G_{\text{pl}})+{\displaystyle \frac{2c}{c-1}}{R}_{ℬ}(G)-\text{Err}(G_{\text{pl}})$ (4.1)

该目标优化了输入一致性正则化器$R_{ℬ}(G)$和拟合伪标签的损失$L_{\text{0-1}}(G,G_{\text{pl}})$的加权组合，并且与最近成功的半监督学习算法相关（孙等人，2020；谢等人，2020）。 我们可以证明 $ℒ(G)\ge 0$ 始终成立。 以下引理根据目标值限制 $G$ 的误差。

Lemma 4.2.

假设假设4.1成立。 那么分类器 $G:𝒳\to [K]$ 的错误在一致性方面受到限制。 伪标签的输入转换和准确性：$\text{Err}(G)\le ℒ(G)$。

当扩展和分离同时成立时，我们表明最小化 (4.1) 会导致分类器能够对伪标签进行去噪并提高其真实准确度。

Theorem 4.3.

假设假设 4.1 和 3.3 成立。 那么对于 (4.1) 的任何最小化 $\widehat{G}$，我们有

$\text{Err}(\widehat{G})\le {\displaystyle \frac{2}{c-1}}\text{Err}(G_{\text{pl}})+{\displaystyle \frac{2c}{c-1}}\mu$ (4.2)

我们在第 4.1 节中提供了证明草图，并在第 A.1 节中提供了完整证明。 我们的结果解释了一个可能令人惊讶的事实，即即使没有提供有关真实标签的附加信息，使用伪标签的自我训练通常也会比伪标签器有所改进。 在定理C.2中，我们使用3.3节中的泛化界限将定理4.3转化为有限样本保证。

乍一看，定理 4.3 中的误差界似乎比定理 3.6 弱，因为对 $\text{Err}(G_{\text{pl}})$ 的额外依赖。 这种差异是由于对扩展和输入一致性正则器的值的要求较弱。 首先，3.2节要求对所有概率小于$1/2$的集合进行扩展，而假设4.1只要求对概率小于$\overline{a}$，它可以比$1/2$小得多。 其次，3.2 节中的误差范围仅适用于 $R_{ℬ}(G)$ 值较小的分类器，如 (3.4) 中所示。 另一方面，引理4.2给出了所有分类器的错误界限，无论$R_{ℬ}(G)$如何。 事实上，加强对3.2节的扩展要求将使我们能够获得类似于定理3.6的精度保证，用于具有低输入一致性正则化值的伪标签训练分类器。

4.1 定理证明草图4.3

我们为所有示例的输入一致性正则化器均为 0 的极端情况提供了引理 4.2 的证明草图，即 $G(x)=G(x^{\prime })\forall x\in 𝒳,x^{\prime }\in ℬ(x)$，因此 $R_{ℬ}(G)=0$。 对于这个证明草图，我们还对 $L_{\text{0-1}}(G,G_{\text{pl}})=\text{Err}(G_{\text{pl}})$ 时的情况做了额外的限制。

我们首先介绍一些一般符号。 对于集合$U,V\subseteq 𝒳$，我们使用$U\setminus V$表示$\{x:x\in U,x\notin V\}$，使用$\cap ,\cup$分别表示集合交集和并集。 让 $\overline{U}\triangleq 𝒳\setminus U$ 表示 $U$ 的补集。

让 ${𝒞}_i\triangleq \{x:G^{\star }(x)=i\}$ 表示带有真实标签 $i$ 的示例集。 对于 $S\subseteq 𝒳$，我们将 ${𝒩}^{\star }(S)$ 定义为 $S$ 的邻域，其邻居仅限于同一类：${𝒩}^{\star }(S)\triangleq {\cup }_{i\in [K]}\left(𝒩(S\cap {𝒞}_i)\cap {𝒞}_i\right)$。 以下关键声明将考虑两个集合：分类器出错的正确伪标记示例集 $\{x:G(x)\ne G_{\text{pl}}(x)\text{and}x\notin ℳ(G_{\text{pl}})\}$，以及分类器和伪标记器都不符合基本事实的示例集 $ℳ(F)\cap ℳ(G_{\text{pl}})$. 下面的权利要求使用扩展属性来表明

$$P(\{x:G(x)\ne G_{\text{pl}}(x)\text{and}x\notin ℳ(G_{\text{pl}})\})>P(ℳ(F)\cap ℳ(G_{\text{pl}}))$$

Claim 4.4.

在定理4.3的设置中，定义集合$V\triangleq ℳ(G)\cap ℳ(G_{\text{pl}})$。 定义$q\triangleq \frac{\text{Err}(G_{\text{pl}})}{c-1}$。 通过展开（假设4.1)，如果$P(V)>q$，则$P({𝒩}^{\star }(V)\setminus ℳ(G_{\text{pl}}))>P(V)$。

权利要求 4.4 的更通用版本由 A.2 节中的引理 A.7 给出。 对于$V$和${𝒩}^{\star }(V)\setminus ℳ(G_{\text{pl}})$的可视化，请参见图2。

Claim 4.5。

假设所有示例的输入一致性正则化器均为 0，即 $\forall x\in 𝒳,x^{\prime }\in ℬ(x)$，则它保持 $G(x)=G(x^{\prime })$。 那么接下来就是

$\{x:G(x)\ne G_{\text{pl}}(x)\text{and}x\notin ℳ(G_{\text{pl}})\}\supseteq {𝒩}^{\star }(V)\setminus ℳ(G_{\text{pl}})$

图2概述了这一主张的证据。 A 部分中的声明 A.4 在 $R_{ℬ}(G)>0$ 的情况下提供了声明 4.5 的更通用版本。 鉴于上述情况，引理 4.2 的证明后面是一个计数论证。

用于简化设置的引理4.2的证明草图。

为了避免矛盾，假设$P(V)>q$。 我们可以将伪标签上$G$的错误分解如下：

$L_{\text{0-1}}(G,G_{\text{pl}})$ $\ge 𝔼[\mathrm{𝟏}(G(x)\ne G_{\text{pl}}(x)\text{and}x\notin ℳ(G_{\text{pl}}))]+𝔼[\mathrm{𝟏}(G(x)\ne G_{\text{pl}}(x)\text{and}x\in ℳ(G_{\text{pl}}))]$

我们通过声明 4.4 和 4.5 将第一项下限为 $P(V)$。 对于后一项，我们注意到如果 $x\in ℳ(G_{\text{pl}})\setminus V$，则 $G(x)=G^{\star }(x)\ne G_{\text{pl}}(x)$。 因此，后一项具有下限$P(ℳ(G_{\text{pl}}))-P(V)$。 结果，我们得到

$L_{\text{0-1}}(G,G_{\text{pl}})>P(V)+P(ℳ(G_{\text{pl}}))-P(V)=\text{Err}(G_{\text{pl}})$

这与我们的简化假设 $L_{\text{0-1}}(G,G_{\text{pl}})=\text{Err}(G_{\text{pl}})$ 相矛盾。 因此，$G$ 最多与 $ℳ(G_{\text{pl}})$ 中的 $q$ 部分示例的 $G^{\star }$ 不一致。 为了完成证明，我们注意到 $G$ 在 $ℳ(G_{\text{pl}})$ 之外最多 $q$ 部分示例上也不同意 $G^{\star }$，否则$L_{\text{0-1}}(G,G_{\text{pl}})$ 又太高了。 ∎

图2： 为了证明声明 4.5，我们首先注意到，在简化的设置中，如果 $ℬ(x)\cap ℬ(z)\ne \mathrm{\varnothing }$ 那么 $G(x)=G(z)$ 则假设 $R_{ℬ}(G)=0$ （参见左)。 根据 ${𝒩}^{\star }(\cdot )$ 的定义，这意味着所有点 $x\in {𝒩}^{\star }(V)\setminus ℳ(G_{\text{pl}})$ 必须满足 $G(x)\ne G^{\star }(x)$，因为 $x$ 与 $V\subseteq ℳ(G)$ 中相邻点的标签相匹配。 但是，$𝒳\setminus ℳ(G_{\text{pl}})$ 中的所有点都必须满足 $G_{\text{pl}}(x)=G^{\star }(x)$，因此也必须满足 $G(x)\ne G_{\text{pl}}(x)$。 这些集合如右侧所示。

5实验

在D.1节中，我们提供了图1中GAN实验的详细信息。 我们还为我们的理论直觉提供了经验证据，即使用输入一致性正则化的自我训练之所以成功，是因为该算法使用正确的伪标记邻居对错误的伪标记示例进行了去噪（图3)。 在D.2节中，我们对伪标签进行了消融研究，结果表明我们的理论目标(4.1)的组成部分确实提高了性能。

6结论

在这项工作中，我们提出了一个数据扩展假设，允许对半监督和无监督学习的自我训练进行统一的理论分析。 我们的假设对于现实世界的数据集是现实的，特别是在视觉方面。 我们的分析适用于深度神经网络，并且可以解释为什么基于自训练和输入一致性正则化的算法可以在未标记的数据上表现得如此出色。 我们希望这一假设能够促进未来的理论分析，并启发半监督和无监督学习的理论原理算法。 例如，未来工作的一个有趣问题是扩展我们的假设，以分析基于对齐源和目标的域适应算法（Hoffman等人，2018）。

致谢

我们要感谢 Ananya Kumar 提供的有益评论和讨论。 CW 感谢 NSF 研究生研究奖学金的支持。 TM 还得到了 Google 教师奖、斯坦福数据科学计划和斯坦福人工智能实验室的部分支持。 作者还要感谢斯坦福研究生奖学金计划的资助。

附录A伪标签去噪证明

在本节中，我们将提供定理4.3的证明。 我们的分析实际上依赖于较弱的加性扩展概念，定义如下。 我们证明定义 3.1 中的乘法定义将意味着加法变体成立。

A.1 放宽伪标签的扩展假设

在本节中，我们提供了定理 4.3 的宽松版本的证明。 然后，我们将在 A.2 节中将定理 4.3 简化为这个宽松版本。 将邻域概念限制为仅同一真实类中的示例将很有帮助：定义 ${𝒩}^{\star }(x)\triangleq \{x^{\prime }:x^{\prime }\in 𝒩(x)\text{and}{G}^{\star }(x^{\prime })=G^{\star }(x)\}$ 和 ${𝒩}^{\star }(S)\triangleq {\cup }_{x\in S}{𝒩}^{\star }(x)$。 请注意，$𝒩(S)$ 和 ${𝒩}^{\star }(S)$ 之间通常存在以下关系：

${𝒩}^{\star }(S)={\cup }_{i\in [K]}\left(𝒩(S\cap {𝒞}_i)\cap {𝒞}_i\right)$

我们将在下面定义 $𝒳$ 子集的扩展的加法概念。

Definition A.1 ($(q,\alpha )$-集合 $S$ 上的加法扩展)。

如果对于包含 $P(V)>q$ 的所有 $V\subseteq S$ 都成立，我们就说 $P$ 满足 $(q,\alpha )$ 在 $S\subseteq 𝒳$ 上的正扩展：

$P({𝒩}^{\star }(V)\setminus S)={\displaystyle \sum _{i\in [K]}}P(𝒩(V\cap {𝒞}_i)\cap {𝒞}_i\setminus S)>P(V)+\alpha$

换句话说，$S$ 的任何足够大的子集都必须具有足够大的共享相同真实标签的示例邻域。 在本节的剩余部分中，我们将分析这种附加的展开概念。 在A.2节中，我们将乘法展开（定义3.1)简化为上面的加法定义。

现在，对于给定的分类器，定义 $G$、${𝒮}_{ℬ}(G)$ 的稳健集，作为 $G$ 在 $ℬ$ 下稳健的输入集t3>-转换：

${𝒮}_{ℬ}(G)=\{x:G(x)=G(x^{\prime })\forall x^{\prime }\in ℬ(x)\}$

以下定理表明，如果分类器 $G$ 具有 $ℬ$ 鲁棒性并且足够好地拟合伪标签，则在 true 标签上的分类精度将会很高。

Theorem A.2.

对于给定的伪标签 $G_{\text{pl}}:𝒳\to \{1,\mathrm{\dots },K\}$，假设 $P$ 对于某些 $q,\alpha$ 在 $ℳ(G_{\text{pl}})$ 上具有 $(q,\alpha )$-additive-expansion 。 假设 $G$ 以足够的准确性和稳健性拟合伪标签：

${𝔼}_P[\mathrm{𝟏}(G(x)\ne G_{\text{pl}}(x)\text{or}x\notin {𝒮}_{ℬ}(G))]\le \text{Err}(G_{\text{pl}})+\alpha$ (A.1)

那么 $G$ 满足以下错误界限：

$\text{Err}(G)\le 2(q+R_{ℬ}(G))+{𝔼}_P[\mathrm{𝟏}(G(x)\ne G_{\text{pl}}(x))]-\text{Err}(G_{\text{pl}})$

为了解释这个陈述，假设 $G$ 拟合伪标签，错误率最多为 $\text{Err}(G_{\text{pl}})$ 并且 (A.1) 成立。 然后是$\text{Err}(G)\le 2(q+R_{ℬ}(G))$，因此如果$G$对$ℬ$对总体分布的扰动具有鲁棒性，则$G$

为了证明定理A.2，我们考虑$ℳ(G)\cap {𝒮}_{ℬ}(G)$的三个不相交子集：

${ℳ}_1$ $\triangleq \{x:G(x)=G_{\text{pl}}(x),G_{\text{pl}}(x)\ne G^{\star }(x),\text{and}x\in {𝒮}_{ℬ}(G)\}$

${ℳ}_2$ $\triangleq \{x:G(x)\ne G_{\text{pl}}(x),G_{\text{pl}}(x)\ne G^{\star }(x),G(x)\ne G^{\star }(x),\text{and}x\in {𝒮}_{ℬ}(G)\}$

${ℳ}_3$ $\triangleq \{x:G(x)\ne G_{\text{pl}}(x),G_{\text{pl}}(x)=G^{\star }(x),\text{and}x\in {𝒮}_{ℬ}(G)\}$

我们可以将这些集合解释如下：${ℳ}_1\cup {ℳ}_2\subseteq {𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G)$，其中$G_{\text{pl}}$和$G$都不适合真实标签的输入集合。 另一组 ${ℳ}_3$ 由输入组成，其中 $G_{\text{pl}}$ 适合真实标签，但 $G$ 不适合。 以下引理限制了 ${ℳ}_1\cup {ℳ}_2$ 的概率。

Lemma A.3.

在定理A.2的设定下，我们有$P({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G))\le q$。 结果，由于它包含 ${ℳ}_1\cup {ℳ}_2\subseteq {𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G)$，因此它紧随 $P({ℳ}_1\cup {ℳ}_2)\le q$ 之后。

证明依赖于以下思想：我们证明如果${𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G)$具有大概率，那么通过扩展假设，集合$U\triangleq {𝒩}^{\star }({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G))\setminus ℳ(G_{\text{pl}})$也将具有大概率（声明A.4 然而，我们还将证明 $x\in U\cap {𝒮}_{ℬ}(G)$ 中的示例必须满足 $G(x)\ne G_{\text{pl}}(x)$（主张 A.5），这意味着伪标签损失会对此类示例造成惩罚。 因此，$U$ 不能太大(A.1)，这意味着 ${𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G)$ 也不能太大。

Claim A.4。

在定理A.2的设置中，定义$U\triangleq {𝒩}^{\star }({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G))\setminus ℳ(G_{\text{pl}})$。 如果$P({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G))>q$，那么

$P(U\cap {𝒮}_{ℬ}(G))>P(ℳ(G_{\text{pl}}))+P({𝒮}_{ℬ}(G))+\alpha -1-P({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap \overline{ℳ(G)})$

证明。

定义$V\triangleq {𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G)$。 假设$ℳ(G_{\text{pl}})$满足$(q,\alpha )$-additive-expansion，如果$P(V)>q$成立，则$P(U)>P(V)+\alpha$成立。 此外，根据 $U$ 和 $V$ 的定义，我们将 $U\setminus {𝒮}_{ℬ}(G)\subseteq \overline{{𝒮}_{ℬ}(G)\cup ℳ(G_{\text{pl}})}$ 定义为 $U\cap ℳ(G_{\text{pl}})=\mathrm{\varnothing }$，等等 $P(U\setminus {𝒮}_{ℬ}(G))\le 1-P({𝒮}_{ℬ}(G)\cup ℳ(G_{\text{pl}}))$。 因此，我们得到

$P(U\cap {𝒮}_{ℬ}(G))$ $=P(U)-P(U\setminus {𝒮}_{ℬ}(G))$

$>P(V)+\alpha -1+P({𝒮}_{ℬ}(G)\cup ℳ(G_{\text{pl}}))$

现在我们利用包含排除原理来计算

$$P({𝒮}_{ℬ}(G)\cup ℳ(G_{\text{pl}}))=P(ℳ(G_{\text{pl}}))+P({𝒮}_{ℬ}(G))-P({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}}))$$

代入上式，我们得到

$P(U\cap {𝒮}_{ℬ}(G))$ $>P(ℳ(G_{\text{pl}}))+P({𝒮}_{ℬ}(G))+\alpha -1+P(V)-P({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}}))$

$=P(ℳ(G_{\text{pl}}))+P({𝒮}_{ℬ}(G))+\alpha -1-P({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap \overline{ℳ(G)})$

我们在其中获得了最后一行，因为 $V={𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G)\subseteq {𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})$。 ∎

Claim A.5。

在定理4.3的设置中，定义$U\triangleq {𝒩}^{\star }({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G))\setminus ℳ(G_{\text{pl}})$。 对于任何$x\in U\cap {𝒮}_{ℬ}(G)$，它都保持$G_{\text{pl}}(x)\ne G(x)$和$G(x)\ne G^{\star }(x)$。

证明。

对于任何$x\in U\subseteq {𝒩}^{\star }({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G))$，存在$x^{\prime }\in {𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G)$，使得根据${𝒩}^{\star }(\cdot )$的定义，$ℬ(x)\cap ℬ(x^{\prime })\ne \mathrm{\varnothing }$和$G^{\star }(x)=G^{\star }(x^{\prime })$。 选择$z\in ℬ(x)\cap ℬ(x^{\prime })$。 正如$x,x^{\prime }\in {𝒮}_{ℬ}(G)$一样，根据${𝒮}_{ℬ}(G)$的定义，我们也必须有$G(x)=G(z)=G(x^{\prime })$。 此外，如$x^{\prime }\in ℳ(G)$、$G(x^{\prime })\ne G^{\star }(x^{\prime })$。 从$G^{\star }(x)=G^{\star }(x^{\prime })$开始，就得出$G(x)\ne G^{\star }(x)$。

正如 $U$ 定义的 $U\cap ℳ(G_{\text{pl}})=\mathrm{\varnothing }$ 一样，$G_{\text{pl}}$ 与 $U$ 上的真实分类器非常匹配，因此 $G_{\text{pl}}(x)=G^{\star }(x)$ 。 根据需要，可以得出 $G(x)\ne G_{\text{pl}}(x)$。 ∎

我们通过结合声明A.4和声明A.5来导出矛盾来完成引理A.3的证明。

引理A.3的证明。

为了完成引理A.3的证明，我们首先将${𝒮}_{ℬ}(G)$组成三个不相交的集合：

$S_1$ $\triangleq \{x:G(x)=G_{\text{pl}}(x)\}\cap {𝒮}_{ℬ}(G)$

$S_2$ $\triangleq \{x:G(x)\ne G_{\text{pl}}(x)\}\cap ℳ(G_{\text{pl}})\cap {𝒮}_{ℬ}(G)$

$S_3$ $\triangleq \{x:G(x)\ne G_{\text{pl}}(x)\}\cap \overline{ℳ(G_{\text{pl}})}\cap {𝒮}_{ℬ}(G)$

首先，根据声明A.5和$U$的定义，我们有$\forall x\in U\cap {𝒮}_{ℬ}(G)$、$G(x)\ne G_{\text{pl}}(x)$和$x\notin ℳ(G_{\text{pl}})$ 。 因此，可以得出$U\cap {𝒮}_{ℬ}(G)\subseteq S_3$。

接下来，我们声明$V^{\prime }\triangleq ℳ(G_{\text{pl}})\cap \overline{ℳ(G)}\cap {𝒮}_{ℬ}(G)\subseteq S_2$。 要查看这一点，请注意 $x\in V^{\prime }$、$G(x)=G^{\star }(x)$ 和 $G_{\text{pl}}(x)\ne G^{\star }(x)$。 因此，$G(x)\ne G_{\text{pl}}(x)$ 和 $x\in {𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})$ 意味着 $x\in S_2$。

为了避免矛盾，假设$P({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G))>q$。 现在我们有

$P({𝒮}_{ℬ}(G))$ $\ge P(S_1)+P(S_2)+P(S_3)$

$\ge P(S_1)+P({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap \overline{ℳ(G)})+P(U\cap {𝒮}_{ℬ}(G))$

$>P(S_1)+P(ℳ(G_{\text{pl}}))+P({𝒮}_{ℬ}(G))+\alpha -1$ (by Claim A.4)

不过，我们也有

$P(S_1)$ $=1-{𝔼}_P[\mathrm{𝟏}(G(x)\ne G_{\text{pl}}(x)\text{or}x\notin {𝒮}_{ℬ}(G))]$

$\ge 1-\text{Err}(G_{\text{pl}})-\alpha$ (by the condition in (A.1))

将其代入会产生一个矛盾 $P(S_1)+P(S_2)+P(S_3)>P({𝒮}_{ℬ}(G))$。 因此，$P({𝒮}_{ℬ}(G)\cap ℳ(G_{\text{pl}})\cap ℳ(G))\le q$，如所希望的那样。 ∎

下一个引理限制$P({ℳ}_3)$。

Lemma A.6.

在定理A.2的设置下，以下界限成立：

$P({ℳ}_3)\le q+R_{ℬ}(G)+{𝔼}_P[\mathrm{𝟏}(G(x)\ne G_{\text{pl}}(x))]-\text{Err}(G_{\text{pl}})$

证明。

证明将从基本操作中得出。 首先，我们注意到

${ℳ}_3\cup \{x:G(x)=G_{\text{pl}}(x)\text{and}x\in {𝒮}_{ℬ}(G)\}$ (A.2)

$=$ $(\{x:G(x)\ne G_{\text{pl}}(x),G_{\text{pl}}(x)=G^{\star }(x)\}\cup \{x:G(x)=G_{\text{pl}}(x),G_{\text{pl}}(x)=G^{\star }(x)\}$

$\cup \{x:G(x)=G_{\text{pl}}(x),G_{\text{pl}}(x)\ne G^{\star }(x)\})\cap 𝒮{}_{ℬ}(G)$

$=$ ${ℳ}_1\cup \{x:G_{\text{pl}}(x)=G^{\star }(x)\text{and}x\in {𝒮}_{ℬ}(G)\}$ (A.3)

由于 (A.2) 和 (A.3) 属于不相交集合的并集，因此可以得出以下结论

$P({ℳ}_3)+P(\{x:G(x)=$

$G_{\text{pl}}(x)\text{and}x\in {𝒮}_{ℬ}(G)\})=P({ℳ}_1)+P(\{x:G_{\text{pl}}(x)=G^{\star }(x)\text{and}x\in {𝒮}_{ℬ}(G)\})$

因此，重新排列我们得到

$P({ℳ}_3)$ $=P({ℳ}_1)+P(\{x:G_{\text{pl}}(x)=G^{\star }(x)\}\cap {𝒮}_{ℬ}(G)\})$

$-P(\{x:G(x)=G_{\text{pl}}(x)\}\cap {𝒮}_{ℬ}(G)\})$

$\le P({ℳ}_1)+P(\{x:G_{\text{pl}}(x)=G^{\star }(x)\})-P(\{x:G(x)=G_{\text{pl}}(x)\}\cap {𝒮}_{ℬ}(G)\})$

$\le P({ℳ}_1)+P(\{x:G_{\text{pl}}(x)=G^{\star }(x)\})-P(\{x:G(x)=G_{\text{pl}}(x)\})$

$+P(\{x:G(x)=G_{\text{pl}}(x)\}\cap \overline{{𝒮}_{ℬ}(G)})$

$\le P({ℳ}_1)+P(\{x:G(x)\ne G_{\text{pl}}(x)\})-P(ℳ(G_{\text{pl}}))+1-P({𝒮}_{ℬ}(G))$

$=P({ℳ}_1)+R_{ℬ}(G)+{𝔼}_P[\mathrm{𝟏}(G(x)\ne G_{\text{pl}}(x))]-\text{Err}(G_{\text{pl}})$

将引理 A.3 替换为 $P({ℳ}_1)\le q$ 即可得到所需的结果。 ∎

最后，结合引理A.3和A.6完成定理A.2的证明。

定理证明A.2。

为了完成证明，我们计算

$\text{Err}(G)=P(ℳ(G))$ $\le P(ℳ(G)\cap {𝒮}_{ℬ}(G))+P(\overline{{𝒮}_{ℬ}(G)})$

$=P({ℳ}_1)+P({ℳ}_2)+P({ℳ}_3)+R_{ℬ}(G)$

$\le 2(q+R_{ℬ}(G))+{𝔼}_P[\mathrm{𝟏}(G(x)\ne G_{\text{pl}}(x))]-\text{Err}(G_{\text{pl}})$ (by Lemmas A.3 and A.6)

∎

A.2 定理证明4.3

在本节中，我们通过将引理4.2简化为定理A.2来完成定理4.3的证明。 这需要将乘法扩展转换为 $(q,\alpha )$-additive-expansion，这是在以下引理中完成的。 让 ${ℳ}_i(G_{\text{pl}})\triangleq ℳ(G_{\text{pl}})\cap {𝒞}_i$ 表示带有真实类 $i$ 的错误伪标签示例。

Lemma A.7.

在定理4.3的设定下，假设假设4.1成立。 然后对于任何 $\beta \in (0,c-1]$,$P_i$ 在 ${ℳ}_i(G_{\text{pl}})$ 上具有 $(q,\alpha )$-additive-expansion，用于以下选择 $q,\alpha$ :

(A.4)

证明。

考虑任何带有 $P_i(S)>\frac{\beta P_i({ℳ}_i(G_{\text{pl}}))}{c-1}$ 的 $S\subseteq {ℳ}_i(G_{\text{pl}})$ 集合。 然后根据假设4.1,$P_i(𝒩(S))\ge \min \{c{P}_i(S),1\}\ge c{P}_i(S)$，我们使用了$P_i(S)\le P_i({ℳ}_i(G_{\text{pl}}))$和$c\le \frac{1}{P_i({ℳ}_i(G_{\text{pl}}))}$这一事实，所以$c{P}_i(S)\le 1$ 。 由此，我们可以得到

$P_i(𝒩(S)\setminus {ℳ}_i(G_{\text{pl}}))$ $\ge c{P}_i(S)-P_i({ℳ}_i(G_{\text{pl}}))$

$=P_i(S)+(c-1)P_i(S)-P_i({ℳ}_i(G_{\text{pl}}))$

$>P_i(S)+(\beta -1)P_i({ℳ}_i(G_{\text{pl}}))$

这里最后一行使用了$P_i(S)>\frac{\beta P_i({ℳ}_i(G_{\text{pl}}))}{c-1}$这一事实。 这意味着对于 (A.4) 中给出的 $(q,\alpha )$ 来说，$P_i$ 在 ${ℳ}_i(G_{\text{pl}})$ 上有 $(q,\alpha )$ 正展开。 ∎

现在我们将完成引理4.2的证明。 Note that given Lemma 4.2, Theorem 4.3 follows immediately by noting that $G^{\star }$ satisfies $L_{\text{0-1}}(G^{\star },G_{\text{pl}})=\text{Err}(G_{\text{pl}})$ and $R_{ℬ}(G^{\star })\le \mu$ by Assumption 3.3.

我们首先定义类条件伪标签和鲁棒性损失：$L_{\text{0-1}}^{(i)}(G,G^{\prime })\triangleq P_i(\{x:G(x)\ne G^{\prime }(x)\})$和$R_{ℬ}^{(i)}(G)\triangleq {𝔼}_{P_i}[\mathrm{𝟏}(\exists x^{\prime }\in ℬ(x)\text{such that}G(x^{\prime })\ne G(x))]$。 我们还将类条件错误定义如下：${\text{Err}}_i(G)\triangleq L_{\text{0-1}}^{(i)}(G,G^{\star })$。 我们在下面证明引理 4.2 的类条件变体。

Lemma A.8.

对于任何 $i\in [K]$，定义

${ℒ}_i(G)\triangleq {\displaystyle \frac{c+1}{c-1}}{L}_{\text{0-1}}^{(i)}(G,G_{\text{pl}})-{\text{Err}}_i(G_{\text{pl}})+{\displaystyle \frac{2c}{c-1}}{R}_{ℬ}^{(i)}(G)$ (A.5)

然后，在假设 4.1 成立的定理 4.3 的设置中，我们对类 $i$ 有以下错误界限：

${\text{Err}}_i(G)\le {ℒ}_i(G)$ (A.6)

证明。

首先，我们考虑$L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})+R_{ℬ}^{(i)}(G)\le (c-1){\text{Err}}_i(G_{\text{pl}})$的情况。 在这种情况下，我们可以应用引理A.7并选择$\beta \in (0,c-1]$，这样

$(\beta -1){\text{Err}}_i(G_{\text{pl}})=L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})+R_{ℬ}^{(i)}(G)-{\text{Err}}_i(G_{\text{pl}})$ (A.7)

我们注意到 $P_i$ 在 ${ℳ}_i(G_{\text{pl}})$ 上有 $(q,\alpha )$-additive-expansion

$q$ $={\displaystyle \frac{\beta }{c-1}}{\text{Err}}_i(G_{\text{pl}})$ (A.8)

$\alpha$ $=(\beta -1){\text{Err}}_i(G_{\text{pl}})$ (A.9)

现在通过(A.7)，我们可以应用定理A.2并选择$(q,\alpha )$来获得

${\text{Err}}_i(G)$ $\le 2(q+R_{ℬ}^{(i)}(G))+L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})-{\text{Err}}_i(G_{\text{pl}})$ (A.10)

$={\displaystyle \frac{2\beta }{c-1}}{\text{Err}}_i(G_{\text{pl}})+2R_{ℬ}^{(i)}(G)+L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})-{\text{Err}}_i(G_{\text{pl}})$ (A.11)

$={\displaystyle \frac{c+1}{c-1}}{L}_{\text{0-1}}^{(i)}(G,G_{\text{pl}})-{\text{Err}}_i(G_{\text{pl}})+{\displaystyle \frac{2c}{c-1}}{R}_{ℬ}^{(i)}(G)$ (plugging in the value of $\beta$)

$={ℒ}_i(G)$ (A.12)

接下来，我们考虑$L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})+R_{ℬ}^{(i)}(G)>(c-1){\text{Err}}_i(G_{\text{pl}})$的情况。 请注意，根据三角不等式，我们有

${\text{Err}}_i(G)=L_{\text{0-1}}^{(i)}(G,G^{\star })$ $\le L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})+L_{\text{0-1}}^{(i)}(G_{\text{pl}},G^{\star })$ (A.13)

$=L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})+2{\text{Err}}_i(G_{\text{pl}})-{\text{Err}}_i(G_{\text{pl}})$ (A.14)

$\le L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})+{\displaystyle \frac{2}{c-1}}(L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})+R_{ℬ}^{(i)}(G))-{\text{Err}}_i(G_{\text{pl}})$ (A.15)

$\le {\displaystyle \frac{c+1}{c-1}}(L_{\text{0-1}}^{(i)}(G,G_{\text{pl}})+R_{ℬ}^{(i)}(G))-{\text{Err}}_i(G_{\text{pl}})$ (A.16)

$\le {\displaystyle \frac{c+1}{c-1}}{L}_{\text{0-1}}^{(i)}(G,G_{\text{pl}})+{\displaystyle \frac{2c}{c-1}}{R}_{ℬ}^{(i)}(G)-{\text{Err}}_i(G_{\text{pl}})$ (using $c>1$)

$={ℒ}_i(G)$ (A.17)

∎

引理 4.2 现在只需对所有类取 (A.6) 中界限的期望即可得出。

附录B无监督学习的证明

我们将首先证明引理 B.7 的宽松扩张概念的类似物。 然后，我们将通过证明乘法展开意味着这个宽松的概念来证明定理3.6，定义如下：

Definition B.1 ($(q,\xi )$-constant-expansion).

如果对于满足 $P(S)\ge q$ 和 $P(S\cap {𝒞}_i)\le P({𝒞}_i)/2$ 的所有 $i$ 的所有 $S\subseteq 𝒳$ 来说，以下条件成立，我们就说分布 $P$ 满足 $(q,\xi )$ 实体扩展：

$P({𝒩}^{\star }(S)\setminus S)\ge \min \{\xi ,P(S)\}$

如前所述，${𝒩}^{\star }(S)$ 由${\cup }_{i\in [K]}(𝒩(S\cap {𝒞}_i)\cap {𝒞}_i)$ 定义。 我们将在本小节中使用上述扩展概念。 我们首先展示了一个为每个类别分配足够概率的$ℬ$鲁棒标记函数，该函数将与真实类别保持一致。

Theorem B.2.

假设 $P$ 满足某个 $q$ 的 $(q,\xi )$-stant-expansion 条件。 如果它成立 并且

$\underset{i}{\min }P(\{x:G(x)=i\})>2\max \{q,R_{ℬ}(G)\}$

存在满足以下条件的排列 $\pi :[K]\to [K]$：

$P(\{x:\pi (G(x))\ne G^{\star }(x)\})\le \max \{q,R_{ℬ}(G)\}+R_{ℬ}(G)$ (B.1)

将${\widehat{𝒞}}_1,\mathrm{\dots },{\widehat{𝒞}}_K$定义为由$G$:${\widehat{𝒞}}_i\triangleq \{x:G(x)=i\}$引起的分区。 以下引理显示 ${\cup }_{j\in 𝒥}{\widehat{𝒞}}_j$ 的某些子集的邻域未由 $G$ 稳健地标记，其中 $𝒥$ 是 $[K]$ 的某些子集。

Lemma B.3.

在定理B.2的设置中，考虑$U\triangleq {𝒮}_{ℬ}(G)\cap ({\cup }_{i\in ℐ}{𝒞}_i)\cap ({\cup }_{j\in 𝒥}{\widehat{𝒞}}_j)$形式的任何集合，其中$ℐ,𝒥$是$[K]$的任意子集。 然后${𝒩}^{\star }(U)\setminus U\subseteq \overline{{𝒮}_{ℬ}(G)}$。

证明。

考虑任何$x\in {𝒩}^{\star }(U)\setminus U$。 有两种情况。 首先，如果$G(x)\in 𝒥$，则根据${𝒩}^{\star }(\cdot )$的定义，$x\in {\cap }_{i\in ℐ}{𝒞}_i{\cap }_{j\in 𝒥}{\widehat{𝒞}}_j$。 然而，$x\notin U$，它一定暗示着$x\notin {𝒮}_{ℬ}(G)$。 其次，如果$G(x)\notin 𝒥$，根据${𝒩}^{\star }(\cdot )$的定义，存在$x^{\prime }\in U$使得$ℬ(x)\cap ℬ(x^{\prime })\ne \mathrm{\varnothing }$。 对于$z\in ℬ(x)\cap ℬ(x^{\prime })$,$G(z)=G(x^{\prime })\in 𝒥$ 也是如此。 因此，由于$G(x)\notin 𝒥$,$G(x)\ne G(z)$所以$x\notin {𝒮}_{ℬ}(G)$。 因此，可以得出${𝒩}^{\star }(U)\setminus U\subseteq \overline{{𝒮}_{ℬ}(G)}$。 ∎

接下来，我们展示 $G$ 找到的每个簇将占据某些真实类别的大部分标签。

Lemma B.4.

在定理B.2的设定下，对于所有$j$，存在$i$使得$P({𝒮}_{ℬ}(G)\cap {𝒞}_i\cap {\widehat{𝒞}}_j)>\frac{P({𝒮}_{ℬ}(G)\cap {𝒞}_i)}{2}$。

证明。

为了矛盾起见，假设存在$j$，使得对于所有$i$,$P({𝒮}_{ℬ}(G)\cap {𝒞}_i\cap {\widehat{𝒞}}_j)\le \frac{P({𝒮}_{ℬ}(G)\cap {𝒞}_i)}{2}$。 定义集合$U_i\triangleq {𝒮}_{ℬ}(G)\cap {𝒞}_i\cap {\widehat{𝒞}}_j$和$U\triangleq {\cup }_i{U}_i={𝒮}_{ℬ}(G)\cap {\widehat{𝒞}}_j$。 请注意，${\{U_i\}}_{i=1}^K$ 形成 $U$ 的分区，因为 ${\{{𝒞}_i\}}_{i=1}^K$ 本身彼此不相交。 此外，我们可以将引理B.3与$ℐ=[K]$一起应用以获得${𝒩}^{\star }(U)\setminus U\subseteq \overline{{𝒮}_{ℬ}(G)}$。

现在我们观察到$P(U)\ge P({\widehat{𝒞}}_j)-P(\overline{{𝒮}_{ℬ}(G)})$。 使用定理条件$P({\widehat{𝒞}}_j)>2P(\overline{{𝒮}_{ℬ}(G)})$，可以得出

$P(U)>{\displaystyle \frac{P({\widehat{𝒞}}_j)}{2}}>\max \{q,P(\overline{{𝒮}_{ℬ}(G)})\}$

此外，对于所有 $i$ 我们注意到

$P({𝒞}_i\setminus U_i)\ge P({𝒮}_{ℬ}(G)\cap {𝒞}_i)-P(U_i)\ge {\displaystyle \frac{P({𝒮}_{ℬ}(G)\cap {𝒞}_i)}{2}}\ge P(U_i)$ (B.2)

因此，$P({𝒞}_i)\ge 2P(U_i)$。 因此，通过 $(q,\xi )$-constant-expansion 我们有

$P({𝒩}^{\star }(U)\setminus U)\ge \min \{\xi ,P(U)\}\ge \min \{\xi ,P({\widehat{𝒞}}_j)/2\}$

作为${𝒩}^{\star }(U)\setminus U\subseteq \overline{{𝒮}_{ℬ}(G)}$，这意味着$R_{ℬ}(G)=P(\overline{{𝒮}_{ℬ}(G)})\ge \min \{\xi ,P({\widehat{𝒞}}_j)/2\}$，一个矛盾。 ∎

前面的引理将用于构造由 $G$ 预测的自然排列映射类到真实类。

Lemma B.5.

在定理B.2和引理B.4的设定下，对于所有$j$，存在唯一的$\pi (j)$，例如表示 $P({𝒮}_{ℬ}(G)\cap {𝒞}_{\pi (j)}\cap {\widehat{𝒞}}_j)>\frac{P({𝒮}_{ℬ}(G)\cap {𝒞}_{\pi (j)})}{2}$,$P({𝒮}_{ℬ}(G)\cap {𝒞}_i\cap {\widehat{𝒞}}_j)\le \frac{P({𝒮}_{ℬ}(G)\cap {𝒞}_i}{2}$ 表示 $i\ne \pi (j)$。 此外，$\pi$是从$[K]$到$[K]$的排列。

证明。

根据引理 B.4 的结论，这种 $\pi$ 的存在可能不成立的唯一方式是，如果存在某个 $j$，其中 $P({𝒮}_{ℬ}(G)\cap {𝒞}_i\cap {\widehat{𝒞}}_j)>\frac{P({𝒮}_{ℬ}(G)\cap {𝒞}_i}{2}$ 代表 $i\in \{i_1,i_2\}$，其中 $i_1\ne i_2$。 在这种情况下，根据鸽子洞原理，由于 Lemma B.4 的结论适用于所有 $j\in [K]$，并且 $i$ 有 $K$ 种可能的选择，因此一定存在 $i$ 其中 $P({𝒮}_{ℬ}(G)\cap {𝒞}_i\cap {\widehat{𝒞}}_j)>\frac{P({𝒮}_{ℬ}(G)\cap {𝒞}_i)}{2}$ 对于 $j\in \{j_1,j_2\}$，其中 $j_1\ne j_2$ 。 那么$P({𝒮}_{ℬ}(G)\cap {𝒞}_i\cap {\widehat{𝒞}}_{j_1})+P({𝒮}_{ℬ}(G)\cap {𝒞}_i\cap {\widehat{𝒞}}_{j_2})>P({𝒮}_{ℬ}(G)\cap {𝒞}_i)$，这是一个矛盾。

最后，要看到 $\pi$ 是一个排列，请注意，如果 $\pi (j_1)=\pi (j_2)$ 为 $j_1\ne j_2$，这将导致与上面相同的矛盾。 ∎

最后，我们通过证明定理B.2的条件意味着引理中构造的排列$\pi$来完成定理B.2的证明B.5会产生较小的误差。

定理证明B.2。

我们将使用引理B.5中定义的$\pi$来证明(B.1)。 定义集合$U_j\triangleq {𝒮}_{ℬ}(G)\cap {𝒞}_{\pi (j)}{\cap }_{k\ne j}{\widehat{𝒞}}_k$。 请注意$U_j=\{x:G(x)\ne j,G^{\star }(x)=\pi (j)\}\cap {𝒮}_{ℬ}(G)$。 定义$U={\cup }_j{U}_j$，并注意${\{U_j\}}_{j=1}^K$形成$U$的分区。 此外，我们还有$U=\{x:\pi (G(x))\ne G^{\star }(x)\}\cap {𝒮}_{ℬ}(G)$。 我们首先展示$P(U)\le \max \{q,R_{ℬ}(G)\}$。 为了矛盾起见，假设这不成立。

首先，我们声明${\{{𝒩}^{\star }(U_j)\setminus U_j\}}_{j=1}^k\supseteq {𝒩}^{\star }(U)\setminus U$。 要看到这一点，请考虑任何 $x\in {𝒞}_{\pi (j)}\cap {𝒩}^{\star }(U)\setminus U$。 根据定义，$\exists x^{\prime }\in U$ 使得 $ℬ(x^{\prime })\cap ℬ(x)\ne \mathrm{\varnothing }$ 和 $G^{\star }(x)=G^{\star }(x^{\prime })$ 或 $x^{\prime }\in {𝒞}_{\pi (j)}$。 因此，可以得出 $x\in {𝒩}^{\star }({𝒞}_{\pi (j)}\cap U)\setminus U={𝒩}^{\star }(U_j)\setminus U={𝒩}^{\star }(U_j)\setminus U_j$，其中最后一个相等是由于 ${𝒩}^{\star }(U_j)$ 和 $U_k$ 对于 $j\ne k$ 来说是不相交的事实。 现在我们将引理 B.3 应用于每个 ${𝒩}^{\star }(U_j)\setminus U_j$ 来得出 ${𝒩}^{\star }(U)\setminus U\subseteq \overline{{𝒮}_{ℬ}(G)}$ 的结论。

最后，我们观察到

$P(U_j)=P({𝒮}_{ℬ}(G)\cap {𝒞}_{\pi (j)})-P({𝒮}_{ℬ}(G)\cap {𝒞}_{\pi (j)}\cap {\widehat{𝒞}}_j)\le {\displaystyle \frac{P({𝒮}_{ℬ}(G)\cap {𝒞}_{\pi (j)})}{2}}\le {\displaystyle \frac{P({𝒞}_{\pi (j)})}{2}}$ (B.3)

根据引理 B.5 中 $\pi$ 的定义。 现在我们再次应用 $(q,\xi )$-constant-expansion 属性，正如我们假设的 $P(U)>q$ 一样，获得

$P({𝒩}^{\star }(U)\setminus U)\ge \min \{\xi ,P(U)\}$

然而，正如我们展示的${𝒩}^{\star }(U)\setminus U\subseteq \overline{{𝒮}_{ℬ}(G)}$，我们也有$R_{ℬ}(G)=P(\overline{{𝒮}_{ℬ}(G)})\ge P({𝒩}^{\star }(U)\setminus U)\ge \min \{\xi ,P(U)\}$。 这与 $P(U)>\max \{q,R_{ℬ}(G)\}$ 和 矛盾，因此与 $P(U)\le \max \{q,R_{ℬ}(G)\}$ 矛盾。

最后，我们注意到$\{x:\pi (G(x))\ne G^{\star }(x)\}\subseteq U\cup \overline{{𝒮}_{ℬ}(G)}$。 这样，我们最终得到

$P(\{x:\pi (G(x))\ne G^{\star }(x)\})\le P(U)+P(\overline{{𝒮}_{ℬ}(G)})\le \max \{q,R_{ℬ}(G)\}+R_{ℬ}(G)$

∎

B.1 定理证明3.6

在本节中，我们通过将乘法展开式转换为$(q,\xi )$-constant-expansion并调用定理B.2来证明定理3.6。 以下引理执行此转换。

Lemma B.6.

假设 $P$ 满足 $𝒳$ 上的 $(1/2,c)$ 乘法展开（定义 3.1）。 那么，对于任何 $\xi >0$ 的选择，$P$ 都满足 $(\frac{\xi }{c-1},\xi )$ 恒定扩展。

证明。

考虑任何$S$，使得$P(S\cap {𝒞}_i)\le P({𝒞}_i)/2$适用于所有$i\in [K]$和$P(S)>q$。 定义$S_i\triangleq S\cap {𝒞}_i$。 首先，在 $c\ge 2$ 的情况下，我们通过乘法展开

$P({𝒩}^{\star }(S)\setminus S)$ $\ge {\displaystyle \sum _i}P({𝒩}^{\star }(S_i))-P(S_i)$

$\ge {\displaystyle \sum _i}\min \{cP(S_i),P({𝒞}_i)\}-P(S_i)$

$\ge {\displaystyle \sum _i}P(S_i)$ (because $c\ge 2$ and $P(S_i)\le P({𝒞}_i)/2$)

这样，我们立即获得了不断的扩张。

现在我们考虑的情况。 通过乘法展开，我们必须有

$P({𝒩}^{\star }(S)\setminus S)$ $\ge {\displaystyle \sum _i}\min \{cP(S_i),P({𝒞}_i)\}-P(S_i)$

$\ge {\displaystyle \sum _i}(c-1)P(S_i)$ (because and $P(S_i)\le P({𝒞}_i)/2$)

$\ge (c-1)q=\xi$

∎

以下引理说明了乘法展开设置的准确性保证。

Lemma B.7.

假设假设 3.2 对于某些 $c>1$ 成立。 如果分类器$G$满足

$\underset{i}{\min }{𝔼}_P[\mathrm{𝟏}(G(x)=i)]>\max \{{\displaystyle \frac{2}{c-1}},2\}{R}_{ℬ}(G)$

那么无监督误差就很小：

${\text{Err}}_{\text{unsup}}(G)\le \max \{{\displaystyle \frac{c}{c-1}},2\}{R}_{ℬ}(G)$ (B.4)

我们现在证明引理B.7，它又立即给出定理3.6的证明。

引理B.7的证明。

根据引理B.6,$P$必须满足$(\frac{R_{ℬ}(G)}{c-1},R_{ℬ}(G))$-constant-expansion。 由于我们还有 ${\min }_{i}P(\{x:G(x)=i\})>\max \{\frac{2}{c-1},2\}{R}_{ℬ}(G)$，我们现在可以应用定理 B.2 得出结论，存在排列 $\pi :[K]\to [K]$，使得

$P(\{x:\pi (G(x))\ne G^{\star }(x)\})\le \max \{{\displaystyle \frac{c}{c-1}},2\}{R}_{ℬ}(G)$

如预期的。 ∎

B.2 示例3.4和3.5的理由

为了避免示例 3.4 的不相交问题，我们可以将真实类 $G^{\star }(x)$ 重新定义为 $x$ 处最有可能的标签。 这也会导致截断的类条件分布 ${\overline{P}}_1$、${\overline{P}}_2$，其中重叠被删除。 我们可以将理论分析应用于 ${\overline{P}}_1$、${\overline{P}}_2$，然后将结果转换回 $P_1,P_2$，仅在重叠最小时稍微改变边界。

为了证明例 3.4，我们使用了高斯等周不等式 （Bobkov 等人，1997 年），该不等式指出，对于任何固定的 $p$，其中 $P_i(S)=p$ 为 $i\in \{1,2\}$，选择 $S$ 使 $P_i(𝒩(S))$ 最小化的半空间给出：$S=H(p)\triangleq \{x:w^{\top }(x-{\tau }_i)\le {\mathrm{\Phi }}^{-1}(p)\}$为矢量 $w$ 与 $\Vert w\Vert =\sqrt{d}$。 然后是设置$r=\frac{1}{\sqrt{d}}$、$𝒩(H(p))\supseteq \{x+t\frac{w}{{\Vert w\Vert }_2}:x\in H(p),0\le t\le r\}\supseteq \{x:w^{\top }(x-{\tau }_i)\le {\mathrm{\Phi }}^{-1}(p)+r\sqrt{d}\}$，以及$P(𝒩(H(p)))\ge \mathrm{\Phi }({\mathrm{\Phi }}^{-1}(p)+r\sqrt{d})$。 由于 $P(𝒩(H(p)))/P(H(p))$ 在 $p$ 中对于 正在减少，因此我们关于扩展的主张如下。 要查看我们关于分离的声明，请考虑集合 ${𝒳}_i\triangleq \{x:{(x-{\tau }_i)}^{\top }{v}_{ij}\le \frac{\Vert {\tau }_i-{\tau }_j\Vert }{2}-r/2\forall j\}$，其中 $v_{ij}\triangleq \frac{{\tau }_j-{\tau }_i}{{\Vert {\tau }_j-{\tau }_i\Vert }_2}$。 我们注意到这些集合是 $\beta$ 相互分离的，此外，对于示例中 $\Vert {\tau }_i-{\tau }_j\Vert$ 的下限，我们注意到 ${𝒳}_i$ 在 $P_i$ 下的概率为 $1-\mu$。

对于示例3.5，我们注意到对于$ℬ(x)\triangleq \{x^{\prime }:{\Vert x^{\prime }-x\Vert }_2\le r\}$,$𝒩(S)\supseteq M(\{x^{\prime }:\exists x\in M^{-1}(S)\text{such that}\Vert x^{\prime }-x\Vert \le r/\kappa \})$。 因此，我们关于扩张的主张简化为高斯情况。

附录C全层边距泛化边界

C.1 端到端保证

在本节中，我们为有限训练集的无监督学习、半监督学习和无监督域适应提供端到端保证。 对于以下两个定理，我们将符号 $\tilde{O}(\cdot )$ 作为某些乘法量的占位符，该乘法量是 $n,d$ 中的多对数。 我们首先为无监督学习提供有限样本保证。

Theorem C.1.

在定理3.6和节3.3的设置下，假设假设3.2成立。 假设 $G={\arg \max }_i{F}_i$ 被参数化为 $F(x)\triangleq W_p\varphi (\mathrm{\cdots }\varphi (W_{1}x)\mathrm{\cdots })$ 形式的神经网络。 以抽取训练样本 $\widehat{P}$ 的概率 $1-\delta$，如果在 $t>0$ 和 ${\{u_y\}}_{y=1}^K$ 中任意选择 $u_y>0\forall y$，则成立

${𝔼}_{\widehat{P}}[\mathrm{𝟏}(m(F,x,y)\ge u_y)]-\max \{{\displaystyle \frac{2}{c-1}},2\}{𝔼}_{\widehat{P}}[\mathrm{𝟏}(m_{ℬ}(F,x)\le t)]$

$\ge \tilde{O}\left(\left({\displaystyle \frac{{\sum }_i\sqrt{q}{\Vert W_i\Vert }_F}{c-1}}\right)\left({\displaystyle \frac{1}{u_y\sqrt{n}}}+{\displaystyle \frac{1}{t\sqrt{n}}}\right)\right)+\zeta \text{for all}y\in [K]$

那么总体无监督误差很小：

${\text{Err}}_{\text{unsup}}(G)\le \max \{{\displaystyle \frac{c}{c-1}},2\}{𝔼}_{\widehat{P}}[\mathrm{𝟏}(m_{ℬ}(F,x)\le t)]+\tilde{O}\left({\displaystyle \frac{{\sum }_i\sqrt{q}{\Vert W_i\Vert }_F}{t\sqrt{n}}}\right)+\zeta$

其中 $\zeta \triangleq O\left(\frac{1}{c-1}\sqrt{\frac{\log (K/\delta )+p\log n}{n}}\right)$ 是低阶项。

以下定理为无监督域适应和半监督学习提供了有限样本保证。

Theorem C.2.

在定理4.3和节3.3的设置下，假设假设4.1成立。 假设 $G={\arg \max }_i{F}_i$ 被参数化为 $F(x)\triangleq W_p\varphi (\mathrm{\cdots }\varphi (W_{1}x)\mathrm{\cdots })$ 形式的神经网络。 对于任何$t_1,t_2>0$，以概率$1-\delta$抽签样本$\widehat{P}$，它认为

$\text{Err}(G)\le$ ${\displaystyle \frac{c+1}{c-1}}{𝔼}_{\widehat{P}}[\mathrm{𝟏}(m(F,x,G_{\text{pl}}(x))\le t_2)]+{\displaystyle \frac{2c}{c-1}}{𝔼}_{\widehat{P}}[\mathrm{𝟏}(m_{ℬ}(F,x)\le t_1)]$

$+\tilde{O}\left(\left({\displaystyle \sum _i}\sqrt{q}{\Vert W_i\Vert }_F\right)\left({\displaystyle \frac{1}{t_1\sqrt{n}}}+{\displaystyle \frac{1}{t_2\sqrt{n}}}\right)\right)-\text{Err}(G_{\text{pl}})+\zeta$

其中 $\zeta \triangleq O\left(\frac{1}{c-1}\sqrt{\frac{\log (K/\delta )+p\log n}{n}}\right)$ 是低阶项。

C.2 第3.3节的证明

在本节中，我们提供定理3.7的证明草图。 该证明非常密切地遵循（Wei & Ma，2019b）的分析，但由于存在一些细微的差异，为了完整性，我们将其包含在此处。 我们首先声明目标中其他量的附加界限，其证明方式与定理 3.7 相同。

Theorem C.3.

训练样本 $\widehat{P}$ 的抽取概率为 $1-\delta$，所有 $F(x)\triangleq W_p\varphi (\mathrm{\cdots }\varphi (W_{1}x))$ 形式的神经网络 $G={\arg \max }_i{F}_i$ 将满足

$L_{\text{0-1}}(G,G_{\text{pl}})$ $\le {𝔼}_{\widehat{P}}[\mathrm{𝟏}(m(F,x,G_{\text{pl}}(x))\le t)]+\tilde{O}\left({\displaystyle \frac{{\sum }_i\sqrt{q}{\Vert W_i\Vert }_F}{t\sqrt{n}}}\right)+\zeta$

对于所有 $t>0$ 的选择，其中 $\zeta \triangleq O\left(\sqrt{\frac{\log (1/\delta )+p\log n}{n}}\right)$ 是低阶项，而 $\tilde{O}(\cdot )$ 隐藏了 $n$ 和 $d$ 中的多对数因子。

Theorem C.4.

训练样本 $\widehat{P}$ 的抽取概率为 $1-\delta$，所有 $F(x)\triangleq W_p\varphi (\mathrm{\cdots }\varphi (W_{1}x))$ 形式的神经网络 $G={\arg \max }_i{F}_i$ 将满足

${𝔼}_P[\mathrm{𝟏}(G(x)=y)]$ $\ge {𝔼}_{\widehat{P}}[\mathrm{𝟏}(m(F,x,y)\ge t)]-\tilde{O}\left({\displaystyle \frac{{\sum }_i\sqrt{q}{\Vert W_i\Vert }_F}{t\sqrt{n}}}\right)-\zeta$

对于所有 $y\in [K]$、$t>0$ 的选择，其中 $\zeta \triangleq O\left(\sqrt{\frac{\log (K/\delta )+p\log n}{n}}\right)$ 为低阶项，$\tilde{O}(\cdot )$ 隐藏了 $n$ 和 $d$ 中的多对数因子。

现在我们概述定理3.7的证明，因为定理C.3和C.4的证明是相同的。 我们首先正式定义在带有标签 $y$ 的示例 $x$ 上评估的神经网络 $F$ 的全层边距 $m(F,x,y)$。 我们记得 $F$ 计算函数 $F(x)\triangleq W_p\varphi (\mathrm{\cdots }\varphi (W_{1}x)\mathrm{\cdots })$。 我们对$F$的图层进行索引，如下：定义$f_1(x)\triangleq W_{1}x$，为$2\le i\le p$定义$f_i(h)\triangleq W_i\varphi (h)$，这样$F(x)=f_p\circ \mathrm{\cdots }\circ f_1(x)$ 。 令$\delta =({\delta }_1,\mathrm{\dots },{\delta }_p)$表示$F$每一层的扰动，我们将扰动输出$F(x,\delta )$定义如下：

$h_1(x,\delta )$ $=f_1(x)+{\delta }_1{\Vert x\Vert }_2$

$h_i(x,\delta )$ $=f_i(h_{i-1}(x,\delta ))+{\delta }_i{\Vert h_{i-1}(x,\delta )\Vert }_2$

$F(x,\delta )$ $=h_p(x,\delta )$

现在所有层边距 $m(F,x,y)$ 定义为

正如泛化界限证明中的典型情况一样，我们定义一类固定的神经网络函数来分析，表示为

$ℱ\triangleq \{x\mapsto W_p\varphi (\mathrm{\cdots }\varphi (W_{1}x)\mathrm{\cdots }):W_i\in {𝒲}_i\forall i\}$

其中 ${𝒲}_i$ 是第 $i$ 权重矩阵的某种可能实例化。 我们还重载符号，让 ${𝒲}_i\triangleq \{h\mapsto W_{i}h:W_i\in {𝒲}_i\}$ 表示与矩阵乘以 ${𝒲}_i$ 中的权重相对应的函数类。 让 $\parallel \cdot {\parallel }_{\text{op}}$ 表示矩阵运算符范数。 对于函数类$𝒢$，我们让${𝒩}_{\parallel \cdot \parallel }(ϵ,𝒢)$表示规范$\parallel \cdot \parallel$中$𝒢$的$ϵ$覆盖数。 以下条件对于分析很有用：

Condition C.5 （条件 A.1 来自 （Wei & Ma，2019b）)。

我们说函数类 $𝒢$ 满足关于范数 $\parallel \cdot \parallel$ 的 ${ϵ}^{-2}$ 覆盖条件，复杂度为 ${𝒞}_{\parallel \cdot \parallel }(𝒢)$ 如果对于所有 $ϵ>0$，

$\log {𝒩}_{\parallel \cdot \parallel }(ϵ,𝒢)\le \lfloor {\displaystyle \frac{{𝒞}_{\parallel \cdot \parallel }^2(𝒢)}{{ϵ}^2}}\rfloor$

为了概述证明技术，我们仅提供定理 3.7 中 (3.6) 的证明，因为其他界限遵循相同的论点。 以下引理根据鲁棒的全层边距 $m_{ℬ}$ 来限制 $R_{ℬ}(G)$。

Lemma C.6 (定理A.1的改编（Wei & Ma, 2019b）)。

假设权重矩阵映射${𝒲}_i$满足条件C.5，运算符范数$\parallel \cdot {\parallel }_{\text{op}}$和复杂度函数${𝒞}_{\parallel \cdot {\parallel }_{\text{op}}}({𝒲}_i)$。 训练数据绘制的概率为 $1-\delta$，对于所有 $t>0$，所有分类器 $F\in ℱ$ 将满足

$R_{ℬ}(G)\le {𝔼}_{\widehat{P}}[\mathrm{𝟏}(m_{ℬ}(F,x)\le t)]+O\left({\displaystyle \frac{{\sum }_i{𝒞}_{\parallel \cdot {\parallel }_{\text{op}}}({𝒲}_i)}{t\sqrt{n}}}\log n\right)+\zeta$ (C.1)

其中 $\zeta \triangleq O\left(\sqrt{\frac{\log (1/\delta )+\log n}{n}}\right)$ 是低阶项。

引理C.6的证明反映了定理A.1的证明（Wei & Ma, 2019b）。 主要区别在于，因为我们寻求边际阈值的界限，而（Wei & Ma，2019b）证明了取决于平均边际的界限，所以我们必须分析稍微修改的泛化损失。 为了证明引理C.6，我们首先定义扰动$\delta$的$\Vert |\delta |\Vert \triangleq {\Vert ({\Vert {\delta }_1\Vert }_2,\mathrm{\dots },{\Vert {\delta }_p\Vert }_2)\Vert }_2$和$\Vert |F|\Vert \triangleq {\Vert ({\Vert W_1\Vert }_{\text{op}},\mathrm{\dots },{\Vert W_p\Vert }_{\text{op}})\Vert }_2$。 我们证明 $m_{ℬ}(F,x)$ 是 $F$ 中的 Lipschitz，相对于 $|||\cdot |||$ 固定 $x$。

Claim C.7。

选择$F,\widehat{F}\in ℱ$。 那么对于任何$x\in 𝒳$，

$|m_{ℬ}(F,x)-m_{ℬ}(\widehat{F},x)|\le \Vert |F-\widehat{F}|\Vert$

如果我们用 $m$ 替换 $m_{ℬ}$，同样的结论成立。

证明。

我们考虑两种情况：

情况 1：${\arg \max }_{i}F{(x)}_i={\arg \max }_i\widehat{F}{(x)}_i$。 让 $y$ 表示公共值。 在这种情况下，期望的结果立即从的权利要求E.1得出(Wei & Ma, 2019b)。

情况 2：${\arg \max }_{i}F{(x)}_i\ne {\arg \max }_i\widehat{F}{(x)}_i$。 在这种情况下，(Wei & Ma, 2019b)中权利要求A.1的解释意味着$0\le m_{ℬ}(F,x)\le \Vert |F-\widehat{F}|\Vert$。 （本质上，我们选择 $\delta$ 和 $\Vert |\delta |\Vert \le \Vert |F-\widehat{F}|\Vert$，这样 $F(x,\delta )=\widehat{F}(x)$。） 同样，$0\le m_{ℬ}(\widehat{F},x)\le \Vert |F-\widehat{F}|\Vert$。 因此，它必须遵循 $|m_{ℬ}(F,x)-m_{ℬ}(\widehat{F},x)|\le \Vert |F-\widehat{F}|\Vert$。 ∎

对于 $t>0$，定义斜坡损失 $h_t$ 如下：

$h_t(a)=1-\mathrm{𝟏}(a\ge 0)\min \{a/t,1\}$

我们现在定义假设类${ℒ}_t\triangleq \{h_t\circ m_{ℬ}(F,\cdot ):F\in ℱ\}$。 现在我们限制该假设类的 Rademacher 复杂度：

Claim C.8。

在引理C.6的设置中，假设${𝒲}_i$满足条件C.5，运算符范数$\parallel \cdot {\parallel }_{\text{op}}$和复杂度${𝒞}_{\parallel \cdot {\parallel }_{\text{op}}}({𝒲}_i)$。 然后

${\text{Rad}}_n({ℒ}_t)\le O\left({\displaystyle \frac{{\sum }_i{𝒞}_{\parallel \cdot {\parallel }_{\text{op}}}({𝒲}_i)}{t\sqrt{n}}}\log n\right)$

由于权利要求C.8的证明是标准的，我们提供了其证明的草图。

权利要求C.8的证明草图。

首先，通过(Wei & Ma, 2019b)的引理A.3，我们得到$ℱ$满足条件C.5且范数$|||\cdot |||$ 和复杂性${𝒞}_{|||\cdot |||}(ℱ)\triangleq {\sum }_i{𝒞}_{\parallel \cdot {\parallel }_{\text{op}}}({ℱ}_i)$。 现在让 $\widehat{ℱ}$ 成为 $|||\cdot |||$ 中 $ℱ$ 的 $tϵ$ 覆盖。 我们定义函数 $f:𝒳\to ℝ$ 的 $L_2(P_n)$-范数如下：

${\Vert f\Vert }_{L_2(P_n)}\triangleq \sqrt{{𝔼}_{\widehat{P}}[f{(x)}^2]}$

然后标准表明

${\widehat{ℒ}}_t\triangleq \{h_t\circ m_{ℬ}(\widehat{F},\cdot ):\widehat{F}\in \widehat{ℱ}\}$

是 ${ℒ}_t$ 在 $L_2(P_n)$ 准则中的 $ϵ$ 覆盖，因为对于任意固定的 $x$，$h_t$ 是 $1/t$ 利普希兹，而 $m_{ℬ}(F,x)$ 在 $F$ 准则 $|||\cdot |||$ 中是 $1$ 利普希兹。 由此可见$\log {𝒩}_{L_2(P_n)}(ϵ,{ℒ}_t)\le \lfloor \frac{{𝒞}_{|||\cdot |||}^2(ℱ)}{t^2{ϵ}^2}\rfloor$。 现在我们应用达德利定理：

${\text{Rad}}_n({ℒ}_t)$ $\le \underset{\beta >0}{inf}\left(\beta +{\displaystyle \frac{1}{\sqrt{n}}}{\displaystyle {\int }_{\beta }^{\mathrm{\infty }}}\sqrt{\log {𝒩}_{L_2(P_n)}(ϵ,{ℒ}_t)}𝑑ϵ\right)$

$\le \underset{\beta >0}{inf}\left(\beta +{\displaystyle \frac{1}{\sqrt{n}}}{\displaystyle {\int }_{\beta }^{\mathrm{\infty }}}\sqrt{\lfloor {\displaystyle \frac{{𝒞}_{|||\cdot |||}^2(ℱ)}{t^2{ϵ}^2}}\rfloor }𝑑ϵ\right)$

可以使用标准计算来限制右侧的数量，从而给出所需的结果。 ∎

引理C.6的证明。

首先，根据 Rademacher 复杂度和泛化之间的标准关系，声明 C.8 让我们得出结论：以概率 $1-\delta$，对于任何 固定 $t>0$，所有$F\in ℱ$满足：

${𝔼}_P[h_t(m_{ℬ}(F,x))]\le {𝔼}_{\widehat{P}}[h_t(m_{ℬ}(F,x))]+O\left({\displaystyle \frac{{\sum }_i{𝒞}_{\parallel \cdot {\parallel }_{\text{op}}}({𝒲}_i)}{t\sqrt{n}}}\log n+\sqrt{{\displaystyle \frac{\log 1/\delta }{n}}}\right)$

我们还注意到 $h_t(m_{ℬ}(F,x))=1$ 当 $x\notin {𝒮}_{ℬ}(G)$ 时，因为在这种情况下 $m_{ℬ}(F,x)=0$。 由此可见$1(x\notin {𝒮}_{ℬ}(G))\le h_t(m_{ℬ}(F,x))$。 因此，我们得到

$R_{ℬ}(G)\le {𝔼}_{\widehat{P}}[\mathrm{𝟏}(m_{ℬ}(F,x)\le t)]+O\left({\displaystyle \frac{{\sum }_i{𝒞}_{\parallel \cdot {\parallel }_{\text{op}}}({𝒲}_i)}{t\sqrt{n}}}\log n+\sqrt{{\displaystyle \frac{\log 1/\delta }{n}}}\right)$ (C.2)

仍有待证明 (C.1) 对于所有 $t$ 成立。现在，以 $t_j\triangleq t_{\min }{2}^j$ 形式对 $t$ 的选择执行联合绑定已成为标准，其中 $t_{\min }\triangleq \frac{{\sum }_i{𝒞}_{\parallel \cdot {\parallel }_{\text{op}}}({𝒲}_i)}{\sqrt{n}}\log n$ 和 $0\le j\le O(\log n)$，因此我们只在这里勾画一下论证。 我们将 $t=t_j$ 与失败概率 ${\delta }_j=\delta /2^{j+1}$ 联合绑定到 (C.2)，因此 (C.2) 将成立对于所有$t_1,\mathrm{\dots },t_{j_{\max }}$，概率为$1-\delta$。 对于 $t$ 的任何选择，都会有 $j$ 使得 $t/2\le t_j\le t$ 或 (C.1) 必定成立。 （有关更详细的论证，请参阅（Wei & Ma，2019b）的定理 C.1。） 因此，将存在一些 $j$，使得 (C.2) 的右侧被 (C.1)，根据需要。 ∎

定理3.7的证明草图。

根据(Wei & Ma, 2019b)的引理B.2，我们有${𝒞}_{\parallel \cdot {\parallel }_{\text{op}}}(\{W:{\Vert W\Vert }_F\le a\})=O(\sqrt{q\log q}a)$。 因此，要获得 (3.6)，只需使用标准联合绑定技术将引理 C.6 应用于 $a$ 的所有选择即可；例如，参见中定理3.1的证明（Wei & Ma, 2019b）。 为了获得其他泛化界限，我们可以遵循引理C.6的类似论证来证明其对于全层边距的其他变体的类似性，然后在权重矩阵范数上重复相同的并集界限像之前一样。 ∎

C.3 全层边距的数据相关下限

现在，当激活 $\varphi$ 具有 $\overline{\nu }$-Lipschitz 导数时，我们将提供定理 3.7 中使用的所有层边距的下界。 在本节中，可以方便地修改索引以将激活计为自己的层，因此总共有 $2p-1$ 层。 令 $s_{(i)}(x)$ 表示第 $i$ 矩阵乘法之前层的 $\parallel \cdot {\parallel }_2$ 范数，其中下标中的括号区分权重索引和层索引（其中还包括激活层）。 将 ${\nu }_{j\leftarrow i}(x)$ 定义为第 $j$ 层相对于在 $x$ 处评估的第 $i-1$ 层的雅可比行列式。 定义$\gamma (F(x),y)\triangleq F{(x)}_y-{\max }_{i\ne y}F{(x)}_i$。 我们使用以下量来测量 $W_{(i)}$ 之后层的稳定性：

${\kappa }_{(i)}(x,y)$ $\triangleq {\displaystyle \frac{s_{(i-1)}(x){\nu }_{2p-1\leftarrow 2i}(x)}{\gamma (F(x),y)}}+{\psi }_{(i)}(x,y)$

对于次要项 ${\psi }_{(i)}(x,y)$ 给出的

${\psi }_{(i)}(x,y)$ $\triangleq {\displaystyle \sum _{j=i}^{p-1}}{\displaystyle \frac{s_{(i-1)}(x){\nu }_{2j\leftarrow 2i}(x)}{s_{(j)}(x)}}+{\displaystyle \sum _{1\le j\le 2i-1\le j^{\prime }\le 2p-1}}{\displaystyle \frac{{\nu }_{j^{\prime }\leftarrow 2i}(x){\nu }_{2i-2\leftarrow j}(x)}{{\nu }_{j^{\prime }\leftarrow j}(x)}}$

$+{\displaystyle \sum _{1\le j\le j^{\prime }\le 2p-1}}{\displaystyle \sum _{j^{\prime \prime }=\max \{2i,j\},j^{\prime \prime }\text{even}}^{j^{\prime }}}{\displaystyle \frac{\overline{\nu }{\nu }_{j^{\prime }\leftarrow j^{\prime \prime }+1}(x){\nu }_{j^{\prime \prime }-1\leftarrow 2i}(x){\nu }_{j^{\prime \prime }-1\leftarrow j}(x)s_{(i-1)}(x)}{{\nu }_{j^{\prime }\leftarrow j}(x)}}$

现在，我们对 $m(F,x,y)$ 和 $m_{ℬ}(F,x)$ 有以下下限：

Proposition C.9 （来自的引理C.1（Wei & Ma，2019b）)。

在上面的设置中，如果$\gamma (F(x),y)>0$，我们有

$m(F,x,y)\ge {\displaystyle \frac{1}{{\Vert {\{{\kappa }_{(i)}(x,y)\}}_{i=1}^p\Vert }_2}}$

此外，如果 $\gamma (F(x^{\prime }),{\arg \max }_{i}F{(x)}_i)>0$ 对于所有 $x^{\prime }\in ℬ(x)$，则

$m_{ℬ}(F,x)\ge \underset{x^{\prime }\in ℬ(x)}{\min }{\displaystyle \frac{1}{{\Vert {\{{\kappa }_{(i)}(x^{\prime },{\arg \max }_{i}F{(x)}_i)\}}_{i=1}^p\Vert }_2}}$

附录D实验

D.1 使用 GAN 对扩展属性的经验支持

在本节中，我们提供有关图 1（左）中所示的 GAN 验证的更多详细信息。 我们使用从预训练的 BigGAN （Brock 等人，2018） 中采样的 128 x 128 图像。 我们将图像分类为 Engstrom 等人 (2019) 鲁棒性库中选择的 10 个超类：狗、鸟、昆虫、猴子、汽车、猫、卡车、水果、真菌、船。 这些超类由属于超类类别的所有 ImageNet 类组成。 为了从超类中采样图像，我们从超类中统一采样 ImageNet 类，然后从以该类为条件的 GAN 中采样。 我们对每个超类采样 1000 张图像，并训练 ResNet-56 (He 等人, 2016) 来预测超类，实现了 93.74% 的验证准确率。

接下来，我们将 GAN 图像近似投影到经过训练的分类器的错误标记集上。 我们近似投影如下：我们优化一个目标，该目标由距原始图像的 ${\mathrm{\ell }}_2$ 距离和预训练分类器与超类标签的负交叉熵损失组成。 令$M$表示GAN映射，$x$表示原始图像，$y$表示标签，$F$表示预训练分类器，目标如下：

$\underset{z}{\min }{\Vert x-M(z)\Vert }_2^2-{\lambda }_{\text{ce}}{\mathrm{\ell }}_{\text{cross-ent}}(F(M(z)),y)$

我们使用 ${\lambda }_{\text{ce}}=10$ 和学习率 $0.0003$ 优化 2000 个梯度下降步骤的 $z$，使用与生成 $x$ 生成的 $M(z)$ 是集合 $ℳ(F)$ 中 $x$ 的邻居，这是错误标记的 $F$ 集合。

对从每个类中采样的 200 个 GAN 图像执行此过程后，我们发现这些图像中有 20% $x$ 的邻居 $x^{\prime }\in ℳ(F)$ 具有 ${\Vert x-x^{\prime }\Vert }_2\le 19.765$。 请注意，这相当于将 [0, 1] 中的像素值平均修改每个像素 0.024。 我们使用 $\widehat{ℳ}$ 来表示通过这种方式找到的一组错误标记的邻居。 通过目视检查，我们发现邻居在视觉上与原始图像非常相似，这表明将这些图像视为“邻居”是合适的。 在图 1 中，我们可视化了此过程找到的邻居的典型示例。 因此，设置$ℬ(x)=\{x^{\prime }:{\Vert x^{\prime }-x\Vert }_2\le \frac{19.765}{2}\}$，概率为0.0626的集合$ℳ(F)$具有由概率为0.2的$ℬ$引起的相对较大的邻域。 这支持了我们的扩展假设，尤其是 A 节中的加性概念。

接下来，我们使用相同的分类器作为伪标记器，对每个超类包含 10000 个额外未标记图像的数据集执行自训练，其中这些图像是独立于上一步中的 200 个 GAN 图像进行采样的。 我们使用 VAT （Miyato 等人，2018）将输入一致性正则化添加到自训练过程中。 经过自训练，新分类器$\tilde{G}$的验证准确率提高到95.69%。

此外，我们还评估了自训练分类器 $\tilde{G}$ 在 $\widehat{ℳ}$ 子集上的性能，其中与邻居的距离大于 1。 我们让 ${\widehat{ℳ}}^{\prime }$ 表示这个子集。 我们选择以这种方式过滤$\widehat{ℳ}$，以排除原始邻居已经被错误分类的情况。 我们发现 $\tilde{G}$ 在 ${\widehat{ℳ}}^{\prime }$ 的示例中达到了 67.27% 的准确率。

此外，图 3 表明 $\tilde{G}$ 在来自 ${\widehat{ℳ}}^{\prime }$ 的示例中更加准确，这些示例更接近用于初始化投影的原始邻居。 这提供了证据，表明输入一致性正则化自训练确实通过依赖正确伪标记的邻居进行去噪来纠正伪标记器的错误，因为图3显示与邻居更接近的示例是更有可能被去噪。 最后，我们还指出，图 3 提供了证据，表明去噪机制确实从自训练数据集推广到总体，因为 ${\widehat{ℳ}}^{\prime }$ 中的示例及其原始邻居都没有出现在自训练数据集中。

图3： 自训练会纠正与正确标记的邻居接近的错误标记的示例。 我们根据 ${\mathrm{\ell }}_2$ 与用于初始化投影的邻居的距离将 ${\widehat{ℳ}}^{\prime }$ 中的示例（在 D.1 节中定义）划分为 5 个容器，并且绘制每个箱中标签通过自我训练纠正的示例的百分比。 选择的垃圾箱大小相同。 该图表明，由于错误标记的示例更接近输入空间中正确标记的示例，因此更有可能通过自我训练进行纠正。 这支持了我们的理论直觉，即输入一致性正则化自训练通过用其正确伪标记的邻居引导错误伪标记的示例来对伪标签进行去噪。

D.2 伪标记实验

在本节中，我们验证 (4.1) 中的理论目标是否按预期工作。 我们考虑一个无监督的域适应设置，我们使用源分类器中的伪标签进行自我训练。 我们评估了以下优化理想目标 (4.1) 的渐进步骤，目的是展示添加我们理论的每个组件所带来的改进：

来源：我们在标记的源数据集上训练模型，并直接在目标验证集上对其进行评估。

PL：使用上面获得的分类器，我们在目标训练集上生成伪标签，并训练一个新的分类器来适应这些伪标签。

PL+VAT：我们考虑理论中的扰动集$ℬ(x)$由$x$周围的${\mathrm{\ell }}_2$球给出的情况。 我们训练一个分类器来拟合伪标签，同时使用 (Miyato 等人，2018) 的增值税损失对目标域上的对抗鲁棒性进行正则化，获得分类器 $F$ 的以下损失：

$ℒ(F)\triangleq L_{\text{cross-ent}}(F,G_{\text{pl}})+{\lambda }_v{L}_{\text{VAT}}(F)$

请注意，此损失仅在 $F(x)$ 正确预测 $G_{\text{pl}}(x)$ 的示例中强制执行真正的稳定性。 对于不符合 $F$ 的伪标签，交叉熵损失会降低模型的置信度，因此离散标签仍然可能在此类示例的输入转换下轻松翻转。

PL+VAT+AMO：由于定理4.3中的理论保证是针对群体损失的，因此我们应用的AMO算法（Wei & Ma, 2019b） 在增值税损失项中，以规范稳健的全层利润（参见第 3.3 节）。 这鼓励了训练集的鲁棒性，以更好地泛化。

PL+VAT+AMO+MinEnt：请注意，PL+VAT 仅鼓励适合伪标签的示例的鲁棒性，但理想的分类器不应适合与真实情况不一致的伪标签。 由于定理 4.3 中的界限随着 $F$ 的鲁棒性而提高，我们的目标是鼓励 $F$ 与 $G_{\text{pl}}$。 为此，我们修改损失以允许分类器忽略伪标签的 $c$ 部分并优化这些示例的最小熵损失。 我们在下面提供了有关如何选择要忽略的伪标签的更多详细信息。

MinEnt+VAT+AMO：我们通过从目标中删除伪标签来研究它们的影响。 相反，我们依赖于以下损失，它只是在拟合源数据集时对目标执行熵最小化：

$ℒ(F)\triangleq {\lambda }_s{L}_{\text{cross-ent, src}}(F)+{\lambda }_t{L}_{\text{min-ent, tgt}}(F)+{\lambda }_v{L}_{\text{VAT, tgt}}(F)$

我们考虑了训练稳定性的源损失。 和之前一样，我们在增值税损失项中应用 AMO 算法，以鼓励分类器泛化的鲁棒性。

表 1 显示了这些方法在六个无监督域适应基准上的性能。 我们看到，当我们向目标添加额外的组件以匹配理论时，性能会提高。 我们注意到，这些实验的目标是验证我们的理论，而不是推动这些数据集的最新技术，这通常依赖于领域混淆（Tzeng 等人，2014；Ganin 等人，2016； Tzeng 等人, 2017)，这超出了我们的理论范围。 例如，Shu 等人 (2018) 通过使用域混淆技术，同时在目标上优化增值税损失和熵最小化，同时在标记源数据上进行训练，在这些基准上取得了出色的结果。 我们的 MinEnt+VAT+AMO 结果表明，当域混淆被消除时，性能会受到影响，并且实际上比仅在除 STL-10 到 CIFAR-10 之外的所有数据集上的源训练更差。 我们在下面提供了更多的实验细节。 我们对每个数据集使用与（Shu等人，2018）相同的数据集设置和模型架构。 所有分类器均使用 SGD 进行优化，余弦学习率和权重衰减为 5e-4，目标批量大小为 128。 学习率的值根据每个数据集和方法的验证集在值范围 $\{0.03,0.01,0.003,0.001\}$ 内进行调整。 我们通过在$\{3,10,30\}$范围内以相同方式进行调整来选择${\lambda }_v$，即增值税损失系数。 对于 MinEnt+VAT+AMO，我们修复 PL+VAT+AMO+MinEnt 的最佳超参数并调整 ${\lambda }_s\in \{0.25,0.5,1\}$ 并修复 ${\lambda }_t=1$。 我们还调整了 $\{64,128\}$ 中源损失的批量大小。 表 1 描述了目标验证集的准确性。 我们使用提前停止并显示训练期间达到的最佳准确性。 所有显示的准确度均基于算法的一次运行，但 (+MinEnt) 方法除外，我们使用相同的超参数对 3 次独立运行进行平均。

为了计算增值税损失（Miyato等人，2018），我们在图像空间中采取一步梯度下降，以最大化扰动图像与原始图像之间的KL散度。 然后我们将此梯度归一化为 ${\mathrm{\ell }}_2$ 范数 1 并将其添加到图像中以获得扰动版本。 为了结合（Wei & Ma，2019a）的AMO算法，我们还优化了DIRT-T架构中池化层之前的三个隐藏层的对抗性扰动。 扰动的初始值设置为 0，我们使用学习率为 1 的一步梯度上升，将它们与对输入的扰动联合优化。

最后，我们提供了有关如何选择要忽略 PL+VAT+AMO+MinEnt 目标的伪标签的详细信息。 在此步骤中需要小心，以防止优化目标陷入不良的局部最小值。 我们将维护一个模型，其权重是过去模型权重的指数移动平均值$F_{\text{ema}}$。 每次梯度更新，$F_{\text{ema}}$的权重都会更新$W_{\text{ema}}\leftarrow 0.999W_{\text{ema}}+0.001W_{\text{curr}}$，其中$W_{\text{curr}}$是梯度更新后的当前模型权重。 我们的目标是丢弃 ${\tau }_i$ - 最大化 ${\mathrm{\ell }}_{\text{cross-ent}}(F_{\text{ema}}(x),G_{\text{pl}}(x))$ 的伪标签部分，其中 $G_{\text{pl}}(x)$ 是伪标签，例如 $x$，而 $i$ 索引当前迭代。 在训练过程中，我们会将 ${\tau }_i$ 从 0 线性增加到最终值 $\tau$。 为了实现这一目标，我们维护损失的 $(1-{\tau }_i)$ 分位数的指数移动平均值，并使用损失 ${\mathrm{\ell }}_{\text{cross-ent}}(F_{\text{ema}}(x),G_{\text{pl}}(x))$ 的 $(1-{\tau }_i)$ 分位数在每次迭代中进行更新> 根据当前批次计算。 我们忽略损失值高于第 $(1-{\tau }_i)$ 个损失分位数的指数移动平均值的伪标签。

表1： 各种自训练方法的目标数据验证准确性。 我们发现，随着我们添加理论目标 (4.1) 的组成部分，性能会有所提高。

Source	MNIST	MNIST	SVHN	SynDigits	SynSigns	STL-10
Target	SVHN	MNIST-M	MNIST	SVHN	GTSRB	CIFAR-10
Source Only	35.8%	57.3%	85.4%	86.3%	77.8%	58.7%
MinEnt + VAT + AMO	20.6%	28.9%	83.2%	83.6%	42.8%	67.6%
PL Only	38.3%	60.7%	92.3%	90.6%	85.7%	62.0%
+ VAT	41.7%	79.8%	97.6%	93.4%	90.5%	62.3%
+ AMO	42.5%	81.4%	97.9%	93.8%	93.0%	63.9%
+ MinEnt	46.8%	93.8%	98.9%	94.8%	95.4%	67.0%