¿Cómo funciona el algoritmo de Levenberg-Marquardt en detalle pero de forma comprensible?

Question

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.

Answer 1

• 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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.