En el folclore matemático , el teorema de " ningún almuerzo gratis " ( NFL ) (a veces pluralizado) de David Wolpert y William Macready aparece en 1997 "No hay teoremas de almuerzo gratis para la optimización". [1] Wolpert no había derivado previamente teoremas del almuerzo gratis para el aprendizaje automático (inferencia estadística). [2]
En 2005, los mismos Wolpert y Macready indicaron que el primer teorema de su artículo "establece que dos algoritmos de optimización cualesquiera son equivalentes cuando su rendimiento se promedia en todos los problemas posibles". [3]
El teorema de "no almuerzo gratis" (NFL) es una consecuencia fácil de expresar y comprender de los teoremas que Wolpert y Macready realmente prueban. Es más débil que los teoremas probados y, por lo tanto, no los encapsula. Varios investigadores han ampliado sustancialmente el trabajo de Wolpert y Macready. Consulte No hay almuerzo gratis en la búsqueda y optimización para el tratamiento del área de investigación.
Mientras que algunos académicos argumentan que la NFL transmite información importante, otros argumentan que la NFL tiene poca relevancia para la investigación del aprendizaje automático. [4] [5]
Ejemplo
Suponga un universo de juguete que existe exactamente durante dos días y que cada día contiene exactamente un objeto, un cuadrado o un triángulo. El universo tiene exactamente cuatro historias posibles:
- (cuadrado, triángulo): el universo contiene un cuadrado el día 1 y un triángulo el día 2
- (cuadrado, cuadrado)
- (triángulo, triángulo)
- (Triángulo rectángulo)
Cualquier estrategia de predicción que tenga éxito para el historial n. ° 2, al predecir un cuadrado el día 2 si hay un cuadrado el día 1, fallará en el historial n. ° 1 y viceversa. Si todas las historias son igualmente probables, entonces cualquier estrategia de predicción puntuará igual, con la misma tasa de precisión de 0,5. [6]
Origen
Wolpert y Macready dan dos teoremas de la NFL que están estrechamente relacionados con el teorema folclórico. En su artículo, afirman:
Hemos denominado los resultados asociados teoremas de la NFL porque demuestran que si un algoritmo funciona bien en una determinada clase de problemas, entonces necesariamente paga por ello con un rendimiento degradado en el conjunto de todos los problemas restantes. [1]
El primer teorema plantea la hipótesis de funciones objetivas que no cambian mientras la optimización está en curso, y el segundo plantea la hipótesis de funciones objetivas que pueden cambiar. [1]
dónde denota el conjunto ordenado de tamaño de los valores de costo asociado a los valores de entrada , es la función que se está optimizando y es la probabilidad condicional de obtener una secuencia dada de valores de costo a partir del algoritmo correr tiempos en función .
El teorema se puede formular de manera equivalente de la siguiente manera:
Aquí, la búsqueda ciega significa que en cada paso del algoritmo, el elemento se elige al azar con una distribución de probabilidad uniforme de los elementos de que no han sido elegidos previamente.
En esencia, esto dice que cuando todas las funciones f son igualmente probables, la probabilidad de observar una secuencia arbitraria de m valores en el curso de la optimización no depende del algoritmo. En el marco analítico de Wolpert y Macready, el rendimiento es una función de la secuencia de valores observados (y no, por ejemplo, del tiempo del reloj de pared), por lo que se deduce fácilmente que todos los algoritmos tienen un rendimiento distribuido de manera idéntica cuando las funciones objetivas se dibujan uniformemente al azar. y también que todos los algoritmos tienen un rendimiento medio idéntico. Pero el rendimiento medio idéntico de todos los algoritmos no implica el teorema 1 y, por lo tanto, el teorema folclórico no es equivalente al teorema original.
El teorema 2 establece un resultado NFL similar, pero "más sutil", para funciones objetivas que varían en el tiempo. [1]
Motivación
Los teoremas de la NFL no estaban explícitamente motivados por la cuestión de qué se puede inferir (en el caso de la NFL para el aprendizaje automático) o encontrar (en el caso de la NFL para la búsqueda) cuando el "entorno es uniformemente aleatorio". Se utilizó una aleatoriedad bastante uniforme como herramienta para comparar el número de entornos en los que el algoritmo A supera al algoritmo B con el número de entornos en los que B supera a A. La NFL nos dice que (ponderado adecuadamente) [ aclaración necesaria ] hay tantos entornos en ambos conjuntos.
Esto es cierto para muchas definiciones de lo que es precisamente un "entorno". En particular, hay tantas distribuciones previas (ponderadas apropiadamente) en las que el algoritmo de aprendizaje A vence a B (en promedio) como viceversa. [ cita requerida ] Esta afirmación sobre conjuntos de previos es lo más importante de NFL, no el hecho de que dos algoritmos cualesquiera funcionen por igual para la distribución previa única y específica que asigna la misma probabilidad a todos los entornos.
Si bien la NFL es importante para comprender la limitación fundamental de un conjunto de problemas, no indica nada sobre cada caso particular de un problema que puede surgir en la práctica. Es decir, la NFL establece lo que está contenido en sus declaraciones matemáticas y no es más que eso. Por ejemplo, se aplica a las situaciones en las que el algoritmo se fija a priori y se elige a posteriori un problema del peor de los casos para el algoritmo fijo. Por lo tanto, si tenemos un problema "bueno" en la práctica o si podemos elegir un algoritmo de aprendizaje "bueno" para una instancia de problema en particular, entonces la NFL no menciona ninguna limitación sobre esta instancia de problema en particular. Aunque la NFL puede parecer contradictoria con los resultados de otros artículos que sugieren la generalización de algoritmos de aprendizaje o heurísticas de búsqueda, es importante comprender la diferencia entre la lógica matemática exacta de la NFL y su interpretación intuitiva. [7]
Trascendencia
Para ilustrar una de las implicaciones contraintuitivas de NFL, suponga que arreglamos dos algoritmos de aprendizaje supervisado, C y D. Luego, muestreamos una función objetivo f para producir un conjunto de pares de entrada-salida, d . ¿Cómo deberíamos elegir entre entrenar C o D en d , para hacer predicciones de qué salida estaría asociada con un punto que se encuentra fuera de d?
Es común en casi toda la ciencia y la estadística responder a esta pregunta, elegir entre C y D, ejecutando una validación cruzada en d con esos dos algoritmos. En otras palabras, para decidir si generalizar desde d con C o D , vemos cuál de ellos tiene un mejor desempeño fuera de la muestra cuando se prueba dentro de d .
Dado que C y D son fijos, este uso de la validación cruzada para elegir entre ellos es en sí mismo un algoritmo, es decir, una forma de generalizar a partir de un conjunto de datos arbitrario. Llame a este algoritmo A. (Podría decirse que A es un modelo simplificado del método científico en sí).
También podríamos usar la validación anti -cruzada para hacer nuestra elección. En otras palabras, podríamos elegir entre C y D en función de cuál tiene peor desempeño fuera de la muestra dentro de d . Nuevamente, dado que C y D son fijos, este uso de validación anti-cruzada es en sí mismo un algoritmo. Llame a ese algoritmo B.
La NFL nos dice (en términos generales) que B debe vencer a A en tantas funciones objetivo (y conjuntos de datos asociados d ) como A vence a B. En este sentido muy específico, el método científico perderá frente al método "anti" científico con la misma facilidad como gana. [8]
NFL solo se aplica si la función objetivo se elige de una distribución uniforme de todas las funciones posibles. Si este no es el caso, y es más probable que se elijan determinadas funciones objetivo que otras, entonces A puede funcionar mejor que B en general. La contribución de NFL es que nos dice que elegir un algoritmo apropiado requiere hacer suposiciones sobre los tipos de funciones objetivo para las que se usa el algoritmo. Sin suposiciones, ningún "meta-algoritmo", como el método científico, funciona mejor que la elección aleatoria.
Mientras que algunos académicos argumentan que la NFL transmite información importante, otros argumentan que la NFL tiene poca relevancia para la investigación del aprendizaje automático. [4] [5] Si la navaja de Occam es correcta, por ejemplo, si las secuencias de menor complejidad de Kolmogorov son más probables que las secuencias de mayor complejidad, entonces (como se observa en la vida real) algunos algoritmos, como la validación cruzada, funcionan mejor en promedio en problemas prácticos (en comparación con la elección aleatoria o con la validación cruzada). [9]
Ver también
Notas
- ^ a b c d Wolpert, DH, Macready, WG (1997), " No hay teoremas de almuerzo gratis para la optimización ", Transacciones IEEE sobre cálculo evolutivo 1 , 67.
- ^ Wolpert, David (1996), " La falta de distinciones a priori entre algoritmos de aprendizaje ", Computación neuronal , págs. 1341-1390. Archivado el 20 de diciembre de 2016 en la Wayback Machine.
- ^ Wolpert, DH y Macready, WG (2005) "Almuerzos gratuitos coevolucionarios", Transacciones de IEEE sobre computación evolutiva , 9 (6): 721-735
- ^ a b Whitley, Darrell y Jean Paul Watson. " Teoría de la complejidad y el teorema de no almuerzo gratis ". En Metodologías de búsqueda, págs. 317–339. Springer, Boston, MA, 2005.
- ^ a b Giraud-Carrier, Christophe y Foster Provost. " Hacia una justificación del metaaprendizaje: el teorema de no almuerzo gratis es un obstáculo ". En Proceedings of the ICML-2005 Workshop on Meta-learning, págs. 12-19. 2005.
- ^ Forster, Malcolm R. (1999). Mentes y Máquinas . 9 (4): 543–564. doi : 10.1023 / A: 1008304819398 . Falta o vacío
|title=
( ayuda ) - ^ Kawaguchi, K., Kaelbling, LP y Bengio, Y. (2017) "Generalización en el aprendizaje profundo", https://arxiv.org/abs/1710.05468
- ^ Wolpert, DH (2013) "Lo que realmente significan los teoremas de no almuerzo gratis", Ubicuidad, Volumen 2013, diciembre de 2013, doi : 10.1145 / 2555235.2555237
- ^ Lattimore, Tor y Marcus Hutter. " No hay almuerzo gratis frente a la navaja de Occam en el aprendizaje supervisado ". En Probabilidad algorítmica y amigos. Predicción bayesiana e inteligencia artificial, págs. 223-235. Springer, Berlín, Heidelberg, 2013.
enlaces externos
- No hay teoremas del almuerzo gratis
- Gráficos que ilustran el teorema