¿Cuáles son las implicaciones del teorema "Sin almuerzo gratis" para el aprendizaje automático?

El teorema de No Free Lunch (NFL) establece (ver el artículo Coevolutionary Free Lunches de David H. Wolpert y William G. Macready)

dos algoritmos son equivalentes cuando su rendimiento se promedia en todos los posibles problemas

¿Es realmente cierto el teorema "Sin almuerzo gratis"? ¿Qué significa en realidad? Un buen ejemplo (en contexto de ML) que ilustra esta afirmación sería bueno.

He visto algunos algoritmos que se comportan muy mal, y me cuesta creer que realmente sigan el teorema mencionado anteriormente, así que estoy tratando de entender si mi interpretación de este teorema es correcta o no. ¿O es simplemente otro teorema ornamental como el teorema de aproximación universal de Cybenko?

Esta es una reacción muy común después de encontrarse por primera vez con los teoremas de No Free Lunch (NFL). El del aprendizaje automático es especialmente poco intuitivo, porque va en contra de todo lo que se discute en la comunidad de ML. Dicho esto, el teorema es cierto, pero lo que significa está abierto a algún debate.

Para reafirmar el teorema de las personas que no lo conocen, el teorema de NFL para el aprendizaje automático es realmente un caso especial del teorema de NFL para la búsqueda y optimización local . La versión de búsqueda local es más fácil de entender. El teorema hace la siguiente afirmación, algo radical:

Promediada en todos los posibles problemas de optimización, la calidad de solución promedio encontrada por cualquier algoritmo de búsqueda local que elija usar es exactamente la misma que la calidad de solución promedio de un algoritmo de "búsqueda" local que solo genera posibles soluciones al muestrear uniformemente al azar desde el espacio de todas las soluciones

Otra formulación, cuando la gente quiere una reacción aún más fuerte, es decir que si desea encontrar la mejor solución a un problema, es tan bueno probar cosas que parecen empeorar su solución de forma iterativa como intentar cosas que parece estar haciendo que su solución sea iterativamente mejor. En promedio, ambos enfoques son igualmente buenos.

Bien, entonces ¿ por qué es esto cierto? Bueno, la clave está en los detalles. Wolpert a veces ha descrito el teorema como una especialización del trabajo de Hume sobre el problema de la inducción . La afirmación básica del problema de la inducción es: no tenemos una base lógica para suponer que el futuro será como el pasado. Lógicamente, no hay razón para que las leyes de la física no puedan cambiar radicalmente mañana. Desde una perspectiva puramente lógica , es totalmente razonable que el futuro pueda ser diferente del pasado de muchas maneras. El problema de Hume es que, en general, el futuro es como el pasado en muchos sentidos. Trató de formular un argumento filosófico (lógico) de que esto tenía que ser así, pero básicamente fracasó.

Los teoremas de No Free Lunch dicen lo mismo. Si no sabe cómo se ve su espacio de búsqueda, entonces si refina iterativamente su suposición sobre cómo se ve una buena solución, en respuesta a las observaciones que ha hecho en el pasado sobre cómo se ven las buenas soluciones (es decir, aprender de datos), entonces es tan probable que la operación que realice ayude como que duela. Es por eso que la parte "promediada sobre todos los posibles problemas de optimización" es clave. Para cualquier problema de optimización donde la escalada sea una buena estrategia después$k$movimientos, podemos hacer uno que sea idéntico, excepto que el movimiento de escalada kth hill conduce a una solución horrible. La prueba real es más sutil que eso, pero esa es la idea básica.

Un resumen laico muy breve podría ser:

Un algoritmo de aprendizaje automático solo se puede hacer que funcione mejor en algunos tipos de problemas haciendo que funcione peor en otro tipo de problemas.

Así que lo que hace este medio en un sentido práctico? Significa que necesita tener alguna razón previa para pensar que su algoritmo será efectivo en un problema en particular . Exactamente cómo es una buena razón es el tema de un debate vigoroso dentro de la comunidad de ML. Esto está muy relacionado con el equilibrio de sesgo / varianza .

Algunas respuestas comunes son:

• Cuando se busca un nuevo problema de optimización, aunque podría tener cualquier tipo de estructura aleatoria, los problemas que realmente encontramos en el mundo real son mucho más regulares y ciertos temas comunes están presentes, como el hecho de que " cuesta arriba "(minimizando el error) iterativamente tiende a conducir a buenas soluciones. Básicamente, esta escuela de pensamiento dice que la NFL es un teorema ornamental: la mayoría de los algoritmos de ML funcionan mejor en "el tipo de problemas que vemos en la vida real", al trabajar peor en "el tipo de problemas que no vemos en la vida real".
• Cuando está buscando un nuevo problema de optimización en [inserte su dominio de aplicación favorito], aunque podría tener cualquier tipo de estructura aleatoria, los problemas tienden a parecerse a [lo que usted piense], lo que hace que [su algoritmo favorito] sea mucho más eficaz que adivinar al azar.
• Wolpert y McCready publicaron un resultado interesante que muestra que en realidad existen procesos de optimización especializados, basados ​​en la coevolución, que son consistentemente mejores que las conjeturas aleatorias.

De todos modos, es indiscutible que algunos algoritmos son mejores que otros, en ciertos subdominios (podemos ver esto empíricamente). La NFL nos dice que para ser mejores allí, deben ser peores en otro lugar. La cuestión a debatir es si el "otro lugar" es un problema real o puramente artificial.