Teorema NFL y meta-learning

El teorema No-Free-Lunch (NFL) de optimización nos dice que no existe un algoritmo de aprendizaje universal. En tareas de clasificación, para cada algoritmo de aprendizaje, siempre existirá una distribución de probabilidad (que genera los datos entrada-salida) en la que falle.

Una definición intuitiva, como la aportada en el libro de Shalev-Shwartz y Ben-David, establece que para cada algoritmo A y una muestra de entrenamiento de tamaño m, existe una distribución sobre X y una función de clasificación h*:X->Y, tal que si A recibe m ejemplos de entrenamiento i.i.d (independientes e idénticamente distribuidos), etiquetados por h*, es probable que A devuelva un clasificador con un error considerable.

Una implicación práctica es que los algoritmos de machine learning no van a funcionar si no existe una estructura previa, unas hipótesis de partida en el espacio de posibles algoritmos, que refleje un conocimiento previo sobre la tareas específica a resolver.

Una hipótesis asumida en el teorema NFL es que el rendimiento del supuesto algoritmo universal es promediado sobre todas las instancias de problemas/tareas extraídas sobre una distribución uniforme. Pero en la realidad, como vimos en nuestro post sobre por qué el deep learning funciona tan bien, los problemas y tareas que se afrontan tienen cierta estructura reduciendo así el espacio de problemas/tareas.

Los problemas reales tienen distribuciones de probabilidad con ciertas propiedades, como ser funciones polinómicas de orden bajo, tener localidad o simetrías, etc.

Por lo tanto, el conjunto de problemas de clasificación, regresión, extracción… que nos interesan en machine learning es una pequeña fracción de los posibles problemas e incorporar un conocimiento previo sobre estos problemas ha ayudado a avanzar mucho. Por ejemplo, en tareas de reconocimiento de imágenes las redes neuronales utilizan unas suposiciones de partida:

  • Existe una composición jerárquica en la que los elementos de bajo nivel como las formas se van combinando para formar elementos de más nivel como orejas, narices, etc.
  • Los elementos importantes de la imagen se pueden reconocer localmente usando convoluciones.
  • Existe cierta invarianza traslacional en la que la posición exacta del elemento no es importante.

Al evaluar las implicaciones del teorema NFL en machine learning, en un principio se pensó que una de sus consecuencias es que limitaba el potencial de los algoritmos de aprendizaje generales que abordaran tareas diferentes. En cambio, como se ha visto en los últimos años, se pueden utilizar algoritmos de meta-learning (aprender a aprender) que aprendan una estructura común a diferentes tareas y que luego se adapten a cada tarea concreta.

Entre los diferentes meta-parámetros que pueden aprender los algoritmos de meta-learning se encuentran:

  • Aprender la función de aprendizaje: Normalmente en machine learning los parámetros se adaptan para minimizar una función de coste por descenso de gradiente Δwi:=-α∇f(xi-1). En lugar de usar descenso por gradiente, se puede aprender una función más general que actualice los parámetros y refleje mejor las características de las tareas a abordar, p.e. una red neuronal.
  • Aprender el modelo base: Los meta-parámetros del modelo en vez de estar prefijados manualmente se pueden aprender utilizando datos de diferentes tareas y de esta forma tener en cuenta aspectos estructurales de este tipo de tareas. P.e. el número de capas, las simetrías, los parámetros base, etc.

En los últimos años se han dado muchos casos de éxito en este sentido como Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks o Learning to learn by gradient descent by gradient descent y todo apunta a que esta línea va a ser muy activa en los próximos años.

Como hemos visto, el teorema NFL implica la necesidad de tener en los algoritmos una estructura previa adecuada a los tipos de tareas a abordar. El meta-learning, en sus diferentes formas, es una forma adecuada de aprender esta meta-estructura y poder tener algoritmos capaces de adaptarse a diferentes tareas.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Orgullosamente ofrecido por WordPress | Tema: Baskerville 2 por Anders Noren.

Subir ↑

A %d blogueros les gusta esto: