https://books.google.com.hk/books?id=n79Zh2JzBhYC&pg=RA1-PA930&lpg=RA1-PA930&dq=PAC%E5%AD%A6%E4%B9%A0&source=bl&ots=bfMpxn5sUv&sig=ACfU3U2S6oXxodelVkXqKmwUxsX6EynaoA&hl=en&sa=X&ved=2ahUKEwic2IP7nsXqAhUSPXAKHQnGBo4Q6AEwBnoECA8QAQ#v=onepage&q=PAC%E5%AD%A6%E4%B9%A0&f=false

1 基础知识

​ 采用数学方法，研究学习算法的计算复杂性和所需信息量的大小，分析算法所需的时间和空间资源，判定学习对象的可学习性等所形成的理论。

1.1 历史研究

1967年，E. M. Gold，形式化语言研究 提出 极限辨识理论

什么是正确的辨识(学习)的形式定义

D. Angluin 探讨新的学习对象，提出 模式语言学习

对学习对象的限制，获取某些有用的结果

1984年，L. G. Valiant 提出 PAC模型（概率近似模型）

反映了机器学习和人类学习的某些特点

VC维数

和可学习型以及所需样本数联系起来

2 PAC学习模型

  1. 允许学习者有时失败
  2. 允许学习者在学习成功时可以是近似正确的

PAC可学习性定义

误差参数、可靠性参数

学习产生的假设和目标之间的误差不超过误差参数

超过误差参数属于失败，失败概率小于 可靠性参数