The analysis of infinite sets of classifiers is very important for machine learning. Infinite sets of classifiers are not just some abstract objects with interest from a theoretical viewpoint, they are indeed very common. Consider the most basic set of classifiers, i.e., the set of linear classifiers. These classifiers are parametrized by real numbers and there is an infinite number of combinations for these numbers.
As seen in the derivation of the first useful error bound, the bound involves the size of the considered set of classifiers for which we want the bound to hold. For sets of infinite size, this approach becomes useless (as the error will be bounded by the infinite) and we have to use a more precise measure of the capacity of the set of classifiers. Informally, we will try to measure the number of classifiers in the set that are truly different with respect to the classification task, thus (hopefully) reducing an infinite number to a finite one.
The first measure of capacity we will consider is the growth function. Using this capacity measure, we will be able to derive an error bound for infinite sets of classifiers. Then, we will reformulate this bound in terms of another capacity measure known as the VC-dimension.
We are now interested in infinite function classes $\F$ (function classes with infinite cardinality). The most simple of such function classes is the set of all linear classifiers in $\R^d$: $$ \F = \{ f \ : \ f(\g x ) = \sign( \g w^T \g x + b),\ \g w\in\R^d,\ b\in\R \} $$ which is parametrized by a vector $\g w$ and a real number $b$ that can take an infinite number of values.
For such function classes, we cannot apply the previous error bound, since it grows with $\log |\F|$, where $|\F|$ is the cardinality of $\F$. Instead, we will consider capacity measures that will count the number of different possible outcomes produced on a data set by any function of $\F$, such as the growth function and the VC-dimension.