计算学习理论，或者说统计学习理论，指的是量化学习任务和算法的数学框架。对于机器学习领域的实践者来说，想找到大多数问题的优质解决方案，并不需要深度了解这些机器学习的子领域。尽管如此，在子领域中，对一些更重要的方法有一个较高水平的理解可能为数据中学习的更广泛的任务中提供洞见。在本文中，你将会发现一个对机器学习的计算学习理论的简要介绍。
计算学习理论使用形式化的方法研究学习任务和学习算法。
PAC学习提供了一个可以量化机器学习任务计算难度的方法。VC维提供了一种可以量化机器学习算法计算能力的方法。计算学习理论，或者简称CoLT，是与应用于学习系统的形式化的数学方法的使用有关的研究领域。它致力于寻找理论计算机科学工具来量化学习问题，包括刻画学习特定任务的难度。计算学习理论可能被认为是统计学习理论的延伸或者是兄弟，两者都是使用形式化的方法来量化学习算法。
学习任务和学习算法之间的区分是十分武断的，并且在实践中，这两个领域有很多重叠之处。计算学习理论主要关注于监督学习任务。实际问题和实际算法的形式化分析非常具有挑战性。因此，通常通过关注二分类任务甚至简单的基于规则的二分类系统来降低分析的复杂度。因而对于实际问题或算法的解释，公理的应用可能是有限且具有挑战性的。
计算学习理论的问题可能包括：如何得知模型对目标函数有一个好的估计？应该使用怎样的假设空间？
如何知道我们得到的是局部最优解还是全局最优解？如何避免过拟合？需要多少数据样本？作为一个机器学习的实践者，知道计算学习理论以及一些主要的研究领域是非常有用的。这个领域为我们在数据上拟合模型时试图实现的目标提供了有用的基础，也可以提供对方法的洞见。该研究有很多子领域，虽然计算学习理论研究中最常讨论的两个领域是：PAC学习和VC维。
简单来说，我们可以将PAC学习叫做机器学习问题的理论，将VC维叫做机器学习算法的理论。
PAC学习（学习问题的理论）概率近似正确学习（Probably approximately correct learning）或者叫做PAC学习，指的是由Leslie Valiant提出的理论性的机器学习框架。PAC学旨在把学习任务的难度量化，可以被认为是计算学习理论的首要子领域。
PAC学习与查找未知目标函数接近的假设（拟合模型）所需的计算量有关。我们的想法是一个差的假设会通过它在新的数据集上预测的结果表现出来，例如，基于它的泛化误差。当一个假设可以使得大部分或者大量的预测结果正确时，例如，一个小的泛化误差就很可能是对目标函数好的近似。
VC维度（学习算法的理论）Vapnik–Chervonenkis理论，简称VC理论，指的是由Vladimir Vapnik和Alexey Chervonenkis提出的理论的机器学习框架。VC理论试图将学习算法的能力进行量化，并被认为是统计学习理论首要的子领域。VC维将假设空间的复杂度量化，例如，给定一个表征和学习算法，模型可被拟合。
VC维是一种非常巧妙的方法，它替代了目标问题的样本数量，这些样本可以通过空间假设来区分。VC维估计了对特定数据集的分类机器学习算法的能力或容量（样本的数量和维数）。形式化地说，VC维是来自算法可以“打散”的假设空间中训练集的最大样本数。