Learning from binary labels with instance-dependent noise

type

status

date

slug

summary

🤔 摘要

在过去几十年中，监督学习已经取得了许多理论和实践上的进展。然而，它的基本假设-训练和测试分布是相同的-在实践中经常无法成立。一个重要的例子是当训练实例受到标签噪声的影响时，观察到的标签不能准确地反映潜在的真实情况。尽管简单噪声模型的影响已经得到了广泛的研究，但相对较少的注意力已经被付给了实际相关标签噪声的设置。因此，目前还不清楚是否可以在没有准确标签的情况下学习，无论是从理论上还是从实践中，从受到这种噪声影响的数据中学习好的模型。我们提供了对这个问题的理论分析，有三个贡献。首先，我们证明对于实例相关（但标签无关）的噪声，任何在噪声分布上对分类一致的算法也一致于无噪声分布。其次，我们证明对于ROC曲线下的区域，一致性也成立，假设噪声（在精确意义上）与实例的固有难度相关。第三，我们展示了当无噪声分布是广义线性模型时，Isotron算法可以高效且可证明地从噪声样本中学习。我们实证地证实了我们的理论发现，我们希望这可以刺激对这一重要学习设置的进一步分析。

📝1 与实例相关标签噪声学习

最近对于分类模型的进展，例如深度神经网络，在很大程度上由于大规模标记训练数据集的可用性已经取得了重大的成功（Krizhevsky 等人2012; He 等人2016; Xiao等人2015）。然而，真实世界的标签经常受到不同实例相关标签噪声的损坏，其中观察到的标签并不代表潜在的真相，并且噪声水平在不同实例之间变化。例如，在物体识别问题中，质量较差的图像更有可能被错标（Reed等人2014; Xiao等人2015）；此外，某些图像类别容易与其他类别混淆。因此，一个自然的问题产生：这样的标签噪声对我们训练模型的准确性有哪些影响？更准确地说，以下几个问题是基本的兴趣：

Q1在噪声分布上良好的分类性能是否能在无噪声（“干净”）分布上得到良好的分类性能？

Q2对于更复杂的度量，例如排名，问题答案是否也成立？

Q3是否存在可以被证明具有噪声鲁棒性的简单算法？

在实例无关的标签噪声的情况下，这些问题Q1-Q3已经被几个最近的理论研究（Stempfel等人2007; Stempfel和Ralaivola2009; Natarajan等人2013; Scott等人2013; Liu和Tao2015; Menon等人2015; van Rooyen等人2015; Patrini等人2016, 2017）研究，其分析结果为令人惊讶的结论：对于强大的（高容量）模型，只要有足够多的噪声样本，就可以实现最优的分类和排序误差，而不需要任何清洁标签。此外，对于适度（低容量）的模型，即使有微小量的噪声也可能是有害的（Long 和 Servedio 2008），但存在简单的可证明的鲁棒算法（Natarajan等人2013；van Rooyen等人2015）。然而，在实例相关标签噪声的情况下，尽管有一些理论先例（Manwani 和 Sastry 2013；Ghosh等人2015；Awasthi等人2015），问题Q1-Q3在我们所知的范围内仍然没有得到回答。在本文中，我们系统地研究了这些问题。通过展示在（被适当限制的）实例相关噪声下，强大的模型可以在有足够的噪声样本的情况下进行最佳分类和排序，我们回答了Q1和Q2这个问题；这是对现有结果的非平凡推广。我们通过展示现有广义线性模型的算法扩展如何可以从有噪声的样本中有效且可证明地学习，回答了问题Q3；这与目前为止的仅仅适用于实例无关噪声的算法不同，后者要么需要知道噪声率，要么缺乏保证。更准确地说，我们的贡献是：

C1我们展示了对于一系列损失，任何在噪声分布上最小化期望损失（即风险）的算法也将最小化干净分布上的期望损失（定理1），即噪声风险最小化是一致的分类；

C2我们展示了在噪声分布上最大化ROC曲线下的区域（AUROC）也在干净分布上也是一致的（定理2），在一种新的边界一致噪声模型下，“更困难”的实例受到噪声（定义4）；

C3我们展示了，如果干净分布是广义线性模型，那么Isotron算法（Kalai 和 Sastry 2009）在边界一致的噪声下是可证明的鲁棒。虽然我们的贡献主要是理论性的，但我们也提供了实验证明（第7节），展示了我们结果的潜在实际影响。

🤗2 背景和符号

2.1 学习二分类标签

在二分类标签的标准学习问题中，观察到一组实例与二进制标签配对，假设这是从未观察到的分布中独立同分布地选择的。目标是找到一个模型，可以确定未来的实例更可能是积极的还是消极的。为了更加形式地陈述这一点，我们需要一些符号。

2.1.1 分布、评分器和风险

固定一个可测的实例空间X。我们用D表示X×{±1}上的某个分布，其中是随机变量。任意的D都可以通过边际分布和类别概率函数来表示。评分器是任意可测函数；例如，线性评分器的形式为。损失函数是任意可测函数，用于度量标签和评分之间的不一致性。风险是任意可测函数，它总结了评分器在从中抽取的样本上的表现。通常来说，人们使用ℓ-风险或ℓ-排名风险。

基于此，从二进制标签中学习的标准问题可以表述为：

给定样本、评分器类别和风险R的选择，学习一个在D上风险较低的评分器s ∈ S。

例子我们感兴趣的是从二进制标签中学习的两个经典问题。在二分类问题中（Devroye 1996），目标是近似地最小化误分类错误，其中是零一损失，其中指示函数。

在双分配排序问题中（Agarwal and Niyogi 2005），目标是近似地最小化成对不一致的排名风险，也称为评分器的ROC曲线下面积减一（AUROC）（Clémençon et al. 2008）。后者相对于类别不平衡下的误分类错误更为优选（Ling and Li 1998）。

2.1.2 贝叶斯最优评分器和遗憾（regret）

在研究学习算法的渐近行为时，还有两个与风险相关的概念是有用的。贝叶斯最优评分器是任何理论上风险最小化的评分器。评分器的遗憾是其相对于任意贝叶斯最优评分器的超过风险，即。

例如，对于误分类错误的贝叶斯最优评分器集合包括满足的所有，其中实例的评分符号与其标签的平均值是否为正相匹配。此外，对于0-1损失函数的遗憾为（Devroye et al. 1996, Theorem 2.2），即在与任意最优评分器不一致的区域附近的附近的浓度。

2.2 从有错误的二进制标签中学习

固定一些分布。在从有错误或噪声的二进制标签中学习的问题中，我们有一个训练样本，对于某个，其保持不变，但。也就是说，我们观察到具有相同实例边际分布但不同标签条件分布的样本。我们的目标仍然是学习一个相对于风险较小的评分器，尽管是不可观测的。更准确地说，从有错误的二进制标签中学习的问题可以表述为：

给定样本、评分器类别和风险的选择，学习一个相对于风险较低的评分器。

我们将D称为“干净”分布，称为“有错误”的分布。请注意，我们允许D是非可分的，即对某个成立；因此，即使在D下，也不一定能确定每个实例的标签。我们对“噪声”和“错误”一词的使用是指在标注过程中存在额外的外部不确定性。

2.2.1 依赖于实例的噪声模型

我们将重点研究由于在D中随机翻转标签引起的噪声。此外，我们对依赖于实例的噪声感兴趣，即噪声强制取决于实例，并且可以选择性地取决于标签。为了捕捉这一点，我们首先介绍了通用的标签依赖于实例的噪声（LIN）模型。

定义1（LIN模型）给定一个干净的分布和标签翻转函数：，在LIN模型下，我们观察到样本，其中首先我们通常地绘制，然后以概率翻转Y以生成。

标签翻转函数ρ±1可以用来模拟依赖于实例和真实标签的标签噪声。我们对这些函数没有施加任何参数假设；我们唯一施加的限制是在平均情况下，嘈杂和真实标签必须一致，即:

当是常量时，这是一个标准的假设（Blum and Mitchell 1998; Scott et al. 2013）。我们将满足方程2的称为可接受的。LIN模型可以专门用于噪声依赖于实例但不依赖于标签的情况。我们将其称为纯粹的实例依赖噪声（PIN）模型。

定义2（PIN模型）给定标签翻转函数，在PIN模型下，我们中观察样本，该模型等于。

LIN模型和PIN模型都考虑了依赖于实例的噪声；但是LIN模型更为一般。特别地，在非可分D中，每个与标签配对的概率都不为零；因此，在LIN模型下，发生在样本中的示例可能与另一个中发生的的标签翻转的概率不同。

请注意，定义2中ρ的映射为，以强制执行方程2中的条件。当D是可分的时，该条件等价于强制保证嘈杂类概率远离1/2，这被称为类概率的Massart条件（Massart and Nédélec 2006）。因此，当D是可分的时，满足方程2的依赖于实例的噪声也被称为Massart或有界噪声模型。

2.2.2 与现有模型的关系

作为一种特殊情况，LIN模型捕捉了不依赖于实例但依赖于标签的噪声。在这种情况下，同一类中的所有实例具有相同的标签翻转概率。这被称为类条件噪声（CCN）设置，并受到了广泛关注（Blumand Mitchell 1998; Natarajan et al. 2013）。

定义3 （CCN模型）给定标签翻转概率，在CCN模型下，我们观察到样本来。

2.3 噪声风险最小化的一致性？

我们在从LIN或PIN噪声中学习时，主要的理论关注点是噪声风险最小化的统计一致性问题。这旨在回答以下问题：如果我们在噪声分布上与某种风险表现接近最优，那么我们在干净分布上是否也会接近最优？更正式地说，我们希望知道，例如，对于任何分布D、损坏的分布和得分器序列，是否存在

确立这一点将意味着在给定足够多的噪声样本和足够强大的得分器类别的情况下，可以进行接近最优的表现。后一个假设与二元分类的标准一致性分析一致（Zhang 2004；Bartlett et al. 2006），然而其实际适用性有些限制。为了解决这个问题，我们进一步研究（第5节）一种针对实例相关噪声有效（且可证明）学习的算法。正如介绍中所提到的，最近的一些研究已经建立了噪声风险最小化的分类一致性（Scott et al. 2013；Natarajan et al. 2013；Menon et al. 2015），但是仅适用于类条件（因而是实例无关）噪声的特殊情况。许多研究已经在各种实例相关噪声模型下提供了PAC样式的保证（Bylander 1997, 1998；Servedio 1999；Awasthi et al. 2015, 2016, 2017）。然而，这些研究对D和得分器类别都有假设。有关更详细的比较和讨论，请参见第6节。

3 仅在纯实例相关噪声下的分类一致性

我们首先从第一个贡献（C1）开始，它显示出只有在给定仅有受到纯实例相关噪声的样本、充分丰富的函数类别和足够多的样本数时，我们才能进行最优分类；即，在噪声风险最小化中是一致的。

3.1 关联干净和损坏的贝叶斯最优得分器

回顾方程式3，确立噪声风险最小化的一致性需要表明，一个能够在损坏的上进行良好分类的得分器s，也会在干净的D上进行良好分类；即，如果合适的损失ℓ下的遗憾较小，则也较小。在继续之前，我们首先应确信这样的结果在第一时间是可能的。一个必要条件是干净和损坏的贝叶斯最优得分器相同；如果没有这个条件，噪声风险最小化将会收敛到错误的对象。对于许多损失函数来说，贝叶斯最优得分器取决于底层的类概率函数（参见方程式1）。因此，为了研究由通用标签和实例相关噪声引起的上的这些得分器，我们检查其类概率函数。

引理1 选择任意分布D。假设，其中是可接受的标签翻转函数。那么，的损坏类概率函数是

方程式4的形式是直观的：损坏的正例可以被看作是正例和负例的混合体，混合权重由翻转概率决定。这也说明噪声的作用是压缩η的范围，因此让人对实例的标签产生更多不确定性。

引理1表明，如果没有进一步的假设，我们无法希望确立一致性。例如，对于0-1损失，方程式1确定了任何D上的贝叶斯最优得分器的符号为sign(s∗(x)) = sign(η(x)− 1/2)。然而，如果ρ1和ρ−1变化任意，那么根据方程式4，可以轻松验证。因此，干净和损坏的最优得分器将不同，通常没有一致性。幸运的是，在进一步假设下，我们可以取得进展：噪声是纯实例相关的（根据定义2），并且根据(Ghosh et al. 2015)，

对于一些C ∈ R成立。方程式5对于0-1损失、ramp损失和“unhinged”损失（van Rooyen et al. 2015）都成立。在这些限制下，干净和损坏的最优得分器是一致的。

推论1 选择任意分布D和满足方程式5的损失ℓ。假设，其中是可接受的标签翻转函数。那么，

对于0-1损失的情况，推论1是直观的：对于满足方程式2中条件的纯实例相关噪声，损坏的标签平均上将与真实标签一致；因此，贝叶斯最优分类器将保持不变，该分类器只是查看一个实例是否更有可能是正面或负面.

强调关于推论1的一个重点是，它不需要D具有确定性的标签函数，即它不需要分离分布。推论1推广了Natarajan等人的结果（2013年，推论10），其针对独立于实例的噪声。Awasthi等人（2015年），Ghosh等人（2015年，定理1）也观察到了类似的情况，但前者仅针对0-1损失，并在D可分离的额外假设下成立，即。

参考文章

致谢：

💡

有关Notion安装或者使用上的问题，欢迎您在底部评论区留言，一起交流~