Revolución IA

La Inteligencia Artificial está llamada a protagonizar la próxima Revolución tecnológica

Inicio

Sobre Revolucionia

Temas

Para saber más

Contacto

Rendimiento del algoritmo Back-Propagation

Fernando P.    05/01/2018

Temas:  Fundamentos

El entrenamiento supervisado para perceptrones multicapa es una forma de optimización clásica en la que buscamos los valores de los parámetros que minimizan cierta función de coste.

Y el algoritmo Back-Propagation no es más que un método para resolver ese problema de optimización clásica. Como tal, podemos estudiar su rendimiento respecto del tamaño del problema.

Algoritmos en optimización clásica
Un problema de optimización en el sentido clásico está definido por una función real de variables reales, contínua (salvo conjuntos no densos de medida cero). Resolver el problema equivale a encontrar un mínimo local de la función o incluso un mínimo global (optimización global).

Existen muchos algoritmos para atacar este tipo de problemas. En general, todos operan partiendo de un punto más o menos al azar del dominio de la función y, en cada iteración del algoritmo, localizan un nuevo punto, más o menos cercano, para el que el valor de la función es menor. Iterando este proceso muchas veces se termina por llegar a un mínimo local.

Para obtener el nuevo punto en cada iteración, los algoritmos suelen usar alguna de las siguientes estrategias para obtener información sobre la función a optimizar:

• Calcular valores de la función en puntos escogidos
• Calcular el gradiente de la función en el punto actual
• Calcular la matriz hessiana de la función en el punto actual

La mayor parte de algoritmos usan información sobre el gradiente de la función en el punto actual. Es una buena estrategia porque hay garantía de que el valor de la función disminuye en dirección opuesta al gradiente. En general, este tipo de algoritmos se dice que siguen la estrategia de descenso del gradiente, aunque cada uno lo lleva a cabo de un forma un poco distinta.

Rendimiento de un algoritmo en optimización clásica
A la hora de evaluar el rendimiento de un algoritmo en optimización clásica podemos fijarnos en tres cuestiones:

• Número de operaciones que son necesarias para cada iteración del algoritmo
• Número de iteraciones que serán necesarias en promedio para alcanzar un mínimo local
• Número de iteraciones que serán necesarias en promedio para alcanzar un mínimo global

En general, es fácil calcular el número de operaciones que serán necesarias para cada iteración del algoritmo. Este número será una función de la dimensión del dominio de la función a optimizar (número de variables que tiene el problema).

Las otras dos cuestiones no son fáciles de calcular, sobre todo la relativa a localizar un mínimo global, que es algo que ráramente se puede garantizar.

En general, se suelen usar ejemplos reales para evaluar unos y otros algoritmos y medir cuantas iteraciones necesitan unos y otros para alcanzar un mínimo local. Se trata de una medida basada en la práctica.

Normalmente, cuanta más información sobre la función pueda usar un algoritmo (gradiente, matriz hessiana ...), más rápida será su convergencia y menos iteraciones necesitará. Pero usar mucha información impacta negativamente en la velocidad en la que se ejecuta cada iteración (son necesarios más cálculos). Por lo que una convergencia muy rápida pero con iteraciones muy costosas igual no es mejor que una convergencia más lenta con iteraciones muy rápidas.

Back-Propagation y optimización clásica
La tarea de entrenar de forma supervisada un perceptrón multicapa puede ser asimilada perfectamente a un problema de optimización clásica en cuanto que tenemos una función de coste cuyo valor queremos minimizar (idealmente a cero), por la vía de buscar los valores de los pesos en las conexiones entre neuronas del perceptrón, que vienen a ser las variables de un problema de optimización clásica.

Nada impide usar un algoritmo ya conocido en optimización clásica para resolver el problema de entrenar el perceptrón. Pero resulta que se trata de un problema con características bien definidas, de las que podemos extraer información extra para usarla a la hora de resolverlo.

El algoritmo Back-Propagation no es más que una implementación de la idea general de descenso del gradiente que hace uso masivo de la información específica que tenemos sobre esta clase de problemas. Por lo demás, no se diferencia en nada de los algoritmos generales para resolver problemas de optimización clásica.

Rendimiento del algoritmo Back-Propagation
Para evaluar el rendimiento del algoritmo Back-Propagation hacemos exactamente lo mismo que haríamos con un algoritmo general para resolver problemas de optimización clásica.

En primer lugar, es fácil ver que cada iteración del algoritmo Back-Propagation (en el caso de optimizar On-Line, o con un caso de entrada cada vez) resulta en un número de operaciones que es proporcional al número de pesos de la red. Podemos decir que la complejidad del algoritmo en tiempo es del orden de  O(w), donde  w  es el número de pesos de la red (número de variables en optimización clásica).

En el caso de optimizar en forma Batch, la complejidad será proporcional al número de pesos y al número de casos que usemos para cada iteración. Aquí es evidente que si usamos muchos casos de entrenamiento de forma simultánea podemos incurrir fácilmente en una pérdida de velocidad en cada iteración del algoritmo, que se compensa con una convergencia mejorada, de forma similar a como ocurre con los algoritmos generales para optimización clásica.

La complejidad de almacenamiento es también del orden de  O(w), porque en cada iteración lo más complicado que debemos guardar son los valores de los pesos de la red.

Estas complejidades de orden potencial son bastante favorables y son las que hacen que el algoritmo Back-Propagation sea una alternativa muy buena a los métodos clásicos para entrenar un perceptrón multicapa.

Respecto a la velocidad de convergencia, el algoritmo Back-Propagation se comporta de forma similar a cómo lo hacen otros algoritmos que siguen la idea del descenso del gradiente. De hecho, hay modificaciones (como alguna que ya hemos visto aquí) que toman ideas de algoritmos clásicos con objeto de acelerar la convergencia.

En general, el algoritmo Back-Propagation es bastante eficiente para entrenar un perceptrón multicapa y puede ser mejorado fácilmente, además de tener la posibilidad de elegir el tipo de estrategia de entrenamiento más adecuada al tamaño de nuestro problema.

Existen casos en los que se han usado algoritmos generales para optimización clásica en el entrenamiento de perceptriones multicapa pero, en general, no se puede decir que sean mejores que el algoritmo Back-Propagation.

El algoritmo Back-Propagation es una implementación muy inteligente del concepto general de descenso del gradiente para el caso particular de RNA. Tiene una complejidad de ejecución reducida y es una excelente alternativa a otros algoritmos genéricos.

Para saber más:

• Neural Smithing. Supervised Learning in Feedforward Artificial Neural Networks

Libro de Russell Reed y Robert J Marks dedicado a redes neuronales artificiales orientadas hacia adelante. El capítulo 5 introduce el algoritmo Back-Propagation y contiene una discusión sobre su complejidad de ejecución. Capítulos posteriores estudian modificaciones para mejorar la velocidad de convergencia.