计算学习理论
计算学习理论研究哪些概念可以从示例中高效学习，将学习视为一个计算和样本复杂性问题。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
计算学习理论是研究从示例中学习概念所需的数据和计算资源；在可能近似正确（PAC）模型中，如果一个算法能够从多项式数量的样本并在多项式时间内输出一个以高概率准确的假设，那么一个概念类就是可学习的。
Scope
本主题涵盖了可学习性的形式模型：可能近似正确（PAC）模型，该模型探讨了在多项式数量的示例和计算下，概念何时能以高概率高精度地学习；错误界限和在线学习模型；弱可学习性与强可学习性及提升（boosting）；以及与计算复杂性的联系。它解决了学习的统计可行性和算法可行性。
Core questions
- 哪些概念类可以从示例中高效学习？
- 学习一个概念需要多少数据和计算？
- 弱可学习性与强可学习性之间有什么关系？
- 可学习性如何与计算复杂性联系起来？
Key theories
- 可能近似正确学习
- 瓦利安特（Valiant）的模型将一个概念类定义为可学习的，即当一个高效算法能够以高概率从多项式数量的示例中产生一个低误差的假设时，从而使可学习性成为一个精确的计算问题。
- 弱可学习性与提升
- 一个核心结果表明，任何比随机猜测稍好的可学习类也是强可学习的，这直接导致了将弱学习器放大为精确学习器的提升算法。
- 统计和计算限制
- 可学习性受样本复杂性（与容量度量相关）和计算难度两方面的限制，因此有些类别在统计上是可学习的，但在计算上是难以处理的。
Clinical relevance
计算学习理论为学习算法的能力和局限性提供了形式基础，并直接启发了实际方法，其中最著名的是提升（boosting），它源于弱学习器是否可以组合成强学习器的问题；它将学习构建为一门严谨的计算学科。
History
瓦利安特（Valiant）于1984年引入了可能近似正确（PAC）模型，为学习提供了精确的计算定义，并开创了该领域。随后的工作确立了样本复杂性特征、弱可学习性与强可学习性的等价性（这激发了提升算法），以及显示学习计算极限的难度结果。
Key figures
- Leslie Valiant
- Michael Kearns
- Robert Schapire
Related topics
Seminal works
- valiant1984
- kearns1994
- vapnik1995
Frequently asked questions
- “可能近似正确”是什么意思？
- 这意味着，在随机样本的高概率下，学习器输出的假设是近似正确的，即在未来数据上具有小误差。可学习性要求从数量和计算量仅呈多项式增长的示例中实现这一点。
- 学习理论是如何导致提升（boosting）的？
- 研究人员曾问，一个仅比随机猜测稍好的学习器是否能转变为一个高度准确的学习器。弱可学习性与强可学习性等价的证明是建设性的，而这种建设性成为了在实践中广泛使用的提升算法。