Wie funktioniert der Levenberg-Marquardt-Algorithmus im Detail, aber auf verständliche Weise?

StackOverflow https://stackoverflow.com/questions/1136416

Frage

Ich bin ein Programmierer, der lernen möchte, wie der Levenberg-Marquardt-Kurvenanpassungsalgorithmus funktioniert, damit ich ihn selbst implementieren kann.Gibt es irgendwo ein gutes Tutorial, das erklären kann, wie es im Detail funktioniert, wenn der Leser ein Programmierer und kein Mathematiker ist?

Mein Ziel ist es, diesen Algorithmus in OpenCL zu implementieren, damit er hardwarebeschleunigt ausgeführt werden kann.

War es hilfreich?

Lösung

Andere Tipps

eine Funktion zu minimieren ist wie der Versuch, tiefster Punkt auf einer Oberfläche zu finden. Stellen Sie sich auf einem hügeligen Oberfläche zu Fuß und dass Sie versuchen, auf den tiefsten Punkt zu bekommen. Sie würden die Richtung finden, die bergab und zu Fuß geht, bis es nicht bergab mehr geht. Dann würden Sie wählten eine neue Richtung, die bergab und zu Fuß in diese Richtung geht, bis es nicht bergab mehr geht, und so weiter. Schließlich (hoffentlich) würden Sie einen Punkt erreichen, wo keine Richtung bergab mehr geht. Sie würden dann in einem (lokalen) minimal sein.

Der LM-Algorithmus, und viele andere Minimierungsalgorithmen, um dieses Schema verwenden.

Nehmen wir an, dass die Funktion F wird minimiert, und wir sind an dem Punkt, x (n) in unserem Iteration. Wir wollen die nächste Iteration x (n + 1), so dass F (x (n + 1))

Zuerst berechnet eine lineare Näherung an F an dem Punkt x (n). Es ist leicht, die bergabe Richtung einer linearen Funktion, um herauszufinden, so verwenden wir die lineare Annäherung Funktion die Abfahrt Richtung zu bestimmen. Als nächstes müssen wir wissen, wie weit wir in dieser gewählten Richtung gehen. Wenn unsere Annäherung lineare Funktion eine gute Näherung für F für einen großen Bereich um x (n) ist, dann können wir einen ziemlich großen Schritt. Wenn es nur ganz in der Nähe x eine gute Näherung ist (n), dann können wir nehmen nur einen sehr kleinen Schritt.

Dies ist, was LM tut - berechnet eine lineare Annäherung an F bei x (n), so dass die Abfahrt Richtung zu geben, dann rechnet sie heraus, wie groß ein Schritt basierend auf nehmen, wie gut die lineare Funktion angenähert ist bei x F (n ). LM findet heraus, wie gut der approximierenden Funktion grundsätzlich ist ein Schritt in die Richtung so bestimmt und verglichen, wie viel die lineare Näherung F verringert die wie viel die die eigentliche Funktion F verringert nehmen. Wenn sie in der Nähe sind, ist die Näherungsfunktion gut und wir können ein wenig größeren Schritt. Wenn sie nicht in der Nähe sind dann die Näherungsfunktion ist nicht gut, und wir sollten einen kleineren Schritt wieder aus und nehmen.

Die Grundideen des LM-Algorithmus lassen sich auf wenigen Seiten erklären – für eine schnelle und robuste Implementierung in Produktionsqualität sind jedoch viele subtile Optimierungen erforderlich.Stand der Technik ist nach wie vor die Minpack-Implementierung von Moré et al., ausführlich dokumentiert von Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) und im Minpack-Benutzerhandbuch (http://www.mcs.anl.gov/~more/ANL8074b.pdf).Um den Code zu studieren, meine C-Übersetzung (https://jugit.fz-juelich.de/mlz/lmfit) ist wahrscheinlich zugänglicher als der ursprüngliche Fortran-Code.

Versuchen Sie Numerical Recipes (Levenberg-Marquardt in Abschnitt 15,5). Es ist online verfügbar, und ich finde, dass sie Algorithmen in einer Art und Weise zu erklären, die detailliert ist (sie vollständige Quellcode haben, wie viel detaillierteren können Sie bekommen ...), noch zugänglich.

Ich benutzen diese Notizen von einem Kurs an der Purdue University einen generischen Levenberg-Marquardt-Kurvenanpassungsalgorithmus in MATLAB codieren, bis die akzeptiert numerische Derivate und daher berechnet jede Funktion der Form f(x;p) wo p ein Vektor des Anpassungsparameters ist.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top