6.5.16 Implementierung im Log-Raum und numerische Stabilität

6.5.16 Implementierung im Log-Raum und numerische Stabilität

In den vorherigen Abschnitten haben wir den Viterbi-Algorithmus mithilfe von Wahrscheinlichkeiten formuliert, die entlang eines Pfades multipliziert werden. Diese Formulierung ist konzeptionell klar, führt in der Praxis jedoch zu einem ernsthaften Problem.

Das Problem des numerischen Unterlaufs

Wahrscheinlichkeiten liegen zwischen 0 und 1. Wenn viele solcher Werte multipliziert werden, sinkt das Ergebnis exponentiell mit der Sequenzlänge.

Schon moderat große Wahrscheinlichkeiten wie

$$0.3 \cdot 0.4 \cdot 0.2 \cdot 0.5 \cdot 0.1$$

liefern kleine Zahlen. Für realistische biologische Sequenzen mit Hunderten oder Tausenden von Positionen werden die resultierenden Werte so klein, dass sie in Gleitkommaarithmetik nicht mehr zuverlässig dargestellt werden können. Dieses Phänomen bezeichnet man als numerischen Unterlauf.

Eine direkte Implementierung des Viterbi-Algorithmus im Wahrscheinlichkeitsraum ist daher für reale Anwendungen instabil und unzuverlässig.

---

Logarithmische Transformation

Um dieses Problem zu lösen, transformieren wir die Berechnung in den Log-Raum.

Die entscheidende Beobachtung lautet, dass die Multiplikation von Wahrscheinlichkeiten im Log-Raum zu einer Addition wird:

$$\log(a \cdot b) = \log a + \log b$$

Wendet man diese Transformation auf die Viterbi-Rekursion an, erhält man eine numerisch stabile Formulierung.

---

Viterbi-Scores im Log-Raum

Wir definieren den Log-Viterbi-Score:

$$\ell_i(j) = \log v_i(j)$$

Dann wird der Initialisierungsschritt zu:

$$\ell_1(j) = \log \pi_j + \log e_j(x_1)$$

Rekursion im Log-Raum

Der rekursive Schritt lautet nun:

$$\ell_{i+1}(j) = \max_k \bigl( \ell_i(k) + \log t_{kj} + \log e_j(x_{i+1}) \bigr)$$

Hier werden Produkte durch Summen ersetzt, was selbst für lange Sequenzen numerisch stabil bleibt.

Backpointer bleiben unverändert

Wichtig ist, dass sich die Berechnung der Backpointer nicht ändert:

$$b_{i+1}(j) = \arg\max_k \bigl( \ell_i(k) + \log t_{kj} + \log e_j(x_{i+1}) \bigr)$$

Die Struktur des Algorithmus bleibt also identisch; nur die Arithmetik wird verändert.

---

Interpretation

Die Arbeit im Log-Raum liefert zugleich eine nützliche konzeptionelle Umdeutung.

• Statt ein Produkt von Wahrscheinlichkeiten zu maximieren, maximieren wir eine Summe von Log-Wahrscheinlichkeiten
• Dies lässt sich als Akkumulation eines Scores entlang eines Pfades auffassen

In dieser Sicht trägt jede Transition und jede Emission einen additiven Beitrag zum Gesamtscore bei. Der Viterbi-Algorithmus findet dann den Pfad mit dem höchsten Gesamtscore.

Diese Formulierung ist häufig sogar intuitiver, wenn man die relativen Beiträge verschiedener Modellbestandteile verstehen möchte.

---

Umgang mit Nullwahrscheinlichkeiten

Ein praktisches Detail entsteht, wenn Wahrscheinlichkeiten null sind. Da

$$\log 0 = -\infty$$

gilt, sind solche Transitionen oder Emissionen effektiv verboten. In Implementierungen wird dies meist dadurch behandelt, dass unmögliche Ereignisse mit einer sehr großen negativen Zahl oder explizit mit $-\infty$ dargestellt werden.

Dies ist vollständig konsistent mit dem probabilistischen Modell: Eine Wahrscheinlichkeit von null bedeutet, dass ein bestimmter Übergang oder eine bestimmte Emission nicht auftreten kann.

---

Vergleich mit dem Forward-Algorithmus

Es ist erwähnenswert, dass der Viterbi-Algorithmus in seiner Rekursion den Maximumsoperator verwendet, während der Forward-Algorithmus eine Summe über alle Vorgängerzustände bildet.

Im Log-Raum führt dies zu einem wichtigen Unterschied:

• Viterbi:

  $$\max_k (\cdot)$$

• Forward:

  $$\log \sum_k \exp(\cdot)$$

Letzterer Ausdruck ist die log-sum-exp-Operation und erfordert seinerseits besondere numerische Sorgfalt. Wir kehren darauf zurück, wenn wir den Forward-Algorithmus behandeln.

---

Praktische Empfehlung

In der Praxis sollte der Viterbi-Algorithmus immer im Log-Raum implementiert werden. Das gewährleistet:

• numerische Stabilität bei langen Sequenzen
• Robustheit gegenüber Unterlauf
• eine oft intuitivere Interpretation als additive Score-Berechnung

---

Konzeptionelle Zusammenfassung

Die Formulierung im Log-Raum erhält die Struktur des Viterbi-Algorithmus unverändert, macht ihn aber für realistische biologische Daten rechnerisch praktikabel.

• Multiplikation → Addition
• Wahrscheinlichkeiten → Log-Scores
• gleiche Struktur dynamischer Programmierung

Diese Transformation ist eine Standardtechnik probabilistischer Modellierung und wird in weiteren Algorithmen dieses Kapitels erneut auftauchen.

---

Fragen zur Selbstkontrolle

1. Warum führt die Multiplikation vieler Wahrscheinlichkeiten zu numerischem Unterlauf?
2. Wie entschärft die logarithmische Transformation dieses Problem?
3. Was ändert sich in der Viterbi-Rekursion beim Übergang in den Log-Raum?
4. Warum bleibt die Berechnung der Backpointer unverändert?
5. Worin besteht der konzeptionelle Unterschied zwischen dem Maximieren von Wahrscheinlichkeiten und dem Maximieren von Log-Scores?