Algoritmo Levenberg-Marquardt

En la tesis doctoral de Fernández Slezak, publicada el año 2010 con el título “Estimación de parámetros en modelos biológicos complejos: Aplicación a modelos de crecimiento tumoral”, se indica que el objetivo de la optimización es encontrar los parámetros que minimicen la distancia entre los valores experimentales y los de la simulación. Esta distancia, a la que se denomina función de costo, puede ser definida de muchas maneras. Una de las técnicas más utilizadas es la llamada minimización de cuadrados mínimos, cuya función de costo es la suma de las diferencias cuadráticas entre el modelo y los datos. Existe una enorme cantidad de algoritmos aproximados de búsqueda de mínimos locales, que pueden separarse en categorías muy diferentes, por ejemplo métodos de descenso, algoritmos genéticos, etc. Las técnicas para la optimización no lineal de la función de cuadrados mínimos, se agrupan en algoritmos de tres categorías: Métodos de descenso, métodos de búsqueda directa y métodos inspirados en fenómenos físicos. Todos los métodos de minimización no lineal son iterativos, es decir que parten de un punto inicial y el método genera una secuencia de parámetros que, en caso de converger, se acerca a un mínimo local. Entre los métodos más conocidos se encuentra el método de Gauss-Newton, descrito en el artículo de Björck, publicado el año 1996 con el título “Métodos numéricos para problemas de mínimos cuadrados”. El método de minimización Levenberg-Marquardt también pertenece a la familia de problemas llamados métodos de descenso, este algoritmo fue presentado por Levenberg en el artículo publicado el año 1944 con el título “Método para la solución de ciertos problemas no lineales en mínimos cuadrados”, el cual fue complementado con el articulo de Marquardt publicado el año 1963 con el título “Un algoritmo para estimación de mínimos cuadrados de parámetros no lineales”. Este algoritmo propone un esquema de Gauss-Newton amortiguado. Al igual que Gauss-Newton, toma la aproximación lineal del modelo y una determinada dirección de descenso.

El método de Levenberg-Marquardt es conocido hace muchos años, y es altamente utilizado en el ambiente de la optimización, en especial en la minimización de cuadrados mínimos. Por tal motivo, para el uso de este algoritmo, en muchos círculos académicos, se opta por una implementación preexistente de la vasta cantidad de opciones disponibles. Una de las bibliotecas numéricas más conocidas es Linpack, descrita por Bunch y sus colegas en la guía de usuario “Linpack” del año 1979, orientada principalmente a la implementación de rutinas relacionadas con el “algebra lineal para el cálculo de vectores y matrices”. Pensada para el cálculo en supercomputadoras, fue desarrollada a fines de la década de los años 1970 y ha estado en constante evolución desde entonces. Ha sido superada por la biblioteca Lapack, la cual es descrita por Anderson y sus colegas en la guía de usuario de “Lapack” publicada el año 1999. En conjunto con Linpack/Lapack, se desarrolló MinPack, una serie de rutinas dedicadas a la resolución de ecuaciones no lineales y problemas de minimización de cuadrados mínimos, la cual es descrita por Moré y sus colegas en el proyecto “Minpack”, publicado el año 1984.

El algoritmo Levenberg-Marquardt calcula el Jacobiano del modelo con respecto a los parámetros, y utilizando éste busca un mínimo local. El Jacobiano es necesario en cada iteración para calcular la dirección hacia el mínimo local. Debido a que no es bastante difícil el cálculo analítico el Jacobiano es estimado a través de un algoritmo. Para estimar el Jacobiano es necesario realizar numerosas corridas del modelo; por ejemplo, para aproximarlo numéricamente utilizando el método de diferencias finitas centradas es necesario duplicar la cantidad de parámetros variables, que forman parte de las evaluaciones del modelo. El modelo a ser minimizado es muy intensivo en poder de cómputo, por lo que el cálculo del Jacobiano también demanda mucho. Por este motivo se realiza una implementación en paralelo para el cálculo efectivo del Jacobiano. Cada corrida necesaria para la estimación es independiente de la otra, por lo que es trivialmente paralelizable. La implementación de este algoritmo es muy sencilla utilizando un modelo Cliente-Servidor. Al necesitar la estimación del Jacobiano, se reservan nodos para procesamiento. La función para calcular el Jacobiano corre en un nodo principal que distribuye las tareas entre los nodos esclavos disponibles, que sólo espera los parámetros con los cuales deben correr y la señal de inicio. Al recibir esta información, el nodo esclavo ejecuta el modelo con los parámetros recibidos. Luego el amo espera a que cada nodo esclavo haya terminado y junta los resultados de todas las ejecuciones. Por último, realiza el cálculo devolviendo la estimación del Jacobiano.

El algoritmo de retropropagación ha demostrado converger de forma lenta hacia el error mínimo, en especial cuando se tiene una gran cantidad de patrones de entrada. A la fecha existen variados algoritmos que convergen a una velocidad mayor que el algoritmo de retropropagación, como el algoritmo de Levenberg-Marquardt, descrito de manera formal por Bishop, en el libro publicado el año 1995 con el título “Redes neuronales para reconocimiento de patrones”. Hudson y sus colegas, en la guía de usuario publicada el año 2013 con el título “Matlab: Caja de herramientas para redes neuronales”, menciona que este algoritmo se aplica a redes neuronales con un número de patrones de pequeño o mediano tamaño, ya que ocupa demasiada memoria en el cálculo, por lo que su complejidad en cálculos es mayor. Esta mayor complejidad se debe a que se tiene que combinar el gradiente y la aproximación de Gauss-Newton de la matriz Hessiana de la función del error en la regla de actualización de los pesos. El cálculo de la matriz Hessiana es muy costoso computacionalmente hablando, por ello la complejidad del algoritmo crece.