¿Cómo funciona el algoritmo de Levenberg-Marquardt en detalle pero de forma comprensible?
-
16-09-2019 - |
Pregunta
Soy un programador que quiere aprender cómo funciona el algoritmo de ajuste de curvas de Levenberg-Marquardt para poder implementarlo yo mismo.¿Existe algún buen tutorial en algún lugar que pueda explicar cómo funciona en detalle siendo el lector un programador y no un matemático?
Mi objetivo es implementar este algoritmo en opencl para poder ejecutarlo acelerado por hardware.
Solución
- http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm
- Tutorial PDF de Ananth Ranganathan
- JavaNumerics tiene una aplicación bastante legible
- El ICS tiene un rel="noreferrer"> aplicación
Otros consejos
Reducción al mínimo de una función es como tratar de encontrar el punto más bajo en una superficie. Piensa de sí mismo caminando sobre una superficie montañosa y que está tratando de llegar al punto más bajo. Se podría encontrar la dirección que va cuesta abajo y caminar hasta que no se va cuesta abajo más. De allí tendría que elegir una nueva dirección que va cuesta abajo y caminar en esa dirección hasta que no se va cuesta abajo más, y así sucesivamente. Con el tiempo (esperemos) la que se llegaría a un punto en ninguna dirección va cuesta abajo más. A continuación, sería como mínimo (local).
El algoritmo LM, y muchos otros algoritmos de minimización, utilizan este esquema.
Supongamos que la función que se está minimizada es F y estamos en el punto x (n) en nuestra iteración. Deseamos encontrar la siguiente iteración x (n + 1) tal que F (x (n + 1)) Primero, calcular una aproximación lineal a F en el punto x (n). Es fácil averiguar la dirección de descenso de una función lineal, de manera que usamos la función de aproximación lineal para determinar la dirección de descenso.
A continuación, tenemos que saber qué tan lejos podemos ir en esta dirección elegida. Si nuestra función lineal que se aproxima es una buena aproximación para F para una gran área alrededor de x (n), entonces podemos dar un paso bastante grande. Si es una buena aproximación única muy cerca de x (n), entonces podemos tomar sólo un paso muy pequeño. Esto es lo que hace LM - calcula una aproximación lineal a F en x (n), dando así la dirección de descenso, entonces se da cuenta de lo grande que un paso a tomar basa en lo bien que la función lineal se aproxima F en x (n ). LM se da cuenta de lo bien que la función de aproximación es por básicamente teniendo un paso en la dirección así determinada y la comparación de la cantidad de la aproximación lineal a F se redujo a la cantidad de la la función real F disminuyó. Si están cerca, la función de aproximación es buena y podemos tomar un pequeño paso más grande. Si no están cerca entonces la función de aproximación no es buena y que debe retroceder y dar un paso más pequeño.
Las ideas básicas del algoritmo LM se pueden explicar en unas pocas páginas, pero para una implementación de nivel de producción que sea rápida y robusta, se necesitan muchas optimizaciones sutiles.El estado del arte sigue siendo la implementación Minpack de Moré et al., documentada en detalle por Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) y en la guía del usuario de Minpack (http://www.mcs.anl.gov/~more/ANL8074b.pdf).Para estudiar el código, mi traducción C (https://jugit.fz-juelich.de/mlz/lmfit) es probablemente más accesible que el código Fortran original.
Trate Numerical Recipes (Levenberg-Marquardt es en la Sección 15.5). Está disponible en línea, y me parece que explican los algoritmos de una manera que se detalla (tienen el código fuente completo, cuánto más detallada se puede obtener ...), pero accesible.
solía estas notas de un curso en la Universidad Purdue codificar un algoritmo genérico de ajuste de curvas de Levenberg-Marquardt en MATLAB que calcule derivadas numéricas y, por lo tanto, acepte cualquier función de la forma f(x;p)
dónde p
es un vector de parámetros de ajuste.