Vapnik-Chervonenkis Dimension

In machine learning theory, the Vapnik-Chervonenkis dimension or VC-dimension of a concept class  is the cardinality of the largest set  which can be shattered by . If arbitrarily large sets can be shattered by , then the VC-dimension is said to be . Given a concept class , the VC-dimension of  is sometimes denoted .

There are several models used to visualize the process of shattering, and hence there are a number of different models of the Vapnik-Chervonenkis dimension. In particular, it is common to use intervals (and unions thereof) on the real line, rectangles and squares in the plane, hyperplanes, etc.

There are also several results quantifying the VC-dimension to various degrees. For example, one can show that the VC-dimension of a finite concept class  satisfies

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.