No hay almuerzo gratis en búsqueda y optimización

En teoría de la complejidad computacional y optimización, el teorema de no hay almuerzo gratis es un resultado que establece que, para ciertos tipos de problemas matemáticos, el recurso 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 a la premisa conocida como tANSTAAFL, que indica que ningún método ofrece un atajo para solucionar el problema. Esto se da bajo el supuesto de que el espacio de búsqueda es una función de densidad de probabilidad. No se aplica cuando el espacio de búsqueda tiene una estructura subyacente (por ejemplo, una función diferenciable) que puede explotarse de manera más eficiente (por ejemplo, con el método de Newton en optimización) que la búsqueda aleatoria, o incluso tiene soluciones cerradas (como por ejemplo, en el caso de los valores extremos de un polinomio cuadrático) que pueden determinarse sin búsqueda alguna. 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 original 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 deducido previamente teoremas de no hay almuerzo gratis para los procesos de aprendizaje automático (en estadística inferencial).^[3]​

Antes de la publicación del artículo de Wolpert, Cullen Schaffer demostró de forma independiente una versión restringida de uno de los teoremas de Wolpert y la utilizó para criticar el estado actual de la investigación en aprendizaje automático sobre el problema de la inducción.^[4]​

En el caso metafórico de no hay almuerzo gratis, cada "restaurante" (procedimiento de resolución de problemas) tiene un "menú" que asocia cada "plato" (problema) con un "precio" (el rendimiento del procedimiento para resolver el problema). Los menús de los restaurantes son idénticos, excepto en un aspecto: los precios se intercambian entre restaurantes. Para un omnívoro con la misma probabilidad de pedir cualquier plato, el coste medio del almuerzo no depende de la elección del restaurante. Sin embargo, un vegetariano que almuerza regularmente con un carnívoro que busca ahorrar podría pagar un coste medio elevado. Para reducir metódicamente el coste medio, es necesario conocer con antelación a) qué se pedirá y b) cuánto costará el pedido en distintos restaurantes. Es decir, la mejora del rendimiento en la resolución de problemas depende del uso de información previa para adecuar los procedimientos a los problemas.^[2]​^[4]​

En términos formales, no hay nada gratis cuando la distribución de probabilidad en las instancias del problema es tal que todos los solucionadores tienen resultados distribuidos idénticamente. En el caso de un proceso de búsqueda, una instancia del problema en este contexto es una función de pérdida particular, y un resultado es una sucesión de valores obtenidos en la evaluación de la región factible en el dominio de la función. Para interpretaciones típicas de resultados, la búsqueda es un proceso de optimización. No hay nada gratis en la búsqueda si y solo si la distribución en las funciones objetivo es invariante bajo permutación del espacio de soluciones candidatas. ^[5]​^[6]​^[7]​ Esta condición no se cumple con precisión en la práctica,^[6]​ pero un teorema de casi nada es gratis sugiere que se cumple aproximadamente.^[8]​

Algunos problemas computacionales se resuelven mediante la búsqueda de buenas soluciones en un espacio de región factible. La 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 general son indistinguibles. De ello se deduce que si un algoritmo obtiene resultados superiores en algunos problemas, debe pagar con resultados inferiores en otros. En este sentido, no existe almuerzo gratis en la búsqueda.^[1]​ Alternativamente, siguiendo a Schaffer, el rendimiento de la búsqueda^[4]​ es conservado. Generalmente, la búsqueda se interpreta como optimización, lo que lleva a la observación de que no hay nada gratis en la optimización.^[2]​

El teorema de Wolpert y Macready, todo es gratis, como lo expresaron claramente los propios Wolpert y Macready, establece que "dos algoritmos cualesquiera son equivalentes cuando su rendimiento se promedia en todos los problemas posibles".^[9]​ Los resultados de todo es gratis indican que la adecuación de algoritmos a los problemas ofrece un rendimiento promedio mayor que la aplicación de un algoritmo fijo a todos. Igel y Toussaint^[6]​ y English^[7]​ han establecido una condición general bajo la cual todo es gratis. Si bien es físicamente posible, no se cumple con precisión.^[6]​ Droste, Jansen y Wegener han demostrado un teorema que, según su interpretación, indica que "casi todo es gratis" en la práctica.^[8]​

Para ser más concretos, considérese a un profesional de la optimización que se enfrenta a un problema. Conociendo cómo surgió el problema, el profesional podría aprovechar este conocimiento para seleccionar un algoritmo que funcione bien en la solución del problema. Si el profesional no comprende cómo aprovechar el conocimiento, o simplemente carece de él, se enfrenta a la pregunta de si un algoritmo suele superar a otros en problemas del mundo real. Los autores del teorema de casi nada es gratis afirman que la respuesta es básicamente 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 de pérdida que asocia la región factible 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. La salida del algoritmo es la sucesión 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 las salidas.^[2]​ Para simplificar, no se considera la aleatoriedad en los algoritmos. En estas condiciones, cuando un algoritmo de búsqueda se ejecuta en cada entrada posible, genera cada salida posible exactamente una vez.^[7]​ Dado que el rendimiento se mide en función de las salidas, los algoritmos son indistinguibles en cuanto a la frecuencia con la que alcanzan determinados niveles de rendimiento.

Algunas medidas indican el rendimiento de los algoritmos de búsqueda en 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 considerada, salvo en problemas de optimización. Una medida común del rendimiento es el índice menor del valor menor 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) asumen 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, la reorganización de las funciones objetivo no afecta a sus probabilidades.^[6]​^[7]​ Aunque esta condición para no hay almuerzo gratis 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. 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 producen aproximadamente los mismos resultados en todas las funciones objetivo.^[7]​ "No NFL" implica únicamente que los algoritmos son inequivalentes en general según alguna medida de rendimiento. Para una medida de rendimiento de interés, los algoritmos pueden permanecer 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 que casi en su totalidad no pueden expresarse de forma 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 pueden expresarse de forma más compacta (por ejemplo, mediante una expresión matemática de tamaño razonable) no son, por definición, aleatorias según la ley de Kolmogorov.

Además, dentro del conjunto de todas las posibles funciones objetivo, los niveles de bondad están igualmente representados entre las soluciones candidatas. Por lo tanto, las buenas soluciones se encuentran dispersas en el espacio de 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 son de complejidad de Kolmogórov tan alta que no pueden ser almacenadas en una computadora en particular.^[5]​^[7]​^[11]​ Más precisamente, si se modela 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 ser almacenadas en sus memorias. Hay más información en la función objetivo o algoritmo típico de lo 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 ceros y unos (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³⁰⁰ bits,^[13]​ y esto es mayor que el límite de Lloyd de 10⁹⁰ ˜ 2²⁹⁹ bits. De ello se desprende que el teorema original de ninguna cosa es gratis no se aplica a lo que se puede almacenar en una computadora física. En su lugar, deben aplicarse los llamados teoremas de ninguna cosa es gratis reforzados. También se ha demostrado que los resultados de la NFL se aplican a funciones incomputables.^[14]​

${\displaystyle Y^{X}}$ es el conjunto de todas las funciones objetivo f:X→Y, donde ${\displaystyle X}$ es una región factible finita e ${\displaystyle Y}$ es un conjunto parcialmente ordenado finito. El conjunto de todos las permutaciones de X es J. Una variable aleatoria F se distribuye en ${\displaystyle Y^{X}}$. Para todo j en J, F o j es una variable aleatoria distribuida en ${\displaystyle Y^{X}}$, con P(F o j = f) = P(F = f o j⁻¹) para todo f en ${\displaystyle Y^{X}}$.

Sea a(f) la salida del algoritmo de búsqueda a con la entrada f. Si a(F) y b(F) se distribuyen idénticamente 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 las funciones objetivo es invariante bajo la permutación del espacio de soluciones.^[15]​ Los teoremas NFL de teoría de conjuntos se han generalizado a cardinalidad arbitraria ${\displaystyle X}$ y ${\displaystyle Y}$.^[16]​

Wolpert y Macready presentan dos teoremas principales de la NFL: el primero se refiere a funciones objetivo que no cambian durante la búsqueda y el segundo a funciones objetivo que pueden cambiar.^[2]​

Teorema 1: Para cualquier par de algoritmos a₁ y a₂

${\displaystyle \sum _{f}P(d_{m}^{y}|f,m,a_{1})=\sum _{f}P(d_{m}^{y}|f,m,a_{2}),}$ donde ${\displaystyle d_{m}^{y}}$ denota el conjunto ordenado de tamaño ${\displaystyle m}$ de los valores de coste ${\displaystyle y\in Y}$ asociados a los valores de entrada ${\displaystyle x\in X}$, ${\displaystyle f:X\rightarrow Y}$ es la función que se está optimizando y ${\displaystyle P(d_{m}^{y}|f,m,a)}$ es la probabilidad condicionada de obtener una secuencia dada de valores de coste del algoritmo ${\displaystyle a}$ ejecutado ${\displaystyle m}$ veces en la función ${\displaystyle f}$.

En esencia, esto indica que cuando todas las funciones f son igualmente probables, la probabilidad de observar una secuencia arbitraria de m valores durante la búsqueda no depende del algoritmo de búsqueda.

El segundo teorema establece un resultado NFL más sutil para funciones objetivo variables en el tiempo.^[2]​

Una interpretación convencional, aunque no del todo precisa, de los resultados 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 cuestión.^[17]​

Conviene hacer varios comentarios:

• Teóricamente, existe un optimizador casi universal de propósito general. Cada algoritmo de búsqueda funciona bien en casi todas las funciones objetivo.^[11]​ Por lo tanto, si no se consideran las diferencias relativamente pequeñas entre los algoritmos de búsqueda, por ejemplo, porque el tiempo de computación es barato, entonces la falta de recursos de computación no sería un condicionante de importancia.
• Un algoritmo puede superar a otro en un problema cuando ninguno está especializado en él. De hecho, es posible que ambos algoritmos se encuentren entre los peores para el problema. De forma más general, Wolpert y Macready han desarrollado una medida del grado de alineación entre un algoritmo y una distribución sobre problemas (en sentido estricto, un producto interno).^[2]​ Decir que un algoritmo se ajusta mejor a una distribución que otro no significa que ninguno de los dos se haya especializado conscientemente en ella. Un algoritmo puede tener una buena alineación simplemente por casualidad.
• En la práctica, algunos algoritmos reevalúan las soluciones candidatas. La razón para considerar únicamente el rendimiento en candidatas nunca antes evaluadas es asegurar que, al comparar algoritmos, se esté comparando elementos homogéneos. Además, cualquier superioridad de un algoritmo que nunca reevalúa las candidatas sobre otro algoritmo que sí lo hace en un problema particular, puede no tener nada que ver con la especialización en dicho problema.
• Para casi todas las funciones objetivo, la especialización es esencialmente accidental. Las funciones objetivo incompresibles, o aleatorias de Kolmogorov, no tienen regularidad que un algoritmo pueda explotar, en lo que respecta al mecanizado universal de Turing utilizado para definir la aleatoriedad de Kolmogorov. Por lo tanto, supóngase que existe una opción claramente superior de máquina universal de Turing. Entonces, dada una función objetivo incompresible para esa máquina de Turing, no hay base para elegir entre dos algoritmos si ambos son comprimibles, medidos con esa máquina de Turing. Si un algoritmo elegido funciona mejor que la mayoría, el resultado es casualidad.^[11]​ Una función aleatoria de Kolmogorov no tiene una representación menor que una tabla de búsqueda que contiene un valor (aleatorio) correspondiente a cada punto en el espacio de búsqueda. Cualquier función que pueda expresarse de forma más compacta no es, por definición, aleatoria de Kolmogorov.

En la práctica, solo las funciones objetivo altamente comprimibles (nada aleatorias) caben en la memoria de los ordenadores, y no es cierto que cada algoritmo funcione bien en casi todas las funciones comprimibles. Generalmente, existe una ventaja de rendimiento al incorporar el conocimiento previo del problema en el algoritmo. Si bien los resultados de la NFL constituyen, en sentido estricto, teoremas del pleno empleo para los profesionales de la optimización, es importante tener en cuenta el contexto general. Por un lado, los humanos a menudo tienen poco conocimiento previo con el que trabajar. Por otro lado, incorporar conocimiento previo no proporciona una gran mejora de rendimiento en algunos problemas. Finalmente, el tiempo humano es muy caro en comparación con el tiempo de computadora. 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 existe un beneficio práctico, que no contradice en absoluto la teoría. Instalar un algoritmo en una computadora cuesta muy poco en comparació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 generado una gran recompensa. Si el algoritmo falla, se pierde poco. Algunos filósofos de la ciencia han argumentado que existen maneras de eludir los teoremas de la "no hay almuerzo gratis" mediante la metainducción. Wolpert aborda estos argumentos en la obra "Las implicaciones de los teoremas de "no hay almuerzo gratis para la metainducción".^[18]​

Wolpert y Macready han demostrado que existen almuerzos gratis en la optimización coevolucionaria.^[9]​ Su análisis abarca problemas de autojuego. 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 una partida 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 su rendimiento contra otros. Un algoritmo intenta utilizar a los jugadores y su calidad de juego para obtener mejores jugadores. El jugador considerado el mejor por el algoritmo es el campeón. Wolpert y Macready han demostrado que algunos algoritmos coevolutivos son generalmente superiores a otros en cuanto a la calidad de los campeones obtenidos. Generar un campeón mediante autojuego es interesante en computación evolutiva y teoría de juegos. Los resultados no son aplicables a la coevolución de especies biológicas, que no produce campeones.^[9]​

• Navaja de Ockham

• http://www.no-free-lunch.org
• Radcliffe y Surry, 1995, "Limitaciones fundamentales de los algoritmos de búsqueda: Computación evolutiva en perspectiva" (un artículo publicado tempranamente sobre la NFL, que apareció poco después del artículo de Schaffer en ICML, que a su vez se basó en la preimpresión de Wolpert; disponible en varios formatos)
• Publicaciones sobre la NFL de Thomas English
• Publicaciones sobre la NFL de Christian Igel y Marc Toussaint
• Publicaciones sobre la NFL y "almuerzos gratuitos" de Darrell Whitley
• Lista antigua de publicaciones de David Wolpert, William Macready y Mario Koeppen sobre optimización y búsqueda