connecting the dots). Shatter coefficient To quantify the richness of a collection C of sets, we use the concept of shattering coefficients (also known as the growth function). For a collection C of sets , being any space, often a sample space, we define the nth shattering coefficient of C as where denotes the cardinality of the set and is any set of n points,. is the largest number of subsets of any set A of n points that can be formed by intersecting A with the sets in collection C. Here are some facts about : for all n because for any . If , that means there is a set of cardinality n, which can be shattered by C. If for some then for all . The third property means that if C cannot shatter any set of cardinality N then it can not shatter sets of larger cardinalities. Vapnik–Chervonenkis class The VC dimension of a class C is defined as or, alternatively, as Note that If for any n there is a set of cardinality n which can be shattered by C, then for all n and the VC dimension of this class C is infinite. A class with finite VC dimension is called a Vapnik–Chervonenkis class or VC class. A class C'' is uniformly Glivenko–Cantelli if and only if it is a VC class. See also Sauer–Shelah lemma, relating the cardinality of a family of sets to the size of its largest shattered set References . . External links Origin of "Shattered sets" terminology, by J. Steele Empirical process Computational learning theory