conjugate gradient Schrittweitenadaption
Philipp Kraus
ich benutze einen stochastischen Gradientenabstieg mit
Schrittweitenadaption um eine
Funktion auf Messdaten zu fitten. Generell funktioniert das auch so
ganz gut, nur habe ich
bei einigen Datens�tzen s�tzen das Problem, dass der Feher zuerst in
einem lokalen
Optimium konvergiert und dann pl�tzlich aus dem Optimum wieder
rausspringt und gegen
"unendlich" l�uft.
Das Problem sind definitiv die Anpassung der Schrittweiten. Ich
vergr��ere den Schritt,
falls fich von der n-ten nur (n+1) Iteration kaum etwas ver�ndert hat,
bzw verringere sie,
falls sich das Vorzeichen des Gradienten �ndert. Das Problem scheint
hier darin zu liegen,
dass ich in meiner Fehlerfl�che oszilliere. Wenn er mir eine ann�hernd
gutes lokales Optimum
findet, reicht mir das, das Optimum, das er findet, bevor er
hinausspringt, ist v�llig in Ordnung.
Gibt es eine gute Technik um sinnvolle Schrittweiten und
Schrittweitenadaptionen zu ermitteln,
z.B. w�hrend des iterativen Fittings?
Das Problem tritt nicht generell, sondern nur bei einzelnen Datens�tzen auf.
Unter http://flashpixx.de/cg.jpg ist ein Bild zu sehen. Die
Fehlerfunktion f�r I,B ist genau
wie ich es haben will, f�r sigma,y0 und x0 sieht man, dass sie bis zu
einem gewissen Grad
konvergiert und dann herausspringt. Die erste Reihe sind die zu
fittenden Werte, die zweite
Reihe gibt den Wert pro Iteration des Gradienten an und die dritte
Reihe die Schrittweitenver�nderung.
Danke f�r die Hilfe
Christian Gollwitzer
Philipp Kraus schrieb:
> ich benutze einen stochastischen Gradientenabstieg mit
> Schrittweitenadaption um eine Funktion auf Messdaten zu fitten.
> Generell funktioniert das auch so ganz gut, nur habe ich bei einigen
> Datens�tzen s�tzen das Problem, dass der Feher zuerst in einem
> lokalen Optimium konvergiert und dann pl�tzlich aus dem Optimum
> wieder rausspringt und gegen "unendlich" l�uft.
>
> Das Problem sind definitiv die Anpassung der Schrittweiten. Ich
> vergr��ere den Schritt, falls fich von der n-ten nur (n+1) Iteration
> kaum etwas ver�ndert hat, bzw verringere sie, falls sich das
> Vorzeichen des Gradienten �ndert. Das Problem scheint hier darin zu
> liegen, dass ich in meiner Fehlerfl�che oszilliere. Wenn er mir eine
> ann�hernd gutes lokales Optimum findet, reicht mir das, das Optimum,
> das er findet, bevor er hinausspringt, ist v�llig in Ordnung.
Bei einem stochastischen Verfahren musst Du nat�rlich damit rechnen,
dass das Optimum wieder verlassen wird - das ist ja auch der Vorteil
davon, dass Du aus einem lokalen Minimum herausgekickt werden kannst.
Ich w�rde einfach den bisher besten Wert zus�tzlich speichern, also in
jedem Schritt mit dem bisher besten vergleichen und evtl. ersetzen, und
dam Schluss dann den nehmen. Bzw. davon nochmal einen deterministischen
Gradientenabstieg starten.
Christian
Philipp Kraus
<Christian....@uni-bayreuth.de> said:
> Hallo Philipp,
>
> Philipp Kraus schrieb:
>> ich benutze einen stochastischen Gradientenabstieg mit
>> Schrittweitenadaption um eine Funktion auf Messdaten zu fitten.
>> Generell funktioniert das auch so ganz gut, nur habe ich bei einigen
>> Datens�tzen s�tzen das Problem, dass der Feher zuerst in einem
>> lokalen Optimium konvergiert und dann pl�tzlich aus dem Optimum
>> wieder rausspringt und gegen "unendlich" l�uft.
>>
>> Das Problem sind definitiv die Anpassung der Schrittweiten. Ich
>> vergr��ere den Schritt, falls fich von der n-ten nur (n+1) Iteration
>> kaum etwas ver�ndert hat, bzw verringere sie, falls sich das
>> Vorzeichen des Gradienten �ndert. Das Problem scheint hier darin zu
>> liegen, dass ich in meiner Fehlerfl�che oszilliere. Wenn er mir eine
>> ann�hernd gutes lokales Optimum findet, reicht mir das, das Optimum,
>> das er findet, bevor er hinausspringt, ist v�llig in Ordnung.
>
>
> Bei einem stochastischen Verfahren musst Du nat�rlich damit rechnen,
> dass das Optimum wieder verlassen wird - das ist ja auch der Vorteil
> davon, dass Du aus einem lokalen Minimum herausgekickt werden kannst.
Das ist auch klar. Habe ich inzwischen korrigiert
> Ich w�rde einfach den bisher besten Wert zus�tzlich speichern, also in
> jedem Schritt mit dem bisher besten vergleichen und evtl. ersetzen, und
> dam Schluss dann den nehmen. Bzw. davon nochmal einen deterministischen
> Gradientenabstieg starten.
Es ging mir um den eigentlichen Adaptionsschritt, da ich die
Schrittweiten dynamisch ver�ndere kann ich halt Plataus bzw
Oszilationen entgegen wirken, nur wie bestimme ich "gute" Schrittweiten?
Danke
Phil
Vogel
news:hd9jo9$8b1$1...@online.de:
> On 2009-11-09 13:29:54 +0100, Christian Gollwitzer
> <Christian....@uni-bayreuth.de> said:
>
>> Hallo Philipp,
>>
>> Philipp Kraus schrieb:
>>> ich benutze einen stochastischen Gradientenabstieg mit
>>> Schrittweitenadaption um eine Funktion auf Messdaten zu fitten.
>>> Generell funktioniert das auch so ganz gut, nur habe ich bei einigen
>>> Datens�tzen s�tzen das Problem, dass der Feher zuerst in einem
>>> lokalen Optimium konvergiert und dann pl�tzlich aus dem Optimum
>>> wieder rausspringt und gegen "unendlich" l�uft.
>>>
>>> Das Problem sind definitiv die Anpassung der Schrittweiten. Ich
>>> vergr��ere den Schritt, falls sich von der n-ten nur (n+1) Iteration
>>> kaum etwas ver�ndert hat, bzw verringere sie, falls sich das
>>> Vorzeichen des Gradienten �ndert. Das Problem scheint hier darin zu
>>> liegen, dass ich in meiner Fehlerfl�che oszilliere. Wenn er mir eine
>>> ann�hernd gutes lokales Optimum findet, reicht mir das, das Optimum,
>>> das er findet, bevor er hinausspringt, ist v�llig in Ordnung.
>>
>>
>> Bei einem stochastischen Verfahren musst Du nat�rlich damit rechnen,
>> dass das Optimum wieder verlassen wird - das ist ja auch der Vorteil
>> davon, dass Du aus einem lokalen Minimum herausgekickt werden kannst.
>
> Das ist auch klar. Habe ich inzwischen korrigiert
>
>> Ich w�rde einfach den bisher besten Wert zus�tzlich speichern, also
>> in jedem Schritt mit dem bisher besten vergleichen und evtl.
>> ersetzen, und dam Schluss dann den nehmen. Bzw. davon nochmal einen
>> deterministischen Gradientenabstieg starten.
>
> Es ging mir um den eigentlichen Adaptionsschritt, da ich die
> Schrittweiten dynamisch ver�ndere kann ich halt Plataus bzw
> Oszilationen entgegen wirken, nur wie bestimme ich "gute"
> Schrittweiten?
>
Indem du durch die Wahl der Schrittweite Oszilationen entgegen wirkst.
>
-- Selber denken macht klug.
Philipp Kraus
Das ist sicherlich keine sinnvolle Antwort. Mir ist schon klar, dass ich
Plateaus mit gro�en Schritten �berspringen kann, Oszillation mit kleinen
umgehe. Ebenfalls ist auch klar, dass das Vorzeichen des Gradienten
�ndert, wenn man ein Minimum �bersprungen hat und somit kann
ich den Schritt und die Schrittweite ver�ndern, so dass ich ihn r�ckg�ngig
machen kann. Ebenfalls kann ich durch einen gewissen Zusatz eines
Zufallsfaktors lokale Extrema evtl umgehen kann.
Mir geht es hier nicht um diese pauschale Antwort "passe die Schrittweite an",
sondern _wie_ man sie hinreichend gut anpasst. Vor allem sollte schon in
den vorhergehenden Postings klar sein, dass ich schon eine dynm. Anpassung
verwenden, aber die im Moment keine guten Ergebnisse liefert
Vogel
> On 2009-11-10 05:36:15 +0100, Vogel <vo...@hotmail.com> said:
>
>>>
>>> Es ging mir um den eigentlichen Adaptionsschritt, da ich die
>>> Schrittweiten dynamisch ver�ndere kann ich halt Plataus bzw
>>> Oszilationen entgegen wirken, nur wie bestimme ich "gute"
>>> Schrittweiten?
>>>
>> Indem du durch die Wahl der Schrittweite Oszilationen entgegen
>> wirkst.
>
> Das ist sicherlich keine sinnvolle Antwort.
>
Aber doch, war ja nur ein Hinweis.
>
> Mir geht es hier nicht um diese pauschale Antwort "passe die
> Schrittweite an", ...
>
Deswegen schrieb ich ja wie du sie anpassen sollst.
Christian Gollwitzer
Philipp Kraus schrieb:
> On 2009-11-09 13:29:54 +0100, Christian Gollwitzer
>>> Das Problem sind definitiv die Anpassung der Schrittweiten. Ich
>>> vergr��ere den Schritt, falls fich von der n-ten nur (n+1) Iteration
>>> kaum etwas ver�ndert hat, bzw verringere sie, falls sich das
>>> Vorzeichen des Gradienten �ndert. Das Problem scheint hier darin zu
>>> liegen, dass ich in meiner Fehlerfl�che oszilliere.
ich kenne ein paar Ideen dazu, bin aber kein Experte. Wenn Du hier gar
keine sinnvollen Antworten bekommst, solltest Du vielleicht mal in
sc.math.num-analysis nachfragen. Was sich vielleicht lohnt zu probieren:
1) Reduziere die die Schrittweite mit einem Faktor, der von der Zahl an
Iterationen abh�ngt. Damit erzwingst Du nach einer gewissen Zeit die
Konvergenz.
2) Simulated Annealing. Wenn Dein Schritt den Fehler erh�ht, dann gehe
nur mit einer Wahrscheinlichkeit exp(-T) nach oben, anderenfalls
reduziere die Schrittweite und gehe in Gegenrichtung. T ("Temperatur")
wird langsam mit der Zahl der Iterationen erniedrigt, so dass das
Verfahren schlie�lich nur noch abw�rts l�uft.
3) Du kennst vermutlich die Gr��e des Minimums ungef�hr aus der Anzahl
Deiner Datenpunkte und deren Fehler. Also kannst Du die Schrittweite
auch am Schluss damit skalieren.
4) Restart. D.h., wenn der Algorithmus zu einem Wert konvergiert ist,
dann startest Du von dort aus komplett neu. Bei conjugate gradient ist
irgendwann das Vorwissen ein Ballast.
Aber wie gesagt, bin kein Experte...
Christian
Philipp Kraus
<Christian....@uni-bayreuth.de> said:
> Hallo Philipp,
>
> Philipp Kraus schrieb:
>> On 2009-11-09 13:29:54 +0100, Christian Gollwitzer
>>>> Das Problem sind definitiv die Anpassung der Schrittweiten. Ich
>>>> vergr��ere den Schritt, falls fich von der n-ten nur (n+1) Iteration
>>>> kaum etwas ver�ndert hat, bzw verringere sie, falls sich das
>>>> Vorzeichen des Gradienten �ndert. Das Problem scheint hier darin zu
>>>> liegen, dass ich in meiner Fehlerfl�che oszilliere.
>
>
> ich kenne ein paar Ideen dazu, bin aber kein Experte. Wenn Du hier gar
> keine sinnvollen Antworten bekommst, solltest Du vielleicht mal in
> sc.math.num-analysis nachfragen. Was sich vielleicht lohnt zu probieren:
Hi,
danke, das probiere ich schon teilweise
>
> 1) Reduziere die die Schrittweite mit einem Faktor, der von der Zahl an
> Iterationen abh�ngt. Damit erzwingst Du nach einer gewissen Zeit die
> Konvergenz.
das habe ich zurzeit im Test und es liefert schon bessere Ergebnisse,
die Konvergenz ist zwar langsamer, aber numerisch stabiler
>
> 2) Simulated Annealing. Wenn Dein Schritt den Fehler erh�ht, dann gehe
> nur mit einer Wahrscheinlichkeit exp(-T) nach oben, anderenfalls
> reduziere die Schrittweite und gehe in Gegenrichtung. T ("Temperatur")
> wird langsam mit der Zahl der Iterationen erniedrigt, so dass das
> Verfahren schlie�lich nur noch abw�rts l�uft.
Das teste ich, ich normiere aber den Gradient (den Vektor f�r alle
Dimensionen) auf 1, damit funktioniert das auch schon besser
>
> 3) Du kennst vermutlich die Gr��e des Minimums ungef�hr aus der Anzahl
> Deiner Datenpunkte und deren Fehler. Also kannst Du die Schrittweite
> auch am Schluss damit skalieren.
leider nicht, das w�re sch�n. Ich habe hier mehrere Datens�tze, bei
einigen l�uft es ohne Probleme durch und bei anderen knallt es eben
numerisch. Teilweise mag auch das Rauschen ca 30-40% schuld sein.
> 4) Restart. D.h., wenn der Algorithmus zu einem Wert konvergiert ist,
> dann startest Du von dort aus komplett neu. Bei conjugate gradient ist
> irgendwann das Vorwissen ein Ballast.
Das habe ich auch schon probiert, bringt aber keinen Unterschied. DIe
Startwerte die ich ermittel liegen schon recht gut, so dass ich auch im
Hinblick auf das Rauschen keine wirkliche Verbesserung habe bzw die
sich nur in etwas weniger Iterationen niederschl�gt.
Das mit der Wahrscheinlichkeit werde ich aber noch mal probieren
Danke, die Tips waren wirklich hilfreich, da ich schon recht lange an
dem Problem sitze