Shattering

Shattering

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 processes as well as in statistical computational learning theory.

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

: U cap A = T.,

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.

hatter 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 subset Ω, Ω being any space, often a probability space, we definethe "n"th "shattering coefficient" of C as

: S _C(n) = max_{x_1,x_2,dots,x_n in Omega } operatorname{card} {,{,x_1,x_2,dots,x_n}cap s, sin C }

where "card" denotes the cardinality, that is the number of elements of a set.

S _C(n) 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 .

It is obvious that :1.S_C(n)leq 2^n for all "n". :2. If S_C(n)=2^n, that means there is a set of cardinality "n", which can be shattered by "C". :3. If S_C(N)<2^N for some N>1 then S_C(n)<2^n for all ngeq N The third property means that if "C" cannot shatter any set of cardinality "N" then it cannot shatter sets of larger cardinalities.

Vapnik-Chervonenkis class

The VC dimension of a class "C" is defined as:VC(C)=underset{n}{min}{n:S_C(n)<2^n},or, alternatively, as:VC_0(C)=underset{n}{max}{n:S_C(n)=2^n}.,

Note that VC(C)=VC_0(C)+1.

If for any "n" there is a set of cardinality "n" which can be shattered by "C", then S_C(n)=2^n 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.

References

*Wencour, R.S., R.M. Dudley (1981), "Some special Vapnik-Chervonenkis classes", Discrete Math, 33, 1981, 313-318.

*Steele, J.M. (1975), "Combinatorial Entropy and Uniform Limit Laws", Stanford University Ph.d Thesis (Mathematics)

*Steele, J.M. (1978), "Empirical discrepancies and subadditive processes", Annals of Probability, 6, 118--227.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • shattering — [[t]ʃæ̱tərɪŋ[/t]] 1) ADJ GRADED Something that is shattering shocks and upsets you very much. The experience of their daughter s death had been absolutely shattering... Yesterday s decision was another shattering blow. Syn: devastating 2) → See… …   English dictionary

  • shattering — I noun the act of breaking something into small pieces • Syn: ↑smashing • Derivationally related forms: ↑shatter, ↑smash (for: ↑smashing) • Hyperny …   Useful english dictionary

  • shattering — shat|ter|ing [ˈʃætərıŋ] adj 1.) very shocking and upsetting ▪ His mother s death was a shattering blow. 2.) BrE informal making you very tired = ↑exhausting ▪ I ve had a shattering day …   Dictionary of contemporary English

  • Shattering — Shatter Shat ter, v. t. [imp. & p. p. {Shattered}; p. pr. & vb. n. {Shattering}.] [OE. schateren, scateren, to scatter, to dash, AS. scateran; cf. D. schateren to crack, to make a great noise, OD. schetteren to scatter, to burst, to crack. Cf.… …   The Collaborative International Dictionary of English

  • shattering — shat|ter|ing [ ʃæt(ə)rıŋ ] adjective 1. ) extremely upsetting: a shattering blow 2. ) MAINLY BRITISH INFORMAL making you feel extremely tired …   Usage of the words and phrases in modern English

  • shattering — adjective 1 very shocking and upsetting: shattering news from home 2 BrE informal making you very tired …   Longman dictionary of contemporary English

  • shattering — UK [ˈʃæt(ə)rɪŋ] / US adjective extremely upsetting a shattering blow …   English dictionary

  • shattering — shat·ter·ing || ʃætÉ™rɪŋ n. breaking into pieces, smashing; destroying, devastating shat·ter || ʃætÉ™(r) v. break to pieces, splinter, smash; be broken into pieces; damage, harm; ruin, destroy …   English contemporary dictionary

  • shattering —  Very upsetting or striking …   A concise dictionary of English slang

  • shattering conventions — doing things in opposition to what is generally accepted, rebelling against accepted values …   English contemporary dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”