Shattered Set - Shatter Coefficient

Shatter Coefficient

To quantify the richness of a collection C of sets, we use the concept of shattering coefficients (also known as shatter coefficients or the growth function). For a collection C of sets s⊂Ω, Ω being any space, often a probability space, we define the nth shattering coefficient of C as

where denotes the cardinality of the set.

is equal to 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 :

1. for all n because for any .

2. If, that means there is a set of cardinality n, which can be shattered by C.

3. 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.