PAC

可能近似正确（PAC）理论

本质上，机器学习也是假设验证。为了帮助理解这个理论的含义，我们解释“近似正确”：在泛化误差足够小（最好0）的情况下，我们就把泛化误差限定在一个很小的数之内。即只要假设满足这个条件，我们就认为这个假设是正确的。上一篇解释了经验误差; 而泛化误差（Generalization error）的定义如下:

然后，我们解释“可能”：不指望选择的假设百分之百是近似正确的，只要很可能是近似正确的就可以，即满足大于一定概率就可以了。

VC维：是描述可学习程度的量。而这个描述是通过散化（Shattering）来表达的，指的是假设空间能实现数据集上全部示例的分类；在分类问题中近似地，不能散花就是不可分。

为了帮助理解这个概念，我们描述VC维跟一些其他量的关系：

1. VC维跟模型复杂度是正相关的;

2. 它只与模型和假设空间有关;

3. 不管数据是怎样分布的，H最多能区分多少个数据;

4. 模型的可学习性，只与数据量与模型复杂度有关。

一些参考文献

- Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. 2014. Q325.5 .S475 2014 c. 1

- Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine

learning. 2012. Q325.5 .M64 2012 c. 1

- Shai Shalev-Shwartz. Online learning and online convex optimization. 2012. Available at:

http://www.cs.huji.ac.il/~shais/papers/OLsurvey.pdf .

- Trevor Hastie, Robert Tibshirani, Jerome Friedman (2001). The Elements of Statistical

Learning. Available at http://statweb.stanford.edu/~tibs/ElemStatLearn/ .

- Luc Devroye, László Györ[i, Gábor Lugosi. A probabilistic theory of pattern recognition. 1996. Q 327 .D5 1996 c. 1

- Vladimir N. Vapnik. Statistical learning theory. 1998. Q325.7.V38 1998 c. 2

- Kevin Murphy. Machine learning: a probabilistic perspective. 2012. Q325.5 .M87 2012 c. 1

- Christopher Bishop. Pattern recognition and machine learning. 2009. Q327.B52 2009 c. 1

- Tom M. Mitchell. Machine learning. 1997. Q325.5.M58 1997 c. 1