Beschäftigt man sich mit Wahrscheinlichkeiten, stolpert man früher oder später über Odds beziehungsweise Log-Odds. In vielen Veröffentlichungen wird schlicht geschrieben
„For computational reasons, it is common practice to calculate the so-called log-odds of p(m|z) instead of estimating the posterior p(m|z).“ – Thrun, S. (2003). Learning occupancy grid maps with forward sensor models. Autonomous robots, 1–28.
Doch was heißt das und was sind die „computational reasons“?
Wahrscheinlichkeitsupdate mit BAYES‘-Theorem
Das Speichern von Wahrscheinlichkeitswerten für einen diskreten Raum ist z.B. nötig, wenn man Belegtheitskarten (Occupancy Grids) verarbeiten möchte. Eine Messung mit einem Sensor gibt ein Update für jede betreffende Zelle, weshalb dessen Wahrscheinlichkeit neu berechnet werden muss. Dazu ist die bestehende Wahrscheinlichkeit mit der Trefferwahrscheinlichkeit des Sensors zusammen zu rechnen. Dies geschieht mit Hilfe des BAYES‘-Theorem:
[math]p(m|z_{1:t})=\cfrac{1}{1+\cfrac{1-p(m|z_t)}{p(m|z_t)} \cdot \cfrac{1-p(m|z_1,…,z_{t-1})}{p(m|z_1,…,z_{t-1})}}[/math]
Hierbei wird mit p die Wahrscheinlichkeit bezeichnet, dass die Zelle m belegt ist. Dazu ist Messung z zum Zeitpunkt t hinzuzuziehen und mit der Wahrscheinlichkeit p(m|zt-1) zusammen zu rechnen.
Wahrscheinlichkeit und Odds
Weshalb wandelt man jetzt eine Wahrscheinlichkeit in Odds (=Verhältnis) um? Man kann sich die Notwendigkeit des Verhältnisses (Odds) sehr einfach vorstellen, wenn man als Mensch intuitiv einschätzen soll, wieviel mal wahrscheinlicher es ist, dass ein Ereignis eintritt, wenn die Wahrscheinlichkeit z.B. von 50% auf 91% steigt oder ein zweites Ereignis steigt von 99.9% auf 99.99%.
Wahrscheinlichkeit steigt von 50% auf 91%
Das Verhältnis zwischen der Wahrscheinlichkeit, dass das Ereignis eintritt und der Wahrscheinlichkeit, dass es nicht eintritt, ist das Odds oder auch Quotenverhältnis.
Wahrscheinlichkeit steigt von 99.9% auf 99.99%
Diese Wahrscheinlichkeitssteigerung ergibt im Odds folgende Ergebnisse:
Log-Odds als Lösung für Wahrscheinlichkeiten nahe 1
BAYES mit Log-Odds
Das Update der Wahrscheinlichkeit kann nun auch mit Log-Odds erfolgen. Die Information ist die Gleiche, die Zahl ist nur eine andere.
Grund 1: Rechenzeit für’s Update
Sieht man sich die Update Formel für das BAYES‘-Theorem an, welche weiter oben dargestellt ist, so stellt man fest, dass dort Divisionen notwendig sind. Für ein Update im Log-Odds sind – nach ein paar mathematischen Umformungen – nur Additionen notwendig, was eine höhere Recheneffizienz bedeutet.
Mit dieser Formel kann das Log-Odds sehr schnell ermittelt werden. Bedenkt man, dass ein Occupancy Grid mit der Kantenlänge 10cm und der Ausdehnung von 100x100Meter schon 1 Million Zellen hat, so ist die Rechenzeit ein wichtiger Faktor.
Das Ergebnis muss nun für jede Zelle abgespeichert werden. Hier wartet der 2. Grund, weshalb sich das Log-Odds Format anbietet.
Grund 2: Abspeichern der Wahrscheinlichkeit
Die Wahrscheinlichkeit p müsste abgespeichert werden. Dies könnte man natürlich einfach so tun, z.B. in einer float() Variablen. Diese hat prinzipbedingt nur endlich viele Nachkommastellen. Ein mehrfaches Update dieser Wahrscheinlichkeit (z.B. mit einer hohen p(m|zt)) würde schnell eine Zahl nahe 1.0000000 ergeben, alle nachfolgenden Messungen könnten nicht mehr hinzugerechnet werden, denn durch Rundung bleibt die 1.0000000 abgespeichert.
Man sieht, dass für die Updates schnell die numerisch Grenze erreicht wird. Der Logarithmus verhält sich da wesentlich freundlicher und ermöglicht so, auch im Bereich nahe p=1 noch Updates hinzuzufügen.
Von Log-Odds zurück zur Wahrscheinlichkeit
Nun hat man das Occupancy Grid geupdated und vollständig und möchte zurück zur Belegtheitswahrscheinlichkeit p einer Zelle. Dies lässt sich durch Umstellen relativ einfach berechnen.
[math]p(m|z_1,…,z_t)=1-\cfrac{1}{1+10^{l_\text{t}}}[/math]