NeurIPS 2019杰出论文深度解读:窥视机器学习的核心问题

简介: 在NeurIPS 2019一千多篇入选论文中,有那么1篇杰出论文值得长时间、深入、反复学习。

微信图片_20220107205942.jpg


该论文的作者是:
Ilias Diakonikolas(威斯康辛大学麦迪逊分校)、Themis Gouleakis(马克斯普朗克计算机科学研究所)、Christos Tzamos(威斯康辛大学麦迪逊分校)。


微信图片_20220107205939.png


论文地址:


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,使错误分类误差微信图片_20220107205936.png最小。对于具有错误分类误差η+ε的问题,作者给出了一个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】给出了微信图片_20220107205934.png采样和时间算法。


方法


相关基础


微信图片_20220107205930.png


带Massart噪声的半空间学习算法


微信图片_20220107205927.png

微信图片_20220107205925.jpg


学习大边界半空间


微信图片_20220107205922.png

微信图片_20220107205920.jpg微信图片_20220107205917.png微信图片_20220107205915.png

微信图片_20220107205912.jpg


一般情况


微信图片_20220107205909.jpg微信图片_20220107205906.jpg


主要结果


作者主要结果是以下定理:


微信图片_20220107205904.png


令D为(d + 1)维度的带标签样本在b-bit复杂度上的分布,由一个未知的半空间所产生,该空间被噪声率为η<1/2的Massart噪声破坏。算法2使用微信图片_20220107205901.png个样本,运行时间为poly(d, 1/ε, b),最终以2/3的概率返回一个分类器h,且其误分类误差微信图片_20220107205857.png


总结


作者提出了首个在带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.


本文经授权转载自:学术头条

相关文章
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
阿里云人工智能平台 PAI 团队发表的图像编辑算法论文在 MM2024 上正式亮相发表。ACM MM(ACM国际多媒体会议)是国际多媒体领域的顶级会议,旨在为研究人员、工程师和行业专家提供一个交流平台,以展示在多媒体领域的最新研究成果、技术进展和应用案例。其主题涵盖了图像处理、视频分析、音频处理、社交媒体和多媒体系统等广泛领域。此次入选标志着阿里云人工智能平台 PAI 在图像编辑算法方面的研究获得了学术界的充分认可。
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】阿里云人工智能平台 PAI 多篇论文入选 EMNLP2024
阿里云人工智能平台 PAI 的多篇论文在 EMNLP2024 上入选。论文成果是阿里云与华南理工大学金连文教授团队、复旦大学王鹏教授团队共同研发。EMNLP 是人工智能自然语言处理领域的顶级国际会议,聚焦于自然语言处理技术在各个应用场景的学术研究,尤其重视自然语言处理的实证研究。该会议曾推动了预训练语言模型、文本挖掘、对话系统、机器翻译等自然语言处理领域的核心创新,在学术和工业界都有巨大的影响力。此次入选标志着阿里云人工智能平台 PAI 在自然语言处理和多模态算法能力方面研究获得了学术界认可。
|
2月前
|
机器学习/深度学习 搜索推荐 算法
机器学习-点击率预估-论文速读-20240916
机器学习-点击率预估-论文速读-20240916
36 0
|
4月前
|
机器学习/深度学习 存储 人工智能
【ACL2024】阿里云人工智能平台PAI多篇论文入选ACL2024
近期,阿里云人工智能平台PAI的多篇论文在ACL2024上入选。论文成果是阿里云与阿里集团安全部、华南理工大学金连文教授团队、华东师范大学何晓丰教授团队共同研发。ACL(国际计算语言学年会)是人工智能自然语言处理领域的顶级国际会议,聚焦于自然语言处理技术在各个应用场景的学术研究。该会议曾推动了预训练语言模型、文本挖掘、对话系统、机器翻译等自然语言处理领域的核心创新,在学术和工业界都有巨大的影响力。此次入选标志着阿里云人工智能平台PAI在自然语言处理和多模态算法、算法框架能力方面研究获得了学术界认可。
|
5月前
|
机器学习/深度学习 人工智能 分布式计算
阿里云人工智能平台PAI论文入选OSDI '24
阿里云人工智能平台PAI的论文《Llumnix: Dynamic Scheduling for Large Language Model Serving》被OSDI '24录用。论文通过对大语言模型(LLM)推理请求的动态调度,大幅提升了推理服务质量和性价比。
|
5月前
|
机器学习/深度学习 人工智能 自然语言处理
|
4月前
|
机器学习/深度学习 数据采集 自然语言处理
【NLP】讯飞英文学术论文分类挑战赛Top10开源多方案–4 机器学习LGB 方案
在讯飞英文学术论文分类挑战赛中使用LightGBM模型进行文本分类的方案,包括数据预处理、特征提取、模型训练及多折交叉验证等步骤,并提供了相关的代码实现。
53 0
|
6月前
|
机器学习/深度学习 人工智能 自然语言处理
【CVPR2024】阿里云人工智能平台PAI图像编辑算法论文入选CVPR2024
近期,阿里云人工智能平台PAI发表的图像编辑算法论文在CVPR-2024上正式亮相发表。论文成果是阿里云与华南理工大学贾奎教授领衔的团队共同研发。此次入选标志着阿里云人工智能平台PAI自主研发的图像编辑算法达到了先进水平,赢得了国际学术界的认可。在阿里云人工智能平台PAI算法团队和华南理工大学的老师学生们一同的坚持和热情下,将阿里云在图像生成与编辑领域的先进理念得以通过学术论文和会议的形式,向业界传递和展现。
|
7月前
|
机器学习/深度学习 数据采集 人工智能
论文介绍:机器学习中数据集规模增长的极限分析
【5月更文挑战第17天】论文《机器学习中数据集规模增长的极限分析》探讨了数据集大小对AI模型性能的影响,预测语言数据可能在2026年前耗尽,图像数据在2030-2060年可能面临相同问题。研究显示数据积累速度无法跟上数据集增长,可能在2030-2040年间导致训练瓶颈。然而,算法创新和新数据源的发展可能缓解这一问题。[链接](https://arxiv.org/pdf/2211.04325.pdf)
106 2