Complejidad de la muestra
La complejidad de la muestra de un algoritmo de aprendizaje automático representa la cantidad de muestras de entrenamiento que necesita para aprender con éxito una función objetivo.
Más precisamente, la complejidad de la muestra es el número de muestras de entrenamiento que necesitamos suministrar al algoritmo, de modo que la función devuelta por el algoritmo esté dentro de un error arbitrariamente pequeño de la mejor función posible, con probabilidad arbitrariamente cercana a 1.
El teorema de no almuerzo gratis , que se analiza a continuación, demuestra que, en general, la gran complejidad de la muestra es infinita, es decir, que no existe un algoritmo que pueda aprender la función objetivo globalmente óptima utilizando un número finito de muestras de entrenamiento.
Sin embargo, si solo estamos interesados en una clase particular de funciones objetivo (por ejemplo, solo funciones lineales), entonces la complejidad de la muestra es finita y depende linealmente de la dimensión VC de la clase de funciones objetivo. [1]
Sea un espacio que llamamos espacio de entrada, y sea un espacio que llamamos espacio de salida, y denotemos el producto . Por ejemplo, en el marco de la clasificación binaria, es típicamente un espacio vectorial de dimensión finita y es el conjunto .
Fijar un espacio de hipótesis de funciones . Un algoritmo de aprendizaje es un mapa computable de a . En otras palabras, es un algoritmo que toma como entrada una secuencia finita de muestras de entrenamiento y genera una función de a . Los algoritmos de aprendizaje típicos incluyen la minimización de riesgos empíricos , sin o con regularización de Tikhonov .
