Understanding the Vapnik-Chervonenkis (VC) dimension.
Post date: Oct 12, 2014 7:31:18 PM
The Vapnik-Chervonenkis (VC) dimension is the fundamental concept when studying binary classifiers from a statistical learning theory perspective. Intuitive understanding of the subject, given in what follows, is therefore critical for any machine learning practitioners.
Binary classifiers are special in the sense that they always have one-to-one mappings to sets. For example, an element can either be inside or outside a set, in the same way that it can be labeled either a 1 or a 0 by a binary classifier. Therefore, it suffices to discuss VC dimension in the context of sets, using set notions like the power set and set intersections.
An arbitrary finite set
with cardinality , i.e. , the cardinality of its power set is . The set is said to be shattered by the given class (of sets)Â if all the intersections between
and elements of is . The VC dimension of , denoted , is defined as follows
This definition is motivated by a critical observation that for large enough
, the structure of the class will manifest by not being able to intersect each of its elements with an arbitrary to form
. Instead of defining VC dimension in terms of an arbitrary set , an alternative definition of VC can be given in terms of the n-th shatter coefficients of , defined as follows.
and
Intuitively, VC dimension says that for small
, . However, for large enough , , and is the VC dimension of . In fact, the Sauer-Shelah lemma makes this precise.
where and is called a VC class. Thus