A theory of universal learning
A theory of universal learning
复制标题
DOI：
10.1145/3406325.3451087
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
O. Bousquet;Steve Hanneke;S. Moran;Ramon van Handel;A. Yehudayoff
中科院分区：
文献类型：
--
作者：
O. Bousquet;Steve Hanneke;S. Moran;Ramon van Handel;A. Yehudayoff
从例子中学习给定的一类概念有多快？通常通过绘制其“学习曲线”来衡量监督机器学习算法的性能，即错误率随训练示例数量的衰减。然而，理解可学习性的经典理论框架，Vapnik-Chervonenkis和Valiant的PAC模型，并没有解释学习曲线的行为：学习的无分布PAC模型只能限制所有可能的数据分布上的学习曲线的上包络。这与机器学习的实践不匹配，在机器学习中，数据源通常在任何给定的场景中都是固定的，而学习者可以根据计算资源和期望的准确性等因素选择训练示例的数量。在本文中，我们研究了另一种学习模型，它更好地捕捉了机器学习的实际方面，但仍然在PAC模型的精神下产生了一个完整的可学习理论。更确切地说，我们考虑了通用学习的问题，它旨在了解学习算法在每个数据分布上的性能，但不要求分布均匀。这篇论文的主要结果是一个显著的分解：只有三种可能的普遍学习率。更准确地说，我们表明，任何给定的概念类的学习曲线衰减指数，线性或任意慢的速度。此外，这些情况下的每一个完全特征在于适当的组合参数，我们展示了最佳的学习算法，在每种情况下，实现最佳的可能速率。为了具体起见，我们在本文中只考虑可实现的情况下，虽然类似的结果预计将扩展到更一般的学习场景。
How quickly can a given class of concepts be learned from examples? It is common to measure the performance of a supervised machine learning algorithm by plotting its “learning curve”, that is, the decay of the error rate as a function of the number of training examples. However, the classical theoretical framework for understanding learnability, the PAC model of Vapnik-Chervonenkis and Valiant, does not explain the behavior of learning curves: the distribution-free PAC model of learning can only bound the upper envelope of the learning curves over all possible data distributions. This does not match the practice of machine learning, where the data source is typically fixed in any given scenario, while the learner may choose the number of training examples on the basis of factors such as computational resources and desired accuracy. In this paper, we study an alternative learning model that better captures such practical aspects of machine learning, but still gives rise to a complete theory of the learnable in the spirit of the PAC model. More precisely, we consider the problem of universal learning, which aims to understand the performance of learning algorithms on every data distribution, but without requiring uniformity over the distribution. The main result of this paper is a remarkable trichotomy: there are only three possible rates of universal learning. More precisely, we show that the learning curves of any given concept class decay either at an exponential, linear, or arbitrarily slow rates. Moreover, each of these cases is completely characterized by appropriate combinatorial parameters, and we exhibit optimal learning algorithms that achieve the best possible rate in each case. For concreteness, we consider in this paper only the realizable case, though analogous results are expected to extend to more general learning scenarios.