Shattering
Encyclopedia
The concept of shattering of a set of points plays an important role in Vapnik–Chervonenkis theory, also known as VC-theory. Shattering and VC-theory are used in the study of empirical process
es as well as in statistical computational learning theory
.
C of sets and a given set A. C is said to shatter A if, for each subset T of A, there is some element U of C such that
Equivalently, C shatters A when the power set P(A) is the set { U ∩ A | U ∈ C }.
For example, the class C of all discs in the plane (two-dimensional space) cannot shatter every set A of four points, yet the class of all convex set
s in the plane shatters every finite set on the (unit) circle. (For the collection of all convex sets, connect the dots!)
We employ the letter C to refer to a "class" or "collection" of sets, as in a Vapnik–Chervonenkis class (VC-class). The set A is often assumed to be finite because, in empirical processes, we are interested in the shattering of finite sets of data points.
To test this, we attempt to draw a disc around every subset of points in A. First, we draw a disc around the subsets of each isolated point, which turns out to be easy. Next, we try to draw a disc around every subset of point pairs. This turns out to be easy for adjacent points, but impossible for points on opposite sides of the circle. As visualized below:
Because there is some subset which can not be isolated by any disc in C, we conclude then that A is not shattered by C. And, with a bit of thought, we can prove that NO set of 4 points is shattered by this C.
However, if we redefine C to be the class of all elliptical discs, we find that we can still isolate all the subsets from above, as well as the points which were problems. Thus, this specific set of 4 points is shattered by the class of ellipitical discs. Visualized below:
With a bit of thought, we could generalize that any set of finite points on a unit circle could be shattered by the class of all convex set
s (visualize connecting the dots).
, 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
:
The third property means that if C cannot shatter any set of cardinality N then it can not shatter sets of larger cardinalities.
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.
Empirical process
The study of empirical processes is a branch of mathematical statistics and a sub-area of probability theory. It is a generalization of the central limit theorem for empirical measures...
es as well as in statistical computational learning theory
Computational learning theory
In theoretical computer science, computational learning theory is a mathematical field related to the analysis of machine learning algorithms.-Overview:Theoretical results in machine learning mainly deal with a type of...
.
Definition
Suppose we have a classClass (set theory)
In set theory and its applications throughout mathematics, a class is a collection of sets which can be unambiguously defined by a property that all its members share. The precise definition of "class" depends on foundational context...
C of sets and a given set A. C is said to shatter A if, for each subset T of A, there is some element U of C such that
Equivalently, C shatters A when the power set P(A) is the set { U ∩ A | U ∈ C }.
For example, the class C of all discs in the plane (two-dimensional space) cannot shatter every set A of four points, yet the class of all convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
s in the plane shatters every finite set on the (unit) circle. (For the collection of all convex sets, connect the dots!)
We employ the letter C to refer to a "class" or "collection" of sets, as in a Vapnik–Chervonenkis class (VC-class). The set A is often assumed to be finite because, in empirical processes, we are interested in the shattering of finite sets of data points.
Example
Suppose we have a set A of 4 points on the unit circle, and we wish to know if it is shattered by the class C of all discs.To test this, we attempt to draw a disc around every subset of points in A. First, we draw a disc around the subsets of each isolated point, which turns out to be easy. Next, we try to draw a disc around every subset of point pairs. This turns out to be easy for adjacent points, but impossible for points on opposite sides of the circle. As visualized below:
Because there is some subset which can not be isolated by any disc in C, we conclude then that A is not shattered by C. And, with a bit of thought, we can prove that NO set of 4 points is shattered by this C.
However, if we redefine C to be the class of all elliptical discs, we find that we can still isolate all the subsets from above, as well as the points which were problems. Thus, this specific set of 4 points is shattered by the class of ellipitical discs. Visualized below:
With a bit of thought, we could generalize that any set of finite points on a unit circle could be shattered by the class of all convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
s (visualize 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 shatter coefficients or the growth function). For a collection C of sets s⊂Ω, Ω being any space, often a probability spaceProbability space
In probability theory, a probability space or a probability triple is a mathematical construct that models a real-world process consisting of states that occur randomly. A probability space is constructed with a specific kind of situation or experiment in mind...
, 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.
Vapnik–Chervonenkis class
The VC dimensionVC dimension
In statistical learning theory, or sometimes computational learning theory, the VC dimension is a measure of the capacity of a statistical classification algorithm, defined as the cardinality of the largest set of points that the algorithm can shatter...
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.