We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. We provide a rather surprising answer - no such parameter exists. Our techniques allow us to show similar results for several general notions of characterizing learnability and for several learning tasks. We show that there is no notion of dimension that characterizes the sample complexity of learning distribution classes. We then consider the weaker requirement of only characterizing learnability (rather than the quantitative sample complexity function). We propose some natural requirements for such a characterization and go on to show that there exists no characterization of learnability that satisfies these requirements for classes of distributions. Furthermore, we show that our results hold for various other learning problems. In particular, we show that there is no notion of dimension characterizing (or characterization of learnability) for any of the tasks: classification learning for distribution classes, learning of binary classifications w.r.t. a restricted set of marginal distributions, and learnability of classes of real-valued functions with continuous losses.


翻译:我们考虑了寻找类别概率分布的学习可能性的参数的长期问题。我们提供一个非常惊人的答案-没有这样的参数存在。我们的技术允许我们展示类似的结果适用于几个常见的可学习性特征的普遍概念和几个学习任务。我们表明没有维度的概念可以描述学习分布类的样本复杂度。然后,我们考虑仅描述可学习性(而不是定量的样本复杂度函数)的要求。我们提出了一些自然的要求,以满足这样的描述,并继续展示,对于分布类中的学习性质,不存在满足这些要求的学习特征。此外,我们表明我们的结果适用于其他各种学习问题。特别是,我们表明不论是:分类学习分布类,有限的边缘分布限制下的二元分类学习,还是连续损失函数的实值函数类学习等都不存在描述可学习性的维度特征(或可学习性描述)的概念。

0
下载
关闭预览

相关内容

专知会员服务
76+阅读 · 2021年3月16日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
Multi-Task Learning的几篇综述文章
深度学习自然语言处理
15+阅读 · 2020年6月15日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月31日
Arxiv
38+阅读 · 2021年8月31日
Arxiv
45+阅读 · 2019年12月20日
VIP会员
相关VIP内容
专知会员服务
76+阅读 · 2021年3月16日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
相关资讯
Multi-Task Learning的几篇综述文章
深度学习自然语言处理
15+阅读 · 2020年6月15日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员