Definition
Suppose we have a class 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 sets 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.
Read more about this topic: Shattered Set
Famous quotes containing the word definition:
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)
“According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
—Ana Castillo (b. 1953)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)