Eine Summe numerisch stabil machen
-
Hej Leute,
ich hab folgendes Problem:
eine Summe die aussieht wie folgt:
s=w\_1x\_1 x\_1^T+w\_2x\_2 x\_2^T+\dots+w\_nx\_n x_n^T
die w_i haben die Form
w\_i = \frac{e^{E\_i}}{e^{E\_1}+\dots+e^{E\_n}}
die x_i sind Vektoren mit 768 Elementen und die Elemente von x_i sind zwischen 0 und 1.
Leider ist n sehr Groß (2^20 oder mehr), so dass wir nicht alle w_i und x_i speichern können. deswegen berechnen wir die Summe als
s'=e^{E\_1}x\_1 x\_1^T+\dots+e^{E\_n}x\_n x\_n^T
n=e^{E\_1}+\dots+e^{E\_n}
Bei kleinen Testproblemen funktioniert das ganz gut. Bei dem großen Problem, das uns aber interessiert, bekommen wir in n ein Overflow-Problem weswegen wir dort bereits auf long double ausgewichen sind.
Die Vektoren selbst haben wir bislang noch auf double gelassen, da wir gerne die Implementation mittels BLAS-dsyrk ausführen wollten und es keine Implementation für long double gibt. Leider scheint aber in s nach unserer Methode nur noch Müll drin zu stehen.
Gibt es vielleicht noch einen Weg, wie wir die SItuation verbessern können? Ich habe von Numerik nicht so viel Ahnung und weiß nur, dass solche Summen eigentlich relativ knifflig sind.//edit formeln gefixt und late xhinzugefügt. awesome dass das wieder geht.
-
otze schrieb:
Leider scheint aber in s nach unserer Methode nur noch Müll drin zu stehen.
Warum? Ist das auch ein Overflow-Problem oder ist es ein Genauigkeitsproblem, weil Summanden ganz unterschiedlicher Größenordnung auftauchen?
-
Überläufe treten scheinbar nicht auf. Aber die Summe berechnet einen Gradienten und der zeigt irgendwann (ca wenn n nicht mehr in double passt) konsequent in die falsche Richtung. Die Vorzeichen stimmen also nicht mehr. Auch die frobenius-norm der so berechneten Matrix scheint zu klein zu sein. Die Optimierungsschritte anhand des Gradienten sind also sehr klein.
Es kann gut sein, dass in der Summe die Größenordnungen relativ unterschiedlich sind. Allerdings in der Art von wegen: wenige Zustände haben einen großen Wert, aber viele kleine Zustände machen immer noch die Masse der Gewichte aus.
//edit man muss dazu sagen, dass der Code extrem gut getestet ist. Wenn wir den Gradienten schätzen (E_i = 0 mit x_i aus der Verteilung gezogen), dann bekommen wir den richtigen Gradientenabstieg raus. Auch die Summe n stimmt, also lassen wir nicht zum Beispiel einzelne Beispiele raus oder ähnliches. da wir aber bei dem Datensatz immer Probleme mit der Numerik haben, würde ich schätzen, dass das auch hier zutrifft.
-
Wenn es tatsächlich daran liegen sollte, dass sich die Größenordnungen der Summanden stark unterscheiden, dann würde es helfen, wenn Ihr die Summanden irgendwie sortieren könntet und von kleinen Absolutbeträgen nach großen aufsummiert. Allerdings habe ich Zweifel, dass das der Punkt ist. Dafür erscheint mir der Effekt zu groß zu sein.
Viel wahrscheinlicher ist, dass es doch irgendwo einen Überlauf gibt.
IMHO. ...allerdings habe ich mit derartigen Fehlern selbst auch keine Erfahrung. Wenn s' von der gleichen Größenordnung wie "norm" ist, dann wäre das sowieso anzunehmen. Warum sollte man den größeren Wertebereich dann nur in einer der beiden Größen benötigen? ...vielleicht tritt so ein Überlauf auch in einem Zwischenschritt bei der Berechnung von s' auf. Das ist sogar sehr wahrscheinlich. Es ist gut möglich, dass sich unterschiedliche Summanden gegenseitig wegheben, was natürlich nicht mehr funktioniert, wenn es zwischendrin einen Überlauf gibt. Auch hier müsstet Ihr die Summanden irgendwie sortieren, so dass sich die entsprechenden Summanden schnell gegenseitig wegheben. Dann würde ich das in so eine Art alternierende Summe mit wachsenden Absolutbeträgen umschreiben. Vielleicht auch nicht alternierend, sondern so, dass man sich an den bisher aufsummierten Absolutbeträgen orientiert.
EDIT: 2^20 ist nicht sooo groß. Ihr könntet dann zumindest die Zwischenwerte s_i = e^E_i x_i x_i^T speichern.
-
Falls die Summanden (hier also die Gewichte, die x_i sind ja alle >= 0) unterschiedliche Vorzeichen haben, sind Auslöschungen noch ein bliebtes Problem.
-
Do könntest auch mal eine Kahan-Summation ausprobieren.
PS:
Latex Quellcode ist schrecklich lesbar.
-
Bitte ein Bit schrieb:
Latex Quellcode ist schrecklich lesbar.
dann mach javascript an ;).
Ich melde mich wieder, wenn wir uns am Montag nochmal darüber gebäugt haben. Sie meinte noch, dass sie die Tage was geändert hat und dass sich nun vielleicht dort der Bug befindet...