ML基石_56_TheoryOfGeneralization

• RECAP
• SOLUTION
  • m增长速度受限
  • 将m带回原式中的M
• 例子
• 总结

RECAP

机器学习是可行的，如果假设集H是有限的并且统计样本数据(statistical data)很大。

那么，问题来了，PLA算法中，假设集是二维空间中的直线，有无数条，不符合上面的条件，那么还可行么？

这里写图片描述

SOLUTION

m增长速度受限

将类似的假设集合并，如果是二分类问题，有N个点的话，理论上会有2^N个分类情况mHm_H，但实际上并不会这么多。

mHm_H: max number of dichotomies B(N,K)B(N,K):如果break point在第k个点上，N个数据点最大的dichotomies ∑k−1i=0C(N,k) \sum_{i=0}^{k-1} C(N,k):B(N,K)B(N,K)的上限，增长速度是O(Nk−1)O(N^{k-1})

mH<=B(N,K)<=∑i=0k−1C(N,k)<=2N

m_H<=B(N,K)<= \sum_{i=0}^{k-1} C(N,k) <=2^N

通过上面的公式，我们知道： 如果可以将mHm_H代替原不等式的M，那么多项式函数的增长速度小于指数函数的增长速度，所以误差率的上限是有保证的，也就是说学习是可行的。

注意： 对于converx图，mH=2Nm_H=2^N，这种情况很难比较。

将m带回原式中的M

通过一些数学变换，可以将m带回原式中的M，得到

这里写图片描述

这表明，随着数据集的增多，如果mHm_H的增长速度受限，或者说其有break point点，那么当N足够大的时候，学习是可行的。

这就是VC维理论。

例子

这里写图片描述

总结

这里写图片描述