Hidden-Markov-Modelle: der Viterbi-Algorithmus und das unehrliche Kasino

Hidden-Markov-Modell, die drei Probleme nach Rabiner, Vorwärts-Algorithmus, Viterbi-Algorithmus, A-posteriori-Dekodierung und Baum-Welch-Algorithmus — an einem Kasino, das ab und zu heimlich den Würfel gegen einen gezinkten tauscht.

14 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 39 von 52

1. Landkarte der künstlichen Intelligenz: was was ist und wie alles zusammenpasst
2. Eine kurze Geschichte der künstlichen Intelligenz: von Turing bis zu Sprachmodellen
3. Daten, Modell, Training, Inferenz: die Grundbegriffe an einem einzigen Beispiel
4. Mathematische Notation lesen: Symbole, Indizes, Summen und Quantoren
5. Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen
6. Funktionen und Abbildungen: warum jedes KI-Modell eine Funktion ist
7. Logik und Beweise: die Regeln, nach denen KI schließt
8. Graphen und Bäume: die Struktur, auf der Suche und neuronale Netze stehen
9. Lineare Algebra für maschinelles Lernen: Vektoren, Matrizen und warum KI vor allem multipliziert
10. Ableitungen, Gradient und Kettenregel: wie ein Modell herausfindet, in welche Richtung es lernen soll
11. Gradientenabstieg: wie ein Modell lernt
12. Was ist Wahrscheinlichkeit: vom Würfelwurf zu den Kolmogorow-Axiomen
13. Bedingte Wahrscheinlichkeit und der Satz von Bayes: wie du deine Einschätzung änderst, wenn du etwas Neues erfährst
14. Zufallsvariable und Verteilungsfunktion: eine Funktion, die alles über eine Verteilung verrät
15. Dichtefunktion und Wahrscheinlichkeitsfunktion: warum eine stetige Zufallsvariable in einem Punkt die Wahrscheinlichkeit null hat
16. Erwartungswert, Varianz und Kovarianz: wo eine Verteilung liegt, wie breit sie ist und was womit zusammenhängt
17. Überblick über Wahrscheinlichkeitsverteilungen: Bernoulli-, Binomial-, Poisson-, Gleich-, Normal- und Exponentialverteilung
18. Gesetz der großen Zahlen und zentraler Grenzwertsatz: Warum sich Durchschnitte so vorhersagbar verhalten
19. Statistik und Parameterschätzung: Maximum Likelihood, MAP und Konfidenzintervalle
20. Informationstheorie: Entropie, Kreuzentropie und KL-Divergenz — woher Verlustfunktionen kommen
21. Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen
22. Spiele und Gegner: Minimax, Alpha-Beta-Suche und Monte Carlo Tree Search
23. Constraint Satisfaction: Backtracking, Constraint-Propagierung und AC-3 an Sudoku und einer Karte tschechischer Regionen
24. Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme
25. Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten
26. Lokale Suche und simulierte Abkühlung: ein Handlungsreisender durch die tschechischen Regionalhauptstädte
27. Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung
28. Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz
29. Ameisenkolonieoptimierung: wie eine Pheromonspur einen kurzen Weg findet
30. Partikelschwarmoptimierung: Trägheit, eigene Erfahrung und die Erfahrung des Schwarms
31. Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT
32. Fuzzy-Mengen und Zugehörigkeitsfunktionen: wie man „etwas warm“ aufschreibt
33. Fuzzy-Logik und Wahrscheinlichkeit: warum „etwas warm“ nicht „wahrscheinlich warm“ bedeutet
34. Fuzzy-Logik: t-Normen, Implikationen und WENN–DANN-Regeln
35. Fuzzy-Regelung: Mamdani und Sugeno vom Ventilator bis zum Pendel auf dem Wagen
36. Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern
37. Neuro-Fuzzy-Systeme (ANFIS): Fuzzy-Regeln, die aus Daten lernen
38. Markow-Ketten: Übergangsmatrix, stationäre Verteilung und PageRank
39. Hidden-Markov-Modelle: der Viterbi-Algorithmus und das unehrliche Kasino
40. Bayessche Netze: warum das Gras nass ist und was das für den Rasensprenger bedeutet
41. Der Kalman-Filter: wie man aus ungenauen Messungen schätzt, wo ein Auto ist und wie schnell es fährt
42. Arten des maschinellen Lernens: überwacht, unüberwacht, halbüberwacht und mehr
43. Prompts, Kontext und RAG: wie man einem Modell die richtigen Informationen gibt
44. Variational Autoencoder (VAE): neue Bilder aus einem stetigen latenten Raum
45. Generative Adversarial Networks (GAN): der Fälscher gegen den Detektiv
46. Diffusionsmodelle: wie aus reinem Rauschen ein Bild wird
47. Markow-Entscheidungsprozesse: Zustände, Aktionen, Belohnungen und Bellman-Gleichungen
48. Q-Learning und DQN: den Wert von Aktionen lernen, von der Tabelle bis zum neuronalen Netz
49. Policy Gradient und PPO: die Strategie direkt lernen
50. Wie ein KI-Agent funktioniert: ein Sprachmodell in einer Schleife mit Werkzeugen
51. Programmieren mit KI-Agenten: Auftrag, Tests und Kontrolle
52. Bewertung und Sicherheit von KI-Systemen: wie man misst und wie man überwacht

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Im letzten Teil haben wir den Zustand der Kette gesehen: Heute scheint die Sonne, morgen regnet es. Oft sehen wir aber nur seine Auswirkungen. Ein Mikrofon nimmt eine Schallwelle auf, nicht das Wort, das sie erzeugt hat. Ein Sequenzierer liest die Buchstaben der DNA, nicht, wo ein Gen beginnt. Und im Kasino sehen wir, welche Zahl gefallen ist, nicht, mit welchem Würfel der Croupier wirft. Hidden-Markov-Modelle sind Ketten, deren Zustände wir nicht sehen — samt Algorithmen, mit denen sich trotzdem herausfinden lässt, was im Inneren vorgeht. Jahrzehntelang beruhte die Spracherkennung auf ihnen.

Er knüpft an den Teil Markow-Ketten an.

1. Das unehrliche Kasino

Das klassische Lehrbuchbeispiel (Durbin u. a., 1998): Der Croupier wirft entweder mit einem fairen oder mit einem gezinkten Würfel, bei dem die Sechs mit Wahrscheinlichkeit 1/2 fällt und jede andere Zahl mit 1/10. Nach jedem Wurf tauscht er mit Wahrscheinlichkeit 0,05 den fairen gegen den gezinkten und mit Wahrscheinlichkeit 0,1 den gezinkten zurück gegen den fairen. Den Tausch sehen wir nicht. Wir sehen nur eine Reihe von Zahlen — in unserem Versuch 300 Würfe, die so beginnen:

163665521623524236522511663566613666222461626262162666626516…

Wir fragen: Wird hier ehrlich gespielt? Und wenn nicht, wann genau war der gezinkte Würfel im Spiel?

2. Hidden-Markov-Modell

Definition — Hidden-Markov-Modell

Ein Hidden-Markov-Modell (HMM) λ = (π, A, B) hat verborgene Zustände 1, …, N und beobachtbare Symbole 1, …, M:

• die verborgenen Zustände X₁, X₂, … bilden eine Markow-Kette mit der Anfangsverteilung π und der Übergangsmatrix A, a_ij = P(X_t+1 = j | X_t = i);
• zu jedem Zeitpunkt erzeugt der Zustand X_t = i eine Beobachtung O_t gemäß den Emissionswahrscheinlichkeiten b_i(o) = P(O_t = o | X_t = i), unabhängig von allem anderen.

Aus der Definition folgt, wie wahrscheinlich eine konkrete „Geschichte“ ist: eine Folge von Würfeln x = (x₁, …, x_T) zusammen mit den Würfen O = (O₁, …, O_T).

P(x, O | λ) = π_x1 b_x1(O₁) · ∏_t=2^T a_{xt−1 xt} b_xt(O_t)

π_x1

der erste Würfel hat keinen Vorgänger, von dem man zu ihm übergehen könnte — seine Wahrscheinlichkeit gibt die Anfangsverteilung an

a_{xt−1 xt}

jeder weitere Würfel hängt nur vom vorherigen ab (Markow-Eigenschaft), also genügt für jeden Schritt eine Zahl aus der Matrix A

b_xt(O_t)

der Wurf hängt nur von dem Würfel ab, mit dem gerade geworfen wird — wir nehmen die Wahrscheinlichkeit der Zahl, die tatsächlich gefallen ist

∏_t=2^T

allgemein würde man Wahrscheinlichkeiten multiplizieren, die von der ganzen Vergangenheit abhängen (Kettenregel); die beiden Unabhängigkeitsannahmen aus der Definition kürzen sie auf diese lokalen Zahlen, und deshalb ist das Ganze ein einfaches Produkt

Beispiel — zwei Geschichten der ersten drei Würfe

Unsere Reihe beginnt mit den Würfen 1, 6, 3. Bezeichnen wir mit F den fairen und mit G den gezinkten Würfel. Die Geschichte „dreimal gezinkt“:

P(GGG, 1, 6, 3) = 0,5 · 0,1 · 0,9 · 0,5 · 0,9 · 0,1 = 0,002025,

die Geschichte „dreimal fair“:

P(FFF, 1, 6, 3) = 0,5 · ¹/₆ · 0,95 · ¹/₆ · 0,95 · ¹/₆ = 0,002089.

Die faire Geschichte ist um ein Haar wahrscheinlicher: Die Sechs bekommt beim gezinkten Würfel zwar 0,5 statt ¹/₆, die Eins und die Drei aber nur 0,1 statt ¹/₆. (In der Simulation wurden übrigens alle drei Würfe mit dem gezinkten Würfel geworfen — aus drei Würfen lässt sich das nicht erkennen.)

Lawrence Rabiner fasste in seiner berühmten Übersicht von 1989 zusammen, was man mit einem solchen Modell tun kann, und zwar in drei Aufgaben: Bewertung (wie wahrscheinlich ist die beobachtete Reihe?), Dekodierung (welche verborgenen Zustände steckten am wahrscheinlichsten dahinter?) und Lernen (welche Parameter hat das Modell, wenn wir nur die Beobachtungen kennen?). Für jede gibt es einen eleganten Algorithmus.

3. Wie wahrscheinlich ist die Reihe: der Vorwärts-Algorithmus

Die Wahrscheinlichkeit der beobachteten Reihe ist eine Summe über alle möglichen Folgen verborgener Zustände. Davon gibt es bei 300 Würfen und zwei Würfeln 2³⁰⁰ ≈ 2 · 10⁹⁰ — mehr, als es Atome im Universum gibt. Direkt aufsummieren lässt sich das nicht. Die Markow-Eigenschaft erlaubt es aber, schrittweise zu rechnen.

Beispiel — Wahrscheinlichkeit von drei Würfen als Summe über alle Geschichten

Die Wahrscheinlichkeit der Beobachtung ist die Summe der gemeinsamen Wahrscheinlichkeit über alle möglichen Geschichten: P(O | λ) = ∑_x P(x, O | λ). Für die Würfe 1, 6, 3 gibt es 2³ = 8 davon:

Geschichte	P(x, O)
FFF	0,002089
FFG	0,000066
FGF	0,000035
FGG	0,000188
GFF	0,000132
GFG	0,000004
GGF	0,000375
GGG	0,002025
Summe	0,004913

Jede Geschichte kostet 2T − 1 = 5 Multiplikationen, zusammen 8 · 5 = 40. Für T Würfe sind es (2T − 1) · 2^T — bei 300 Würfen unvorstellbar viele.

Algorithmus — Vorwärts-Algorithmus

Sei α_t(j) = P(O₁, …, O_t, X_t = j). Dann gilt

α₁(j) = π_j b_j(O₁),   α_t+1(j) = [∑_i α_t(i) a_ij] b_j(O_t+1),   P(O | λ) = ∑_j α_T(j).

Die Berechnung dauert O(N² T) statt O(N^T). Damit die Zahlen nicht unterlaufen, wird α_t in jedem Schritt normiert, und man summiert die Logarithmen der Normierungskonstanten.

α_t+1(j) = ∑_i α_t(i) a_ij · b_j(O_t+1)

α_t(i)

alles, was wir über die Vergangenheit wissen: die Wahrscheinlichkeit der bisherigen Würfe und dafür, dass jetzt der Würfel i im Spiel ist; in dieser einen Zahl sind alle Geschichten zusammengefasst, die in i enden

a_ij

ein Schritt der Kette von i nach j; dank der Markow-Eigenschaft spielt es keine Rolle, wie wir nach i gekommen sind

∑_i

wir wissen nicht, mit welchem Würfel zuletzt geworfen wurde, und nach j gelangt man von jedem aus — deshalb summieren wir über alle Möglichkeiten (die Geschichten sind einander ausschließende Ereignisse)

b_j(O_t+1)

den neuen Wurf muss der Würfel j tatsächlich erzeugen; er hängt nicht von i ab und lässt sich daher vor die Summe ziehen

Beispiel — Vorwärts-Algorithmus für die Würfe 1, 6, 3

Start: α₁(F) = 0,5 · ¹/₆ = 0,0833, α₁(G) = 0,5 · 0,1 = 0,0500. Der zweite Wurf ist eine Sechs:

α₂(F) = (0,0833 · 0,95 + 0,0500 · 0,1) · ¹/₆ = 0,0140,
α₂(G) = (0,0833 · 0,05 + 0,0500 · 0,9) · 0,5 = 0,0246.

t	Wurf	αt(F)	αt(G)	Summe = P(O1, …, Ot)	ct
1	1	0,0833	0,0500	0,133333	0,1333
2	6	0,0140	0,0246	0,038611	0,2896
3	3	0,0026	0,0023	0,004913	0,1273

Die Summe in der letzten Zeile ist genau die Summe der acht Geschichten aus dem vorigen Beispiel, nur reichten statt 40 Multiplikationen 2 + 2 · 6 = 14. Die letzte Spalte c_t = P(O_t | O₁, …, O_t−1) ist die Normierungskonstante aus der Skalierung: wie wahrscheinlich der Wurf t angesichts der vorherigen war. Ihr Produkt ist P(O | λ), also log P(O | λ) = ∑_t log c_t.

Warum Logarithmen? Bei 3 000 Würfen liegt P(O | λ) bei etwa 10^−2 278, und die kleinste positive Zahl, die ein Computer in gewöhnlicher doppelter Genauigkeit (IEEE 754) speichern kann, ist etwa 4,9 · 10⁻³²⁴. Ohne Skalierung würde α auf null unterlaufen.

def dopredu(hody, pi, A, B):
    alfa = pi * B[:, hody[0]]
    logP = 0.0
    for t in range(len(hody)):
        if t > 0:
            alfa = (alfa @ A) * B[:, hody[t]]       # Summe über i, dann Emission
        c = alfa.sum()                              # c_t = P(O_t | O_1, …, O_t−1)
        alfa = alfa / c                             # Skalierung: α_t summiert jetzt zu 1
        logP += np.log(c)
    return logP                                     # log P(O | λ)

Für unsere 300 Würfe ergibt sich P(Würfe | Kasinomodell) ≈ 10^−230,03. Würde die ganze Zeit ehrlich gespielt, wäre die Wahrscheinlichkeit (1/6)³⁰⁰ ≈ 10^−233,45. Das Modell mit gelegentlich gezinktem Würfel erklärt die beobachteten Würfe etwa 2 600-mal besser — ein starker Beweis, dass hier betrogen wird, obwohl kein einzelner Wurf den Betrug verrät.

Definition — Likelihood-Quotient (Bayes-Faktor)

Für zwei Modelle M₁, M₂ und Daten O ist der Bayes-Faktor K = P(O | M₁) / P(O | M₂). Aus dem Satz von Bayes (für beide Modelle aufgeschrieben und durcheinander geteilt) folgt:

P(M₁ | O) / P(M₂ | O) = P(O | M₁) / P(O | M₂) · P(M₁) / P(M₂)

P(M₁ | O) / P(M₂ | O)

Chancenverhältnis nach der Beobachtung — das, was uns interessiert: um wie viel mehr wir an Betrug glauben als an ehrliches Spiel, nachdem wir die Würfe gesehen haben

P(O | M₁) / P(O | M₂)

Bayes-Faktor — die einzige Stelle, an der die Daten in die Formel eingehen; beide Likelihoods berechnet der Vorwärts-Algorithmus. Der Nenner P(O) aus dem Satz von Bayes kürzt sich beim Teilen heraus, deshalb muss man ihn nicht kennen

P(M₁) / P(M₂)

Chancenverhältnis im Voraus — wer dem Kasino von vornherein vertraut, braucht einen stärkeren Beweis; die Daten multiplizieren es nur

Berechnung. log₁₀ K = −230,03 − (−233,45) = 3,42 (aus den ungerundeten Werten 3,413), also K ≈ 10^3,413 ≈ 2 590, gerundet 2 600. Wer Betrug und ehrliches Spiel im Voraus für gleich wahrscheinlich hielt, hat nach 300 Würfen Chancen von etwa 2 600 : 1 für Betrug. Nach der verbreiteten Skala von Kass und Raftery (1995) ist ein Bayes-Faktor über 150 ein „sehr starker“ Beweis.

4. Wann geschummelt wurde: der Viterbi-Algorithmus

Algorithmus — Viterbi-Algorithmus (1967)

Gesucht ist die wahrscheinlichste Zustandsfolge argmax_x P(x, O | λ). Sei δ_t(j) die Wahrscheinlichkeit des besten Pfads, der zum Zeitpunkt t im Zustand j endet:

δ₁(j) = π_j b_j(O₁),   δ_t+1(j) = max_i [δ_t(i) a_ij] · b_j(O_t+1),

und merke dir bei jedem δ_t+1(j), von welchem i es kam. Am Ende wähle den besten Zustand und gehe entlang der gemerkten Verweise zurück. Gerechnet wird in Logarithmen; die Zeit ist wieder O(N² T).

δ_t+1(j) = max_i δ_t(i) a_ij · b_j(O_t+1),   ψ_t+1(j) = argmax_i δ_t(i) a_ij

δ_t(i)

Wahrscheinlichkeit der besten Geschichte, die zum Zeitpunkt t mit dem Würfel i endet; schlechtere Geschichten nach i brauchen wir nicht mehr — führte der beste Gesamtpfad über i, ginge er auf dem besten weiter

a_ij

Preis des Übergangs von i nach j; das kleine a_FG = 0,05 ist der Grund, warum Viterbi wegen einer einzelnen Sechs nicht umschalten will

max_i, ψ_t+1(j)

anders als beim Vorwärts-Algorithmus summieren wir nicht, sondern wählen den besten Vorgänger — wir wollen einen Pfad, nicht die Wahrscheinlichkeit aller; ψ merkt sich, wer gewonnen hat (im Gitter die bernsteinfarbenen Pfeile), damit sich der Pfad am Ende rückwärts zusammensetzen lässt

b_j(O_t+1)

wie gut der Würfel j den neuen Wurf erklärt — genau wie bei α

An zwölf Würfen sieht man, wie Viterbi entscheidet. Die ersten sechs Würfe (5, 2, 2, 5, 1, 1) sehen fair aus. Dann fallen zwei Sechsen hintereinander und zwei weitere kurz danach — und der beste Pfad schaltet auf den gezinkten Würfel um. In Wirklichkeit tauschte der Croupier den Würfel erst vier Würfe später; zwei Sechsen hintereinander fallen auch mit einem fairen Würfel.

Beispiel — Viterbi Schritt für Schritt für die Würfe 1, 6, 3

Der Start ist derselbe wie bei α: δ₁(F) = 0,0833, δ₁(G) = 0,0500. Für die Sechs im zweiten Wurf:

δ₂(F) = max(0,0833 · 0,95; 0,0500 · 0,1) · ¹/₆ = 0,0792 · ¹/₆ = 0,0132   (F gewinnt),
δ₂(G) = max(0,0833 · 0,05; 0,0500 · 0,9) · 0,5 = 0,0450 · 0,5 = 0,0225   (G gewinnt).

t	Wurf	δt(F)	ψt(F)	δt(G)	ψt(G)
1	1	0,083333	—	0,050000	—
2	6	0,013194	F	0,022500	G
3	3	0,002089	F	0,002025	G

Am Ende gewinnt F (0,002089 > 0,002025), und rückwärts entlang der Verweise ψ ergibt sich der Pfad FFF — genau die Geschichte aus dem ersten Beispiel, die von allen acht die wahrscheinlichste war. Der Vorwärts-Algorithmus liefert für den dritten Wurf aber P(G | O₁, O₂, O₃) = 0,002283 / 0,004913 = 0,465. Der beste Pfad und der wahrscheinlichste Zustand stimmen hier überein (F), aber der „Sieg“ ist knapp, und drei Würfe reichen für Gewissheit nicht. Im Allgemeinen müssen sie nicht übereinstimmen — darauf kommen wir bei der A-posteriori-Dekodierung zurück.

import numpy as np

def viterbi(hody, pi, A, B):
    T, N = len(hody), len(pi)
    delta = np.log(pi) + np.log(B[:, hody[0]])
    odkud = np.zeros((T, N), dtype=int)
    for t in range(1, T):
        kandidati = delta[:, None] + np.log(A)       # von jedem i zu jedem j
        odkud[t] = kandidati.argmax(axis=0)
        delta = kandidati.max(axis=0) + np.log(B[:, hody[t]])
    cesta = [int(delta.argmax())]
    for t in range(T - 1, 0, -1):                     # zurück entlang der siegreichen Verweise
        cesta.append(odkud[t][cesta[-1]])
    return cesta[::-1]

5. Alle 300 Würfe

Der gezinkte Würfel war 88-mal im Spiel, in neun Abschnitten. Viterbi hat 62 Würfe als gezinkt markiert, davon 56 richtig, und insgesamt bei 87,3 % der Würfe den Würfel richtig bestimmt. Die langen Betrugsabschnitte hat er gefunden, die kurzen aber übersehen oder zusammengelegt — statt neun Abschnitten sieht er zwei. Auf einem kurzen Abschnitt fallen einfach nicht genug Sechsen, damit sich der „teure“ Würfeltausch lohnt (die Wahrscheinlichkeit eines Tauschs ist nur 0,05).

Definition — A-posteriori-Wahrscheinlichkeit eines Zustands

Der Vorwärts-Rückwärts-Algorithmus berechnet zusätzlich von hinten β_t(i) = P(O_t+1, …, O_T | X_t = i) und erhält aus beiden γ_t(i) = P(X_t = i | O) ∝ α_t(i) β_t(i).

γ_t(i) = α_t(i) · β_t(i) / P(O | λ),   β_t(i) = ∑_j a_ij b_j(O_t+1) β_t+1(j),   β_T(i) = 1

γ_t(i)

Wahrscheinlichkeit, dass zum Zeitpunkt t der Würfel i im Spiel war, wenn wir alle Würfe kennen — für den gezinkten Würfel ist das die rote Kurve in der Abbildung

α_t(i)

Indizien aus der Vergangenheit: die Würfe 1 bis t und der Zustand i zum Zeitpunkt t

β_t(i)

Indizien aus der Zukunft: wie gut der Zustand i die Würfe t + 1 bis T erklärt. Berechnet wird es von hinten mit demselben Trick wie α — ein Schritt der Kette, Emission, Rest der Zukunft. α und β dürfen wir multiplizieren, weil bei bekanntem Zustand X_t vergangene und zukünftige Würfe unabhängig sind

P(O | λ)

das Produkt α·β ist die gemeinsame Wahrscheinlichkeit P(X_t = i, O); durch Teilen durch die Wahrscheinlichkeit aller Würfe machen wir daraus eine bedingte. Es ist dieselbe Zahl, die der Vorwärts-Algorithmus geliefert hat, und es gilt ∑_i α_t(i) β_t(i) = P(O | λ) für jedes t

Beispiel — der zweite Wurf: was die Zukunft hinzufügt

Bleiben wir bei den Würfen 1, 6, 3 und fragen nach dem zweiten Wurf (der Sechs). Der Rückwärtsschritt von β₃ = 1 mit dem dritten Wurf (der Drei):

β₂(F) = 0,95 · ¹/₆ + 0,05 · 0,1 = 0,1633,   β₂(G) = 0,1 · ¹/₆ + 0,9 · 0,1 = 0,1067.

γ₂(G) = 0,024583 · 0,106667 / 0,004913 = 0,534.

Kennten wir nur die ersten beiden Würfe, wäre P(G | O₁, O₂) = α₂(G) / (α₂(F) + α₂(G)) = 0,637. Die Drei, die danach fiel, ist beim gezinkten Würfel weniger wahrscheinlich, und so senkt sie den Verdacht für den zweiten Wurf rückwirkend auf 0,534.

Definition — A-posteriori-Dekodierung und Genauigkeit

Die A-posteriori-Dekodierung wählt zu jedem Zeitpunkt einzeln x̂_t = argmax_i γ_t(i). Die Genauigkeit einer Dekodierung x̂ gegenüber den wahren Zuständen x ist der Anteil der Übereinstimmungen (1/T) ∑_t [x̂_t = x_t], wobei [·] gleich 1 ist, wenn die Aussage gilt, sonst 0.

Die A-posteriori-Dekodierung maximiert die erwartete Anzahl richtig bestimmter Würfe, Viterbi die Wahrscheinlichkeit, dass der ganze Pfad auf einmal stimmt. Deshalb kann die A-posteriori-Folge sogar einen Übergang enthalten, der im Modell die Wahrscheinlichkeit null hat — beim Kasino gibt es keinen solchen, allgemein kann das aber vorkommen.

Würden wir bei jedem Wurf den Würfel mit der größeren A-posteriori-Wahrscheinlichkeit wählen, lägen wir bei 87,7 % richtig — um ein Haar mehr als Viterbi (263 von 300 Würfen gegenüber 262, ein Unterschied von einem einzigen Wurf). (Viterbi sucht den besten ganzen Pfad, die A-posteriori-Dekodierung die beste Schätzung jedes Wurfs einzeln; das ist nicht dasselbe.) Und Vorsicht bei einer einzigen Simulation: In zwölf verschiedenen Versuchen lag die Genauigkeit des Viterbi-Algorithmus zwischen 73,3 und 90,0 %, im Mittel bei 83,4 % — je nachdem, wie lange Betrugsabschnitte der Zufall erzeugt.

6. Lernen: der Baum-Welch-Algorithmus

Bisher kannten wir die Parameter des Kasinos. Was, wenn wir nur wissen, dass es zwei Würfel gibt, und alles andere aus den Würfen herausgelesen werden muss?

Algorithmus — Baum-Welch-Algorithmus

Es ist ein EM-Algorithmus (Baum u. a., um 1970). Wiederhole:

1. E-Schritt: berechne mit den aktuellen Parametern per Vorwärts-Rückwärts-Algorithmus γ_t(i) und die erwarteten Übergangsanzahlen ξ_t(i, j) = P(X_t = i, X_t+1 = j | O);
2. M-Schritt: neues a_ij = ∑_t ξ_t(i, j) / ∑_t γ_t(i), neues b_i(o) = Anteil von γ zu den Zeitpunkten, an denen o fiel.

Die Likelihood P(O | λ) sinkt in keiner Iteration; der Algorithmus konvergiert gegen ein lokales Maximum.

Die erwartete Anzahl der Übergänge berechnet sich aus denselben α und β wie γ, nur wird zwischen sie ein Schritt der Kette eingefügt:

ξ_t(i, j) = α_t(i) a_ij b_j(O_t+1) β_t+1(j) / P(O | λ)

α_t(i)

die Würfe bis zum Zeitpunkt t und der Würfel i zum Zeitpunkt t — das linke Ende des Übergangs

a_ij

der Übergang i → j selbst, dessen Häufigkeit wir schätzen

b_j(O_t+1)

den Wurf t + 1 muss der neue Würfel j erzeugen

β_t+1(j)

die restlichen Würfe ab t + 2, erklärt vom Würfel j aus — das rechte Ende des Übergangs

P(O | λ)

durch Teilen machen wir aus der gemeinsamen Wahrscheinlichkeit „Übergang und alle Würfe“ die bedingte „Übergang, wenn wir die Würfe kennen“

â_ij = ∑_t=1^T−1 ξ_t(i, j) / ∑_t=1^T−1 γ_t(i)

â_ij

neue Schätzung der Übergangswahrscheinlichkeit — eine relative Häufigkeit, als würden wir Striche zählen

∑ ξ_t(i, j)

erwartete Anzahl der Übergänge i → j; statt „übergegangen oder nicht“ (1 oder 0) summieren wir Wahrscheinlichkeiten, weil wir die Zustände nicht sehen

∑ γ_t(i)

erwartete Anzahl der Abgänge aus dem Zustand i; summiert wird nur bis T − 1, weil vom letzten Zustand kein Übergang mehr ausgeht. Dadurch summiert sich jede Zeile der neuen Matrix zu 1

wiederhole (bei uns 100-mal):
    α, β, P(O) ← Vorwärts-Rückwärts-Algorithmus mit aktuellen π, A, B
    # E-Schritt: weiche Zählungen
    für jedes t, i:           γ[t][i]    ← α[t][i] · β[t][i] / P(O)
    für jedes t < T, i, j:    ξ[t][i][j] ← α[t][i] · a[i][j] · b[j](O[t+1]) · β[t+1][j] / P(O)
    # M-Schritt: relative Häufigkeiten
    π[i]    ← γ[1][i]
    a[i][j] ← ∑_{t<T} ξ[t][i][j] / ∑_{t<T} γ[t][i]
    b[i](o) ← ∑_{t: O[t]=o} γ[t][i] / ∑_t γ[t][i]

Wir haben mit einer schlechten Schätzung begonnen: Die Würfel unterscheiden sich kaum und werden oft getauscht. Aus 300 Würfen kam Baum-Welch zu einem Modell, das die Würfel fast nie tauscht und dem gezinkten Würfel die Sechs nur mit Wahrscheinlichkeit 0,39 gibt — für eine zuverlässige Schätzung sind 300 Würfe zu wenig. Aus 3 000 Würfen (einer anderen Simulation desselben Kasinos) kam er schon sehr nah an die Wahrheit:

Warum 300 Würfe nicht reichen, zeigt die Likelihood. Während 100 Iterationen auf unseren 300 Würfen stieg sie von 10^−231,26 auf 10^−227,14 — und das ist mehr als die 10^−230,03 des wahren Kasinomodells. Das gelernte Modell erklärt also genau diese Würfe besser als die Wahrheit: Es hat sich auch an die zufälligen Schwankungen der konkreten Daten angepasst. Die Maximum-Likelihood-Schätzung nähert sich der Wahrheit erst mit wachsender Datenmenge.

7. Hidden-Markov-Modelle in der Praxis

• Spracherkennung. Von den Achtzigerjahren bis zum Aufkommen tiefer Netze um 2010 beruhten fast alle Systeme auf HMMs: Die verborgenen Zustände sind Teile von Lauten, die Beobachtungen kurze Ausschnitte des Klangspektrums, und Viterbi sucht die wahrscheinlichste Wortfolge.
• Sprache. Wortartenbestimmung: Der verborgene Zustand ist die Wortart, die Beobachtung das Wort. „Laut“ kann ein Substantiv, ein Adjektiv oder eine Präposition sein — der Kontext entscheidet.
• Bioinformatik. Gensuche in der DNA (codierende und nicht codierende Abschnitte sind die verborgenen Zustände) oder Profil-HMMs für Proteinfamilien in der Datenbank Pfam.
• Kontinuierliche Zustände. Ist der verborgene Zustand nicht „Würfel A oder B“, sondern Position und Geschwindigkeit, verwendet man statt eines HMM den Kalman-Filter — er hat im Lehrplan einen eigenen Teil.

8. Zusammenfassung

• Ein Hidden-Markov-Modell ist eine Markow-Kette verborgener Zustände, von denen wir nur die Emissionen sehen; es wird durch π, A und B bestimmt.
• Der Vorwärts-Algorithmus berechnet die Wahrscheinlichkeit der Beobachtungen in der Zeit O(N²T) statt einer Summe über 2³⁰⁰ Pfade; das Kasino mit Betrug erklärt unsere Würfe etwa 2 600-mal besser als ehrliches Spiel.
• Der Viterbi-Algorithmus findet mit dynamischer Programmierung den wahrscheinlichsten Pfad verborgener Zustände — in unserer Simulation bestimmte er den Würfel bei 87,3 % der Würfe richtig, kurze Abschnitte übersah er aber.
• Der Vorwärts-Rückwärts-Algorithmus liefert die A-posteriori-Wahrscheinlichkeit des Zustands zu jedem Zeitpunkt.
• Der Baum-Welch-Algorithmus lernt die Parameter nur aus Beobachtungen — braucht aber genug Daten: 300 Würfe reichten nicht, 3 000 schon.

Willst du es selbst ausprobieren? Lass einen KI-Agenten ein HMM mit zwei Zuständen auf die täglichen Renditen eines Aktienindex trainieren — und schau, ob er von selbst die „ruhigen“ und die „stürmischen“ Marktphasen findet.

Siehst du das anders? Schreib an support@coden-app.com.