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