Konvertieren (Normalisieren) sehr kleiner Wahrscheinlichkeitswerte in Wahrscheinlichkeit

21

Ich schreibe einen Algorithmus, bei dem ich anhand eines Modells Wahrscheinlichkeiten für eine Liste von Datensätzen berechne und dann jede Wahrscheinlichkeit normalisieren muss. So könnte etwas wie [0,00043, 0,00004, 0,00321] in [0,2, 0,03, 0,77] umgewandelt werden.

Mein Problem ist, dass die Log-Wahrscheinlichkeiten, mit denen ich arbeite, ziemlich klein sind (zum Beispiel im Log-Bereich sind die Werte wie -269647.432, -231444.981 usw.). Wenn ich in meinem C ++ - Code versuche, zwei davon hinzuzufügen (indem ich ihren Exponenten nehme), erhalte ich die Antwort "Inf". Ich habe versucht, sie im Protokollbereich (Summation / Subtraction of log) hinzuzufügen, bin aber wieder auf dasselbe Problem gestoßen.

Kann jemand seine / ihre Expertenmeinung dazu teilen?

Ikram
quelle
Wenn Sie die Funktionen hingewiesen Sie denen log(1+) , haben Sie die Verwendung log1pFunktion in Ihrer Sprache? Dies verwendet die Taylor-Erweiterung um 1.
Neil G
1
Siehe auch einige frühere, verwandte Diskussionen hier
Glen_b -Reinstate Monica

Antworten:

30

Subtrahieren Sie den maximalen Logarithmus von allen Logs. Werfen Sie alle Ergebnisse weg, die so negativ sind, dass sie das Exponential unterlaufen. (Ihre Wahrscheinlichkeiten sind für alle praktischen Zwecke Null.)

In der Tat, wenn Sie eine relative Genauigkeit von (wie z. B. ϵ = 10 - d für d Stellen der Genauigkeit) und Sie n Wahrscheinlichkeiten haben, werfen Sie jedes Ergebnis weg, das kleiner als der Logarithmus von ϵ / n ist . Gehen Sie dann wie gewohnt vor, um die resultierenden Werte zu potenzieren und durch die Summe aller Exponentiale zu dividieren.ϵϵ=10ddnϵ/n

Für diejenigen, die Formeln mögen, seien die Logarithmen mit λ n = max ( λ i ) . Für Logarithmen zur Basis b > 1 definieren Sieλ1,λ2,,λnλn=max(λi)b>1

αi={bλiλn,λiλnlog(ϵ)log(n)0otherwise.

Die normalisierten Wahrscheinlichkeiten sind gleich , i = 1 , 2 , , n . Dies funktioniert, weil das Ersetzen aller ansonsten unterströmenden α i durch Null einen Gesamtfehler von höchstens ( n - 1 ) ϵ / n < ϵ ergibt, wohingegen α n = b λ n - λ n = b 0 =αi/j=1nαji=1,2,,n.αi(n1)ϵ/n<ϵ und alle α i sind nicht negativ, der Nenner A = j α j1 , weshalb der gesamterelativeFehler aufgrund der Nullersetzungsregel streng kleiner ist als ( ( n - 1 ) ϵ / n ) / A < ϵ nach Wunsch.αn=bλnλn=b0=1αiA=jαj1((n1)ϵ/n)/A<ϵ

Um zu viele Rundungsfehler zu vermeiden, berechnen Sie die Summe ausgehend von den kleinsten Werten von . Dies erfolgt automatisch, wenn die λ i zuerst in aufsteigender Reihenfolge sortiert werden. Dies ist eine Überlegung nur für sehr große nαiλin .

Übrigens geht dieses Rezept davon aus, dass die Basis der Protokolle größer als . Für Basen b kleiner als 1 negieren Sie zuerst alle Protokolle und verfahren Sie so, als ob die Basis 1 / b wäre .1b11/b


Beispiel

Lassen Sie es mit Logarithmen drei Werte (natürliche Protokolle, sagen wir) , die gleich - 231444,981 , und - 231444,699. Der letzte ist der größte; es von jedem Wert abgezogen gibt - 38202.733 , - 0.282 , und 0.269647.432, 231444.981,231444.699.38202.733, 0.282,0.

Angenommen, Sie möchten eine Genauigkeit, die mit IEEE-Doppelwerten vergleichbar ist (etwa 16 Dezimalstellen), so dass und n = 3 ist . (Diese Genauigkeit kann man eigentlich nicht erreichen, weil - 0,282 nur für drei signifikante Zahlen angegeben wird, aber das ist in Ordnung: Wir werfen nur Werte weg, die garantiert nicht das Bessere der gewünschten und der tatsächlichen Genauigkeit beeinflussen haben.) Berechne log ( ϵ / n ) = log ( 10 - 16 ) - log ( 3 ) = -ϵ=1016n=30.282log(ϵ/n)log(1016)log(3) Der erste der drei Unterschiede, - 38202.733 , ist kleiner als dieser, also werfen Sie ihn weg und lassen Sie nur - 0.282 und 0. Ihre Exponierung ergibt exp ( - 0.282 ) = 0.754 und exp ( 0 ) = 1 (natürlich). Die normalisierten Werte sind - in der Reihenfolge - 0 für den, den Sieweggeworfen haben, 0,754 / ( 1 + 0,754 ) = 0,430 und 1 / ( 1 +)37.93997.38202.733,0.2820.exp(0.282)=0.754exp(0)=100.754/(1+0.754)=0.430 .1/(1+0.754)=0.570

whuber
quelle
Das ist genial - so einfach und im Nachhinein so offensichtlich. @Ikram, bitte markiere dies als die richtige Antwort! (es sei denn natürlich, Sie haben etwas besseres, in diesem Fall bitte teilen)
Zelanix
2
@whuber müssen wir sogar wegwerfen -38202.733? Eine Exponentiierung, die ohnehin Null ergibt und daher nicht zur Summe beiträgt.
Taylor