Probably Approximately Correct learning framework

在计算学习理论中，可能近似正确的学习（PAC学习）是机器学习的数学分析的框架。它由Leslie Valiant于1984年提出。
[1]在这个框架中，学习者接收样本并且必须从某类可能的函数中选择泛化函数（称为假设）。
目标是，具有高概率（“可能”部分），所选择的函数将具有低泛化误差（“近似正确”部分）。给定任意近似比，成功概率或样本分布，学习者必须能够学习概念。该模型后来扩展到处理噪声（错误分类的样本）。
PAC框架的一个重要创新是将计算复杂性理论概念引入机器学习。特别是，期望学习者找到有效的函数（时间和空间要求受限于示例大小的多项式），并且学习者本身必须实现有效的过程（需要将示例计数限制为概念大小的多项式，修改通过近似和似然界限）。
定义和术语