Praca z małymi prawdopodobieństwami, za pomocą dzienników

Question

Źródło: Google Code Jam. https://code.google.com/codejam/contest/10224486/dashboard#s=a&a=1

Jesteśmy proszeni o obliczenie Prob (sukcesy K z testów N), gdzie każde z N prób ma znane prawdopodobieństwo sukcesu p_n.

Niektóre analizy i przemyślenia na temat problemu są podawane po wystąpieniu zakleszczenia kodu.

Zauważają, że ocena wszystkich możliwych wyników twoich N testów zajęłaby ci wykładniczy czas w N, więc zamiast tego dostarczają fajne "styl programowania dynamicznego", czyli O (N^2).

Niech P (p # q) = prob (Sukcesy p Po pierwsze próby q) Następnie zaobserwować fakt, że:

Prob(p#q) = Prob(qth trial succeeds)*P(p-1#q-1) + Prob(qth trial fails)*P(p#q-1) 

Teraz budujemy tabelę P (I # j) gdzie i < = j, dla i = 1 ... N

To wszystko piękne - podążam za tym wszystkim i mogę je wdrożyć.

---

Następnie jako ostatni komentarz, mówią:

In practice, in problems like this, one should store the logarithms of 
probabilities instead of the actual values, which can become small 
enough for floating-point precision errors to matter. 

myślę szeroko zrozumieć punkt Próbują zrobić, ale konkretnie nie może dowiedzieć się, jak wykorzystać tę sugestię .

Biorąc powyższe równanie, a substuting w niektórych literach zmienne:

P = A*B + C*D 

Jeśli chcemy pracować w obszaru dziennika, wtedy mamy:

Log(P) = Log(A*B + C*D), 

gdzie mamy rekurencyjnie wstępnie obliczane Log(B) i Log(D) i A & to znane, łatwe w obsłudze miejsca dziesiętne.

Ale nie widzę sposobu, aby obliczyć Log(P), nie robiąc po prostu e^(Log(B)), itp., Co wydaje się, że pokona punkt pracy w przestrzeni dziennika "?

Czy ktoś rozumie bardziej szczegółowo, co mam robić?

Answer 1

Począwszy od początkowego stosunku:

P = A⋅B + C⋅D

Ze względu na symetrię możemy założyć, że B jest większe niż D, bez utraty ogólności. następujące przetwarzanie są użyteczne:

Log (P) = log (A⋅B + C * D) = log (A⋅e ^{log (B)} + C⋅e ^{log (D)}) = log (e ^{log (B)} ⋅ (A + C⋅e ^{log (D) - log (B)})

Log (P) = log (b) + log (A + C⋅e ^{log (D) - log (B)}).

Jest to przydatne, ponieważ w tym przypadku log (B) i log (D) są liczbami ujemnymi (logarytmy niektórych prawdopodobieństw). Założono, że B jest większe niż D, zatem jego log jest bliższy zeru. Dlatego log (D) - log (B) jest nadal ujemny, ale nie tak negatywny jak log (D).

Teraz, zamiast konieczności wykonywania potęgowania log (B) i log (D) osobno, musimy jedynie wykonać potęgowanie log (D) - log (B), który jest liczbą nieznacznie ujemną. Tak więc powyższe przetwarzanie prowadzi do lepszego zachowania liczbowego niż użycie logarytmów i stosowania potęgowania w sposób trywialny, lub, równoważnie, niż w ogóle nie używania logarytmów.