Shattered Set

Let  be a set and  a collection of subsets of . A subset  is shattered by  if each subset  of  can be expressed as the intersection of  with a subset  in . Symbolically, then,  is shattered by  if for all , there exists some  for which .

If  is shattered by , one says that  shatters .

There are a number of equivalent ways to define shattering. One can easily verify that the above definition is equivalent to saying that  shatters  if

where  denotes the power set of . Yet another way to express this concept is to say that a set  of cardinality  is shattered by a set  if  where here,

In the field of machine learning theory, one usually considers the set  to be a sample of outcomes drawn according to a distribution  with the set  representing a collection of "known" concepts or laws. In this context, saying that  is shattered by  intuitively means that all of the constituent outcomes in  can be known by knowing only the laws in .

REFERENCES:

Bhaskar, A. and Sukhar, I. "VC-Dimension." 2008. http://www.cs.cornell.edu/courses/cs683/2008sp/lecture%20notes/683notes_0428.pdf.

Shashua, A. "Lecture 11: PAC II." 2009. http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf.