机器学习是可行的,如果假设集H是有限的并且统计样本数据(statistical data)很大。
那么,问题来了,PLA算法中,假设集是二维空间中的直线,有无数条,不符合上面的条件,那么还可行么?
将类似的假设集合并,如果是二分类问题,有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,得到
这表明,随着数据集的增多,如果mHm_H的增长速度受限,或者说其有break point
点,那么当N足够大的时候,学习是可行的。
这就是VC维理论。