Distribution-Independent PAC Learning of Halfspaces with Massart Noise
论文作者：
Ilias Diakonikolas, Themis Gouleakis, Christos Tzamos（威斯康辛大学麦迪逊分校、马克斯普朗克计算机科学研究所）
论文链接：
https://www.aminer.cn/pub/5d1eb9d3da562961f0b0dc62/
开源地址：
https://papers.nips.cc/paper/8722-distribution-independent-pac-learning-of- halfspaces-with-massart-noise
前言
本文将对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）【1】是Massart噪声的特殊情况，其每个标签的翻转概率恰好为η＜1/2。似乎Massart噪声比RCN更易于处理。但实际上，Massart对抗需要选择是否扰动给定的标签，如扰动，以何种概率进行，因此，在该模型中设计有效的算法具有很大挑战性。尤其是，RCN学习与统计查询（Statistical Query，SQ）模型【2】【3】之间的联系不再成立，即，作为SQ算法的性质已不能自动满足用Massart噪声进行噪声容忍学习（noise-tolerant learning）的需要。而【4】【5】中正是利用了RCN与SQ模型的关系，得到了用RCN学习半空间的多项式时间算法。
相关工作介绍
Bylander【6】给出了多项式时间算法来学习带有RCN的大边界半空间（large margin halfspaces）（在附加的反集中假设下）。布鲁姆等人【7】给出了第一个多项式时间算法，用于在无任何边界假设情况下使用RCN对半空间进行与分布独立的学习。此后不久，Cohen【8】针对该问题给出了多项式时间适当的学习算法。随后，Dunagan和Vempala【9】提出了一种重缩放的感知器算法，用于求解线性规划，从而转化为更简单和快速的适当学习算法。
在这项工作之前，在分布独立的Massart噪声模型中，基本上没有具有非平凡误差保证的有效算法。应该注意的是，当未标记数据上的边界分布在单位球面上时，具有误差OPT +ε的多项式时间算法是已知的【10】【11】【12】。对于未标记数据来自各向同性对数凹分布的情况，【13】给出了
采样和时间算法。
方法
相关基础
带Massart噪声的半空间学习算法
学习大边界半空间
一般情况
主要结果
作者主要结果是以下定理：
令D为（d + 1）维度的带标签样本在b-bit复杂度上的分布，由一个未知的半空间所产生，该空间被噪声率为η＜1/2的Massart噪声破坏。算法2使用
个样本，运行时间为poly(d, 1/ε, b)，最终以2/3的概率返回一个分类器h，且其误分类误差
。
总结
作者提出了首个在带Massart噪声的半空间（halfspaces）的分布独立的PAC学习的方法，即对具有错误分类误差η+ε的问题，给出了一个poly(d, 1/ε)时间算法。作者还证明对算法的错误保证而进行的改进可能很难实现。
参考文献：
【1】D. Angluin and P. Laird. Learning from noisy examples. Mach. Learn., 2(4):343–370,1988.
【2】M. J. Kearns. Efficient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 392–401,1993.
【3】M. J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983–1006, 1998.
【4】A. Blum, A. M. Frieze, R. Kannan, and S. Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, pages 330–338, 1996.
【5】A. Blum, A. Frieze, R. Kannan, and S. Vempala. A polynomial time algorithm for learning noisy linear threshold functions. Algorithmica, 22(1/2):35–52, 1997.
【6】T. Bylander. Learning linear threshold functions in the presence of classification noise.In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 1994, pages 340–347, 1994.
【7】A. Blum, A. M. Frieze, R. Kannan, and S. Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, pages 330–338, 1996.
【8】E. Cohen. Learning noisy perceptrons by a perceptron in polynomial time. In Proceedings of the Thirty-Eighth Symposium on Foundations of Computer Science, pages 514–521,1997.
【9】J. Dunagan and S. Vempala. A simple polynomial-time rescaling algorithm for solving linear programs. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 315–320, 2004
【10】P. Awasthi, M. F. Balcan, N. Haghtalab, and R. Urner. Efficient learning of linear separators under bounded noise. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, pages 167–190, 2015.
【11】Y. Zhang, P. Liang, and M. Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages 1980–2022, 2017.
【12】Y. Zhang, P. Liang, and M. Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages 1980–2022, 2017.
【13】P. Awasthi, M. F. Balcan, N. Haghtalab, and H. Zhang. Learning and 1-bit compressed sensing under asymmetric noise. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, pages 152–192, 2016.
【14】A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Mathematical Statistics, 27(3):642–669, 1956.
【15】J. Dunagan and S. Vempala. Optimal outlier removal in high-dimensional spaces. J.Computer & System Sciences, 68(2):335–373, 2004.
