VC Dimension

In statistical learning theory, or sometimes computational learning theory, the VC dimension (for Vapnik–Chervonenkis 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. It is a core concept in Vapnik–Chervonenkis theory, and was originally defined by Vladimir Vapnik and Alexey Chervonenkis.

Informally, the capacity of a classification model is related to how complicated it can be. For example, consider the thresholding of a high-degree polynomial: if the polynomial evaluates above zero, that point is classified as positive, otherwise as negative. A high-degree polynomial can be wiggly, so it can fit a given set of training points well. But one can expect that the classifier will make errors on other points, because it is too wiggly. Such a polynomial has a high capacity. A much simpler alternative is to threshold a linear function. This function may not fit the training set well, because it has a low capacity. We make this notion of capacity more rigorous below.

Read more about VC DimensionShattering, Uses

Other articles related to "vc dimension, vc":

Shattered Set - Vapnik–Chervonenkis Class
... The VC dimension 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 ... 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 ...
VC Dimension - Uses
... The VC dimension has utility in statistical learning theory, because it can predict a probabilistic upper bound on the test error of a classification model ... as the training set) is given by with probability, where is the VC dimension of the classification model, and is the size of the training set (restriction this formula is valid when ) ... but Rademacher complexity can sometimes provide more insight than VC dimension calculations into such statistical methods such as those using kernels ...

Famous quotes containing the word dimension:

    By intervening in the Vietnamese struggle the United States was attempting to fit its global strategies into a world of hillocks and hamlets, to reduce its majestic concerns for the containment of communism and the security of the Free World to a dimension where governments rose and fell as a result of arguments between two colonels’ wives.
    Frances Fitzgerald (b. 1940)