¿Cuál es el papel de la dimensión VC y la complejidad de Rademacher en la generalización?

Answer 1

¿Cuál es el papel de la dimensión VC y la complejidad de Rademacher en la generalización?

Entonces, primero, generalización significa el proceso en el que escoges una hipótesis ([matemáticas] f_i: X \ rightarrow Y [/ matemáticas]) de una clase de hipótesis [matemáticas] H = \ {f_1, f_2,… \} [/ matemática] basada en los datos de entrenamiento [matemática] \ {(x_1 ^ {train}, y_1 ^ {train}), (x_2 ^ {train}, y_2 ^ {train}),…, (x_m ^ {train}, y_m ^ {train}) \} [/ math] usando algún algoritmo, y realiza la predicción con esta hipótesis [math] f_i [/ ​​math] en algunos datos no vistos, o datos de prueba [math] \ {(x_1 ^ {test}, y_1 ^ {prueba}), (x_2 ^ {prueba}, y_2 ^ {prueba}),… \} [/ matemática], que se extrae de la misma distribución, pero desconocida ([matemática] D [/ matemática]) como Los datos de entrenamiento.

En general, una cosa que le importa a la gente es cuántos “errores” comete este proceso, también conocido como error de generación o riesgo verdadero. Denotemos esta cantidad como [math] error_ {generalization} [/ math]. En realidad, sin embargo, uno solo tiene los datos de entrenamiento, por lo tanto solo puede obtener los “errores” que la hipótesis [matemática] f_i [/ ​​math] hace sobre los datos de entrenamiento, también conocido como error de entrenamiento o riesgo empírico, denotado como [math] error_ {train} [/ math].

Ahora, volviendo a la pregunta original. Tanto la dimensión VC ([matemática] d [/ matemática]) como la complejidad de Rademacher ([matemática] R [/ matemática]) son algunas medidas de la complejidad de una clase de hipótesis [matemática] H = \ {f_1, f_2, … \ }[/matemáticas]. Y normalmente se puede mostrar que el error de generalización [math] error_ {generalization} [/ math] tiene el siguiente límite superior:

[math] error_ {generalization} \ leq error_ {train} + g (d (or ~ R), m) \ tag * {} [/ math]

donde [math] g (.) [/ math] es una función que se acerca a [math] 0 [/ math] a medida que el tamaño de los datos de entrenamiento [math] m [/ math] se aproxima al infinito. Este es el papel de la dimensión VC y la complejidad de Rademacher en la generalización, es decir, conectar el concepto de error de generalización ([math] error_ {generalization} [/ math]) con el tamaño de los datos de entrenamiento ([math] m [/ math ]) y con alguna medida de complejidad de la clase de hipótesis ([math] d [/ math], o [math] R [/ math] u otras medidas de complejidad). Esto es particularmente útil si la dimensión de la clase de hipótesis [matemática] | H | [/ matemática] es infinita, de lo contrario, la complejidad puede medirse directamente por [matemática] | H | [/ matemática] sin introducir la dimensión VC o la complejidad de Rademacher .

Comparando las dos medidas de complejidad, la complejidad de Rademacher tiene un límite más estricto que la dimensión VC en el error de generalización, y puede aplicarse no solo a la clasificación como a la dimensión VC, sino también a la regresión. Pero la complejidad de Rademacher depende de la distribución de datos, mientras que la dimensión VC es independiente de la distribución. Ambos podrían ser difíciles de calcular.