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. 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 H {displaystyle H} be a set family (a set of sets) and C {displaystyle C} a set. Their intersection is defined as the following set-family: The intersection-size (also called the index) of H {displaystyle H} with respect to C {displaystyle C} is | H ∩ C | {displaystyle |Hcap C|} . Obviously, if a set C m {displaystyle C_{m}} has m {displaystyle m} elements then the index is at most 2 m {displaystyle 2^{m}} . The growth function measures the size of H ∩ C {displaystyle Hcap C} as a function of | C | {displaystyle |C|} . Formally: Equivalently, let H {displaystyle H} be a hypothesis-class (a set of binary functions) and C {displaystyle C} a set with m {displaystyle m} elements. The restriction of H {displaystyle H} to C {displaystyle C} is the set of binary functions on C {displaystyle C} that can be derived from H {displaystyle H} ::45 The growth function measures the size of H C {displaystyle H_{C}} as a function of | C | {displaystyle |C|} ::49 1. The domain is the real line R {displaystyle mathbb {R} } . The set-family H {displaystyle H} contains all the half-lines (rays) from a given number to positive infinity, i.e., all sets of the form { x > x 0 ∣ x ∈ R } {displaystyle {x>x_{0}mid xin mathbb {R} }} for some x 0 ∈ R {displaystyle x_{0}in mathbb {R} } . For any set C {displaystyle C} of m {displaystyle m} real numbers, the intersection H ∩ C {displaystyle Hcap C} contains m + 1 {displaystyle m+1} sets: the empty set, the set containing the largest element of C {displaystyle C} , the set containing the two largest elements of C {displaystyle C} , and so on. Therefore: Growth ⁡ ( H , m ) = m + 1 {displaystyle operatorname {Growth} (H,m)=m+1} .:Ex.1 The same is true whether H {displaystyle H} contains open half-lines, closed half-lines, or both. 2. The domain is the segment [ 0 , 1 ] {displaystyle } . The set-family H {displaystyle H} contains all the open sets. For any set C {displaystyle C} of m {displaystyle m} real numbers, the intersection H ∩ C {displaystyle Hcap C} contains all possible subsets of C {displaystyle C} . There are 2 m {displaystyle 2^{m}} such subsets, so Growth ⁡ ( H , m ) = 2 m {displaystyle operatorname {Growth} (H,m)=2^{m}} .:Ex.2 3. The domain is the Euclidean space R n {displaystyle mathbb {R} ^{n}} . The set-family H {displaystyle H} contains all the half-spaces of the form: x ⋅ ϕ ≥ 1 {displaystyle xcdot phi geq 1} , where ϕ {displaystyle phi } is a fixed vector.Then Growth ⁡ ( H , m ) = Comp ⁡ ( n , m ) {displaystyle operatorname {Growth} (H,m)=operatorname {Comp} (n,m)} ,where Comp is the number of number of components in a partitioning of an n-dimensional space by m hyperplanes.:Ex.3