TOPICS
Search

Shattered Set


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

If A is shattered by S, one says that S shatters A.

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

 P(A)={T intersection A:T in S}

where P(A) denotes the power set of A. Yet another way to express this concept is to say that a set A of cardinality m is shattered by a set S if |Pi_S(A)|=2^m where here,

 Pi_S(A)={s intersection A:s in S}.

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


See also

Concept, Distribution Function, Intersection, Outcome, Power Set, Sample, Subset

This entry contributed by Christopher Stover

Explore with Wolfram|Alpha

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.

Cite this as:

Stover, Christopher. "Shattered Set." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/ShatteredSet.html

Subject classifications