在计算学习理论中，概率近似正确学习（PAC) 是机器学习领域中的一种数学分析框架。它是1984年由莱斯利·瓦里安Leslie Valiant提出的。[1]
在这个框架中，学习者接收样本，并且必须从一类可能的函数中选择一个泛化函数(称为归纳偏移)。其目标是，在尽可能高的概率下，所选函数的泛化误差应当较低。学习者必须能够在任意给定比率、成功概率或样本的分布学得概念。
该模型后来被扩展到处理噪声(被错误分类的样本)。
PAC框架的一个重要创新是引入了机器学习中计算复杂性理论的概念。特别地，学习者需要找到有效的函数(时间和空间复杂度限制在 多项式内)， 并且学习者本身必须实现一个有效的程序(该程序的一个例子需要在近似多项式时间复杂度内完成)。
为了给PAC可学习下定义，我们首先要介绍一些术语。[2][3]
对于以下定义，将引入两个示例。 第一个例子是在给定一个 编码二进制值图像的数组的情况下完成字符识别的问题。另一个例子是找到一个区间，该区间将正确地将区间内的点分类为正，将区间外的点分类为负。
设 是一个叫做样本空间 （或者说是所有样本的编码）。在字符识别问题中，样本空间是 。 在区间问题中，样本空间 ，是中所有有界区间的集合 ，其中 表示所有实数的集合。
一个概念应当是 的子集。第一个例子一个概念是 中所有的编码字母“P”的图片的比特的模式的集合。第二个例子中的一个概念是一组开放区间 ，其中每一个区间只包含正数。 一个概念类 是一组定义在 上的概念构成的集合。这可以是比特数组的所有子集的集合骨架化的 4-连接 (字体宽度为1)。
设 是一个举个例子的过程， ，使用概率分布 并给出正确的标签 ，即为1如果 否则为0。
现在，鉴于 ，假设有一个算法 和多项式 在 (以及该类的其他相关参数 )使得，给定根据以下标准绘制的尺寸为p的样本 那么，至少有可能 , 输出一个假设 平均误差小于或等于 在 具有相同的分布 。 此外，如果上述算法语句 对每个概念都是正确的 对于每一次发行 超过 对所有人来说 然后 是(有效地) PAC可学习 (或免分发包装可学习)。我们也可以这么说 是一个包装学习算法为 。
在某些特定条件下，以下三个条件是等价的:
暂无