¿Por qué es importante la dimensión VC?

Wikipedia dice que:

La dimensión VC es la cardinalidad del mayor conjunto de puntos que un algoritmo puede destruir.

Por ejemplo, un clasificador lineal tiene una cardinalidad n + 1. Mi pregunta es ¿por qué nos importa? La mayoría de los conjuntos de datos en los que realiza una clasificación lineal tienden a ser muy grandes y contienen muchos puntos.

¿Cuál es la dimensión VC?

Como mencionó @CPerkins, la dimensión VC es una medida de la complejidad de un modelo. También se puede definir con respecto a la capacidad de destruir puntos de datos como, como mencionó, wikipedia lo hace.

El problema basico

• Queremos un modelo (por ejemplo, algún clasificador) que se generalice bien en datos no vistos .
• Estamos limitados a una cantidad específica de datos de muestra.

La siguiente imagen (tomada de aquí ) muestra algunos Modelos ( hasta ) de diferente complejidad (dimensión VC), mostrados aquí en el eje x y llamados .S k$\mathcal{S_1}$$\mathcal{S_k}$$h$

Las imágenes muestran que una dimensión de VC más alta permite un menor riesgo empírico (el error que un modelo comete en los datos de la muestra), pero también introduce un intervalo de confianza más alto. Este intervalo puede verse como la confianza en la capacidad del modelo para generalizar.

Dimensión de VC baja (alto sesgo)

Si usamos un modelo de baja complejidad, introducimos algún tipo de suposición (sesgo) con respecto al conjunto de datos, por ejemplo, cuando usamos un clasificador lineal asumimos que los datos pueden describirse con un modelo lineal. Si este no es el caso, nuestro problema dado no puede resolverse mediante un modelo lineal, por ejemplo, porque el problema es de naturaleza no lineal. Terminaremos con un modelo de mal desempeño que no podrá aprender la estructura de los datos. Por lo tanto, debemos tratar de evitar introducir un sesgo fuerte.

Dimensión de VC alta (mayor intervalo de confianza)

En el otro lado del eje x, vemos modelos de mayor complejidad que podrían tener una capacidad tan grande que más bien memorizarán los datos en lugar de aprender su estructura subyacente general, es decir, los sobreajustes del modelo. Después de darnos cuenta de este problema, parece que debemos evitar los modelos complejos.

Esto puede parecer controvertido ya que no introduciremos un sesgo, es decir, que tenga una dimensión de VC baja, pero tampoco debería tener una dimensión de VC alta. Este problema tiene raíces profundas en la teoría del aprendizaje estadístico y se conoce como el sesgo-varianza-compensación . Lo que deberíamos hacer en esta situación es ser lo más complejo posible y lo más simplista posible, por lo tanto, al comparar dos modelos que terminen con el mismo error empírico, deberíamos usar el menos complejo.

Espero poder mostrarles que hay más detrás de la idea de la dimensión VC.

La dimensión VC es el número de bits de información (muestras) que uno necesita para encontrar un objeto específico (función) entre un conjunto de objetos (funciones)$N$ .

$VC$ dimensión proviene de un concepto similar en la teoría de la información. La teoría de la información comenzó a partir de la observación de Shannon de lo siguiente:

Si tiene objetos y entre estos objetos, está buscando uno específico. ¿Cuántos bits de información necesitas para encontrar este objeto ? Puede dividir su conjunto de objetos en dos partes y preguntar "¿En qué mitad se encuentra el objeto que estoy buscando?" . Recibe "sí" si está en la primera mitad o "no", si está en la segunda mitad. En otras palabras, recibe 1 bit de información . Después de eso, haces la misma pregunta y divides tu conjunto una y otra vez, hasta que finalmente encuentras el objeto deseado. ¿Cuántos bits de información necesita ( respuestas sí / no )? Es claramente$N$$N$l o g 2 ( N )$log_2(N)$bits de información: de manera similar al problema de búsqueda binaria con la matriz ordenada

$N$$x$$N$$D=\{(x_1,y_1), (x_2, y_2), ..., (x_l, y_l)\}$$x_i$$x_i$$N$$x_i$$\epsilon$$\epsilon$$1-\delta$$(\epsilon, \delta)$$\frac{log_2N/\delta}{\epsilon}$

$N$$\epsilon$$1-\delta$$\frac{log_2N/\delta}{\epsilon^2}$

$log_2N$

$\epsilon$$1-\delta$$\epsilon$

^{___________________ Ambas líneas (función) clasificarán los puntos con el mismo éxito___________________}

$VC$$log_2N$$VC$$\frac{VC -log(\delta)}{\epsilon}$$\frac{VC - log(\delta)}{\epsilon^2}$

$VC$$\epsilon$$1-\delta$

La dimensión VC es una medida de la complejidad del modelo. Por ejemplo, dada la dimensión VC Dvc, una buena regla general es que debe tener n = 10xDvc puntos de datos dada la complejidad de su modelo.

También puede usarlo para crear un límite superior en el error de prueba.