En el folclore matemático , el teorema de “ no hay almuerzo gratis ” ( NFL ) (a veces en plural) de David Wolpert y William Macready, alude al dicho “ no hay tal cosa como un almuerzo gratis ”, es decir, no hay atajos fáciles para el éxito. Apareció en el libro de 1997 “No Free Lunch Theorems for Optimization” (Teoremas de no almuerzo gratis para optimización). [1] Wolpert había derivado previamente teoremas de no almuerzo gratis para aprendizaje automático (inferencia estadística). [2]
En 2005, los propios 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 hay almuerzo gratis" (NFL, por sus siglas en inglés) es una consecuencia fácil de enunciar y comprender de los teoremas que Wolpert y Macready realmente demuestran. Es más débil que los teoremas demostrados y, por lo tanto, no los resume. Varios investigadores han ampliado sustancialmente el trabajo de Wolpert y Macready. En términos de cómo se utiliza el teorema de NFL en el contexto del área de investigación, el teorema de " no hay almuerzo gratis" en búsqueda y optimización es un campo que se dedica a fines de análisis matemático de datos para la identidad estadística, particularmente búsqueda [4] y optimización. [1]
Mientras que algunos académicos sostienen que la NFL transmite información importante, otros sostienen que la NFL tiene poca relevancia para la investigación del aprendizaje automático. [5] [6] [7]
Supongamos que un universo de juguete existe durante exactamente 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:
Cualquier estrategia de predicción que tenga éxito en 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 todos los historiales tienen la misma probabilidad, entonces cualquier estrategia de predicción tendrá la misma puntuación, con la misma tasa de precisión de 0,5. [8]
Wolpert y Macready ofrecen dos teoremas de la NFL que están estrechamente relacionados con el teorema folclórico. En su artículo, afirman:
Hemos denominado a los resultados asociados teoremas NFL porque demuestran que si un algoritmo tiene un buen desempeño en una determinada clase de problemas, necesariamente paga por ello con un desempeño degradado en el conjunto de todos los problemas restantes. [1]
El primer teorema plantea la hipótesis de funciones objetivo que no cambian mientras la optimización está en curso, y el segundo plantea la hipótesis de funciones objetivo que pueden cambiar. [1]
Teorema — Para cualquier algoritmo a 1 y a 2 , en el paso de iteración m donde denota el conjunto ordenado de tamaño de los valores de costo asociados 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 de los tiempos de ejecución del algoritmo en la función .
El teorema puede formularse de manera equivalente de la siguiente manera:
Teorema : Dado un conjunto finito y un conjunto finito de números reales , suponga que se elige al azar según una distribución uniforme en el conjunto de todas las funciones posibles de a . Para el problema de optimización sobre el conjunto , entonces ningún algoritmo funciona mejor que la búsqueda a ciegas.
Aquí, búsqueda ciega significa que en cada paso del algoritmo, el elemento se elige al azar con una distribución de probabilidad uniforme entre los elementos que no se han elegido 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, de la hora 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 objetivo se extraen de manera uniforme 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 objetivo que varían en el tiempo. [1]
Los teoremas de la NFL no fueron motivados explícitamente por la pregunta 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 aleatorio uniforme". Más bien, se utilizó la aleatoriedad uniforme como herramienta para comparar la cantidad de entornos para los que el algoritmo A supera al algoritmo B con la cantidad de entornos para los que B supera al A. La NFL nos dice que (ponderado adecuadamente) [ aclaración necesaria ] hay la misma cantidad de entornos en ambos conjuntos.
Esto es cierto para muchas definiciones de lo que es exactamente un "entorno". En particular, hay tantas distribuciones previas (ponderadas apropiadamente) en las que el algoritmo de aprendizaje A supera a B (en promedio) como viceversa. [ cita requerida ] Esta afirmación sobre los conjuntos de valores previos es lo más importante de NFL, no el hecho de que dos algoritmos cualesquiera tengan el mismo rendimiento 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 establece nada sobre cada instancia particular de un problema que puede surgir en la práctica. Es decir, la NFL establece lo que está contenido en sus enunciados matemáticos y no es nada más que eso. Por ejemplo, se aplica a las situaciones en las que el algoritmo está fijado a priori y se elige a posteriori un problema en el peor de los casos para el algoritmo fijado. Por lo tanto, si tenemos un "buen" problema en la práctica o si podemos elegir un "buen" algoritmo de aprendizaje para una instancia de problema particular dada, entonces la NFL no menciona ninguna limitación sobre esta instancia de problema 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. [9]
Para ilustrar una de las implicaciones contraintuitivas de la NFL, supongamos que fijamos dos algoritmos de aprendizaje supervisado, C y D. Luego, tomamos una muestra de una función objetivo f para producir un conjunto de pares de entrada-salida, d . La pregunta es cómo deberíamos elegir si entrenar a C o D en d , para hacer predicciones sobre qué salida estaría asociada con un punto que se encuentra fuera de d .
En casi todas las ciencias y las estadísticas, es habitual 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 a partir de d con C o D , vemos cuál de ellos tiene un mejor rendimiento 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. Llamemos a este algoritmo A. (Podría decirse que A es un modelo simplificado del propio método científico).
También podríamos utilizar la antivalidación cruzada para hacer nuestra elección. En otras palabras, podríamos elegir entre C y D en función de cuál tenga un peor rendimiento fuera de la muestra dentro de d . Nuevamente, dado que C y D son fijos, este uso de la antivalidación cruzada es en sí mismo un algoritmo. Llamemos 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á ante el método "anti" científico con la misma facilidad con la que gana. [10]
El algoritmo NFL sólo se aplica si la función objetivo se elige de una distribución uniforme de todas las funciones posibles. Si no es así y es más probable que se elijan ciertas funciones objetivo que otras, entonces A puede tener un mejor rendimiento que B en general. La contribución del algoritmo NFL es que nos dice que elegir un algoritmo apropiado requiere hacer suposiciones sobre los tipos de funciones objetivo para las que se utiliza el algoritmo. Sin suposiciones, ningún "metaalgoritmo", como el método científico, tiene un mejor rendimiento que la elección aleatoria.
Mientras que algunos académicos sostienen que la NFL transmite información importante, otros sostienen que la NFL tiene poca relevancia para la investigación del aprendizaje automático. [5] [6] [7] 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 antivalidación cruzada). [11]
Sin embargo, existen importantes desafíos formales al utilizar argumentos basados en la complejidad de Kolmogorov para establecer propiedades del mundo real, ya que no es computable y no está definida hasta una constante aditiva arbitraria. En parte como reconocimiento de estos desafíos, recientemente se ha argumentado que existen formas de sortear los teoremas de que no hay almuerzo gratis sin invocar máquinas de Turing, mediante el uso de la "metainducción". [12] [13] Además, la complejidad de Kolmogorov de los modelos de aprendizaje automático se puede acotar superiormente mediante compresiones de su etiquetado de datos, y es posible producir límites de generalización no vacíos entre dominios mediante la complejidad de Kolmogorov. [7]
