Probably Approximately Correct 概率近似正确
其实是从算法训练成功的样本数量出发，定义了一系列的可学习概念
PAC学习框架概述
分析机器学习算法的框架，描述有限数据下，学习算法能够以高概率找到接近于最优的假设
基本目标是确保模型不仅能够在训练数据上表现良好，而且能够在未见的数据上保持同样的性能，保证描述了模型的泛化能力
其提供了泛化误差的上界
泛化误差上界
PAC框架中，希望找到一个假设 h(模型)，使得这个假设的泛化误差(generalization error)可以在高概率下被控制在一个可接受的范围内
通常表示为 在未见数据的误差
PAC框架目标是找到一个满足条件：
即误差大于 精度 的概率要小与 置信度
其包含了近似正确和近似正确的概率，含义为如果输入到一个算法的样本的数目关于, 是多项式的，且该算法基于这些样本得到的假设是高概率近似正确的，则概念类C是PAC可学习的。
假设空间和VC维
PAC 通过考虑假设空间的大小和复杂度来估计泛化误差的上界，假设空间越大越复杂，则训练数据效果越好，但这通常会导致过拟合，为量化假设空间的复杂度，通常使用VC维(Capnik-Chervonenkis Dimension) 来衡量假设空间容量，其表示假设空间能够“打散(shatter)“样本点的最大数量
打散 假设空间中存在一个假设，它能够在选定样本集合所有可能的标记组合下，将样本点完全正确分类
VC维关键思想是：
- 如果VC维很大，意味着假设空间能够在高维空间中灵活地对数据进行分类，空间复杂度高，容易过拟合
- 如果VC维很小，假设空间的容量有限，可能不足以捕捉数据中的复杂模式，泛化能力较强
VC维描述模型能多大程度的讲数据分割成不同的类别，假设VC维是d，则PAC框架中的泛化误差上界通常表示为：
其中：
- 是训练误差。
- 是训练样本的数量。
- 是 VC 维。
- 是上界的置信度参数。
Hoeffding 不等式
为独立随机变量的和提供一个上界，用来描述训练误差和泛化误差之间的差异，能够确保在m（训练样本量）足够大的情况下，泛化误差不会显著高于训练误差