Liyang作者学术菠菜排版学术青 会会校对学术青 优学术责编

NeurIPS 2019最佳论文:具有Massart噪声半空间的分布独立PAC学习

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.

AMiner学术头条
AMiner学术头条

AMiner平台由清华大学计算机系研发,拥有我国完全自主知识产权。系统2006年上线,吸引了全球220个国家/地区800多万独立IP访问,数据下载量230万次,年度访问量1000万,成为学术搜索和社会网络挖掘研究的重要数据和实验平台。

https://www.aminer.cn/
专栏二维码
理论论文NeurIPS 2019
1
相关数据
感知技术

知觉或感知是外界刺激作用于感官时,脑对外界的整体的看法和理解,为我们对外界的感官信息进行组织和解释。在认知科学中,也可看作一组程序,包括获取信息、理解信息、筛选信息、组织信息。与感觉不同,知觉反映的是由对象的各样属性及关系构成的整体。

线性规划技术

在数学中,线性规划(Linear Programming,简称LP)特指目标函数和约束条件皆为线性的最优化问题。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

感知器技术

感知器是Frank Rosenblatt在1957年就职于Cornell航空实验室时所发明的一种人工神经网络。它可以被视为一种最简单形式的前馈神经网络,是一种二元线性分类器。 Frank Rosenblatt给出了相应的感知机学习算法,常用的有感知机学习、最小二乘法和梯度下降法。

暂无评论
暂无评论~