本文将对 NeurIPS 2019 最佳论文《Distribution-Independent PAC Learning of Halfspaces with Massart Noise》进行解读，该论文在半空间学习上取得了显著进展。作者研究了存在 Massart 噪声的半空间（halfspaces）分布独立的 PAC 学习问题。
具体而言，给定从 R^d+1 上的分布 D 中提取的一组有标签样本 (x, y)，使无标记点 x 上的边缘分布是任意的，且标签 y 由未知半空间生成，该空间被噪声率为 η ＜ 1/2 的 Massart 噪声破坏。最终目标是找到一个分类器 h，使错误分类误差最小。对于具有错误分类误差 η + ε 的问题，作者给出了一个 poly(d, 1/ε) 时间算法。
作者还证明了对算法的误差保证进行改进可能很难实现。
Massart 噪声与 RCN 随机分类噪声（Random Classification Noise，RCN）是 Massart 噪声的特殊情况，其每个标签的翻转概率恰好为 η ＜ 1/2。似乎 Massart 噪声比 RCN 更易于处理。
但实际上，Massart 对抗需要选择是否扰动给定的标签，如扰动，以何种概率进行，因此，在该模型中设计有效的算法具有很大挑战性。尤其是，RCN 学习与统计查询（Statistical Query，SQ）模型之间的联系不再成立，即，作为 SQ 算法的性质已不能自动满足用 Massart 噪声进行噪声容忍学习（noise-tolerant learning）的需要。
而正是利用了 RCN 与 SQ 模型的关系，得到了用 RCN 学习半空间的多项式时间算法。
Bylander 给出了多项式时间算法来学习带有 RCN 的大边界半空间（large margin halfspaces）（在附加的反集中假设下）。布鲁姆等人给出了第一个多项式时间算法，用于在无任何边界假设情况下使用 RCN 对半空间进行与分布独立的学习。
此后不久，Cohen 针对该问题给出了多项式时间适当的学习算法。随后，Dunagan 和 Vempala 提出了一种重缩放的感知器算法，用于求解线性规划，从而转化为更简单和快速的适当学习算法。
作者主要结果是以下定理：令 D 为（d + 1）维度的带标签样本在 b-bit 复杂度上的分布，由一个未知的半空间所产生，该空间被噪声率为 η ＜ 1/2 的 Massart 噪声破坏。
算法 2 使用个样本，运行时间为 poly(d, 1/ε, b)，最终以 2/3 的概率返回一个分类器 h，且其误分类误差。作者提出了首个在带 Massart 噪声的半空间（halfspaces）的分布独立的 PAC 学习的方法，即对具有错误分类误差 η + ε 的问题，给出了一个 poly(d, 1/ε) 时间算法。作者还证明对算法的错误保证而进行的改进可能很难实现。