En complejidad y optimización computacional, el teorema del almuerzo gratis es un resultado que establece que para ciertos tipos de problemas matemáticos, el costo computacional de encontrar una solución, promediado entre todos los problemas de la clase, es el mismo para cualquier método de solución. El nombre alude al dicho " no hay nada gratis ", es decir, ningún método ofrece un "atajo". Esto se basa en 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 puede explotarse más eficientemente (por ejemplo, el método de optimización de Newton ) que la búsqueda aleatoria o incluso tiene soluciones de forma cerrada (por ejemplo, el extremos de un polinomio cuadrático) que se pueden determinar sin necesidad de realizar ninguna búsqueda. 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 no había deducido previamente el teorema del 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 del "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" (la realización 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 tantas probabilidades de pedir cada plato como cualquier otro, el coste medio del almuerzo no depende del restaurante elegido. Pero un vegano que va a almorzar regularmente con un carnívoro que busca economía podría pagar un costo promedio alto por el almuerzo. Para reducir metódicamente el costo promedio, se debe utilizar el conocimiento previo de a) qué pedirá yb) 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 relacionar los procedimientos con los problemas. [2] [4]
En términos formales, no hay nada gratis cuando la distribución de probabilidad de las instancias del problema es tal que todos los que resuelven el problema tienen resultados distribuidos de manera idéntica. En el caso de la búsqueda , una instancia de 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 interpretaciones típicas de resultados, la búsqueda es un proceso de optimización . No hay almuerzo gratis en la búsqueda si y sólo si la distribución de 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) no hay 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 su evaluación se denomina 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, en la búsqueda no hay almuerzo gratis . [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 nada gratis en la optimización. [2]
"El teorema de Wolpert y Macready de 'no hay almuerzo gratis'", como lo afirman en lenguaje sencillo los propios Wolpert y Macready, es que "dos algoritmos cualesquiera son equivalentes cuando su desempeño se promedia en todos los problemas posibles". [9] Los resultados "no hay almuerzo gratis" indican que hacer coincidir los algoritmos con los problemas proporciona un rendimiento promedio más alto que aplicar un algoritmo fijo a todos. [ cita necesaria ] Igel y Toussaint [6] e 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. Dado algún conocimiento de cómo surgió el problema, el profesional puede aprovechar ese conocimiento para seleccionar un algoritmo que funcione bien para resolver el problema. Si el practicante no entiende cómo explotar el conocimiento, o simplemente no tiene conocimiento, entonces se enfrenta a la pregunta de si algún algoritmo generalmente supera a otros en problemas del mundo real. Los autores del teorema de "(casi) no hay almuerzo gratis" dicen que la respuesta es esencialmente no, pero admiten algunas reservas sobre si el teorema aborda la práctica. [8]
Un "problema" es, más formalmente, una función objetiva 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 el rendimiento del algoritmo se mide en función de los resultados. [2] Por simplicidad, 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 las salidas, los algoritmos son indistinguibles en cuanto a la frecuencia con la que alcanzan niveles particulares 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 que estamos considerando excepto a los problemas de optimización. Una medida de rendimiento común es el índice mínimo del valor mínimo 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 hay almuerzo gratis (NFL) suponen que todas las funciones objetivas tienen la misma probabilidad de ingresar a los algoritmos de búsqueda. [2] Desde entonces se ha establecido que existe la NFL si y sólo si, en términos generales, "barajar" las funciones objetivas no tiene impacto en sus probabilidades. [6] [7] Aunque esta condición para la NFL es físicamente posible, se ha argumentado que ciertamente no se cumple con precisión. [6]
La interpretación obvia de "no NFL" es "almuerzo gratis", pero esto es engañoso. La NFL es una cuestión de grado, no una propuesta de todo o nada. Si la condición para NFL se cumple aproximadamente, entonces todos los algoritmos producen aproximadamente los mismos resultados en todas las funciones objetivo. [7] "No NFL" implica sólo que los algoritmos no son equivalentes en general según alguna medida de rendimiento. Para una medida de rendimiento 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 aleatorios de Kolmogorov y, por lo tanto, los teoremas de la NFL se aplican a un conjunto de funciones, casi todas las cuales no pueden expresarse de manera más compacta que como una búsqueda. tabla que contiene una entrada distinta (y aleatoria) para cada punto en el espacio de búsqueda. Las funciones que pueden expresarse de manera más compacta (por ejemplo, mediante una expresión matemática de tamaño razonable) no son, por definición, aleatorias de Kolmogorov.
Además, dentro del conjunto de todas las funciones objetivo posibles, los niveles de bondad están igualmente representados entre las soluciones candidatas, por lo que las buenas soluciones están dispersas por todo el espacio de las candidatas. En consecuencia, un algoritmo de búsqueda rara vez evaluará más que una pequeña fracción de los candidatos antes de localizar una muy buena solución. [11]
Casi todas las funciones objetivas tienen una complejidad Kolmogorov tan alta que no pueden almacenarse en una computadora en particular. [5] [7] [11] Más precisamente, si modelamos una computadora física determinada como una máquina de registro con un tamaño de memoria determinado en el orden de las memorias de las computadoras modernas, entonces la mayoría de las funciones objetivas no se pueden almacenar 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 su lugar, es necesario aplicar los llamados teoremas "reforzados" del almuerzo 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 solución finito y es un 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 ) yb ( F ) se distribuyen idénticamente para todos los algoritmos de búsqueda ayb , entonces F tiene una distribución NFL . Esta condición se cumple si y sólo si F y F o j están distribuidos idénticamente para todos los j en J. [6] [7] En otras palabras, no hay almuerzo gratis para los algoritmos de búsqueda si y sólo si la distribución de funciones objetivo es invariante bajo permutación del espacio de solución. [15] Los teoremas de la NFL de teoría de conjuntos se han generalizado recientemente a cardinalidad arbitraria y . [dieciséis]
Wolpert y Macready dan dos teoremas principales de la NFL, el primero sobre funciones objetivas que no cambian mientras se realiza la búsqueda y el segundo sobre funciones objetivas 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, pero 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 manera en que una estrategia puede superar a otra es si está especializada en el problema específico que se está considerando". [17] Conviene hacer varios comentarios:
En la práctica, sólo las funciones objetivo altamente comprimibles (lejos de ser aleatorias) caben en el almacenamiento de las computadoras, y no se da el caso de que cada algoritmo funcione bien en casi todas las funciones comprimibles. Generalmente existe una ventaja de rendimiento al incorporar el conocimiento previo del problema al algoritmo. Si bien los resultados de la 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 humanos a menudo tienen pocos conocimientos previos con los que trabajar. Por otro lado, la incorporación de conocimientos previos no mejora mucho el rendimiento en algunos problemas. Finalmente, el tiempo humano es muy caro en comparación con el tiempo de la computadora. Hay muchos casos en los que una empresa optaría por optimizar una función lentamente con un programa informático no modificado en lugar de 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 cuales un algoritmo produce buenos resultados rápidamente. Y hay un almuerzo gratis en la práctica, 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 período de tiempo aceptable, una pequeña inversión ha dado un gran beneficio. Si el algoritmo falla, poco se pierde.
Recientemente, algunos filósofos de la ciencia han argumentado que hay formas de eludir los teoremas del almuerzo gratis mediante el uso de la "metainducción". Wolpert aborda estos argumentos en [18] .
Wolpert y Macready han demostrado que hay almuerzos gratis en la optimización coevolutiva . [9] Su análisis "cubre problemas de 'juego personal'. En estos problemas, el conjunto de jugadores trabaja en conjunto para producir un campeón, quien luego se enfrenta a uno o más antagonistas en un juego multijugador posterior". [9] Es decir, el objetivo es conseguir un buen jugador, pero sin una función objetiva. La bondad de cada jugador (solución candidata) se evalúa observando qué tan bien juega contra los demás. Un algoritmo intenta utilizar a los jugadores y su calidad de juego para obtener mejores jugadores. El jugador considerado mejor 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 juego propio es de interés en la computación evolutiva y la teoría de juegos . Los resultados no son aplicables a la coevolución de especies biológicas, que no produce campeones. [9]
