En la complejidad computacional y la optimización, el teorema de que no hay almuerzo gratis es un resultado que establece que para ciertos tipos de problemas matemáticos, el costo computacional de encontrar una solución, promediado sobre todos los problemas de la clase, es el mismo para cualquier método de solución. El nombre alude al dicho " no hay tal cosa como un almuerzo gratis ", es decir, ningún método ofrece un "atajo". Esto es bajo el supuesto de que el espacio de búsqueda es una función de densidad de probabilidad . No se aplica al caso en el que el espacio de búsqueda tiene una estructura subyacente (por ejemplo, es una función diferenciable) que se puede explotar de manera más eficiente (por ejemplo, el método de Newton en optimización ) que la búsqueda aleatoria o incluso tiene soluciones de forma cerrada (por ejemplo, los extremos de un polinomio cuadrático) que se pueden determinar sin búsqueda en absoluto. Para tales supuestos probabilísticos, los resultados de todos los procedimientos que resuelven un tipo particular de problema son estadísticamente idénticos. Una forma colorida de describir tal circunstancia, introducida por David Wolpert y William G. Macready en relación con los problemas de búsqueda [1] y optimización, [2] es decir que no hay almuerzo gratis . Wolpert había derivado previamente teoremas de que no hay almuerzo gratis para el aprendizaje automático ( inferencia estadística ). [3] Antes de que se publicara el artículo de Wolpert, Cullen Schaffer demostró de forma independiente una versión restringida de uno de los teoremas de Wolpert y lo utilizó para criticar el estado actual de la investigación del aprendizaje automático sobre el problema de la inducción. [4]
En la metáfora de que "no hay almuerzo gratis" , cada "restaurante" (procedimiento de resolución de problemas) tiene un "menú" que asocia cada "plato de almuerzo" (problema) con un "precio" (el desempeño del procedimiento para resolver el problema). Los menús de los restaurantes son idénticos excepto en un aspecto: los precios se barajan de un restaurante a otro. Para un omnívoro que tiene la misma probabilidad de pedir cualquier plato que cualquier otro, el costo promedio del almuerzo no depende de la elección del restaurante. Pero un vegano que va a almorzar regularmente con un carnívoro que busca la economía podría pagar un alto costo promedio por el almuerzo. Para reducir metódicamente el costo promedio, uno debe usar el conocimiento previo de a) lo que uno pedirá y b) cuánto costará el pedido en varios restaurantes. Es decir, la mejora del desempeño en la resolución de problemas depende del uso de información previa para hacer coincidir los procedimientos con los problemas. [2] [4]
En términos formales, no hay almuerzo gratis cuando la distribución de probabilidad en las instancias del problema es tal que todos los solucionadores de problemas tienen resultados distribuidos de manera idéntica. En el caso de la búsqueda , una instancia del problema en este contexto es una función objetivo particular , y un resultado es una secuencia de valores obtenidos en la evaluación de soluciones candidatas en el dominio de la función. Para las interpretaciones típicas de los resultados, la búsqueda es un proceso de optimización . No hay almuerzo gratis en la búsqueda si y solo si la distribución en las funciones objetivo es invariante bajo la permutación del espacio de soluciones candidatas. [5] [6] [7] Esta condición no se cumple precisamente en la práctica, [6] pero un teorema de "(casi) ningún almuerzo gratis" sugiere que se cumple aproximadamente. [8]
Algunos problemas computacionales se resuelven buscando buenas soluciones en un espacio de soluciones candidatas . Una descripción de cómo seleccionar repetidamente soluciones candidatas para la evaluación se llama algoritmo de búsqueda . En un problema particular, diferentes algoritmos de búsqueda pueden obtener resultados diferentes, pero en todos los problemas, son indistinguibles. De ello se deduce que si un algoritmo logra resultados superiores en algunos problemas, debe pagar con inferioridad en otros problemas. En este sentido, no hay almuerzo gratis en la búsqueda. [1] Alternativamente, siguiendo a Schaffer, [4] el rendimiento de la búsqueda se conserva . Por lo general, la búsqueda se interpreta como optimización , y esto lleva a la observación de que no hay almuerzo gratis en la optimización. [2]
El teorema de Wolpert y Macready, "no hay almuerzo gratis", tal como lo enunciaron en lenguaje sencillo Wolpert y Macready, es que "cualquier par de algoritmos son equivalentes cuando su desempeño se promedia entre todos los problemas posibles". [9] Los resultados de "no hay almuerzo gratis" indican que hacer coincidir algoritmos con problemas da un desempeño promedio más alto que aplicar un algoritmo fijo a todos. [ cita requerida ] Igel y Toussaint [6] y English [7] han establecido una condición general bajo la cual no hay almuerzo gratis. Si bien es físicamente posible, no se cumple con precisión. [6] Droste, Jansen y Wegener han demostrado un teorema que interpretan como indicativo de que "(casi) no hay almuerzo gratis" en la práctica. [8]
Para hacer las cosas más concretas, consideremos a un profesional de la optimización que se enfrenta a un problema. Si tiene algún conocimiento de cómo surgió el problema, el profesional puede aprovechar ese conocimiento para seleccionar un algoritmo que funcione bien para resolverlo. Si el profesional no entiende cómo aprovechar ese conocimiento, o simplemente no tiene conocimiento, entonces se enfrenta a la cuestión de si un algoritmo en general supera a otros en problemas del mundo real. Los autores del teorema de que "(casi) nada es gratis" dicen que la respuesta es esencialmente no, pero admiten algunas reservas sobre si el teorema se aplica a la práctica. [8]
Un "problema" es, más formalmente, una función objetivo que asocia soluciones candidatas con valores de bondad. Un algoritmo de búsqueda toma una función objetivo como entrada y evalúa las soluciones candidatas una por una. El resultado del algoritmo es la secuencia de valores de bondad observados. [10] [11]
Wolpert y Macready estipulan que un algoritmo nunca reevalúa una solución candidata y que su rendimiento se mide en función de los resultados. [2] Para simplificar, no permitimos la aleatoriedad en los algoritmos. En estas condiciones, cuando se ejecuta un algoritmo de búsqueda en cada entrada posible, genera cada salida posible exactamente una vez. [7] Debido a que el rendimiento se mide en función de los resultados, los algoritmos son indistinguibles en cuanto a la frecuencia con la que alcanzan determinados niveles de rendimiento.
Algunas medidas de rendimiento indican qué tan bien funcionan los algoritmos de búsqueda en la optimización de la función objetivo. De hecho, no parece haber ninguna aplicación interesante de los algoritmos de búsqueda en la clase en consideración, excepto en los problemas de optimización. Una medida de rendimiento común es el índice más bajo del valor más bajo en la secuencia de salida. Este es el número de evaluaciones necesarias para minimizar la función objetivo. Para algunos algoritmos, el tiempo necesario para encontrar el mínimo es proporcional al número de evaluaciones. [7]
Los teoremas originales de "no free lunch" (NFL) suponen que todas las funciones objetivo tienen la misma probabilidad de ser introducidas en los algoritmos de búsqueda. [2] Desde entonces se ha establecido que existe NFL si y solo si, en términos generales, "mezclar" funciones objetivo no tiene impacto en sus probabilidades. [6] [7] Aunque esta condición para NFL es físicamente posible, se ha argumentado que ciertamente no se cumple con precisión. [6]
La interpretación obvia de "no es NFL" es "almuerzo gratis", pero esto es engañoso. La NFL es una cuestión de grado, no una proposición de todo o nada. Si la condición para la NFL se cumple aproximadamente, entonces todos los algoritmos arrojan aproximadamente los mismos resultados en todas las funciones objetivo. [7] "No es NFL" implica únicamente que los algoritmos son inequivalentes en general en alguna medida de desempeño. Para una medida de desempeño de interés, los algoritmos pueden seguir siendo equivalentes, o casi. [7]
Casi todos los elementos del conjunto de todas las funciones posibles (en el sentido de "función" en la teoría de conjuntos) son funciones aleatorias de Kolmogorov y, por lo tanto, los teoremas de NFL se aplican a un conjunto de funciones que casi todas no se pueden expresar de manera más compacta que como una tabla de búsqueda que contiene una entrada distinta (y aleatoria) para cada punto en el espacio de búsqueda. Las funciones que se pueden expresar de manera más compacta (por ejemplo, mediante una expresión matemática de tamaño razonable) no son, por definición, funciones aleatorias de Kolmogorov.
Además, dentro del conjunto de todas las funciones objetivo posibles, los niveles de bondad están representados de manera igualitaria entre las soluciones candidatas, por lo que las buenas soluciones están dispersas en todo el espacio de las candidatas. En consecuencia, un algoritmo de búsqueda rara vez evaluará más de una pequeña fracción de las candidatas antes de encontrar una muy buena solución. [11]
Casi todas las funciones objetivo tienen una complejidad de Kolmogorov tan alta que no pueden almacenarse en una computadora en particular. [5] [7] [11] Más precisamente, si modelamos una computadora física dada como una máquina de registro con una memoria de tamaño dado en el orden de las memorias de las computadoras modernas, entonces la mayoría de las funciones objetivo no pueden almacenarse en sus memorias. Hay más información en la función objetivo o algoritmo típico de la que Seth Lloyd estima que el universo observable es capaz de registrar. [12] Por ejemplo, si cada solución candidata está codificada como una secuencia de 300 0 y 1, y los valores de bondad son 0 y 1, entonces la mayoría de las funciones objetivo tienen una complejidad de Kolmogorov de al menos 2 300 bits, [13] y esto es mayor que el límite de Lloyd de 10 90 ≈ 2 299 bits. De ello se deduce que el teorema original de "no hay almuerzo gratis" no se aplica a lo que se puede almacenar en una computadora física; En lugar de ello, es necesario aplicar los llamados teoremas "restringidos" de que no hay nada gratis. También se ha demostrado que los resultados de la NFL se aplican a funciones incomputables. [14]
es el conjunto de todas las funciones objetivo f : X → Y , donde es un espacio de soluciones finito y es un conjunto poset finito . El conjunto de todas las permutaciones de X es J . Una variable aleatoria F se distribuye en . Para todo j en J , F o j es una variable aleatoria distribuida en , con P( F o j = f ) = P( F = f o j −1 ) para todo f en .
Sea a ( f ) la salida del algoritmo de búsqueda a en la entrada f . Si a ( F ) y b ( F ) se distribuyen de forma idéntica para todos los algoritmos de búsqueda a y b , entonces F tiene una distribución NFL . Esta condición se cumple si y solo si F y F o j se distribuyen de forma idéntica para todos los j en J . [6] [7] En otras palabras, no hay nada gratis para los algoritmos de búsqueda si y solo si la distribución de funciones objetivo es invariante bajo la permutación del espacio de soluciones. [15] Los teoremas NFL de teoría de conjuntos se han generalizado recientemente a cardinalidad arbitraria y . [16]
Wolpert y Macready dan dos teoremas NFL principales, el primero sobre funciones objetivo que no cambian mientras la búsqueda está en progreso, y el segundo sobre funciones objetivo que pueden cambiar. [2]
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 búsqueda no depende del algoritmo de búsqueda.
El segundo teorema establece un resultado NFL "más sutil" para funciones objetivo que varían en el tiempo. [2]
Una interpretación convencional, aunque no del todo precisa, de los resultados de la NFL es que "una estrategia de optimización universal de propósito general es teóricamente imposible, y la única forma en que una estrategia puede superar a otra es si está especializada en el problema específico en consideración". [17] Se deben hacer varios comentarios:
En la práctica, sólo las funciones objetivo altamente comprimibles (que no son para nada aleatorias) caben en la memoria de los ordenadores, y no es cierto que cada algoritmo funcione bien en casi todas las funciones comprimibles. En general, hay una ventaja de rendimiento al incorporar el conocimiento previo del problema al algoritmo. Si bien los resultados de NFL constituyen, en sentido estricto, teoremas de pleno empleo para los profesionales de la optimización, es importante tener en cuenta el contexto más amplio. Por un lado, los seres humanos a menudo tienen poco conocimiento previo con el que trabajar. Por otro lado, la incorporación de conocimiento previo no proporciona una gran ganancia de rendimiento en algunos problemas. Por último, el tiempo humano es muy caro en relación con el tiempo de ordenador. Hay muchos casos en los que una empresa optaría por optimizar una función lentamente con un programa informático sin modificar en lugar de hacerlo rápidamente con un programa modificado por humanos.
Los resultados de la NFL no indican que sea inútil intentar resolver problemas con algoritmos no especializados. Nadie ha determinado la fracción de problemas prácticos para los que un algoritmo produce buenos resultados rápidamente. Y en la práctica hay un almuerzo gratis, que no está en absoluto en conflicto con la teoría. Ejecutar una implementación de un algoritmo en una computadora cuesta muy poco en relación con el costo del tiempo humano y el beneficio de una buena solución. Si un algoritmo logra encontrar una solución satisfactoria en un tiempo aceptable, una pequeña inversión ha producido una gran recompensa. Si el algoritmo falla, entonces se pierde poco.
Recientemente, algunos filósofos de la ciencia han sostenido que existen formas de sortear los teoremas de que no hay nada gratis, mediante el uso de la "metainducción". Wolpert aborda estos argumentos en [18] .
Wolpert y Macready han demostrado que existen almuerzos gratis en la optimización coevolutiva . [9] Su análisis "cubre problemas de 'auto-juego'. En estos problemas, el conjunto de jugadores trabaja en conjunto para producir un campeón, que luego se enfrenta a uno o más antagonistas en un juego multijugador posterior". [9] Es decir, el objetivo es obtener un buen jugador, pero sin una función objetivo. La bondad de cada jugador (solución candidata) se evalúa observando qué tan bien juega contra otros. Un algoritmo intenta utilizar a los jugadores y su calidad de juego para obtener mejores jugadores. El jugador considerado el mejor de todos por el algoritmo es el campeón. Wolpert y Macready han demostrado que algunos algoritmos coevolutivos son generalmente superiores a otros algoritmos en la calidad de los campeones obtenidos. Generar un campeón a través del auto-juego es de interés en la computación evolutiva y la teoría de juegos . Los resultados son inaplicables a la coevolución de especies biológicas, que no produce campeones. [9]
