Markov-Modelle und versteckte Markov-Modelle

Ein veränderliches System braucht für jeden Zeitpunkt einen Zustand und eine Regel für den Übergang zum nächsten Zeitpunkt. Eine zeitdiskrete Markov-Kette erfasst diese Zustände in gleichmäßig verteilten Schritten. Wähle Zustand und Zeitschritt gemeinsam: Das tägliche Wetter und die Position eines Roboters in jeder Sekunde beschreiben unterschiedliche Prozesse.

Was der aktuelle Zustand enthalten muss

Die Markov-Eigenschaft erster Ordnung lautet:

Ist der aktuelle Zustand bekannt, liefern frühere Zustände keine zusätzliche Information über den nächsten. Das ist bedingte Unabhängigkeit, keine Unabhängigkeit aufeinanderfolgender Zustände. Kennt man das heutige Wetter nicht, kann das gestrige Wetter helfen, das morgige vorherzusagen.

Eine Kette benötigt eine Anfangsverteilung, $P(X_1)$, und ein Übergangsmodell. Wir verwenden zeithomogene Übergänge: In jedem Schritt gelten dieselben Wahrscheinlichkeiten. Manche KI-Texte nennen dies eine Stationaritätsannahme. In der Wahrscheinlichkeitstheorie hat ein stationärer Prozess gemeinsame Verteilungen, die sich bei einer zeitlichen Verschiebung nicht ändern; feste Übergänge allein gewährleisten das nicht. Startet eine zeithomogene Kette in einer stationären Verteilung, ist diese Bedingung erfüllt.

Eine Übergangsmatrix lesen

Für das Wetter seien die Zustände Sonnig (S) und Bewölkt (C). Die Zeilen bezeichnen den aktuellen Zustand, die Spalten den nächsten:

Von Sonnig aus ist der nächste Tag mit Wahrscheinlichkeit 0,8 sonnig und mit Wahrscheinlichkeit 0,2 bewölkt. Von Bewölkt aus betragen diese Wahrscheinlichkeiten 0,4 und 0,6. Jede Zeile summiert sich zu 1, weil sie alle Ziele von einem Ausgangszustand aus aufführt. Die Spalten müssen sich nicht zu 1 summieren. Ein Zustandsdiagramm stellt dieselbe Tabelle durch Pfeile dar, einschließlich Pfeilen zurück zum selben Zustand.

Manche Bücher transponieren diese Konvention. Lies vor der Berechnung die Definition eines Eintrags: Hier gilt $T_{ij}=P(X_{t+1}=j\mid X_t=i)$. Korrekte Zahlen in der falschen Ausrichtung ergeben eine falsche Vorhersage.

Entlang eines Pfads multiplizieren

Für einen bestimmten Pfad multipliziert man seine Anfangswahrscheinlichkeit mit einem Übergang pro Schritt:

Ist Tag 1 sicher sonnig, hat der Pfad Sonnig, Sonnig, Bewölkt, Bewölkt die Wahrscheinlichkeit

Der erste Übergang trägt 0,8 bei, der Wechsel 0,2 und das Verbleiben bei Bewölkt 0,6. Würde man die einzelnen Tageshäufigkeiten multiplizieren, gingen die Verbindungen zwischen den Tagen verloren. In einem bayesschen Netz sind diese Verbindungen die Pfeile in $X_1\to X_2\to X_3\to \cdots$.

Genug Vorgeschichte im Zustand speichern

Ein Modell zweiter Ordnung hängt von den letzten zwei Werten ab. Wandle es in ein Modell erster Ordnung um, indem du den Zustand als (gestern, heute) definierst. Zwei Wetterwerte ergeben dann vier mögliche Paare. Ein Übergang von (Sonnig, Bewölkt) kann nur zu einem Paar führen, das mit Bewölkt beginnt, weil benachbarte Paare überlappen müssen. Speichere für einen Prozess der Ordnung $k$ die letzten $k$ Werte zusammen; die Algorithmen bleiben von erster Ordnung, während die Anzahl der kombinierten Zustände wächst.

Eine Kette befindet sich zu jedem Zeitpunkt in einem Zustand, aber du weißt möglicherweise nicht, in welchem. Eine Zustandsverteilung speichert diese Unsicherheit als Zeilenvektor. Seine Einträge geben die Wahrscheinlichkeiten der möglichen Zustände an, keine Zeitanteile innerhalb eines einzelnen Schritts.

Alle Wege zu einem Ziel addieren

Um Sonnig für morgen vorherzusagen, betrachte beide Wege dorthin: Heute kann es Sonnig oder Bewölkt sein. Gewichte jeden Übergang mit der Wahrscheinlichkeit seines Ausgangszustands:

Für den vollständigen Vektor ergibt das $p_{t+1}=p_{t}T$. Nach $k$ Schritten gilt $p_{t+k}=p_t{T}^k$. Diese Aktualisierung wird manchmal Mini-Vorwärtsalgorithmus genannt, die Version der HMM-Filterung ohne Evidenz.

Die Wetterkette durchrechnen

Verwende die Zeilen (0,8; 0,2) von Sonnig aus und (0,4; 0,6) von Bewölkt aus. Beginne mit einem sicher sonnigen Tag: $p_1=(1,0)$. Ein Übergang ergibt $p_2=(\mathrm{0,8};\mathrm{0,2})$. Für Tag 3 beträgt der Beitrag zu Sonnig $\mathrm{0,8}\times \mathrm{0,8}=\mathrm{0,64}$ von Sonnig und $\mathrm{0,2}\times \mathrm{0,4}=\mathrm{0,08}$ von Bewölkt aus. Addiert ergibt das 0,72. Die Beiträge zu Bewölkt sind $\mathrm{0,8}\times \mathrm{0,2}=\mathrm{0,16}$ und $\mathrm{0,2}\times \mathrm{0,6}=\mathrm{0,12}$, zusammen 0,28.

Damit ist $p_3=(\mathrm{0,72};\mathrm{0,28})$. Eine weitere Aktualisierung ergibt $P(X_4=S)=\mathrm{0,72}\times \mathrm{0,8}+\mathrm{0,28}\times \mathrm{0,4}=\mathrm{0,688}$ und $P(X_4=C)=\mathrm{0,312}$. Runde Zwischenergebnisse nicht und runde angezeigte Ergebnisse am Ende.

Bedeutung und Ausrichtung prüfen

Jedes Ergebnis muss nicht negativ sein und sich zu 1 summieren. Bei der Zeilenkonvention steht die Verteilung links. Verwendet man stattdessen $T{p}_1^{𝖳}$, ergibt sich die Spalte (0,8; 0,4) mit der Summe 1,2. Diese Rechnung wählt die Wahrscheinlichkeiten aus, Sonnig von zwei verschiedenen Ausgangszuständen aus zu erreichen; sie verteilt keinen Ausgangs-Glaubenszustand auf Zielzustände.

Der Wert 0,72 an Tag 3 bedeutet, dass bei vielen unabhängigen Durchläufen mit einem sonnigen Tag 1 etwa 72 % an Tag 3 sonnig sind. Er beschreibt weder ein festes wiederkehrendes Wettermuster noch einen Tag, der zu 72 % sonnig ist.

Warum die Vorhersage handhabbar bleibt

Eine Aktualisierung mit einer dicht besetzten Matrix über $S$ Zustände benötigt $O(S^2)$ Operationen. Sie fasst alle bisherigen Pfade im aktuellen Vektor zusammen, sodass der Aufwand pro Übergang im Zeitverlauf gleich bleibt. Würde man stattdessen alle Pfade von einem bekannten Start aus auflisten, wären zum Zeitpunkt $t$ insgesamt $S^{t-1}$ Pfade nötig.

Für diese Wetterkette nähern sich die aufeinanderfolgenden Wahrscheinlichkeiten für Sonnig dem Wert $2\mathrm{/}3$. Ist $s_t=P(X_t=S)$, gilt $s_{t+1}=\mathrm{0,4}+\mathrm{0,4}{s}_t$. Subtrahiert man $2\mathrm{/}3$, zeigt sich, dass der Abstand in jedem Schritt um den Faktor 0,4 schrumpft. Andere Ketten können sich anders verhalten; Konvergenz setzt die Bedingungen voraus, die bei stationären Verteilungen behandelt werden.

Du kannst auch einen Durchlauf simulieren. Ziehe den Anfangszustand und danach jeweils aus der Übergangszeile des aktuellen Zustands. Von Sonnig aus wählt eine gleichmäßig gezogene Zufallszahl unter 0,8 Sonnig; eine Zahl von mindestens 0,8 wählt Bewölkt. Viele wiederholte Durchläufe schätzen dieselbe vorhergesagte Verteilung und führen die Stichprobenidee ein, die Partikelfilter nutzen.

Eine Verteilung kann unverändert bleiben, während einzelne Durchläufe weiter zwischen Zuständen wechseln. Eine stationäre Verteilung beschreibt dieses Gleichgewicht. Sie ist für langfristige Vorhersagen nützlich, aber ihre bloße Existenz sagt nicht, ob sich eine Kette ihr von einem bestimmten Start aus nähert.

Die Bilanzgleichungen lösen

Ein stationärer Zeilenvektor erfüllt $\pi =\pi T$ sowie ${\sum }_j{\pi }_j=1$ und hat nicht negative Einträge. Für die Wetterkette muss der Wahrscheinlichkeitsfluss von Sonnig nach Bewölkt den Rückfluss ausgleichen:

Die erste Gleichung ergibt ${\pi }_S=2{\pi }_C$. Einsetzen ergibt $3{\pi }_C=1$, also $\pi =(2\mathrm{/}3,1\mathrm{/}3)$. Für eine Kette mit zwei Zuständen und Wechselwahrscheinlichkeiten $a$ von Zustand 1 nach 2 und $b$ von 2 nach 1 gilt ${\pi }_1=b\mathrm{/}(a+b)$, wenn $a+b>0$.

Stelle bei mehr Zuständen pro Zustand eine Gleichung für den eingehenden Fluss auf. Ersetze eine davon durch die Gleichung, dass sich die Einträge zu 1 summieren, und löse das lineare Gleichungssystem. Die Bilanzgleichungen allein lassen die Skalierung unbestimmt. Multipliziere abschließend den vorgeschlagenen Vektor zur Prüfung mit der Matrix.

Für die Fahrradverleihstationen A, B, C verwende die Zeilen (0,6; 0,2; 0,2), (0,1; 0,8; 0,1) und (0,2; 0,2; 0,6). Die Lösung ist (0,25; 0,5; 0,25). Beispielsweise beträgt die eingehende Wahrscheinlichkeit bei B $\mathrm{0,25}(\mathrm{0,2})+\mathrm{0,5}(\mathrm{0,8})+\mathrm{0,25}(\mathrm{0,2})=\mathrm{0,5}$. Eine gleichmäßige Wahrscheinlichkeit würde diese Prüfung nicht bestehen.

Drei Fragen unterscheiden

Irreduzibel bedeutet, dass jeder Zustand jeden anderen erreichen kann, möglicherweise über mehrere Übergänge. Aperiodisch bedeutet, dass Rückkehrzeiten nicht an einen festen Zyklus von mehr als einem Schritt gebunden sind. Alle Einträge der Wettermatrix sind positiv, sodass beide Bedingungen erfüllt sind. In einer endlichen irreduziblen Kette geben die stationären Wahrscheinlichkeiten auch die langfristigen Anteile der Schritte in jedem Zustand an, selbst wenn Periodizität die Konvergenz der zeitpunktbezogenen Verteilung verhindert.

Zwei aufschlussreiche Gegenbeispiele

Wechseln zwei Zustände immer, wechselt die Verteilung bei einem sicheren Start im ersten Zustand zwischen (1, 0) und (0, 1). Der eindeutige stationäre Vektor ist (0,5; 0,5), aber diese Vorhersagen nähern sich ihm nie an. In einem langen Durchlauf nimmt jeder Zustand dennoch die Hälfte der Schritte ein.

Sind beide Zustände absorbierend, bleibt jeder für immer dort, wo er ist. Jeder Vektor (q, 1 − q) ist stationär, sodass es kein eindeutiges Gleichgewicht für alle Ausgangszustände gibt. Diese Beispiele zeigen, warum Eindeutigkeit, Konvergenz und zeitliche Mittelwerte getrennt geprüft werden müssen.

Die Anfangsverteilung beschreibt den Start; sie entspricht nur dann einer stationären Verteilung, wenn du im Gleichgewicht startest. Feste Übergangswahrscheinlichkeiten beschreiben das Gesetz des Modells, nicht seine aktuelle Verteilung. PageRank nutzt stationäre Wahrscheinlichkeiten, um Seiten in einem Modell zufälligen Surfens zu ordnen. Markov-Ketten-Monte-Carlo erzeugt eine Kette mit einer gewünschten stationären Verteilung, sodass ihr langfristiger Verlauf Stichproben liefern kann.

Ein Sensorwert liefert Evidenz über einen Zustand, ohne ihn vollständig offenzulegen. In einem versteckten Markov-Modell, kurz HMM, verändert sich der Zustand im Laufe der Zeit und jeder Zustand erzeugt eine Beobachtung. Ein Roboter kann wissen, was sein Entfernungssensor gemeldet hat, und dennoch über seine Position unsicher sein.

Drei Wahrscheinlichkeitsmodelle festlegen

Ein HMM benötigt eine Anfangsverteilung der Zustände, ein Übergangsmodell und ein Sensormodell:

Der verborgene Zustand ist eine diskrete Variable. Das Sensormodell, auch Emissions- oder Beobachtungsmodell genannt, gibt die Likelihood jeder Beobachtung in jedem Zustand an. Wir legen eine A-priori-Verteilung direkt für $X_1$ fest und beobachten dort $E_1$. Texte, die mit einem unbeobachteten $X_0$ beginnen, führen stattdessen vor der ersten Beobachtung einen Übergang aus.

Der Zustand erfüllt die Markov-Eigenschaft erster Ordnung. Die Beobachtung zu einem Zeitpunkt hängt nur vom Zustand zu diesem Zeitpunkt ab: $P(E_t\mid X_{1:t},E_{1:t-1})=P(E_t\mid X_t)$. Zeichne in einem bayesschen Netz eine Kette verborgener Zustände und ergänze von jedem Zustand einen Pfeil zu seiner Beobachtung.

Das Solarmodulmodell erstellen

Das verborgene Wetter ist Sonnig oder Bewölkt, mit den Übergangszeilen (0,8; 0,2) und (0,4; 0,6). Beide Anfangszustände haben die Wahrscheinlichkeit 0,5. Die tägliche Leistung des Moduls ist Hoch oder Niedrig:

Jede Sensorzeile summiert sich zu 1. Auch ein bewölkter Tag kann eine hohe Leistung erzeugen, sodass Hoch nicht mit Sicherheit Sonnig bezeichnet. Ebenso ist $P(L\mid C)=\mathrm{0,7}$ eine Aussage über die Leistung an bewölkten Tagen. Um $P(C\mid L)$ zu bestimmen, braucht man außerdem die A-priori-Verteilung und den Satz von Bayes.

Zustände und Evidenz gemeinsam bewerten

Für einen bestimmten Zustandspfad und eine Beobachtungsfolge gilt:

Für Bewölkt, Bewölkt, Sonnig mit Niedrig, Niedrig, Hoch beginne mit $\mathrm{0,5}\times \mathrm{0,7}=\mathrm{0,35}$. Bewölkt zu bleiben und Niedrig zu beobachten ergibt $\mathrm{0,35}\times \mathrm{0,6}\times \mathrm{0,7}=\mathrm{0,147}$. Der Wechsel zu Sonnig und die Beobachtung Hoch ergeben $\mathrm{0,147}\times \mathrm{0,4}\times \mathrm{0,8}=\mathrm{0,04704}$.

Beobachtungen können abhängig sein, obwohl keine direkten Pfeile zwischen ihnen verlaufen. Anhaltend bewölktes Wetter führt dazu, dass aufeinanderfolgende niedrige Messwerte häufig gemeinsam auftreten. Bedingt man auf die verborgenen Zustände, entfällt diese Abhängigkeit. Evidenz aktualisiert den Glaubenszustand des Beobachters; die Beobachtung Niedrig verändert das Wetter nicht selbst.

Die Inferenzfrage wählen

Dieselben drei Modelle ermöglichen alle fünf Aufgaben. Was sich ändert, ist, welche Variablen du beibehältst, welche du aussummierst und ob du über Pfade summierst oder den größten Pfadwert auswählst.

Die Definition des Zustands bestimmt, was sich das Modell merken kann. Ein nützliches zeitliches Modell behält die Information, die zur Vorhersage des nächsten Zustands nötig ist, und hält zugleich den Inferenzaufwand vertretbar. Seine Wahrscheinlichkeiten müssen außerdem die Daten und Sensorausfälle widerspiegeln, auf die es trifft.

Genügend Zustandsinformation wählen

Die Position allein kann für ein Objekt mit Impuls unzureichend sein: Frühere Positionen verraten seine Richtung. Ergänzt man die Geschwindigkeit, kann der aktuelle Zustand diese Richtung erklären. Ergänze die Jahreszeit, wenn die Dynamik von ihr abhängt. Diese Entscheidungen machen die Markov-Näherung plausibler; sie bestimmen, welche Information weitergegeben wird.

Eine kontinuierliche Größe lässt sich auf einem Raster darstellen. Temperaturen von 10 °C bis 20 °C in Schritten von 0,1 °C ergeben 101 Werte einschließlich beider Endpunkte. Feinere Abstände erhöhen die Anzahl der Zustände. Kombiniert man mehrere Größen auf Rastern, multiplizieren sich ihre Anzahlen und die exakte Inferenz mit dicht besetzten Matrizen benötigt $O(S^2)$ pro Schritt.

Unabhängige Parameter zählen

Eine Zeile einer kategorialen Verteilung mit $r$ Einträgen hat $r-1$ freie Parameter, weil der letzte Eintrag durch ihre Summe festgelegt ist. Bei $S$ Zuständen und $O$ Beobachtungswerten benötigt ein uneingeschränktes HMM daher

freie Parameter: für A-priori-Verteilung, Übergänge und Emissionen. Das Solarmodell mit zwei Zuständen und zwei Leistungswerten benötigt $1+2+2=5$. Würde man jeden Tabelleneintrag zählen, zählte man die Bedingungen für die Zeilensummen als zusätzliche Wahlmöglichkeiten mit.

Den Zustand mit einem dynamischen bayesschen Netz faktorisieren

Ein dynamisches bayessches Netz (DBN) enthält mehrere Zustandsvariablen und weist jeder eigene Elternknoten zu. Es kann lokale Abhängigkeiten ausdrücken, ohne eine riesige flache Übergangstabelle zu erstellen. Zwanzig boolesche Variablen haben $2^{20}=\mathrm{1.048.576}$ gemeinsame Zustände; eine flache Übergangstabelle hat $2^{40}$ Einträge. Hat jede boolesche Variable des nächsten Schritts drei boolesche Elternknoten, benötigt ihre Tabelle acht Wahrscheinlichkeiten, alle 20 zusammen also $20\times 8=160$.

Ein diskretes DBN lässt sich in ein HMM überführen, indem man eine vollständige Belegung als einen Zustand behandelt. Die faktorisierte Speicherung ist kompakt, aber exakte Inferenz kann dennoch aufwendig werden, wenn Abhängigkeiten viele Variablen koppeln. Partikelverfahren können diese Belegungen direkt ziehen.

Zeilen anhand von Daten schätzen

Sind Zustände gekennzeichnet, nutze bedingte Häufigkeiten. Vierzig sonnige Folgetage unter 50 aufgezeichneten Übergängen von Sonnig ergeben $P(S\to S)=40\mathrm{/}50=\mathrm{0,8}$. Der Nenner zählt Übergänge, die von Sonnig ausgehen, nicht jeden Tag der Aufzeichnung. Für einen Zustand am Ende einer Aufzeichnung ist kein Folgezustand beobachtet.

Häufigkeiten von null ergeben Maximum-Likelihood-Wahrscheinlichkeiten von null. Die Add-one-Korrektur weist jedem Ziel einen Pseudozählwert zu und erhöht die Zeilensumme entsprechend. Dadurch wird vermieden, einen Übergang nur deshalb auszuschließen, weil er in einer kleinen Trainingsaufzeichnung nicht vorkam. Bei verborgenen Zuständen wechselt Baum-Welch zwischen geglätteten erwarteten Häufigkeiten und der erneuten Schätzung der Parameter.

Ausfälle im Sensormodell berücksichtigen

Weist jeder mögliche Zustand einem Messwert die Likelihood null zu, hat eine Aktualisierung die Summe null und lässt sich nicht normieren. Eine kleine Ausreißerkomponente kann ungewöhnlichen Messwerten eine gewisse Wahrscheinlichkeit geben. Eine normierte Mischung hat die Form $P(e\mid x)=\mathrm{0,99}{P}_{\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{r}}(e\mid x)+\mathrm{0,01}{P}_{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{r}}(e)$. Beide Komponentenverteilungen müssen normiert sein.

Die Wirkung eines Messwerts hängt von den Likelihood-Quotienten zwischen den Zuständen ab. Gleiche Likelihoods lassen den vorhergesagten Glaubenszustand nach der Normierung unverändert. Eine kleine Likelihood in jedem Zustand kann dennoch informativ sein, wenn sich die Likelihoods relativ zueinander stark unterscheiden.

Filterung verfolgt den aktuellen verborgenen Zustand anhand aller bisher verfügbaren Beobachtungen. Ihr Ergebnis ist eine Glaubensverteilung, $f_t(x)=P(X_t=x\mid e_{1:t})$. Du aktualisierst diese kompakte Verteilung, wenn ein neuer Messwert eintrifft, ohne jeden möglichen früheren Pfad zu speichern.

Vorhersagen, gewichten, normieren

Für einen späteren Schritt führe den Glaubenszustand zunächst durch das Übergangsmodell fort:

Gewichte dann jeden Zielzustand mit der Likelihood der neuen Beobachtung und normiere:

Die Vorhersage beschreibt, wohin sich der Zustand bewegt haben könnte. Die Aktualisierung anhand der Evidenz ist der Satz von Bayes zum neuen Zeitpunkt. Bei einer A-priori-Verteilung für $X_1$ beginne damit, diese mit der ersten Beobachtung zu gewichten; davor findet kein Übergang statt.

Tag 1: Niedrig beobachten

Verwende das Solarmodulmodell: A-priori-Verteilung (0,5; 0,5), Übergangszeilen (0,8; 0,2) und (0,4; 0,6) sowie Likelihoods für Niedrig (0,2; 0,7). Die Gewichtung ergibt $\mathrm{0,5}(\mathrm{0,2})=\mathrm{0,10}$ für Sonnig und $\mathrm{0,5}(\mathrm{0,7})=\mathrm{0,35}$ für Bewölkt. Die Summe ist 0,45. Dividiere jedes Gewicht durch diese Summe und erhalte $f_1=(2\mathrm{/}9,7\mathrm{/}9)\approx (\mathrm{0,2222};\mathrm{0,7778})$.

Tag 2: Erneut Niedrig beobachten

Die Vorhersage ergibt ${\bar{f}}_2(S)=(2\mathrm{/}9)(\mathrm{0,8})+(7\mathrm{/}9)(\mathrm{0,4})=22\mathrm{/}45\approx \mathrm{0,4889}$. Bewölkt hat die Wahrscheinlichkeit $23\mathrm{/}45\approx \mathrm{0,5111}$. Die neuen Gewichte sind $22\mathrm{/}225\approx \mathrm{0,0978}$ und $161\mathrm{/}450\approx \mathrm{0,3578}$. Ihre Summe ist $41\mathrm{/}90\approx \mathrm{0,4556}$, woraus $f_2=(44\mathrm{/}205,161\mathrm{/}205)\approx (\mathrm{0,2146};\mathrm{0,7854})$ folgt.

Das zweite Niedrig erhöht die Wahrscheinlichkeit für Bewölkt nur leicht. Die Bewegung zum Gleichgewicht der Kette mit höherer Wahrscheinlichkeit für Sonnig wirkt der neuen Evidenz zugunsten von Bewölkt entgegen. Würde man Niedrig direkt auf den gestrigen Glaubenszustand anwenden, bliebe diese Bewegung unberücksichtigt.

Tag 3: Hoch beobachten

Sage ${\bar{f}}_3=(498\mathrm{/}1025,527\mathrm{/}1025)\approx (\mathrm{0,4859};\mathrm{0,5141})$ voraus. Hoch hat die Likelihoods (0,8; 0,3), sodass die Gewichte ungefähr (0,3887; 0,1542) betragen. Dividiere durch ihre Summe von ungefähr 0,5429 und erhalte $f_3\approx (\mathrm{0,7159};\mathrm{0,2841})$.

Hoch ist unter Sonnig $\mathrm{0,8}\mathrm{/}\mathrm{0,3}\approx \mathrm{2,67}$-mal so wahrscheinlich wie unter Bewölkt. Dieser Likelihood-Quotient verschiebt die Chancen zugunsten von Sonnig. Eine große Likelihood allein ist weniger aussagekräftig als ihre Größe im Verhältnis zur Likelihood des konkurrierenden Zustands.

Einen Online-Filter zuverlässig betreiben

Ein Schritt mit dicht besetzter Matrix benötigt $O(S^2)$ Zeit und speichert $O(S)$ Einträge des Glaubenszustands, unabhängig von der Länge der Vorgeschichte. Dies ist exakte Variablenelimination: Jeder vergangene Zustand wird beim Fortschreiten aussummiert.

Normiere bei jeder Beobachtung. Ohne Skalierung speichert der Vektor gemeinsame Wahrscheinlichkeiten von Zustand und Evidenz, die unter den darstellbaren Gleitkommazahlenbereich sinken können. Bewahre die dabei entfernten Summen getrennt auf, wenn du die Beobachtungswahrscheinlichkeit benötigst. Bei einer Summe von null muss das Modell oder die Abdeckung durch die Partikel wiederhergestellt werden; eine Division kann das nicht beheben.

Unsere Formel für Zeilenvektoren lautet $f_{t+1}\propto (f_{t}T)O_{t+1}$, wobei die Diagonalmatrix die neuen Likelihoods enthält. Für Glaubenszustände als Spaltenvektoren lautet die entsprechende Formel $f_{t+1}\propto O_{t+1}{T}^{𝖳}{f}_t$. Das Vermischen dieser Konventionen ist eine häufige Fehlerquelle.

Ein gefilterter Glaubenszustand ermöglicht zwei nützliche Fragen: Was könnte als Nächstes geschehen und wie gut hat das Modell die bisher beobachteten Messwerte erklärt? Beide Fragen nutzen dieselben Übergangs- und Sensormodelle, doch die Antworten beschreiben unterschiedliche Zufallsgrößen.

Ohne zukünftige Messwerte vorhersagen

Für eine Vorhersage $k$ Schritte voraus wende die Übergangsmatrix $k$-mal auf den zuletzt gefilterten Glaubenszustand an:

Zu einem unbeobachteten zukünftigen Schritt gehört keine Aktualisierung anhand einer Beobachtung. Nachdem das Solarmodell Niedrig, Niedrig, Hoch beobachtet hat, beträgt der Glaubenszustand an Tag 3 ungefähr (0,7159; 0,2841). Eine Vorhersage ergibt $P(X_4=S)\approx \mathrm{0,7159}(\mathrm{0,8})+\mathrm{0,2841}(\mathrm{0,4})=\mathrm{0,6864}$. Rechnest du mit ungerundeten Werten weiter, ergeben sich für Sonnig die Wahrscheinlichkeiten 0,6745, 0,6698, 0,6679 und 0,6672.

Diese nähern sich $2\mathrm{/}3$. Die Kette verliert allmählich ihre Abhängigkeit vom letzten Glaubenszustand. Die Mischzeit gibt an, wie viele Schritte nötig sind, um von jedem Anfangszustand aus innerhalb eines gewählten Abstands zum Gleichgewicht zu gelangen. Eine Vorhersage nahe am Gleichgewicht enthält noch einen kleinen Einfluss der aktuellen Evidenz; sie wird nicht exakt zurückgesetzt.

Eine Vorhersage muss die Unsicherheit nicht in jedem Schritt erhöhen. Aus (0,5; 0,5) sagt diese Wetterkette (0,6; 0,4) voraus, eine stärker konzentrierte Verteilung. Bei der Konvergenz geht es um den Verlust der Abhängigkeit vom Ausgangs-Glaubenszustand, nicht um eine Regel, nach der Vorhersagen gleichmäßig werden müssen.

Eine Beobachtung vorhersagen

Für eine Leistungsvorhersage wird die Sensor-Likelihood über die vorhergesagten Zustände gemittelt:

Verwende für Hoch an Tag 4 die Zustandsvorhersage für Tag 4, nicht den gefilterten Glaubenszustand von Tag 3: $\mathrm{0,6864}(\mathrm{0,8})+\mathrm{0,3136}(\mathrm{0,3})\approx \mathrm{0,6432}$. Die Wahrscheinlichkeit für Sonnig und die Wahrscheinlichkeit für eine hohe Leistung unterscheiden sich, weil beide Wetterzustände eine hohe Leistung erzeugen können.

Die Summen aus der Filterung aufbewahren

Vor dem Normieren ist die Summe jeder Aktualisierung die Wahrscheinlichkeit dieser Beobachtung gegeben die früheren Beobachtungen. Nenne sie $c_t=P(e_t\mid e_{1:t-1})$. Die Kettenregel ergibt

Für Niedrig, Niedrig, Hoch betragen die Summen ungefähr 0,45, 0,4556 und 0,5429. Ihr vor dem Runden berechnetes Produkt ist 0,1113. Dies ist eine Summe über jeden mit der Evidenz vereinbaren verborgenen Pfad. Der beste Pfad allein trägt 0,04704 bei, also nur einen Teil der Summe.

Ein nicht normierter Vorwärtsdurchlauf ergibt dieselbe Beobachtungswahrscheinlichkeit, wenn man seine letzten Einträge summiert. Ein normierter Durchlauf ist stabiler, sofern die Summen aufbewahrt werden. Speichere bei langen Folgen $\log P(e_{1:t})={\sum }_i\log c_i$, statt winzige Werte zu multiplizieren. Hier beträgt der natürliche Logarithmus etwa −2,196.

Modelle anhand derselben Evidenz vergleichen

Eine Beobachtungswahrscheinlichkeit misst, wie gut ein Modell eine bestimmte Beobachtungsfolge erklärt. Um HMMs für mögliche Wörter anhand derselben Aufnahme zu vergleichen, bewerte die Aufnahme unter jedem Modell und kombiniere das Ergebnis mit den A-priori-Wahrscheinlichkeiten der Wörter, wenn du deren A-posteriori-Wahrscheinlichkeiten bestimmst. Längere Folgen haben gewöhnlich kleinere rohe Likelihoods. Eine kleinere Zahl aus einer längeren Aufnahme allein belegt daher kein schlechteres Modell.

Eine spätere Beobachtung kann deine Einschätzung eines früheren Zustands verändern. Die Glättung schätzt $P(X_k\mid e_{1:t})$ für $k<t$. Sie ist nützlich, wenn eine aufgezeichnete Bewegungsbahn rekonstruiert wird oder wenn eine Anwendung kurz warten kann, bevor sie eine Schätzung für die Vergangenheit ausgibt.

Die Evidenz am Zielzeitpunkt aufteilen

Die Filterung hat die Evidenz bis zum Zeitpunkt $k$ bereits als $f_k(x)=P(X_k=x\mid e_{1:k})$ zusammengefasst. Eine Rückwärtsnachricht fasst die übrigen Beobachtungen als Likelihood zusammen: $b_k(x)=P(e_{k+1:t}\mid X_k=x)$. Kombiniere beide für jeden Zustand einzeln:

Normiere die Produkte über alle Zustände. Die spätere Evidenz wird danach gewichtet, wie plausibel sie von jedem möglichen Zustand zum Zeitpunkt $k$ aus wäre.

Die zukünftige Likelihood rückwärts weitergeben

Zum letzten Zeitpunkt gibt es keine späteren Beobachtungen, daher gilt für jeden Zustand $b_t(x)=1$. Ein Schritt zurück ergibt

Multipliziere für jeden möglichen Folgezustand die Wahrscheinlichkeit des Übergangs dorthin, die Likelihood seiner Beobachtung und die verbleibende zukünftige Likelihood. Addiere dann über die Folgezustände. Eine Rückwärtsnachricht ist eine Likelihood-Funktion über mögliche Ausgangszustände, keine Zustandsverteilung; ihre Einträge müssen sich nicht zu 1 summieren.

Tag 2 im Solarbeispiel glätten

Die Beobachtungen sind Niedrig, Niedrig, Hoch. Nach den beiden niedrigen Messwerten beträgt der gefilterte Glaubenszustand von Tag 2 ungefähr (0,2146; 0,7854). Für den letzten hohen Messwert ist die Rückwärts-Likelihood von einem sonnigen Tag 2 aus $\mathrm{0,8}(\mathrm{0,8})+\mathrm{0,2}(\mathrm{0,3})=\mathrm{0,70}$. Von einem bewölkten Tag 2 aus ist sie $\mathrm{0,4}(\mathrm{0,8})+\mathrm{0,6}(\mathrm{0,3})=\mathrm{0,50}$.

Multipliziere: Die Produkte sind ungefähr $\mathrm{0,2146}(\mathrm{0,70})=\mathrm{0,1502}$ und $\mathrm{0,7854}(\mathrm{0,50})=\mathrm{0,3927}$. Normiere ihre ungerundeten Werte, um für Tag 2 eine Wahrscheinlichkeit für Sonnig von 0,2767 zu erhalten. Hoch an Tag 3 macht einen sonnigen Tag 2 plausibler, als es die ursprüngliche gefilterte Wahrscheinlichkeit von 0,2146 tat.

Bis Tag 1 fortfahren

Die Rückwärts-Likelihood von Sonnig an Tag 1 aus ist $\mathrm{0,8}(\mathrm{0,2})(\mathrm{0,70})+\mathrm{0,2}(\mathrm{0,7})(\mathrm{0,50})=\mathrm{0,182}$. Von Bewölkt aus ist sie $\mathrm{0,4}(\mathrm{0,2})(\mathrm{0,70})+\mathrm{0,6}(\mathrm{0,7})(\mathrm{0,50})=\mathrm{0,266}$. Kombiniere dies mit $f_1=(2\mathrm{/}9,7\mathrm{/}9)$ und normiere. Die geglättete Wahrscheinlichkeit für Sonnig beträgt ungefähr 0,1635 und ist damit gegenüber 0,2222 gesunken: Die gesamte Zukunft enthält neben dem abschließenden Hoch auch ein weiteres Niedrig.

Spätere Evidenz muss nicht jede frühere Schätzung in dieselbe Richtung verschieben. Zum letzten Zeitpunkt sind Glättung und Filterung gleich, weil keine spätere Evidenz vorliegt.

Die Berechnung organisieren

Der Vorwärts-Rückwärts-Algorithmus speichert zuerst alle Vorwärts-Glaubenszustände und berechnet dann Rückwärtsnachrichten und normierte Produkte. Für $t$ Schritte und $S$ Zustände benötigt die Berechnung mit dicht besetzter Matrix $O(S^{2}t)$ und speichert $O(St)$ Werte. Die Glättung mit fester Verzögerung gibt den Zustand eine feste Anzahl von Schritten hinter der Gegenwart aus und tauscht so Verzögerung gegen mehr Evidenz.

Die Beobachtungsliste umzukehren und einen gewöhnlichen Filter auszuführen ist eine andere Berechnung. Die Rückwärtsrekursion nutzt die ursprünglichen Vorwärtsübergänge und zukünftigen Likelihoods; sie führt am Ende der Aufzeichnung keine neue Anfangsverteilung ein. Geglättete Zustandswahrscheinlichkeiten liefern auch erwartete Häufigkeiten für das Lernen mit Baum-Welch.

Manchmal wird eine einzelne vollständige Erklärung der Beobachtungen gesucht. Die Viterbi-Dekodierung findet die wahrscheinlichste Folge verborgener Zustände. Sie berücksichtigt Übergänge zwischen Zuständen, die bei der getrennten Wahl der wahrscheinlichsten Zustände zu einzelnen Zeitpunkten unberücksichtigt bleiben können.

Das Ziel ändern

Gesucht ist $\arg {\max }_{x_{1:t}}P(x_{1:t}\mid e_{1:t})$. Jeder Kandidat hat denselben Evidenznenner, sodass die Maximierung des gemeinsamen Werts $P(x_{1:t},e_{1:t})$ denselben Pfad auswählt. Dieser Wert unterscheidet sich von einer A-posteriori-Wahrscheinlichkeit des Endzustands, die alle in diesem Zustand endenden Pfade addiert.

Bei den Solarbeobachtungen Hoch, Niedrig sind die nach der Glättung einzeln wahrscheinlichsten Zustände Sonnig an Tag 1 und Bewölkt an Tag 2. Dennoch ist Sonnig, Sonnig der wahrscheinlichste vollständige Pfad: Seine A-posteriori-Wahrscheinlichkeit beträgt etwa 0,3282 gegenüber 0,2872 für Sonnig, Bewölkt. Bei verbotenen Übergängen können einzeln plausible Zustände sogar einen unmöglichen Pfad bilden.

Das beste Präfix für jeden Endzustand behalten

Sei $m_t(j)$ der beste gemeinsame Wert von Pfad und Evidenz, der in Zustand $j$ endet. Initialisiere $m_1(j)=P(X_1=j)P(e_1\mid j)$. Verwende dann

Speichere den maximierenden Vorgänger als Rückwärtszeiger. Pfade, die im selben Zustand enden, haben dieselben möglichen zukünftigen Fortsetzungen, sodass ein Präfix mit niedrigerem Wert verworfen werden kann. Der Vorwärtsalgorithmus addiert konkurrierende Präfixe; Viterbi wählt ihr Maximum.

Das Trellis für Niedrig, Niedrig, Hoch ausfüllen

Die Anfangswerte sind (0,10; 0,35). An Tag 2 sind die Kandidaten für Sonnig vor der Emission $\mathrm{0,10}(\mathrm{0,8})=\mathrm{0,08}$ und $\mathrm{0,35}(\mathrm{0,4})=\mathrm{0,14}$. Behalte den zweiten und multipliziere mit 0,2. Das ergibt 0,028 mit Zeiger auf Bewölkt. Vergleiche für Bewölkt 0,02 mit 0,21; die Multiplikation des größeren Werts mit 0,7 ergibt 0,147, ebenfalls mit Zeiger auf Bewölkt.

An Tag 3 vergleicht Sonnig $\mathrm{0,028}(\mathrm{0,8})=\mathrm{0,0224}$ mit $\mathrm{0,147}(\mathrm{0,4})=\mathrm{0,0588}$. Die Multiplikation des größeren Werts mit der Hoch-Likelihood 0,8 ergibt 0,04704. Bewölkt vergleicht 0,0056 mit 0,0882; die Multiplikation des größeren Werts mit 0,3 ergibt 0,02646. Beide abschließenden Zeiger führen zu Bewölkt an Tag 2.

Vom Ende aus zurückverfolgen

Der größte Endwert ist 0,04704 bei Sonnig. Folge seinem Zeiger zu Bewölkt an Tag 2 und dann dessen Zeiger zu Bewölkt an Tag 1. Kehre diesen Rückwärtsdurchlauf um und erhalte Bewölkt, Bewölkt, Sonnig. Die Division durch die Beobachtungswahrscheinlichkeit 0,1113 ergibt die A-posteriori-Wahrscheinlichkeit von ungefähr 0,4226.

Würdest du in jeder Spalte getrennt den größten Wert wählen, gingen die gespeicherten Vorgängerbeziehungen verloren. Der Vektor der Endwerte lässt sich auch nicht zu einem gefilterten Glaubenszustand normieren: Er enthält nur einen Pfad pro Zustand, nicht deren Summen.

Für lange Folgen Logarithmen verwenden

Produkte können nach unten überlaufen. Speichere stattdessen logarithmierte Werte:

Logarithmen erhalten die Reihenfolge, sodass Pfad und Zeiger unverändert bleiben. Wahrscheinlichkeiten von null werden zu minus unendlich. Gleichwertig dazu machen negative logarithmierte Werte die Dekodierung zu einem Pfad mit minimalen Kosten durch einen zeitlich geschichteten Graphen, ein Trellis. Viterbi mit dicht besetzter Matrix benötigt $O(S^{2}t)$ Zeit und speichert $O(St)$ Zeiger. Haben mehrere Pfade denselben höchsten Wert, ist jeder eine zulässige wahrscheinlichste Erklärung.

Eine Wahrscheinlichkeitstabelle wird schwer zu speichern, wenn der Zustandsraum riesig ist. Auch kontinuierliche Glaubenszustände lassen sich im Allgemeinen nicht als endliche Tabelle darstellen. Ein Partikelfilter stellt einen Glaubenszustand durch gezogene Zustände dar und konzentriert so die Berechnung auf eine handhabbare Population von Möglichkeiten.

Wahrscheinlichkeit durch Partikel darstellen

Jedes Partikel ist ein vollständiger Zustand, kein eigenes physisches Objekt. Nach dem Resampling haben alle Partikel dasselbe Gewicht und die geschätzte Wahrscheinlichkeit eines Zustands ist der Anteil der Partikel darin. Zehn Partikel, aufgeteilt in sieben sonnige und drei bewölkte, stellen den Glaubenszustand (0,7; 0,3) dar.

Ziehe die Anfangspartikel aus $P(X_1)$. Bei einer A-priori-Verteilung von (0,5; 0,5) werden gleiche Anzahlen erwartet, aber nicht jede zufällige Stichprobe muss gleich aufgeteilt sein. Nach unserer Zeitkonvention werden diese Anfangspartikel anhand der ersten Beobachtung gewichtet und vor jedem Übergang erneut gezogen.

Zeit durch Ziehen von Übergängen fortschreiten lassen

Bewege für jeden späteren Schritt jedes Partikel unabhängig anhand der Übergangszeile seines aktuellen Zustands. Bei den Wetterzeilen (0,8; 0,2) und (0,4; 0,6) haben sieben sonnige und drei bewölkte Partikel nach der Bewegung eine erwartete Anzahl sonniger Partikel von $7(\mathrm{0,8})+3(\mathrm{0,4})=\mathrm{6,8}$.

Eine tatsächlich gezogene Stichprobe könnte sechs sonnige und vier bewölkte Partikel enthalten. Eine erwartete Anzahl kann gebrochen sein; eine tatsächlich gezogene Partikelanzahl muss ganzzahlig sein. Genau 6,8 Partikel zu behalten wäre kein Stichprobenalgorithmus.

Anhand des Messwerts gewichten

Angenommen, die neue Solarleistung ist Niedrig. Jedes sonnige Partikel erhält die Likelihood 0,2, jedes bewölkte 0,7. Die sechs sonnigen Partikel haben das Gesamtgewicht $6(\mathrm{0,2})=\mathrm{1,2}$ und die vier bewölkten $4(\mathrm{0,7})=\mathrm{2,8}$. Bei einem Gesamtgewicht von 4,0 hat Sonnig die gewichtete Wahrscheinlichkeit 0,3 und Bewölkt 0,7.

Neben den Gewichten pro Partikel zählen auch die Anzahlen. Würde man nur 0,2 und 0,7 normieren, bliebe unberücksichtigt, wie viel vorhergesagte Wahrscheinlichkeit jede Gruppe darstellt. Die Gewichtung nutzt dieselbe Bayes-Aktualisierung wie die exakte Filterung auf dieser durch Stichproben gewonnenen Vorhersage.

Eine neue Population durch Resampling ziehen

Ziehe zehn Partikel mit Zurücklegen, wobei jedes alte Partikel proportional zu seinem Gewicht ausgewählt wird. Jede neue Ziehung ist mit Wahrscheinlichkeit 0,3 Sonnig und mit Wahrscheinlichkeit 0,7 Bewölkt. Die erwartete Anzahl sonniger Partikel ist drei, ein Durchlauf kann aber zwei, vier oder eine andere Anzahl ergeben. Mehrfache Kopien sind erlaubt; sie stellen Wahrscheinlichkeitsmasse dar.

Setze die resultierenden Partikel auf gleiche Gewichte zurück. Die Evidenz hat bereits beeinflusst, welche Partikel kopiert wurden. Die alten Likelihood-Gewichte beizubehalten würde sie erneut zählen. Die nächste Iteration bewegt diese neue Population, bevor sie die nächste Beobachtung verarbeitet.

Mit der exakten Aktualisierung vergleichen

Die exakte Filterung aus (0,7; 0,3) sagt (0,68; 0,32) voraus. Niedrig ergibt dann die Gewichte (0,136; 0,224), sodass die exakte A-posteriori-Wahrscheinlichkeit für Sonnig $\mathrm{0,136}\mathrm{/}\mathrm{0,36}\approx \mathrm{0,3778}$ beträgt. Das gewichtete Ergebnis des Partikeldurchlaufs war 0,3, weil seine zufällige Bewegung nur sechs sonnige Partikel erzeugte. Resampling führt eine weitere Quelle für Schwankungen ein.

Der Ablauf besteht also aus Initialisierung, Gewichtung anhand der ersten Beobachtung und Resampling, gefolgt von wiederholter Bewegung, Gewichtung und Resampling. Lies vor dem Resampling gewichtete Anteile ab, danach Anzahlen. Ein Schritt benötigt für $N$ Partikel ungefähr $O(N)$, wenn das Ziehen und Gewichten eines Zustands festen Aufwand hat. Für zwei Wetterzustände ist die exakte Filterung einfacher. Partikelverfahren werden nützlich, wenn für einen großen oder kontinuierlichen Zustandsraum kein kompakter exakter Filter mit vertretbarem Aufwand existiert.

Eine Partikelschätzung ist zufällig. Ihre Qualität hängt daher sowohl von der Populationsgröße als auch davon ab, wo Partikel erhalten bleiben. Mehr Partikel verbessern die Näherung, aber auch eine große Population kann wenig wirksam sein, wenn fast ihre gesamte nützliche Information in einigen wenigen Stichproben liegt.

Die Größenordnung der Genauigkeit verstehen

Für die Schätzung einer Wahrscheinlichkeit $p$ aus unabhängigen Stichproben beträgt der Standardfehler ungefähr $\sqrt{p(1-p)\mathrm{/}N}$. Bei $p=\mathrm{0,3}$ sind das etwa 0,046 für 100 Stichproben und 0,0046 für 10.000. Der Fehler eines Partikelfilters hat oft dieselbe ungefähre Größenordnung $1\mathrm{/}\sqrt{N}$, obwohl durch Resampling gezogene Partikel abhängig sind und auch die Schwierigkeit des Modells eine Rolle spielt.

Eine Vervierfachung der Population halbiert den Fehler ungefähr; eine Verdopplung tut das nicht. Bei einer festen Beobachtungsfolge nähert sich ein konsistenter Partikelfilter mit wachsender Partikelanzahl dem exakten Glaubenszustand. Dadurch wird weder ein einzelner endlicher Durchlauf exakt noch werden Fehler im zugrunde liegenden Modell beseitigt. Lege für reproduzierbare Vergleiche einen Startwert des Zufallszahlengenerators fest oder vergleiche Ergebnisse aus mehreren Durchläufen.

Zwei Fehlermuster unterscheiden

Ohne Resampling kann die Multiplikation von Likelihoods über viele Schritte dazu führen, dass fast jedes Partikel ein vernachlässigbares Gewicht hat. Resampling ersetzt diesen ungenutzten Aufwand durch Kopien nützlicher Zustände. Es kann aber auch einen alternativen Ort auslöschen, der vorübergehend weniger gut passt.

Resampling allein kann einen fehlenden Bereich nicht wiederherstellen. Die Erholung hängt davon ab, dass Bewegungsziehungen ihn erreichen oder ein anderer Mechanismus dort Partikel einführt. Machen Übergänge diesen Bereich nahezu unerreichbar, kann die Erholung langsam sein. Kleine zufällige Störungen hinzuzufügen oder einen kleinen Anteil durch neue Partikel zu ersetzen kann helfen. Diese Entscheidungen müssen jedoch zur Zustandsrepräsentation und zur beabsichtigten Näherung passen.

Mit einem Gesamtgewicht von null umgehen

Erhält jedes Partikel das Gewicht null, sind die Resampling-Wahrscheinlichkeiten nicht definiert. Die Beobachtung kann an anderer Stelle im Modell möglich sein, obwohl die gezogene Population diese Zustände verfehlt hat. Initialisiere aus einer geeigneten Verteilung neu, etwa der A-priori-Verteilung oder einer gleichmäßigen Verteilung über zulässige Zustände, und prüfe das Sensormodell. Eine Ausreißerkomponente größer als null kann solche Ausfälle verringern. Schließt das Modell selbst die Beobachtung überall aus, können mehr Partikel allein das Problem nicht beheben.

Eine zum Modell passende Darstellung wählen

Die exakte Vorwärtsfilterung eignet sich für kleine diskrete Zustandsräume. Ein Kalman-Filter ist exakt, wenn die A-priori-Verteilung gaußsch ist und Übergangs- und Sensormodell linear mit gaußschem Rauschen sind; ein Mittelwert und eine Kovarianz beschreiben dann den Glaubenszustand. Ein Partikelfilter kann nichtlineare Modelle und Glaubenszustände mit getrennten Maxima behandeln.

Eine einzelne Gauß-Verteilung kann einen Roboter nicht getreu darstellen, der sich wahrscheinlich in einem von zwei weit entfernten Korridoren befindet, aber wahrscheinlich nicht dazwischen. Partikelgruppen können beide Alternativen beibehalten. Für ein lineares Gauß-Modell zur Objektverfolgung vermeidet die Kalman-Darstellung gewöhnlich unnötiges Stichprobenrauschen.

In einem DBN enthält jedes Partikel eine vollständige Belegung aller Zustandsvariablen. Ziehe die Variablen des nächsten Schritts in topologischer Ordnung aus ihren auf die Elternknoten bedingten Modellen. Die Faktorisierung verringert den Aufwand pro Stichprobe gegenüber der Aufzählung jedes gemeinsamen Zustands. Hochdimensionale Glaubenszustände können dennoch viele Partikel benötigen, um ihre wichtigen Bereiche abzudecken.

Objektverfolgung kombiniert unsichere Bewegung mit verrauschten Messungen. Der verborgene Zustand kann Position und Geschwindigkeit enthalten; Beobachtungen können von GPS, Radar oder einer Kamera stammen. Die Filterung führt eine Verteilung plausibler Orte von einem Messwert zum nächsten fort.

In einem Korridor mit fünf Zellen lokalisieren

Ein Roboter befindet sich in einer von fünf Zellen, wobei an den Zellen 1 und 4 Türen liegen. Sein Sensor meldet an einer Tür mit Wahrscheinlichkeit 0,9 eine Tür und sonst mit Wahrscheinlichkeit 0,2. Beginne gleichmäßig mit Wahrscheinlichkeit 0,2 pro Zelle. Eine Türmeldung ergibt die Gewichte (0,18; 0,04; 0,04; 0,18; 0,04) mit der Summe 0,48.

Der aktualisierte Glaubenszustand ist $(\mathrm{0,375};1\mathrm{/}12;1\mathrm{/}12;\mathrm{0,375};1\mathrm{/}12)\mathrm{.}$ Beide Türzellen bleiben plausibel. Nur ein Maximum auszuwählen würde die Symmetrie verwerfen, die der Sensor noch nicht aufgelöst hat.

Den gesamten Glaubenszustand bewegen

Der Roboter versucht, sich eine Zelle nach rechts zu bewegen. Das gelingt mit Wahrscheinlichkeit 0,8 und mit Wahrscheinlichkeit 0,2 bleibt er stehen; von Zelle 5 aus bleibt er an der Wand mit Sicherheit stehen. Jede Zelle erhält Beiträge von allen Ausgangszellen, die sie erreichen können.

Zelle 1 erhält $\mathrm{0,375}(\mathrm{0,2})=\mathrm{0,075}$. Zelle 2 erhält $\mathrm{0,375}(\mathrm{0,8})+(1\mathrm{/}12)(\mathrm{0,2})\approx \mathrm{0,3167}$. Die Zellen 3 und 4 erhalten ungefähr 0,0833 und 0,1417. Zelle 5 erhält $(\mathrm{0,375})(\mathrm{0,8})+1\mathrm{/}12\approx \mathrm{0,3833}$: Sowohl die Zugänge aus Zelle 4 als auch die gesamte bereits in Zelle 5 liegende Wahrscheinlichkeitsmasse bleiben dort.

Die Vorhersage ist ungefähr (0,0750; 0,3167; 0,0833; 0,1417; 0,3833). Würde man den Rand wie eine weitere gewöhnliche Bewegung mit Wahrscheinlichkeit 0,8 behandeln, ginge Wahrscheinlichkeit über den modellierten Korridor hinaus verloren.

Keine Tür beobachten

Die Likelihood für keine Tür beträgt 0,1 in den Zellen 1 und 4 und sonst 0,8. Die Multiplikation mit der ungerundeten Vorhersage ergibt ein Gesamtgewicht von ungefähr 0,6483. Das Normieren ergibt (0,0116; 0,3907; 0,1028; 0,0219; 0,4730).

Die wahrscheinlichen Orte sind nun die Zellen 2 und 5, direkt hinter den beiden Türen. Der Glaubenszustand bleibt multimodal und hat getrennte Maxima. Ein einzelner Sensorwert ist Evidenz, keine Messung der wahren Position; bleiben Alternativen erhalten, können spätere Bewegungen und Messwerte zwischen ihnen unterscheiden.

Auf realistische Roboter erweitern

Bei der Monte-Carlo-Lokalisierung ist ein Partikel eine Pose: Position in Metern und Ausrichtung. Bewege jede Pose anhand der befohlenen Bewegung zuzüglich Rauschen und gewichte sie dann anhand der Übereinstimmung zwischen beobachteten Entfernungen und den aus einer bekannten Karte vorhergesagten Entfernungen. Eine konzentrierte Anfangspopulation verfolgt einen bekannten Startort; eine breit gestreute ermöglicht globale Lokalisierung.

Ist auch die Karte unbekannt, nimm sie in den verborgenen Zustand auf. Die gleichzeitige Lokalisierung und Kartierung, kurz SLAM, schätzt Karte und Pose gemeinsam. Bei mehreren Objekten entsteht außerdem die Frage der Datenassoziation: Welche Erfassung gehört zu welchem Objekt? Unterschiedliche Zuordnungen ergeben unterschiedliche Hypothesen über Bewegungsbahnen.

Die Fahrzeugverfolgung kann eine Bewegungsvorhersage mit GPS-Messwerten kombinieren. Bei 15 m/s und Schritten von einer Sekunde beträgt die erwartete Bewegung zwischen Messwerten etwa 15 m. Ein geeignetes Kalman-Modell kombiniert unsichere Bewegung und Messung, um die Wirkung verrauschter Messwerte zu verringern. Ein Übergangsmodell, das keine tatsächlichen Bewegungsschwankungen zulässt, kann die wahre Bewegungsbahn ausschließen, selbst wenn seine Rechnung korrekt ist.

Sequenzmodelle können sowohl Labels als auch physische Zustände erschließen. Ein Spracherkennungssystem verknüpft ein veränderliches Audiosignal mit möglichen Wörtern. Ein Wortartenannotator verknüpft beobachtete Wörter mit verborgenen grammatischen Labels. Beide müssen Entscheidungen im zeitlichen Kontext bewerten.

Passung zum Audiosignal und Sprachwahrscheinlichkeit kombinieren

Die Spracherkennung sucht die Wortfolge mit der größten A-posteriori-Wahrscheinlichkeit:

Das akustische Modell $P(s\mid w)$ bewertet, wie gut Wörter das Audiosignal erklären; das Sprachmodell $P(w)$ bewertet ihre A-priori-Plausibilität. Der gemeinsame Nenner $P(s)$ beeinflusst die Rangfolge nicht. Eine akustische Likelihood ist selbst keine A-posteriori-Wahrscheinlichkeit von Wörtern.

Vergleiche für illustrative Werte „alte Minen“ mit „alte Mienen“. Die akustischen Likelihoods sind 0,0004 und 0,0005; die Sprachwahrscheinlichkeiten sind 0,00002 und 0,000001. Das erste Produkt ist $8\times {10}^{-9}$ und das zweite $5\times {10}^{-10}$. Durch den sprachlichen Kontext gewinnt die erste Wortfolge trotz ihrer etwas niedrigeren akustischen Likelihood.

Audiosignale in eine zeitliche Folge umwandeln

Ein üblicher Aufbau verwendet überlappende Segmente von 25 ms, die alle 10 ms beginnen. Das ergibt etwa 100 Merkmalsvektoren pro Sekunde. Die Vektoren sind Beobachtungen. Verborgene Zustände stehen für Teile von Sprachlauten, also Phonen, häufig mit Zuständen für Anfang, Mitte und Ende. Ein Aussprachewörterbuch verbindet Wörter mit Phonen.

Selbstschleifen erlauben einem Lautzustand, mehrere Segmente einzunehmen. Ohne flexible Dauer würde eine veränderte Sprechgeschwindigkeit eine feste und häufig ungeeignete Zuordnung zwischen Segmenten und Lautzuständen erfordern. Unterschiedliche Zustandspfade drücken unterschiedliche Zuordnungen derselben beobachteten Aufnahme aus.

Kurzen Sprachkontext darstellen

Ein Bigrammmodell nähert eine Wortfolge durch $P(w_1){\prod }_{i=2}^{n}P(w_i\mid w_{i-1})$ an. Ein Trigramm nutzt die zwei vorherigen Wörter. Schätze diese bedingten Wahrscheinlichkeiten anhand von Texthäufigkeiten. Die Markov-Annahme ist hier eine praktische Näherung: Weitreichende grammatische und semantische Beziehungen können über ein oder zwei vorhergehende Wörter hinausgehen.

Viterbi kann den besten Zustandspfad durch verknüpfte Phon- und Wortmodelle finden. Bei großem Vokabular verwirft die Strahlsuche weniger vielversprechende Teilpfade, um den Aufwand zu verringern. Ein einmal verworfener Pfad kann später nicht mehr gewinnen, sodass eine schmale Suchbreite den besten vollständigen Pfad übersehen kann. Außerdem hat der beste einzelne Zustandspfad für eine Wortfolge ein anderes Ziel als die Summe über alle ihre möglichen Zuordnungen.

Dieselbe Struktur für Labels nutzen

Bei der Wortartenannotation sind Zustände die Labels und Beobachtungen die Wörter. Übergänge bewerten $P({\mathrm{L}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}}_i\mid {\mathrm{L}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}}_{i-1})$; Emissionen bewerten $P({\mathrm{W}\mathrm{o}\mathrm{r}\mathrm{t}}_i\mid {\mathrm{L}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}}_i)$. In „Sie sehen Fliegen“ kann „Fliegen“ ein Nomen oder ein Verb sein. Der Labelpfad muss sowohl Wort-Likelihoods als auch Übergänge zwischen Labels berücksichtigen.

HMMs in der Spracherkennungspraxis einordnen

Systeme mit großem Vokabular kombinierten von den 1980er-Jahren bis Anfang der 2010er-Jahre häufig HMMs mit akustischen gaußschen Mischmodellen. Um 2010–2012 gewannen neuronale akustische Modelle in hybriden DNN-HMM-Systemen an Bedeutung. Moderne durchgängige neuronale Systeme können Audiosignale ohne explizites HMM auf Text abbilden. Die gemeinsamen Ideen der unsicheren Zuordnung, der Sequenzbewertung und der dynamischen Programmierung bleiben nützlich. HMMs werden auch in Anwendungen wie der Gensuche in DNA eingesetzt.