计算学习理论

在计算机科学中，计算学习理论（或只是学习理论）是人工智能的一个子领域，致力于研究机器学习算法的设计和分析。

机器学习的理论成果主要涉及一种被称为监督学习的归纳学习。在监督学习中，一个算法被赋予了以某种有用方式标记的样本。例如，样本可能是对蘑菇的描述，而标签可能是蘑菇是否可以食用。该算法采用这些先前标记的样本，并使用它们来诱导一个分类器。这个分类器是一个为样本分配标签的函数，包括算法以前没有见过的样本。监督学习算法的目标是优化一些性能指标，如最小化在新样本上的错误数量。除了性能界限外，计算学习理论还研究学习的时间复杂性和可行性。在计算学习理论中，如果一个计算可以在多项式时间内完成，就被认为是可行的。有两种时间复杂性的结果。正面结果--表明某类函数可以在多项式时间内学习。负面结果--表明某些类别不能在多项式时间内学习。负面结果往往依赖于普遍认为但尚未证实的假设，如：。计算复杂性--P≠NP（P与NP的问题）；密码学--存在单向函数。