题目: Distribution-Independent PAC Learning of Halfspaces with Massart Noise

摘要: 研究了存在Massart噪声的半空间{em分布无关}PAC学习问题。具体地说,我们给出了一组从\R~d+1上的\D分布中提取的标记示例(\b_x,y),使得未标记点\b_x上的边缘分布是任意的,并且标签y是由以噪声率ŋ<1/2被Massart噪声污染的未知半空间生成的。我们的目标是找到一个可以最小化错误分类\P~r(\b_x,y)~\D~[h(\bx)≠y]的假设h。我们给出了一个有误分类错误的时间算法\poly(d,1/\eps)。我们还证明了改进算法的误差保证在计算上可能是困难的。在我们的研究之前,在这个模型中,没有一个有效的弱(分布独立)学习者是已知的,即使是对于析取类。在Sulon(1988),科恩(1997)中,半空间(甚至间断)的这种算法的存在已经作为一个开放的问题提出,并且最近在Avrim Blum的FoCS 2003教程中被高亮显示。

作者简介: Ilias Diakonikolas,是威斯康星大学麦迪逊分校 (WISC)计算机系的一名教员。在加入威斯康星州大学之前,他是安德鲁和埃娜·维特比(Erna Viterbi)在南加州大学(USC)担任计算机科学早期职业主席,在爱丁堡大学(University of Edinburgh)任教员。在此之前,他在加州大学伯克利分校读了两年的博士后,在理论计算机科学研究员。他在哥伦比亚大学获得了计算机科学博士学位。个人主页:http://www.iliasdiakonikolas.org/

Themis Gouleakis,于2018年完成了麻省理工学院的博士学位,隶属于CSAIL的计算理论小组,现在是Max普朗克信息研究所算法与复杂性系的博士后研究员。

成为VIP会员查看完整内容
2

相关内容

神经信息处理系统年会(Annual Conference on Neural Information Processing Systems)的目的是促进有关神经信息处理系统生物学,技术,数学和理论方面的研究交流。核心重点是在同行会议上介绍和讨论的同行评审新颖研究,以及各自领域的领导人邀请的演讲。在周日的世博会上,我们的顶级行业赞助商将就具有学术意义的主题进行讲座,小组讨论,演示和研讨会。星期一是教程,涵盖了当前的问询,亲和力小组会议以及开幕式演讲和招待会的广泛背景。一般会议在星期二至星期四举行,包括演讲,海报和示范。 官网地址:http://dblp.uni-trier.de/db/conf/nips/
【CMU】机器学习导论课程(Introduction to Machine Learning)
专知会员服务
58+阅读 · 2019年8月26日
半监督多任务学习:Semisupervised Multitask Learning
我爱读PAMI
18+阅读 · 2018年4月29日
读论文Discriminative Deep Metric Learning for Face and KV
统计学习与视觉计算组
12+阅读 · 2018年4月6日
Arxiv
42+阅读 · 2019年12月20日
Arxiv
20+阅读 · 2019年11月24日
Few-shot Learning: A Survey
Arxiv
362+阅读 · 2019年4月10日
Arxiv
3+阅读 · 2018年10月11日
Mobile big data analysis with machine learning
Arxiv
6+阅读 · 2018年8月2日
The Matrix Calculus You Need For Deep Learning
Arxiv
10+阅读 · 2018年7月2日
Arxiv
5+阅读 · 2018年4月22日
VIP会员
相关VIP内容
【CMU】机器学习导论课程(Introduction to Machine Learning)
专知会员服务
58+阅读 · 2019年8月26日
相关论文
Arxiv
42+阅读 · 2019年12月20日
Arxiv
20+阅读 · 2019年11月24日
Few-shot Learning: A Survey
Arxiv
362+阅读 · 2019年4月10日
Arxiv
3+阅读 · 2018年10月11日
Mobile big data analysis with machine learning
Arxiv
6+阅读 · 2018年8月2日
The Matrix Calculus You Need For Deep Learning
Arxiv
10+阅读 · 2018年7月2日
Arxiv
5+阅读 · 2018年4月22日
微信扫码咨询专知VIP会员