Growth function

The growth function, also called the shatter coefficient or the shattering number, measures the richness of a set family. It is especially used in the context of statistical learning theory, where it measures the complexity of a hypothesis class. The term 'growth function' was coined by Vapnik and Chervonenkis in their 1968 paper, where they also proved many of its properties. It is a basic concept in machine learning. Let be a set family (a set of sets) and a set. Their intersection is defined as the following set-family: The intersection-size (also called the index) of with respect to is . If a set has elements then the index is at most . If the index is exactly 2m then the set is said to be shattered by , because contains all the subsets of , i.e.: The growth function measures the size of as a function of . Formally: Equivalently, let be a hypothesis-class (a set of binary functions) and a set with elements. The restriction of to is the set of binary functions on that can be derived from : The growth function measures the size of as a function of :

1. The domain is the real line . The set-family contains all the half-lines (rays) from a given number to positive infinity, i.e., all sets of the form for some . For any set of real numbers, the intersection contains sets: the empty set, the set containing the largest element of , the set containing the two largest elements of , and so on. Therefore: . The same is true whether contains open half-lines, closed half-lines, or both.
2. The domain is the segment . The set-family contains all the open sets. For any finite set of real numbers, the intersection contains all possible subsets of . There are such subsets, so .
3. The domain is the Euclidean space . The set-family contains all the half-spaces of the form: , where is a fixed vector. Then , where Comp is the number of components in a partitioning of an n-dimensional space by m hyperplanes.
4. The domain is the real line . The set-family contains all the real intervals, i.e., all sets of the form for some .