Growth Function

AnalysisProbabilityTheoryMachineLearning Given a class of binary functions the Growth function or shattering dimension of is a distribution independent measure of the complexity of in terms of how many ways it could classify points in , i.e. the maximum number of dichotomies generated by : The growth function is clearly bounded by the total number of binary strings of length and we say that a data set is shattered by if the growth function achieves this maximum, so that all dichotomies can be achieved under .

The growth function bounds the Rademacher Complexity, leading to the following generalization bounds:

1. Confidence:
2. Accuracy: Unfortunately, as the growth function is exponential in the number of points in the worst case this bound could be vacuous, so we would like a criteria under which we can guarantee the growth function is bounded by a polynomial. This is given by Sauer’s Lemma, relating the growth function and the VC Dimension: