Levenberg-Marquardt-Algorithmus: Probleme bei sehr großen und kleinen Zahlen?

23.07.2010, 18:32

Johnny will fitten

Levenberg-Marquardt-Algorithmus: Probleme bei sehr großen und kleinen Zahlen?

Meine Frage:
Hallo liebe Mathematiker!

Ich verwende den Levenberg-Marquardt-Algorithmus in verschiedenen Softwareprogrammen wie z.B. Labview oder gepasi (www.gepasi.org), um Datenpunkte nach verschiedenen Gleichungen zu Fitten, z.B. einen simplen exponentiellen Abfall: Y = A * exp ( - k * X ) + C.

Das funktioniert meistens gut, aber manchmal endet der Algorithmus nach 1-3 Iterationen, ohne dass ich einen schönen Fit erhalte. Ich habe den Eindruck, das der Algorithmus immer dann vorzeitig abbricht, wenn eine der Variablen sehr groß ist (z.B. k = 10^9) im Vergleich zu den anderen Variablen (z.B. A = 1, C = 0).
Kann das eurer Meinung nach sein, dass das ein prinzipielles Problem für den Algorithmus ist, wenn die Werte der Variablen so unterschiedlich groß sind? Wie könnte ich dieses Problem umgehen?

Meine Ideen:
Bei den Startwerten habe ich schon ziemlich viel herumprobiert, und auch wenn ich vernünftige Startwerte kenne, kommt der Algorithmus damit nicht zurecht.
Ich könnte mir vorstellen, dass das bei der Berechnung der Fehlerquadrate problematisch ist, wenn eine Variable einen sehr hohen Wert hat (10^9 oder so) im Vergleich zu den anderen. Aber ich wollte mal die Meinung von euch Mathematikern einholen: Klingt das für euch plausibel?

Das einzige, was mir bisher eingefallen ist, ist folgendes: Statt der Exponentialgleichung Y = A * exp ( - k * X ) + C in welcher ich für k einen sehr hohen Wert erwarten würde (10^6 - 10^9), ersetze ich k durch ( k_start * k' ) so dass k_start eine große Konstante ist (10^6-10^9) und k' meine Variable, für die ich dann eine kleine Zahl (ca. 1) erwarten würde.
Wenn ich dann die Gleichung Y = A * exp ( - k_start * k' * X ) + C fitte, dann funktioniert der Levenberg-Marquardt-Algorithmus problemlos. Abschließend multipliziere ich k' wieder mit k_start, um die gesuchte Variable k zu erhalten. Ich fürchte aber, dass das nicht ganz mathematisch äquivalent ist. Was meint ihr dazu?

Habt ihr vielleicht eine andere Idee, wie ich solche Kurven ordnungsgemäß fitten kann?

Vielen lieben Dank!

30.07.2010, 11:01

Johnny will fitten

Auf diesen Beitrag antworten »

RE: Levenberg-Marquardt-Algorithmus: Probleme bei sehr großen und kleinen Zahlen?
Hallo nochmal!

Scheint, als ob mir hier keiner weiterhelfen kann bei meiner Frage...

Kennt jemand von euch vielleicht ein anderes Forum, wo dieses Thema hinpasst und wo ich es mit meiner Frage noch probieren könnte?

Danke für eure Tipps!

31.07.2010, 19:56

Auf diesen Beitrag antworten »

RE: Levenberg-Marquardt-Algorithmus: Probleme bei sehr großen und kleinen Zahlen?
Mmh... offensichtlich scheinen deine Variablen mit großen Werten ein Problem irgendwo in eine zu lange Schleife zu laufen (beim Dämpfungsparameter?). Hast du mal versucht, ein, zwei Iterationsschritte per Hand durchzuführen oder dir anzeigen zu lassen, welche Schleife wie oft, etc. durchlaufen wird? Dann kommst du dem Problem vllt. auf die Spur.

Auf der anderen Seite sehe ich nicht, warum dein Workaround schlecht sein sollte. Da die Multiplikation ja per se gut konditioniert ist, sollten selbst die Fehler auf deine Werte nicht zu sehr verstärkt werden, wenn ich mir das recht überlege.
Wenn der Plot gut gefittet aussieht, würde ich mir da also keine zu großen Gedanken machen.

Gruß
MI

01.08.2010, 22:22

Johnny will fitten

Auf diesen Beitrag antworten »

RE: Levenberg-Marquardt-Algorithmus: Probleme bei sehr großen und kleinen Zahlen?
Hallo MI, danke für deine Antwort!

@Iterationsschritte per Hand: Ich fürchte, das kann ich nicht ausprobieren, weil das in beiden Programmen ein fix implementierter Algorithmus ist, auf dessen Quellcode ich keinen Zugriff habe. Außerdem wäre das mir als mathematischem Laien wahrscheinlich ohnehin ein bisschen zu hoch, auch wenn es nicht zusätzlich noch in Programmcode gepackt wäre ;-)

@Workaround: Die gefitteten Plots sehen sehr gut aus und liefern auch vernünftige Ergebnisse. Da ich die Mathematik hinter dem Algorithmus aber nicht verstanden habe, hatte ich halt Sorgen, dass ich da irgendwas mache, was eigentlich nicht ganz erlaubt ist...
Es beruhigt mein Gewissen aber jetzt schon mal sehr, dass du als Mathe-Profi keine Einwände gegen meinen Workaround hast :-)

Leider kann ich den nur in LabView anwenden, das andere Programm gibt mir nicht soviele Freiheiten... Aber da lässt sich dann wohl nix machen, denke ich. Bin ja schon sehr froh, dass es zumindest in LabView klappt :-)

Grüße,
Johnny

02.08.2010, 17:14

Auf diesen Beitrag antworten »

RE: Levenberg-Marquardt-Algorithmus: Probleme bei sehr großen und kleinen Zahlen?
Ich versuche dir mal zu erklären, was ich mir dabei gedacht hat. Vllt. hat ja ein richtiger Profi da noch was anderes zu zu sagen Augenzwinkern

.

Das Levenberg-Marquardt-Verfahren (zumindest in der Form, in der ich es kenne) linearisiert eben dein Problem und iteriert dieses dann, wobei noch eine Dämpfung eingebaut wird.

Nehmen wir mal an, deine Funktion ist $\begin{eqnarray*} f(t)=A*e^{-k*t}+C \end{eqnarray*}$ . Mit den Messwerten $\begin{eqnarray*} (t_i,y_i) \end{eqnarray*}$ möchtest du also A,k,C fitten, sodass
$\begin{eqnarray*} A*e^{-k*t_i}+C-y_i \end{eqnarray*}$ möglichst nahe bei Null ist - und zwar für alle Punktepaare. Das "möglichst nahe" wird dann eben durch ein Minimierungsproblem in einer Norm übersetzt, d.h.:

Setze (A,k,C) so, dass
$\begin{eqnarray*} \left\| \begin{pmatrix} A\cdot e^{-k\cdot t_1}+C-y_1 \\ A\cdot e^{-k\cdot t_2}+C-y_2 \\ \vdots \\ A\cdot e^{-k\cdot t_n}+C-y_n\end{pmatrix}\right\|_2 \end{eqnarray*}$
minimal wird. Den Vektor in der Norm nennen wir die Funktion F.

Normalerweise wird dabei die Zweinorm genommen (das ist die euklidischen Norm, also der "normale" Abstand).

Um das Problem zu lösen, wird quasi eine Taylorentwicklung iteriert (wie das Newton-Verfahren für Nullstellensuchen Augenzwinkern

). Das LM-Verfahren minimiert nun statt des obigen Problems folgendes Problem:

Wähle einen Startwert $\begin{eqnarray*} x_0 \end{eqnarray*}$ und iteriere:

Suche $\begin{eqnarray*} s_k \end{eqnarray*}$ sodass
$\begin{eqnarray*} \left\| \begin{pmatrix} F'(x_k) \\ \mu I \end{pmatrix}\cdot s_k+\begin{pmatrix}F(x_k)\\ 0\end{pmatrix} \right\|_2 \end{eqnarray*}$ minimal ist.
Dann gilt: $\begin{eqnarray*} x_{k+1}=x_k+s_k \end{eqnarray*}$

wobei $\begin{eqnarray*} F'(x_k) \end{eqnarray*}$ die Jacobi-Matrix an der Stelle x_k des Problems ist. Der untere Teil der ersten Matrix mit Mu x Einheitsmatrix bringt dir eine Dämpfung und sorgt dafür, dass die Matrix vollen Rang hat. Damit ist das Problem eindeutig lösbar. Zum Lösen gibt's verschiedene Optionen, auf jeden Fall musst du lineare Gleichungssysteme lösen. Zumeist wird die Normalengleichung angewendet.

Der vollständige Algorithmus betrachtet jetzt noch die Dämpfung. Er schaut sich an, ob die iterierte Näherung wirklich eine bessere Näherung ist (also ob wir uns auf das Minimum zubewegen) und verkleinert oder vergrößert die Dämpfung sonst.
Zunächst bestimmt er eben nur eine bestimmte Anzahl von x_k - wenn k groß wird, bricht er ab, da normalerweise die Näherung dann gut genug ist.
Die zweite Abbruchbedingung, die (ohne genau die Implementierung zu kennen) offensichtlich ist, ist die für Mu. Wenn er für EIN k das Mu eine bestimmte Anzahl von Schritten verändert hat, dann wird er irgendwann abbrechen, weil ja nicht klar ist, wie viele Mu er noch ausprobieren muss.
Und ich vermute halt, dass er das genau bei deinem Problem tut. Dafür müsste man wie gesagt einfach mal wissen, womit der Computer anfängt und wie er weitergeht und welches Mu gut ist für die verschiedenen Schritte.

Nun zu deinem Workaround. Ich bin kein Spezialist (gerade nicht in der Anwendung der Verfahren, ich kenne mich nur marginal mit der Theorie aus, da müsste man also wirklich mal mit rumspielen Augenzwinkern

), vllt. übersehe ich also etwas, aber ich würde jetzt folgendes sagen:

Dein Problem, also die Kurve, die du anfittest und die Werte, die du eingibst, sind ja dieselben --> Das Minimum ist dasselbe.
Der Algorithmus durchläuft also im Grunde auch dieselben Schritte.
Der rechte Teil, also das $\begin{eqnarray*} F(x_k) \end{eqnarray*}$ ist also fast genaudasselbe, ob du jetzt mit der eigentlichen Funktion F oder deinem Workaround $\begin{eqnarray*} \overline{F} \end{eqnarray*}$ (oder wie immer du das nennen möchtest) arbeitest.
Was halt passieren könnte ist, dass das lineare Gleichungssystem, was du hinterher lösen musst, eine gravierend andere Kondition hat und dein $\begin{eqnarray*} s_k \end{eqnarray*}$ ziemlich daneben liegt und damit die Iteration in eine falsch Richtung läuft. Normalerweise müsste aber selbst das von der Dämpfung unterbunden werden - und das wiederum würde dazu führen, dass dein Algorithmus im schlimmsten Fall zu früh abbricht und dir nur ne schlechte Näherung liefert. Das würdest du in den Plots sehen.

Gruß
MI

02.08.2010, 20:01

Johnny will fitten

Auf diesen Beitrag antworten »

Danke für deine Mühe :-) Jetzt hab ich zumindest eine Idee, woran es scheitern könnte. Die Information, dass es tatsächlich am Algorithmus liegen KANN, wenn ich keinen guten Fit hinkriege, ist ja auch schon sehr hilfreich.

Wenn ich dich richtig verstanden habe, könnte mein Workaround den Algorithmus höchstens so beeinflussen, dass er das Optimum nicht findet, aber das Optimum muss gleich bleiben.
Wenn ich's mir jetzt nocheinmal überlege: Wenn ich nachher die Originaldaten und den Fit miteinander vergleiche und R² > 0.99 ist, zeigt mir das ja auch schon, dass mein Workaround einwandfreie Ergebnisse liefert, oder?

Vielen Dank jedenfalls für deine Erklärungen smile

02.08.2010, 22:55

Auf diesen Beitrag antworten »

Ja, dass du keine Konvergenz erhälst, kann am Algorithmus liegen.
Die einfachen Fitalgorithmen ohne Dämpfung (z.B. das Gauß-Newton-Verfahren ungedämpft) gewährleisten z.B. überhaupt keine Konvergenz.
Das kann man zwar mit der Dämpfung (dem Mu) grundlegend beheben, aber es kann schwierig sein, eine gute Dämpfung zu finden - und da kann es schon einmal zu einem Abbruch des Verfahrens kommen, weil keine gute Dämpfung gefunden wurde.

Zitat:

Wenn ich dich richtig verstanden habe, könnte mein Workaround den Algorithmus höchstens so beeinflussen, dass er das Optimum nicht findet, aber das Optimum muss gleich bleiben.

Ja, so sehe ich das.
Was zusätzlich passieren könnte ist, dass die Annäherung ans Optimum gravierend schlechter ist als eine Annäherung mit der "richtigen" Angabe. Das Problem wird natürlich umgangen, da du ja dein Workaround nur anwendest, weil der normale Weg schiefgeht und dieser hier bessere Ergebnisse liefert.

Was du mit dem "R^2" sagen möchtest, verstehe ich aber leider nicht.

Gruß
MI

06.08.2010, 22:55

Johnny will fitten

Auf diesen Beitrag antworten »

Re: R²
R² ist ein statistischer Parameter, mit dem man die Güte eines Fits angeben kann. Das Excel macht das z.B. auch für seine Trendlinien, wenn man ein Häkchen bei "Bestimmtheitsmaß anzeigen" setzt. Wenn die Übereinstimmung perfekt ist, ist R² = 1, ansonsten < 1.

Wenn bei meinen Fits das R² passt (>0.9), müsste ich eigentlich aus dem Schneider sein mit meinem Workaround.

Wie man das berechnet, darfst du mich aber nicht fragen - das macht für mich immer der Computer ;-)

Wikipedia kennt es offenbar auch: http://de.wikipedia.org/wiki/Bestimmtheitsma%C3%9F

Liebe Grüße,
Johnny

07.08.2010, 02:05

Auf diesen Beitrag antworten »

Re: R²
Aja, für lineare Modelle scheint das ganze einfach das Quadrat des Korrelationsquotienten zu sein. So etwas hatte ich mir schon gedacht. Ansonsten ist es wohl etwas Ähnliches.
Sagen wir mal, es ist ein weiterer Hinweis darauf, dass deine Anpassung mit dem Workaround gut ist. Als wirklichen Gradmesser sind solche Bestimmtheitsmaße eher nicht geeignet, weil sie zu wenig abbilden.
Solche statistischen Parameter sind immer eine sehr zwiespältige Angelegenheit und werden allzu häufig nicht richtig angewandt (was nicht heißen soll, dass das hier falsch ist Augenzwinkern

- dafür kenne ich mich bei diesem spezifischen Maß nicht aus ).

Fassen wir zusammen:
- mathematisch sehe ich nicht (und da sich niemand eingeschaltet hat wohl auch niemand anderes auf Anhieb), was da grundlegend schief gehen sollte, wenn der Fit vernünftig aussieht. Wenn das Verfahren konvergiert, dann konvergiert es und das Minimum muss dasselbe sein (okay, es ließen sich evtl. exotische Fälle konstruieren, wo es leichte Abweichungen gibt, weil zwei Minima direkt nebeneinanderliegen... aber darum brauchst du dich nicht zu kümmern).
- Die Abweichung zwischen der perfekten Annäherung und dem Fit könnte anders sein (bei dem "richtigen" Verfahren liegt man eventuell nach k Schritten näher am Minimum dran als beim Workaround - allerdings kann das sogar genau anders herum aussehen und genau das vermute ich hier sogar)
- Die Kurve sieht gut gefittet aus (immer ein wichtiger Punkt - sagt meiner Meinung nach sogar mehr aus als dein R^2)
- Dein R^2 ist gut (wie genau das jetzt zu bewerten ist, weiß ich nicht - aber schlecht wird's auf jeden Fall nicht sein).

Fazit: Ich denke das Workaround ist hier ein wunderbarer und korrekter Trick.

Es kann natürlich sein, dass es da noch in irgendeiner Form bessere, speziellere Tricks gibt, wie man in solchen Fällen damit umgeht - da müsstest du dich vermutlich direkt an Numeriker wenden (d.h. an einen Lehrstuhl/Institut für Numerik - per Internetforum geht da vermutlich nicht viel).

Gruß
MI

07.08.2010, 08:13

Johnny will fitten

Auf diesen Beitrag antworten »

Vielen Dank!

Deine Antworten in diesem Forum haben mir wirklich sehr geholfen; jetzt kann ich meinen Workaround beruhigt anwenden. :-) Habe mich auch schon an die Arbeit gemacht und jede Menge Exponentialkurven damit produziert...

Liebe Grüße,
Johnny

Neue Frage »

Antworten »

Levenberg-Marquardt-Algorithmus: Probleme bei sehr großen und kleinen Zahlen?

Verwandte Themen