Dimensión VC


Dimensión VC

Dimensión VC

La dimensión VC (del inglés Vapnik-Chervonenkis dimension) es una medida de la capacidad de los algoritmos de clasificación estadística, definida como la cardinalidad del mayor conjunto de puntos que el algoritmo puede separar. Es un concepto central en la teoría Vapnik-Chervonenkis, y fue originalmente definido por Vladimir Vapnik y Alexey Chervonenkis.

Separación

Un modelo de clasificación f con algún vector de parámetros θ es llamado separador de un conjunto de puntos (x_1,x_2,\ldots,x_n) si, para todas las asignaciones de las etiquetas de esos puntos, existe una θ tal que el modelo f no tiene errores cuando evalúa ese conjunto de puntos.

La dimensión VC del modelo f es el máximo h para el cuál algún punto del conjunto de datos de cardinalidad h puede ser separado por f.

Por ejemplo, considerando una línea recta como modelo de clasificación: el modelo empleado por un perceptrón. La línea debería separar los puntos de clase "+" (positivos) de los de clase "-" (negativos). Cuando hay 3 puntos que no sean colineales, la línea puede separarlos. Sin embargo, la línea no puede separar 4 puntos. Es importante recordar que uno puede elegir una configuración de puntos que pueden ser separables por una recta, pero no podríamos separar todas las permutaciones. Sólo 2 de las 8 permutaciones posibles son mostradas para 3 puntos.

VC1.png VC2.png VC4.png
Separación de 3 puntos Separación imposible con 4 puntos

Uso

La dimensión VC tiene utilidad en teoría de aprendizaje estadístico, porque puede predecir el límite superior probabilístico sobre el error de test del modelo de clasificación.

El límite sobre el error de test del modelo de clasificación (en datos de entrenamiento son independientes y cumplen una distribución aleatoria de la misma distribución) está dado por

Error de entrenamiento + \sqrt{h(\log(2N/h)+1)-\log(\eta/4)\over N}

con probabilidad 1 − η, donde h es la dimensión VC del modelo de clasificación, y N es el tamaño del conjunto de entrenamiento.

Referencias y fuentes

  • Andrew Moore's VC dimension tutorial
  • V. Vapnik and A. Chervonenkis. "On the uniform convergence of relative frequencies of events to their probabilities." Theory of Probability and its Applications, 16(2):264--280, 1971.
  • A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. "Learnability and the Vapnik-Chervonenkis dimension." Journal of the ACM, 36(4):929--865, 1989.
Obtenido de "Dimensi%C3%B3n VC"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • dimension — Dimension …   Thresor de la langue françoyse

  • Dimension — Dimension …   Deutsch Wörterbuch

  • dimension — [ dimɑ̃sjɔ̃ ] n. f. • 1425; lat. dimensio, de metiri « mesurer » I ♦ 1 ♦ Grandeur réelle, mesurable, qui détermine la portion d espace occupée par un corps. ⇒ étendue, grandeur, grosseur. Dimension relative. ⇒ proportion. « Notre âme est jetée… …   Encyclopédie Universelle

  • Dimension — Di*men sion, n. [L. dimensio, fr. dimensus, p. p. of dimetiri to measure out; di = dis + metiri to measure: cf. F. dimension. See {Measure}.] 1. Measure in a single line, as length, breadth, height, thickness, or circumference; extension;… …   The Collaborative International Dictionary of English

  • Dimension — steht für: die in einem Größensystem festgelegte Dimension einer physikalischen Größe, siehe Dimension (Größensystem) die Anzahl der Freiheitsgrade in einem bestimmten mathematischen Raum im Allgemeinen, siehe Dimension (Mathematik) die Anzahl… …   Deutsch Wikipedia

  • Dimension — Dimension, Ausdehnung einer geometrischen Größe in einer bestimmten Richtung. Ein Punkt hat keine Dimension, eine Strecke eine einzige, die Länge. Mehrere Dimensionen hat eine geometrische Größe, wenn sie in mehreren zueinander senkrechten… …   Lexikon der gesamten Technik

  • dimensión — sustantivo femenino 1. Área: física Cada una de las magnitudes de un conjunto que sirve para definir un fenómeno físico: El espacio tiene cuatro dimensiones en la teoría de la relatividad. Nuestras dimensiones espaciales son la altura, la anchura …   Diccionario Salamanca de la Lengua Española

  • Dimension 8 — Studio album by Velvet Acid Christ Released 2000 Recorded 1993 1994 Genre electro industrial …   Wikipedia

  • dimension — UK US /ˌdaɪˈmenʃən/ noun [C] ► a measurement of something in a particular direction, especially its height, length, or width: »The estate agent s brochure specifies the dimensions of each room. »approximate/exact/precise dimensions ► a part or… …   Financial and business terms

  • Dimension — Sf Ausdehnung, Größe erw. fach. (15. Jh.) Entlehnung. Entlehnt aus l. dīmēnsiō, einem Abstraktum zu l. dīmētīrī ausmessen, vermessen , zu l. mētīrī (mēnsus sum) messen und l. dis .    Ebenso nndl. dimensie, ne. dimension, nfrz. dimension, nschw.… …   Etymologisches Wörterbuch der deutschen sprache