No free lunch theorem

Si un algoritmo funciona bien en algunos problemas, entonces vale la pena en otros problemas.

In mathematical folklore, the "no free lunch" (NFL) theorem (sometimes pluralized) of David Wolpert and William Macready, alludes to the saying "no such thing as a free lunch", that is, there are no easy shortcuts to success. It appeared in the 1997 "No Free Lunch Theorems for Optimization".^[1] Wolpert had previously derived no free lunch theorems for machine learning (statistical inference).^[2]

In 2005, Wolpert and Macready themselves indicated that the first theorem in their paper "state[s] that any two optimization algorithms are equivalent when their performance is averaged across all possible problems".^[3]

The "no free lunch" (NFL) theorem is an easily stated and easily understood consequence of theorems Wolpert and Macready actually prove. It is weaker than the proven theorems, and thus does not encapsulate them. Various investigators have extended the work of Wolpert and Macready substantively. In terms of how the NFL theorem is used in the context of the research area, the no free lunch in search and optimization is a field that is dedicated for purposes of mathematically analyzing data for statistical identity, particularly search^[4] and optimization.^[1]

While some scholars argue that NFL conveys important insight, others argue that NFL is of little relevance to machine learning research.^[5][6][7]

Example

Posit a toy universe that exists for exactly two days and on each day contains exactly one object: a square or a triangle. The universe has exactly four possible histories:

1. (square, triangle): the universe contains a square on day 1, and a triangle on day 2
2. (square, square)
3. (triangle, triangle)
4. (triangle, square)

Any prediction strategy that succeeds for history #2, by predicting a square on day 2 if there is a square on day 1, will fail on history #1, and vice versa. If all histories are equally likely, then any prediction strategy will score the same, with the same accuracy rate of 0.5.^[8]

Origin

Wolpert and Macready give two NFL theorems that are closely related to the folkloric theorem. In their paper, they state:

We have dubbed the associated results NFL theorems because they demonstrate that if an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems.^[1]

The first theorem hypothesizes objective functions that do not change while optimization is in progress, and the second hypothesizes objective functions that may change.^[1]

Teorema  :  para cualquier algoritmo a ₁ y a ₂ , en el paso de iteración m

$${\displaystyle \sum _{f}P(d_{m}^{y}\mid f,m,a_{1})=\sum _{f}P(d_{m}^{y}\mid f,m,a_{2}),}$$

donde denota el conjunto ordenado de tamaños 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 . ${\displaystyle d_{m}^{y}}$ ${\displaystyle m}$ ${\displaystyle y}$ ${\displaystyle x\in X}$ ${\displaystyle f:X\rightarrow Y}$ ${\displaystyle P(d_{m}^{y}\mid f,m,a)}$ ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle f}$

El teorema se puede formular de manera equivalente de la siguiente manera:

Teorema  :  dado un conjunto finito y un conjunto finito de números reales , supongamos que se elige al azar de acuerdo con una distribución uniforme en el conjunto de todas las funciones posibles desde hasta . Para el problema de optimización sobre el conjunto , ningún algoritmo funciona mejor que la búsqueda ciega. ${\displaystyle V}$ ${\displaystyle S}$ ${\displaystyle f:V\to S}$ ${\displaystyle S^{V\!}}$ ${\displaystyle V}$ ${\displaystyle S}$ ${\displaystyle f}$ ${\displaystyle V}$

Aquí, la 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 han sido elegidos previamente. ${\displaystyle v\in V}$ ${\displaystyle V}$

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, del tiempo del reloj de pared), por lo que se deduce fácilmente que todos los algoritmos tienen un rendimiento distribuido idénticamente cuando las funciones objetivo se extraen uniformemente 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 tanto, el teorema folclórico no es equivalente al teorema original.

El teorema 2 establece un resultado similar, pero "más sutil", de la NFL para funciones objetivas que varían en el tiempo. ^[1]

Motivación

Los teoremas de la NFL no estaban explícitamente motivados por la cuestión 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". Se utilizó una aleatoriedad bastante uniforme como herramienta para comparar el número de entornos en los que el algoritmo A supera al algoritmo B con el número de entornos en los que B supera a A. La NFL nos dice que (apropiadamente ponderado) ^{[ se necesita aclaración ]} hay tantos entornos en ambos conjuntos.

Esto es cierto para muchas definiciones de qué es exactamente un "medio ambiente". En particular, hay tantas distribuciones previas (apropiadamente ponderadas) en las que el algoritmo de aprendizaje A supera a B (en promedio) como viceversa. ^{[ cita necesaria ]} Esta afirmación sobre conjuntos de antecedentes es lo más importante de la NFL, no el hecho de que dos algoritmos cualesquiera funcionen de manera igual para una 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 dice nada sobre cada caso particular de un problema que puede surgir en la práctica. Es decir, la NFL afirma lo contenido en sus enunciados matemáticos y no es más que eso. Por ejemplo, se aplica a situaciones en las que el algoritmo se fija a priori y se elige a posteriori el peor de los casos para el algoritmo fijo. Por lo tanto, si tenemos un "buen" problema en la práctica o si podemos elegir un "buen" algoritmo de aprendizaje para una determinada instancia de problema en particular, entonces la NFL no menciona ninguna limitación sobre esta instancia de problema en 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]

Trascendencia

Para ilustrar una de las implicaciones contraintuitivas de la NFL, supongamos que arreglamos dos algoritmos de aprendizaje supervisado, C y D. Luego tomamos muestras 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 C o D en d , para hacer predicciones sobre qué salida estaría asociada con un punto que se encuentra fuera de d.

Es común en casi toda la ciencia y la estadística 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 desde d con C o D , vemos cuál de ellos tiene mejor rendimiento fuera de la muestra cuando se prueba dentro de d .

Dado que C y D son fijos, este uso de 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. Llame a este algoritmo A. (Podría decirse que A es un modelo simplificado del método científico en sí).

También podríamos usar antivalidación cruzada para hacer nuestra elección. En otras palabras, podríamos elegir entre C y D según cuál tenga peor rendimiento fuera de muestra dentro de d . Nuevamente, dado que C y D son fijos, este uso de antivalidación cruzada es en sí mismo un algoritmo. Llame 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á frente al método "anti" científico con la misma facilidad. como gana. ^[10]

NFL sólo se aplica si la función objetivo se elige entre una distribución uniforme de todas las funciones posibles. Si este no es el caso, y es más probable que se elijan ciertas funciones objetivo que otras, entonces A puede tener un mejor desempeño que B en general. La contribución de la 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, funciona mejor 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, obtienen mejores resultados 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 es incomputable e indefinido hasta una constante aditiva arbitraria. En parte como reconocimiento de estos desafíos, recientemente se ha argumentado que hay maneras de eludir los teoremas del almuerzo gratis sin invocar las 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 limitar mediante compresiones de su etiquetado de datos, y es posible producir límites de generalización entre dominios no vacíos a través de la complejidad de Kolmogorov. ^[7]

Ver también

• portal de negocios

• Exterioridad
• Costo oculto

Notas

1. Wolpert, DH; Macready, WG (1997). "Teoremas de optimización sin almuerzo gratis". Transacciones IEEE sobre computación evolutiva . 1 : 67–82. CiteSeerX  10.1.1.138.6606 . doi :10.1109/4235.585893. S2CID  5553697.
2. Wolpert, David (1996), "La falta de distinciones a priori entre algoritmos de aprendizaje", Computación neuronal , págs. Archivado el 20 de diciembre de 2016 en Wayback Machine.
3. Wolpert, DH y Macready, WG (2005) "Almuerzos gratuitos coevolutivos", IEEE Transactions on Evolutionary Computation , 9(6): 721–735
4. Wolpert, DH; Macready, WG (1995). "Teoremas de búsqueda sin almuerzo gratis". Informe Técnico SFI-TR-95-02-010 . Instituto Santa Fe. S2CID  12890367.
5. Whitley, Darrell y Jean Paul Watson. "Teoría de la complejidad y el teorema del almuerzo gratis". En Metodologías de búsqueda, págs. 317–339. Springer, Boston, MA, 2005.
6. Giraud-Carrier, Christophe y Foster Provost. "Hacia una justificación del metaaprendizaje: ¿Es el teorema del almuerzo gratis un obstáculo?". En Actas del taller ICML-2005 sobre metaaprendizaje, págs. 2005.
7. Goldblum, M., Finzi, M., Keefer, R. y Wilson, AG. "El teorema del almuerzo gratis, la complejidad de Kolmogorov y el papel de los sesgos inductivos en el aprendizaje automático". En Actas de la Conferencia Internacional sobre Aprendizaje Automático, 2024.
8. Forster, Malcolm R. (1999). "¿Cómo se 'adaptan las reglas simples a la realidad' en un mundo complejo?". Mentes y Máquinas . 9 (4): 543–564. doi :10.1023/A:1008304819398. S2CID  8802657.
9. Kawaguchi, K., Kaelbling, LP y Bengio, Y.(2017) "Generalización en el aprendizaje profundo", https://arxiv.org/abs/1710.05468
10. Wolpert, DH (2013) "Lo que realmente significan los teoremas del almuerzo gratis", Ubiquity, Volumen 2013, diciembre de 2013, doi :10.1145/2555235.2555237
11. Lattimore, Tor y Marcus Hutter. "No hay almuerzo gratis frente a la navaja de Occam en el aprendizaje supervisado". En Probabilidad algorítmica y amigos. Predicción bayesiana e inteligencia artificial, págs. Springer, Berlín, Heidelberg, 2013.
12. Schurz, G. (2019). El problema de Hume resuelto: la optimidad de la metainducción . Prensa del MIT.
13. Wolpert, DH (2023). "Las implicaciones de los teoremas de no almuerzo gratis para la metainducción". Revista de Filosofía General de la Ciencia . 54 : 421–432. arXiv : 2103.11956 . doi :10.1007/s10838-022-09609-2.

enlaces externos

• Teoremas sin almuerzo gratis
• Gráficos que ilustran el teorema.