Tag Archives: Learning Theory

PAC Learning

PAC的全称是Probably Approximately Correct,首先是一些符号的定义,下面以图像中的字符识别为例说明:

X: 所有可能实例的集合,如n维的0/1位图矩阵{0,1}^n,其中一个具体值表示为x
c: concept,是指一个X的子集,或者说是一个X中的元素到布尔值的{0,1}映射,比如“该字符是8”这个concept就表明一个映射,它对所有是8的图像x有c(x)=1,对于其它x有c(x)=0
C: 一系列concept的集合
D: X的概率分布
h: 要考察的算法输出的一个hypothesis,在这里就是识别某字符是否为8的一个算法,我们希望它尽可能地接近c

这里“尽可能地接近”的意思是,有比较大的概率(Probably)得到的结果在大部分情况下(Approximately)与c一致。更严格地定义PAC-learnable如下:

集合C为PAC-learnable是指对于其中的所有concept c,对于任意分布D,对于任意小的数0 < eps < 1/2和0 < delta < 1/2,我们要考察的算法有至少(1-delta)的概率输出一个h满足P[h(x) != c(x)] <= eps,并且算法花费时间与 1/eps, 1/detla成多项式关系。

经典PAC framework的限制是(1)映射的值域只能为离散值(2)数据不能有噪声。针对这两个缺陷的扩展也有相关的研究。

参考资料

http://en.wikipedia.org/wiki/Probably_approximately_correct_learning
http://citeseer.ist.psu.edu/haussler92part.html