林轩田机器学习基石心得7：The VC Dimension

该文章为本人观看视频心得，详细笔记可前往：
http://blog.****.net/red_stone1/article/details/71191232

0. 前言

前一课中着重介绍了机器能够学习的条件并做了详细的推导和解释。机器学习可行需要满足两个条件：
- Ein≈Eout
- Ein≈0

上次课引入了break point，并推导出只要break point存在，则M有上界，一定存在Ein≈Eout
这次课主要介绍VC维。

1. Definition of VC Dimension

1. 两点结论（对应机器学习要解决的两个问题）：
   
   • 若假设空间H有break point k，且N足够大，则根据VC bound理论，算法有良好的泛化能力
   • 在假设空间中选择一个g，使Ein≈0，则其在全集数据中的错误率会较低。
     

2. VC Dimension（VC维）：可以被shatter的最多样本个数。

   shatter：shatterN个样本就是说一共有2N种假设函数分类方法。

3. VC维的值为break point -1。

2. VC Dimension of Perceptrons

1. 证明得到：对于线性二分类问题，VC维的值为样本维度+1。即
   dvc=d+1

3. Physical Intuition VC Dimension

1. VC维的物理意义：自由度。
2. 举例：比如当样本维度为2时，VC维为3，自由度也为3。
   
   • 考虑1：假设函数是一个直线：y=w1x+w0，其中w1和w0为两个自由度，另外一个自由度是指直线上方的是正还是负。
   • 考虑2：假设函数为：y=sign(w2x2+w1x1+w0)，其中一共需要3个特征。

4. Interpreting VC Dimension

1. Eout和Ein的差距可以反映模型复杂度。
   

2. VC维， Eout和，Ein及模型复杂度Ω的关系：
   

3. 我们的目的是找到最小的Eout，所以不能一味的使分类器复杂化（提升VC维，提升自由度）而减小Ein。我们需要找到合适的Ein。

5. 总结

这次课主要介绍了VC维的定义及其物理意义，我们也知道假设函数并不是越复杂越好的，需要找到合适的。