Teorema No Free Lunch

Los teoremas No Free Lunch (NFL) publicados en 1997 por David Wolpert y William MacReady, son un conjunto de teoremas matemáticos que tienen implicaciones para el campo de la optimización y el aprendizaje supervisado. Estos teoremas establecen que, para cualquier algoritmo de optimización, cualquier mejora en el desempeño sobre una clase de problemas se compensa con un desempeño inferior en otra clase, es decir, no existe un algoritmo óptimo universal para todos los problemas de optimización.

La idea básica detrás de los teoremas NFL es que, para cualquier algoritmo de optimización, cualquier mejora en el rendimiento sobre una clase de problemas se compensa con el rendimiento sobre otra clase. En otras palabras, no existe un algoritmo de optimización que se adapte a todos los problemas por igual. Este es un resultado contraintuitivo, ya que implica que hay límites fundamentales en el poder de los algoritmos de optimización.

Implicaciones[editar]

Supongamos que tenemos dos algoritmos de optimización, A y B, y dos clases de problemas, P y Q. Asumamos además que el algoritmo A tiene un mejor rendimiento que el algoritmo B en los problemas de la clase P, mientras que el algoritmo B tiene un mejor rendimiento que el algoritmo A en los problemas de la clase Q. Entonces, según el teorema NFL, debe existir alguna distribución de problemas sobre P y Q tal que el algoritmo A y el algoritmo B tengan un rendimiento igual en promedio.

En otras palabras, cualquier mejora en el rendimiento del algoritmo A sobre el algoritmo B en los problemas de clase P se compensa exactamente con una disminución en el rendimiento en los problemas de clase Q, y viceversa.

Podemos expresar esta idea utilizando el concepto de valor esperado. Sea f una función de optimización que asigna un espacio de entrada X a un conjunto de posibles valores de salida Y. Sea F el conjunto de todas las posibles funciones f, y sea D una distribución de probabilidad sobre el espacio de entrada X. Entonces, el valor esperado de una función f con respecto a la distribución D se define como:

$E[f]=\int _{x}f(x)D(x)dx$

donde la integral se toma sobre todo el espacio de entrada X. En otras palabras, el valor esperado de una función f es el valor promedio que f toma sobre todas las posibles entradas, ponderado por su probabilidad de ocurrencia.

Las implicaciones del teorema NFL son significativas. Sugieren que el desempeño de los algoritmos de optimización está limitado inherentemente por la estructura de los problemas que se resuelven. Esto significa que, en la práctica, diferentes algoritmos de optimización pueden ser más adecuados para diferentes tipos de problemas. También significa que la búsqueda de un algoritmo óptimo universal es inútil.

Expresión matemática[editar]

Los teoremas NFL se pueden expresar matemáticamente. Sean A y B dos algoritmos de optimización, y sean P y Q dos clases de problemas. Sea $f_{A}(P)$ la mejor solución encontrada por el algoritmo A en los problemas de la clase P, y $f_{B}(Q)$ la mejor solución encontrada por el algoritmo B en los problemas de la clase Q. Entonces, los teoremas NFL establecen que:

$E[f_{A}(P)]=E[f_{B}(Q)]$

donde $E[f_{A}(P)]$ es el valor esperado de la mejor solución encontrada por el algoritmo A sobre los problemas de la clase P, y $E[f_{B}(Q)]$ es el valor esperado de la mejor solución encontrada por el algoritmo B sobre los problemas de la clase Q.

Esto significa que, independientemente de lo bien que se desempeñe un algoritmo A en los problemas de la clase P, siempre existe alguna distribución de problemas sobre P y Q tal que el algoritmo B tenga un desempeño igualmente bueno en promedio.

Referencias[editar]

^[1]^[1]^[2]^[3]^[4]

↑ ^a ^b Wolpert, D.H.; Macready, W.G. (1997-04). «No free lunch theorems for optimization». IEEE Transactions on Evolutionary Computation 1 (1): 67-82. ISSN 1089-778X. doi:10.1109/4235.585893. Consultado el 3 de mayo de 2023.
↑ Wolpert, David H. (1996-10). «The Lack of A Priori Distinctions Between Learning Algorithms». Neural Computation 8 (7): 1341-1390. ISSN 0899-7667. doi:10.1162/neco.1996.8.7.1341. Consultado el 3 de mayo de 2023.
↑ Pulido, J.A.G. (1997). «An application of genetic algorithms to the ROBDD optimization». Second International Conference on Genetic Algorithms in Engineering Systems (IEE). doi:10.1049/cp:19971195. Consultado el 3 de mayo de 2023.
↑ Bandyopadhyay, Sanghamitra; Pal, Sankar K. Genetic Algorithms in Clustering. Springer Berlin Heidelberg. pp. 181-212. ISBN 978-3-540-49606-9. Consultado el 3 de mayo de 2023.

Datos: Q7045226

[Sin_nombre-20230526131328-1] Wolpert, D.H.; Macready, W.G. (1997-04). «No free lunch theorems for optimization». IEEE Transactions on Evolutionary Computation 1 (1): 67-82. ISSN 1089-778X. doi:10.1109/4235.585893. Consultado el 3 de mayo de 2023.

[2] Wolpert, David H. (1996-10). «The Lack of A Priori Distinctions Between Learning Algorithms». Neural Computation 8 (7): 1341-1390. ISSN 0899-7667. doi:10.1162/neco.1996.8.7.1341. Consultado el 3 de mayo de 2023.

[3] Pulido, J.A.G. (1997). «An application of genetic algorithms to the ROBDD optimization». Second International Conference on Genetic Algorithms in Engineering Systems (IEE). doi:10.1049/cp:19971195. Consultado el 3 de mayo de 2023.

[4] Bandyopadhyay, Sanghamitra; Pal, Sankar K. Genetic Algorithms in Clustering. Springer Berlin Heidelberg. pp. 181-212. ISBN 978-3-540-49606-9. Consultado el 3 de mayo de 2023.

[1]

[2]

[3]

[4]