可能近似正确 (PAC) 学习理论有助于分析学习者是否以及在什么条件下$L$可能会输出一个近似正确的分类器。（你会看到一些来源使用$A$代替$L$.)

首先，让我们定义“近似”。一个假设$h \in H$如果它在输入分布上的误差受到某些限制，则近似正确$\epsilon, 0 \le \epsilon \le \frac{1}{2}.$IE，$error_D(h)\lt \epsilon$， 在哪里$D$是输入的分布。

接下来，“可能”。如果$L$会以概率输出这样的分类器$1 - \delta$， 和$0 \le \delta \le \frac{1}{2}$，我们称该分类器可能大致正确。

知道目标概念是 PAC 可学习的，您可以限制可能学习近似正确分类器所需的样本量，这就是您复制的公式中显示的内容：

为了对此有一些直觉，请注意对$m$当您更改右侧的变量时。随着允许误差的减小，必要的样本量就会增加。同样，它随着近似正确学习器的概率以及假设空间的大小而增长$H$. （粗略地说，假设空间是您的算法考虑的分类器集合。）更清楚地说，当您考虑更多可能的分类器，或者希望更低的错误或更高的正确概率时，您需要更多的数据来区分它们。

此外，这个和其他相关视频可能会有所帮助，例如，这个冗长的介绍或许多机器学习文本之一可能会有所帮助，例如Mitchell。

可能近似正确的定义是由于 Valiant。它旨在对什么是机器学习给出严格的数学定义。
让我闲逛一下。虽然 PAC 使用“假设”一词，但大多数人使用模型一词而不是假设。向统计界致敬，我更喜欢模型，但我会尝试同时使用这两种模型。机器学习从一些数据开始， $(x_i, y_i)$并且想要找到一个假设或模型，在给定输入的情况下$x_i$返回$y_i$或非常接近的东西。更重要的是考虑到新数据$\tilde{x}$ 该模型将计算或预测相应的$\tilde{y}$.
真的有人对假设在给定（训练）数据上的准确性不感兴趣，除非很难相信使用某些数据创建的模型不会准确反映该数据集，但在任何未来都是准确的数据集。两个重要的警告是，一个人无法以 100% 的准确率预测新数据，而且一个人看到的数据示例也有可能遗漏了一些重要的东西。一个玩具例子是，如果我给你“数据”1、2、3、4，一个人会“预测”5 将是下一个数字。如果你通过询问人们序列中的下一个数字是什么来测试这一点，大多数人会说 5。有人可以说1,000,000。如果给您序列 1,2,3,...999,999，则可以确定下一个数字是 1,000,000。然而，下一个数字可能是 999,999.5，甚至是 5。关键是人们看到的数据越多，就越能确定一个人已经产生了一个准确的模型，但永远不能绝对确定。

可能近似正确的定义给出了这个想法的数学精确版本。给定数据$x_i, 1 \leq i \leq m$带输出$y_i$和一类模型$f_{\theta}$这构成了一个可以提出 2 个问题的假设。我们可以使用数据来找到一个特定的假设吗$f_{\Theta}$这在预测新值时可能真的很准确？此外，该模型与我们预期一样准确的可能性有多大？那就是我们可以训练一个很可能非常准确的模型。正如 Sean Easter 的回答一样，如果我们可以进行“epsilon，delta”论证，我们说一类假设（模型类）是 PAC。也就是说，我们可以用概率说$p >1-\delta$我们的模型$f_{\Theta}$准确到内$\epsilon$. 必须查看多少数据才能满足特定对$(\delta,\epsilon)$取决于实际$(\delta,\epsilon)$以及给定类别的假设有多复杂。

更准确地说，一类假设$\mathcal{H}$或模型$f_{\theta}$是 PAC 如果对于任何一对 $(\epsilon, \delta)$和$0 < \epsilon,\delta , <.5$有特定型号$f_{\Theta}$这样任何新数据$\tilde{x}, \tilde{y}$, 该模型将满足$Err(f_{\Theta}(\tilde{x}) ,\tilde{y} ) < \epsilon$ 有概率$p > 1-\delta$如果模型被选择（训练）至少 $m = m(\delta,\epsilon,\mathcal{H})$训练示例。这里 Err 是选择的损失函数，通常是$(f_{\Theta}(\tilde{x}) -\tilde{y})^2$.

您的图表给出了一个公式，说明对于给定的假设类别需要训练多少数据才能满足给定的对$(\delta,\epsilon)$. 我可能是错的，但我相信这个定义是 Valiant 在一篇名为“A Theory of the Learnable”的论文中给出的，并且是 Valiant 获得图灵奖的部分原因。