可能近似正确的学习

在计算学习理论中，可能近似正确的学习（PAC）是一个机器学习的数学分析框架。在这个框架中，学习者收到样本，必须从某类可能的函数中选择一个概括性的函数（称为假设）。目标是，在高概率的情况下（可能的部分），所选的函数将具有低泛化误差（近似正确的部分）。学习者必须能够在任何任意的近似率、成功概率或样本分布的情况下学习这个概念。该模型后来被扩展到处理噪声（错误分类的样本）。PAC框架的一个重要创新是将计算复杂性理论的概念引入机器学习。特别是，学习者被期望找到有效的函数（时间和空间的要求被约束为例子大小的多项式），而学习者本身必须实现一个有效的程序。

为了给出PAC可学习的东西的定义，我们首先要介绍一些术语。对于下面的定义，我们将使用两个例子。xxx个例子是字符识别的问题，给定一个数组为n的数组位编码的二值图像。

另一个例子是寻找一个区间的问题，该区间内的点将被正确地分类为正值，而区间外的点则是负值。{displaystyleX}是一个被称为实例空间的集合。是一个称为实例空间或所有样本编码的集合。在字符识别问题中，实例空间为{displaystyleX}是区间问题中所有有界区间的集合。是R中所有有界区间的集合。

在某些规则性条件下，这些条件是等价的。概念类C是可PAC学习的。C的VC维度是有限的。