AnalysisProbabilityTheoryMachineLearningStatistics
Given a class of binary functions the VC-dimension of is a distribution independent measure of the complexity of in terms of the largest subset of points that can be shattered by : Computing VC-dimension can be shown by providing:
Lower bounds: i.e. there exists a set of points that can be shattered
Upper bounds: i.e. no set of points can be shattered
Using Sauer’s Lemma one has the following generalization bound for hypothesis classes with finite VC-dimension the ratio can be viewed as an instance of Occam’s razor, where the simplicity is measure in terms of small VC-dimension, relative to the amount of available data.