Comment fonctionne l'algorithme de Levenberg-Marquardt en détail mais de manière compréhensible?
Im un programmeur qui veut apprendre comment la Levenberg–Marquardt curvefitting algorithme fonctionne pour que je puisse l'appliquer moi-même. Est-il un bon tutoriel n'importe où qui peut expliquer comment cela fonctionne dans le détail avec le lecteur étant un programmeur et pas un mathémagicien.
Mon objectif est de mettre en œuvre cet algorithme en opencl, de sorte que je peux l'avoir à accélération matérielle.
source d'informationauteur Per Arneng
Vous devez vous connecter pour publier un commentaire.
En minimisant une fonction, c'est comme essayer de trouver le point le plus bas sur une surface. Pensez-vous marcher sur un parcours vallonné de la surface et que vous essayez d'obtenir le point le plus bas. Vous trouverez la direction de descente et de marcher jusqu'à ce qu'il ne veut pas descendre plus. Ensuite, vous a choisi une nouvelle direction qui va de descente et de marcher dans cette direction jusqu'à ce qu'il ne veut pas descendre plus, et ainsi de suite. Finalement (je l'espère), vous atteignez un point où aucune direction descend plus. Vous serait alors à un (local) minimum.
L'algorithme de LM, et de nombreux autres algorithmes de minimisation, l'utilisation de ce programme.
Supposons que la fonction à minimiser est F, et nous sommes au point x(n) dans notre itération. Nous souhaitons trouver la prochaine itération x(n+1) tel que F(x(n+1)) < F(x(n)), c'est à dire la valeur de la fonction est plus petit. Afin de bien choisir x(n+1) nous avons besoin de deux choses, d'une direction à partir de x(n) et une étape de taille (jusqu'où aller dans cette direction). Le LM algorithme détermine ces valeurs comme suit -
D'abord, calculer une approximation linéaire de F au point x(n). Il est facile de trouver la descente en direction d'une fonction linéaire, donc, nous utilisons l'approximation linéaire de la fonction de déterminer la direction de descente.
Ensuite, nous avons besoin de savoir jusqu'où nous pouvons aller dans cette direction choisie. Si notre approximation de la fonction linéaire est une bonne approximation de F par une large zone autour de x(n), alors on peut prendre une assez grande étape. Si c'est une bonne approximation très proche de x(n), alors on peut prendre seulement un très petit pas.
C'est ce LM ne calcule une approximation linéaire de F à x(n), et donc de donner de la descente direction, puis il détermine comment taille une étape à prendre en fonction de la manière dont le linéaire de la fonction se rapproche de F à x(n). LM chiffres sur l'approximation de la fonction est essentiellement de prendre un pas dans la direction ainsi déterminée et en comparant la façon dont beaucoup de l'approximation linéaire de F a diminué à combien de la fonction réelle F diminué. Si elles sont proches, l'approximation de la fonction est bonne et nous pouvons prendre un peu plus grande étape. Si ils ne sont pas près, puis l'approximation de la fonction n'est pas bonne et nous devons faire marche arrière et de prendre une petite étape.
Les idées de base de l'algorithme de LM peut être expliqué, en quelques pages, mais pour une production de qualité de la mise en œuvre est rapide et robuste, de nombreuses optimisations sont nécessaires. État de l'art est encore la Minpack mise en œuvre par Moré et coll., documentées en détail par la Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) et dans le Minpack guide de l'utilisateur (http://www.mcs.anl.gov/~plus/ANL8074b.pdf). Pour étudier le code, mon C (traduction http:apps.jcns.fz-juelich.de/lmfit) est sans doute plus accessible que l'original du code Fortran.
Essayer Numérique Recettes (Levenberg-Marquardt est dans l'Article 15.5). Elle est disponible en ligne, et je trouve qu'ils expliquent les algorithmes de manière détaillée (ils ont le code source complet, de façon beaucoup plus détaillée pouvez-vous obtenir...), mais accessible.
J'ai utilisé ces notes d'un cours à l'Université de Purdue de code générique de Levenberg-Marquardt courbe d'ajustement de l'algorithme dans MATLAB qui calcule numérique des dérivés et, par conséquent, accepte toute fonction de la forme
f(x;p)
oùp
est un vecteur de paramètres d'appareillage.