Optimización, complejidad computacional y deep learning

En la base de muchos algoritmos de machine learning está encontrar los parámetros del modelo que minimizan una función de coste dados los datos de entrenamiento. Este problema de optimización es clave ya que si tenemos garantizada su solución podremos encontrar los parámetros que minimizan el error.

Las claves para que este problema de optimización sea tratable son que se trate de un problema de optimización convexa y de que se pueda resolver en tiempo polinómico.

Si un problema de optimización es convexo sabemos que si existe un mínimo local este será un mínimo global, el conjunto de mínimos globales es convexo y para cada función estrictamente convexa si la función tiene un mínimo el mínimo es único.

Por ejemplo, hemos generado en Python la función de Rosenbrock usando matplotlib y mplot3d para visualizar el gráfico en 3D. La función Rosenbrock es una función no convexa empleada para probar algoritmos de optimización.

Función de Rosenbrock
Función de Rosenbrock

Como comentamos en un post sobre el problema P vs NP, en un problema en P el número de pasos del algoritmo para resolver el problema está acotado por un polinomio en n, donde n es la longitud de la entrada.

Para problemas simples como una red neuronal de una única capa, los SVM (Support Vector Machine) y la regresión logística, los parámetros que minimizan el error se pueden encontrar en tiempo polinómico.

En cambio, para una red neuronal de dos capas y tres nodos entrenar la red para encontrar los parámetros que minimizan el error es un problema en NP-completo como demostraron Avrim Blum y Ronald Rivest. Recordemos que la clase NP contiene los problemas cuya solución se verifica en tiempo polinómico y que todo problema en NP se puede reducir a un problema de NP-completo.

Por lo tanto para redes neuronales de más capas y nodos, como es el caso del Deep Learning, la optimización se complica y no tenemos garantizado que usando descenso por gradiente lleguemos a un mínimo global. Surge la duda de si tenemos este problema de optimización cómo es posible que en muchas tareas el uso de modelos de deep learning ha permitido alcanzar errores muy bajos. Aunque no se ha encontrado una respuesta teórica clara, hay algunos indicios solventes:

  • Aunque en el espacio de los parámetros del modelo hay muchos mínimos locales para la función de coste, estos mínimos parecen ser similarmente buenos en muchas tareas.
  • La realización de un pre-entrenamiento de cada capa del modelo con un algoritmo no supervisado (por ejemplo Restricted Boltzmann Machine o Autoencoders) consigue mejores resultados ya que para realizar el entrenamiento los parámetros de partida no son aleatorios sino que han sido fijados usando el pre-entrenamiento y la estructura estadística de los datos. Ver el monográfico “Learning Deep Architectures for AI” para una interesante discusión del tema.
  • La mejora de los recursos de computación, por ejemplo con el uso de GPUs que optimizan las operaciones matemáticas en paralelo, ha permitido realizar el entrenamiento con más datos y realizar más iteraciones sobre dichos datos.

Como hemos visto parece que, a la espera de resultados teóricos claros, los modelos de deep learning y el descenso por gradiente han podido avanzar a pesar del problema de la optimización no-convexa y mejorar la tasa de error en muchas tareas de machine learning.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

Blog de WordPress.com.

Subir ↑

A %d blogueros les gusta esto: