对于一个concept class C，如果存在一个算法A和一个多项式poly(.,.,.,.),有对于任意的ε>0、δ>0以及X的任意分布D和任何target concept C，当sample size m>=poly(1/ε,1/δ,n,size(c))时，不等式：

都成立，那么就说这个concept class C是PAC-learnable的。

(1).n：x的维度。

(2).size(c):

O(n):an upper bound on the cost of the computational representation of any element x?X。对于一个维度为n的用数组表示的x来说要计算的话时间复杂度最高就是O(n)。

size(n):the maximal cost of the computation representation of c?C。同O(n)的解释，可以看做就是c的大小。

如果算法A的样本复杂度关于1/δ,1/ε,n,size(c)的大小是多项式的，那么就说C是efficiently PAC-learnable的。当这样的A存在的时候，该算法A被叫做concept class C的PAC learning algorithm。

对于PAC-learnability还有一些要注意的地方：

1.PAC对于x的任意分布D都是成立的。

2.虽然对分布没有限定，training sample和testing sample都要产生与同一个分布D。

3.PAC所解决的是一个concept class C的可学习性问题，并不针对一个特别的concept c(通常target c也是未知的但C是已知的)。

一个例子：

    如图，X=R^2，concept class C是在R^2上的所有边与坐标轴平行的矩阵，目标是求得一个concept C使得矩阵内部的点都为1(蓝点)，矩阵外部的点都为2(红点)。对于这个问题设计了一个非常简单的算法，算法返回包含了所有label为1的点的最小的矩阵。

    假设算法返回的矩阵为R‘，我们沿R的四个边做四个矩形为r1,r2,r3,r4，并令它们的probability mass等于ε/4，如果我们要使R(R‘)也就是R‘的gerneralization error大于ε，那么R‘不能和四个矩阵都有交集，否则R-R‘=R(R‘)必小于ε。也就是R‘至少要和一个矩阵ri没有交集。

于是有：

（1）:由于Rs与ri没有交集等价于没有蓝点落在ri中，又ri在target concept R中，所以没有红点落在ri中，综合下也就是没有点落在ri中，每个点落在ri的概率为ε/4，那么对于每个ri，m个点都不落在其中的概率为(1-ε/4)^m，有四个ri。

（2）:为exp^(-x)的泰勒的泰勒展开缩放。

由此得：

也就是样本大小m在满足上述不等式时能够保证concept space是PAC Learnable的。这里对于1/δ是ln复杂度，对于1/ε是线性复杂度，总的来说是efficiently PAC-learnable的。

[FML学习笔记二]PAC Learning Model