Markovmodellen en verborgen Markovmodellen

Een veranderend systeem heeft voor elk moment een toestand nodig en een regel voor de overgang naar het volgende moment. Een Markovketen in discrete tijd legt deze toestanden vast op gelijkmatig verdeelde tijdstappen. Kies de toestand en de tijdstap samen: dagelijks weer en de locatie van een robot per seconde beschrijven verschillende processen.

Wat de huidige toestand moet bevatten

De eerste-orde-Markoveigenschap luidt:

Zodra de huidige toestand bekend is, voegen eerdere toestanden geen informatie toe over de volgende toestand. Dit is voorwaardelijke onafhankelijkheid, geen onafhankelijkheid tussen opeenvolgende toestanden. Als het weer van vandaag onbekend is, kan kennis van het weer van gisteren helpen om dat van morgen te voorspellen.

Een keten heeft een beginverdeling $P(X_1)$ en een overgangsmodel nodig. We gebruiken tijdshomogene overgangen: bij elke stap gelden dezelfde kansen. Sommige AI-teksten noemen dit een stationariteitsaanname. In de kansrekening heeft een stationair proces gezamenlijke kansverdelingen die niet veranderen als je de tijd verschuift; vaste overgangen alleen garanderen dat niet. Een tijdshomogene keten die in een stationaire verdeling begint, voldoet daar wel aan.

Lees een overgangsmatrix af

Neem voor het weer de toestanden zonnig (S) en bewolkt (C). De rijen geven de huidige toestand aan en de kolommen de volgende toestand:

Vanuit zonnig is de volgende dag met kans 0,8 zonnig en met kans 0,2 bewolkt. Vanuit bewolkt zijn die kansen 0,4 en 0,6. Elke rij telt op tot 1 omdat die alle bestemmingen vanuit één begintoestand bevat. Kolommen hoeven niet op te tellen tot 1. Een toestandsdiagram geeft dezelfde tabel weer met pijlen, waaronder pijlen terug naar dezelfde toestand.

Sommige boeken gebruiken de getransponeerde conventie. Lees vóór het rekenen de definitie van een element: hier is $T_{ij}=P(X_{t+1}=j\mid X_t=i)$. Correcte getallen in de verkeerde oriëntatie leveren een verkeerde voorspelling op.

Vermenigvuldig langs een pad

Voor een specifiek pad gebruik je de beginkans en één overgang per stap:

Als dag 1 zeker zonnig is, heeft het pad zonnig, zonnig, bewolkt, bewolkt de kans

De eerste overgang draagt 0,8 bij, de omslag 0,2 en het bewolkt blijven 0,6. Als je afzonderlijke dagelijkse frequenties vermenigvuldigt, laat je de verbanden tussen dagen weg. In een bayesiaans netwerk zijn die verbanden de pijlen in $X_1\to X_2\to X_3\to \cdots$.

Bewaar genoeg geschiedenis in de toestand

Een model van de tweede orde hangt af van de laatste twee waarden. Maak er een model van de eerste orde van door de toestand te definiëren als (gisteren, vandaag). Twee weerwaarden leveren dan vier mogelijke paren op. Een overgang vanuit (zonnig, bewolkt) kan alleen leiden naar een paar dat met bewolkt begint, omdat aangrenzende paren moeten overlappen. Bewaar voor een proces van orde $k$ de laatste $k$ waarden samen; de algoritmen blijven van de eerste orde, terwijl het aantal gecombineerde toestanden groeit.

Een keten bevindt zich op elk tijdstip in één toestand, maar je weet misschien niet welke. Een toestandsverdeling legt die onzekerheid vast als een rijvector. De elementen geven de kansen van de mogelijke toestanden, geen tijdsaandelen binnen één stap.

Tel elke route naar een bestemming op

Om te voorspellen of het morgen zonnig is, bekijk je beide manieren om daar te komen: vandaag kan het zonnig of bewolkt zijn. Weeg elke overgang met de kans op de begintoestand ervan:

Voor de volledige vector is dit $p_{t+1}=p_{t}T$. Na $k$ overgangen is $p_{t+k}=p_t{T}^k$. Deze actualisatie heet soms het vereenvoudigd voorwaarts algoritme, de versie van HMM-filtering zonder observaties.

Doorloop de weerketen

Gebruik de rijen (0,8; 0,2) vanuit zonnig en (0,4; 0,6) vanuit bewolkt. Begin met een zeker zonnige dag: $p_1=(1,0)$. Eén overgang geeft $p_2=(\mathrm{0,8};\mathrm{0,2})$. Voor dag 3 is de bijdrage aan zonnig $\mathrm{0,8}\times \mathrm{0,8}=\mathrm{0,64}$ vanuit zonnig en $\mathrm{0,2}\times \mathrm{0,4}=\mathrm{0,08}$ vanuit bewolkt. Tel ze op en je krijgt 0,72. De bijdragen aan bewolkt zijn $\mathrm{0,8}\times \mathrm{0,2}=\mathrm{0,16}$ en $\mathrm{0,2}\times \mathrm{0,6}=\mathrm{0,12}$, samen 0,28.

Dus $p_3=(\mathrm{0,72};\mathrm{0,28})$. Nog één actualisatie geeft $P(X_4=S)=\mathrm{0,72}\times \mathrm{0,8}+\mathrm{0,28}\times \mathrm{0,4}=\mathrm{0,688}$ en $P(X_4=C)=\mathrm{0,312}$. Gebruik tussen stappen ongeronde waarden en rond weergegeven resultaten aan het eind af.

Controleer de betekenis en oriëntatie

Elk resultaat moet niet-negatief zijn en optellen tot 1. Zet bij de rijconventie de verdeling links. Als je in plaats daarvan $T{p}_1^{𝖳}$ gebruikt, krijg je de kolom (0,8; 0,4), met als totaal 1,2. Die berekening selecteert de kansen om vanuit twee verschillende begintoestanden zonnig te bereiken; ze verdeelt niet één beginkansinschatting over bestemmingen.

De waarde 0,72 op dag 3 betekent dat ongeveer 72% van veel onafhankelijke reeksen met een zonnige dag 1 op dag 3 zonnig zal zijn. De waarde beschrijft geen vast herhalend weerpatroon en ook geen dag die voor 72% zonnig is.

Waarom voorspellen beheersbaar blijft

Een actualisatie met een dichte matrix voor $S$ toestanden kost $O(S^2)$ bewerkingen. De huidige vector vat alle eerdere paden samen, zodat de kosten per overgang gelijk blijven naarmate de tijd verstrijkt. Als je in plaats daarvan elk pad vanuit een bekend begin zou opsommen, heb je op tijdstip $t$ juist $S^{t-1}$ paden nodig.

Voor deze weerketen naderen opeenvolgende kansen op zonnig de waarde $2\mathrm{/}3$. Als $s_t=P(X_t=S)$, dan is $s_{t+1}=\mathrm{0,4}+\mathrm{0,4}{s}_t$. Trek $2\mathrm{/}3$ af en je ziet dat het verschil bij elke stap met een factor 0,4 krimpt. Andere ketens kunnen zich anders gedragen; voor convergentie zijn de voorwaarden nodig die bij stationaire verdelingen aan bod komen.

Je kunt ook een reeks simuleren. Trek de begintoestand en trek daarna uit de overgangsrij van de toestand waarin de keten zich bevindt. Vanuit zonnig kies je bij een uniforme willekeurige trekking onder 0,8 voor zonnig; bij een trekking van ten minste 0,8 kies je bewolkt. Door veel reeksen te simuleren, schat je dezelfde voorspelde verdeling en maak je kennis met het idee van steekproeftrekking dat deeltjesfilters gebruiken.

Een verdeling kan onveranderd blijven terwijl afzonderlijke reeksen blijven bewegen. Een stationaire verdeling beschrijft dit evenwicht. Ze is nuttig voor voorspellingen op lange termijn, maar haar bestaan alleen vertelt niet of een keten die verdeling vanuit een bepaald begin nadert.

Los de balansvergelijkingen op

Een stationaire rijvector voldoet aan $\pi =\pi T$ en aan ${\sum }_j{\pi }_j=1$ en heeft niet-negatieve elementen. Voor de weerketen moet de kansstroom van zonnig naar bewolkt in evenwicht zijn met de kansstroom terug:

De eerste vergelijking geeft ${\pi }_S=2{\pi }_C$. Substitutie geeft $3{\pi }_C=1$, dus $\pi =(2\mathrm{/}3,1\mathrm{/}3)$. Voor een keten met twee toestanden en overgangskansen $a$ van toestand 1 naar 2 en $b$ van 2 naar 1 geldt ${\pi }_1=b\mathrm{/}(a+b)$ als $a+b>0$.

Schrijf bij meer toestanden per toestand één vergelijking voor de binnenkomende stroom. Vervang er één door de vergelijking dat de som 1 is en los het lineaire stelsel op. De balansvergelijkingen alleen laten de schaal onbepaald. Vermenigvuldig ten slotte de gevonden vector met de matrix om die te controleren.

Neem voor deelfietsstations A, B, C de rijen (0,6; 0,2; 0,2), (0,1; 0,8; 0,1) en (0,2; 0,2; 0,6). De oplossing is (0,25; 0,5; 0,25). De binnenkomende kans bij B is bijvoorbeeld $\mathrm{0,25}(\mathrm{0,2})+\mathrm{0,5}(\mathrm{0,8})+\mathrm{0,25}(\mathrm{0,2})=\mathrm{0,5}$. Een uniforme kansverdeling zou niet door deze controle komen.

Onderscheid drie vragen

Irreducibel betekent dat elke toestand elke andere toestand kan bereiken, eventueel via meerdere overgangen. Aperiodiek betekent dat terugkeer niet vastzit aan een vaste cyclus van meer dan één stap. Alle elementen van de weermatrix zijn positief, dus aan beide voorwaarden is voldaan. In een eindige irreducibele keten geven stationaire kansen ook de aandelen stappen op lange termijn in elke toestand, zelfs als periodiciteit convergentie van de verdeling op een specifiek tijdstip verhindert.

Twee verhelderende tegenvoorbeelden

Als twee toestanden altijd van de ene naar de andere overgaan, wisselt de verdeling vanuit een zekere eerste toestand tussen (1, 0) en (0, 1). De unieke stationaire vector is (0,5; 0,5), maar deze voorspellingen naderen die nooit. Over een lange reeks neemt elke toestand nog steeds de helft van de stappen in beslag.

Als beide toestanden absorberend zijn, blijft elk voor altijd waar die is. Elke vector (q, 1 − q) is stationair, dus er is geen uniek evenwicht dat alle begintoestanden delen. Deze voorbeelden laten zien waarom uniciteit, convergentie en tijdgemiddelden afzonderlijke controles vereisen.

De beginverdeling beschrijft het begin; die is alleen gelijk aan een stationaire verdeling als je in evenwicht begint. Vaste overgangskansen beschrijven de wetmatigheid van het model, niet de huidige verdeling. PageRank gebruikt stationaire kansen om pagina's te rangschikken in een model van een willekeurige websurfer. Markovketen-Monte-Carlo bouwt een keten met een gewenste stationaire verdeling, zodat de keten op lange termijn steekproeven kan leveren.

Een sensormeting geeft informatie over een toestand zonder die volledig te onthullen. In een verborgen Markovmodel, of HMM, verandert de toestand in de loop van de tijd en levert elke toestand een observatie op. Een robot kan weten wat zijn afstandssensor heeft gemeld, terwijl zijn positie onzeker blijft.

Specificeer drie kansmodellen

Een HMM heeft een beginverdeling van de toestand, een overgangsmodel en een sensormodel nodig:

De verborgen toestand is een discrete variabele. Het sensormodel, ook wel emissie- of observatiemodel genoemd, geeft de aannemelijkheid van elke observatie in elke toestand. We kennen rechtstreeks een a-prioriverdeling toe aan $X_1$ en observeren daar $E_1$. Teksten die beginnen met een niet-waargenomen $X_0$ voeren in plaats daarvan vóór de eerste observatie een overgang uit.

De toestand heeft de eerste-orde-Markoveigenschap. De observatie op een tijdstip hangt alleen af van de toestand op dat tijdstip: $P(E_t\mid X_{1:t},E_{1:t-1})=P(E_t\mid X_t)$. In een bayesiaans netwerk teken je een keten van verborgen toestanden en voeg je vanuit elke toestand een pijl naar de bijbehorende observatie toe.

Bouw het zonnepaneelmodel

Het verborgen weer is zonnig of bewolkt, met overgangsrijen (0,8; 0,2) en (0,4; 0,6). Beide begintoestanden hebben kans 0,5. De dagelijkse opbrengst van het paneel is hoog of laag:

Elke rij van het sensormodel telt op tot 1. Een bewolkte dag kan toch een hoge opbrengst geven, dus een hoge opbrengst wijst niet met zekerheid op zonnig weer. Evenzo is $P(L\mid C)=\mathrm{0,7}$ een uitspraak over de opbrengst op bewolkte dagen. Om $P(C\mid L)$ te bepalen, heb je ook de a-prioriverdeling en de regel van Bayes nodig.

Bereken de gezamenlijke kans van toestanden en observaties

Voor een specifiek toestandsverloop en een specifieke observatiereeks geldt:

Voor bewolkt, bewolkt, zonnig met laag, laag, hoog begin je met $\mathrm{0,5}\times \mathrm{0,7}=\mathrm{0,35}$. Bewolkt blijven en laag waarnemen geeft $\mathrm{0,35}\times \mathrm{0,6}\times \mathrm{0,7}=\mathrm{0,147}$. Overgaan naar zonnig en hoog waarnemen geeft $\mathrm{0,147}\times \mathrm{0,4}\times \mathrm{0,8}=\mathrm{0,04704}$.

Observaties kunnen afhankelijk zijn, ook al lopen er geen directe pijlen tussen. Aanhoudend bewolkt weer maakt dat opeenvolgende lage metingen vaak samen voorkomen. Als je conditioneert op de verborgen toestanden, verdwijnt die afhankelijkheid. Observaties actualiseren de kansinschatting van de waarnemer; een lage opbrengst waarnemen verandert op zichzelf het weer niet.

Kies de inferentievraag

Dezelfde drie modellen ondersteunen alle vijf taken. Wat verandert, is welke variabelen je behoudt, welke je uitsommeert en of je over paden sommeert of de hoogste padscore kiest.

De definitie van de toestand bepaalt wat het model kan onthouden. Een bruikbaar tijdsmodel bewaart de informatie die nodig is om de volgende toestand te voorspellen en houdt inferentie betaalbaar. De kansen moeten ook passen bij de gegevens en sensorstoringen waarmee het model te maken krijgt.

Kies voldoende toestandsinformatie

Alleen positie kan onvoldoende zijn voor een object dat door zijn traagheid blijft bewegen: eerdere posities onthullen de richting. Door snelheid toe te voegen kan de huidige toestand die richting verklaren. Voeg het seizoen toe als de dynamiek daarvan afhangt. Deze keuzes maken de Markovbenadering redelijker; ze bepalen welke informatie wordt meegenomen naar de volgende stap.

Een continue grootheid kun je op een rooster plaatsen. Temperaturen van 10 °C tot 20 °C in stappen van 0,1 °C geven 101 waarden, inclusief beide eindpunten. Een fijnere indeling vergroot het aantal toestanden. Als je meerdere ingedeelde grootheden combineert, vermenigvuldig je hun aantallen en kost exacte inferentie met een dichte matrix $O(S^2)$ per stap.

Tel onafhankelijke parameters

Een rij met $r$ categorieën heeft $r-1$ vrije parameters, omdat het laatste element door hun som vastligt. Met $S$ toestanden en $O$ observatiewaarden heeft een onbeperkt HMM daarom

vrije parameters nodig: voor de a-prioriverdeling, overgangen en emissies. Het zonnepaneelmodel met twee toestanden en twee opbrengsten heeft er $1+2+2=5$ nodig. Als je elk tabelelement telt, tel je de beperkingen op de rijsommen als extra keuzes mee.

Factoriseer de toestand met een dynamisch bayesiaans netwerk

Een dynamisch bayesiaans netwerk (DBN) bewaart meerdere toestandsvariabelen en geeft elk eigen ouderknopen. Het kan lokale afhankelijkheden uitdrukken zonder een enorme volledige overgangstabel op te bouwen. Twintig Booleaanse variabelen hebben $2^{20}=\mathrm{1.048.576}$ gezamenlijke toestanden; een volledige overgangstabel heeft $2^{40}$ elementen. Als elke Booleaanse variabele in de volgende stap drie Booleaanse ouderknopen heeft, zijn voor haar tabel acht kansen nodig, dus voor alle 20 samen $20\times 8=160$.

Je kunt een discreet DBN omzetten in een HMM door een volledige waardetoekenning als één toestand te behandelen. Gefactoriseerde opslag is compact, maar exacte inferentie kan nog steeds duur worden als afhankelijkheden veel variabelen koppelen. Methoden met deeltjes kunnen deze waardetoekenningen rechtstreeks trekken.

Schat rijen op basis van gegevens

Als toestanden zijn gelabeld, gebruik je voorwaardelijke tellingen. Veertig zonnige opvolgers uit 50 vastgelegde overgangen vanuit zonnig geven $P(S\to S)=40\mathrm{/}50=\mathrm{0,8}$. De noemer telt overgangen vanuit zonnig, niet alle dagen in de registratie. Een toestand aan het einde van een registratie heeft geen waargenomen opvolger.

Nultellingen leveren meest aannemelijke kansen van nul op. Een correctie waarbij je één optelt, geeft elke bestemming één pseudotelling en verhoogt het rijtotaal overeenkomstig. Zo voorkom je dat je een overgang uitsluit alleen omdat die in een kleine trainingsregistratie niet voorkwam. Als toestanden verborgen zijn, wisselt Baum-Welch gegladde verwachte tellingen af met nieuwe schattingen van de parameters.

Geef storingen een plaats in het sensormodel

Als elke mogelijke toestand aannemelijkheid nul aan een meting toekent, heeft een actualisatie totaal nul en kun je niet normaliseren. Een kleine uitbijtercomponent kan ongebruikelijke metingen enige kans geven. Een genormaliseerd mengsel heeft de vorm $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 componentverdelingen moeten genormaliseerd zijn.

Het effect van een meting hangt af van aannemelijkheidsverhoudingen tussen toestanden. Gelijke aannemelijkheden laten de voorspelde kansinschatting na normalisatie ongewijzigd. Een kleine aannemelijkheid onder elke toestand kan nog steeds informatief zijn als de aannemelijkheden onderling sterk verschillen.

Filtering volgt de huidige verborgen toestand met alle observaties die tot nu toe beschikbaar zijn. Het resultaat is een kansverdeling $f_t(x)=P(X_t=x\mid e_{1:t})$. Je actualiseert deze compacte verdeling wanneer een nieuwe meting binnenkomt, zonder elk mogelijk eerder pad te bewaren.

Voorspel, weeg en normaliseer

Verplaats voor een latere stap eerst de kansinschatting met het overgangsmodel:

Weeg daarna elke bestemming met de aannemelijkheid van de nieuwe observatie en normaliseer:

De voorspelling beschrijft waar de toestand naartoe kan zijn gegaan. De actualisatie met de observatie is de regel van Bayes op het nieuwe tijdstip. Met een a-prioriverdeling voor $X_1$ begin je door die verdeling te wegen met de eerste observatie; daarvoor vindt geen overgang plaats.

Dag 1: neem laag waar

Gebruik het zonnepaneelmodel: a-prioriverdeling (0,5; 0,5), overgangsrijen (0,8; 0,2) en (0,4; 0,6), en aannemelijkheden voor laag (0,2; 0,7). Wegen geeft $\mathrm{0,5}(\mathrm{0,2})=\mathrm{0,10}$ voor zonnig en $\mathrm{0,5}(\mathrm{0,7})=\mathrm{0,35}$ voor bewolkt. Het totaal is 0,45. Deel elk gewicht hierdoor en je krijgt $f_1=(2\mathrm{/}9,7\mathrm{/}9)\approx (\mathrm{0,2222};\mathrm{0,7778})$.

Dag 2: neem opnieuw laag waar

De voorspelling geeft ${\bar{f}}_2(S)=(2\mathrm{/}9)(\mathrm{0,8})+(7\mathrm{/}9)(\mathrm{0,4})=22\mathrm{/}45\approx \mathrm{0,4889}$. Bewolkt heeft kans $23\mathrm{/}45\approx \mathrm{0,5111}$. De nieuwe gewichten zijn $22\mathrm{/}225\approx \mathrm{0,0978}$ en $161\mathrm{/}450\approx \mathrm{0,3578}$. Hun totaal is $41\mathrm{/}90\approx \mathrm{0,4556}$, wat $f_2=(44\mathrm{/}205,161\mathrm{/}205)\approx (\mathrm{0,2146};\mathrm{0,7854})$ oplevert.

De tweede lage opbrengst verhoogt de kansinschatting voor bewolkt slechts een beetje. De beweging naar het evenwicht van de keten, waarin zonnig vaker voorkomt, werkt de nieuwe observatie ten gunste van bewolkt tegen. Als je laag rechtstreeks op de kansinschatting van gisteren zou toepassen, mis je die beweging.

Dag 3: neem hoog waar

Voorspel ${\bar{f}}_3=(498\mathrm{/}1025,527\mathrm{/}1025)\approx (\mathrm{0,4859};\mathrm{0,5141})$. Hoog heeft aannemelijkheden (0,8; 0,3), dus de gewichten zijn ongeveer (0,3887; 0,1542). Deel door hun totaal, ongeveer 0,5429, om $f_3\approx (\mathrm{0,7159};\mathrm{0,2841})$ te krijgen.

Hoog is onder zonnig $\mathrm{0,8}\mathrm{/}\mathrm{0,3}\approx \mathrm{2,67}$ keer zo waarschijnlijk als onder bewolkt. Die aannemelijkheidsverhouding verschuift de kansverhouding naar zonnig. Een grote aannemelijkheid op zichzelf zegt minder dan haar grootte ten opzichte van de aannemelijkheid van de concurrerende toestand.

Houd een online filter betrouwbaar

Een stap met een dichte matrix kost $O(S^2)$ tijd en slaat $O(S)$ elementen van de kansinschatting op, onafhankelijk van de lengte van de geschiedenis. Dit is exacte variabele-eliminatie: elke eerdere toestand wordt uitgesommeerd terwijl je verdergaat.

Normaliseer bij elke observatie. Zonder schaling bewaart de vector gezamenlijke kansen van toestand en observaties, die kleiner kunnen worden dan het bereik van drijvendekommagetallen. Bewaar de weggedeelde totalen apart als je de aannemelijkheid van de observatiereeks nodig hebt. Een totaal van nul vereist herstel van het model of van de toestanden die de deeltjes vertegenwoordigen; delen kan dat niet oplossen.

Onze formule met rijvectoren is $f_{t+1}\propto (f_{t}T)O_{t+1}$, waarbij de diagonaalmatrix de nieuwe aannemelijkheden bevat. Voor kolomvectoren is de equivalente formule $f_{t+1}\propto O_{t+1}{T}^{𝖳}{f}_t$. Het verwarren van deze conventies is een veelvoorkomende bron van fouten.

Een gefilterde kansinschatting ondersteunt twee nuttige vragen: wat zou er hierna kunnen gebeuren en hoe goed verklaarde het model de metingen die al zijn gedaan? Beide gebruiken dezelfde overgangs- en sensormodellen, maar de antwoorden beschrijven verschillende stochastische grootheden.

Voorspel zonder toekomstige metingen

Voor een voorspelling $k$ stappen vooruit pas je de overgangsmatrix $k$ keer toe op de laatste gefilterde kansinschatting:

Bij een toekomstige stap waarvoor geen observatie bekend is, hoort geen actualisatie met een observatie. Nadat het zonnepaneelmodel laag, laag, hoog heeft waargenomen, is de kansinschatting op dag 3 ongeveer (0,7159; 0,2841). Eén voorspelling geeft $P(X_4=S)\approx \mathrm{0,7159}(\mathrm{0,8})+\mathrm{0,2841}(\mathrm{0,4})=\mathrm{0,6864}$. Als je met ongeronde waarden doorgaat, krijg je voor zonnig de kansen 0,6745; 0,6698; 0,6679 en 0,6672.

Deze naderen $2\mathrm{/}3$. De keten verliest geleidelijk haar afhankelijkheid van de laatste kansinschatting. De mengtijd geeft aan hoeveel stappen nodig zijn om vanuit elke begintoestand binnen een gekozen afstand van het evenwicht te komen. Bij een voorspelling dicht bij het evenwicht hebben de huidige observaties nog een kleine invloed; de invloed is niet volledig verdwenen.

Een voorspelling hoeft de onzekerheid niet bij elke stap te vergroten. Vanuit (0,5; 0,5) voorspelt deze weerketen (0,6; 0,4), een sterker geconcentreerde verdeling. Convergentie gaat over het verlies van afhankelijkheid van de beginkansinschatting, niet over een regel dat voorspellingen uniform moeten worden.

Voorspel een observatie

Een voorspelling van de opbrengst neemt het gemiddelde van de sensoraannemelijkheid over de voorspelde toestanden:

Gebruik voor hoog op dag 4 de toestandsvoorspelling van dag 4, niet de gefilterde kansinschatting van dag 3: $\mathrm{0,6864}(\mathrm{0,8})+\mathrm{0,3136}(\mathrm{0,3})\approx \mathrm{0,6432}$. De kans op zonnig en de kans op een hoge opbrengst verschillen, omdat beide weertoestanden een hoge opbrengst kunnen geven.

Bewaar de totalen van filtering

Vóór normalisatie is het totaal van elke actualisatie de kans op die observatie gegeven de eerdere observaties. Noem die $c_t=P(e_t\mid e_{1:t-1})$. De kettingregel geeft:

Voor laag, laag, hoog zijn de totalen ongeveer 0,45; 0,4556 en 0,5429. Hun product, berekend vóór afronding, is 0,1113. Dit is een som over elk verborgen pad dat bij de observaties past. Het beste pad alleen draagt 0,04704 bij, slechts een deel van het totaal.

Een ongenormaliseerde voorwaartse doorloop geeft dezelfde aannemelijkheid als je de laatste elementen optelt. Een genormaliseerde doorloop is stabieler, mits je de totalen bewaart. Sla bij lange reeksen $\log P(e_{1:t})={\sum }_i\log c_i$ op in plaats van zeer kleine waarden te vermenigvuldigen. Hier is de natuurlijke logaritme ongeveer −2,196.

Vergelijk modellen op basis van dezelfde observaties

Een aannemelijkheid meet hoe goed één model een bepaalde observatiereeks verklaart. Om kandidaat-HMM's voor woorden met dezelfde opname te vergelijken, bereken je de score van die opname onder elk model en combineer je die met de a-priorikansen van de woorden om a-posteriorikansen van woorden te vinden. Langere reeksen hebben meestal kleinere ruwe aannemelijkheden, dus een kleiner getal bij een langere opname toont op zichzelf niet aan dat een model slechter is.

Een latere observatie kan veranderen wat je over een eerdere toestand denkt. Gladding schat $P(X_k\mid e_{1:t})$ voor $k<t$. Dit is nuttig om een vastgelegd traject te reconstrueren of wanneer een toepassing even kan wachten voordat ze een schatting van een eerdere toestand geeft.

Verdeel de observaties bij het doeltijdstip

Filtering heeft de observaties tot en met tijdstip $k$ al samengevat als $f_k(x)=P(X_k=x\mid e_{1:k})$. Een achterwaarts bericht vat de overige observaties samen als een aannemelijkheid, $b_k(x)=P(e_{k+1:t}\mid X_k=x)$. Combineer ze per toestand:

Normaliseer de producten over de toestanden. De latere observaties worden gewogen naar hoe aannemelijk ze vanuit elke kandidaat-toestand op tijdstip $k$ zouden zijn.

Geef de toekomstige aannemelijkheid achterwaarts door

Op het laatste tijdstip zijn er geen latere observaties, dus is $b_t(x)=1$ voor elke toestand. Eén stap terug geeft:

Vermenigvuldig voor elke mogelijke opvolger de kans om daarheen te gaan, de aannemelijkheid van de bijbehorende observatie en de resterende toekomstige aannemelijkheid. Tel daarna op over de opvolgers. Een achterwaarts bericht is een aannemelijkheidsfunctie over mogelijke begintoestanden, geen toestandsverdeling; de elementen hoeven niet op te tellen tot 1.

Glad dag 2 in het zonnepaneelvoorbeeld

De observaties zijn laag, laag, hoog. Na de twee lage metingen is de gefilterde kansinschatting van dag 2 ongeveer (0,2146; 0,7854). Voor de laatste hoge meting is de achterwaartse aannemelijkheid vanuit een zonnige dag 2 gelijk aan $\mathrm{0,8}(\mathrm{0,8})+\mathrm{0,2}(\mathrm{0,3})=\mathrm{0,70}$. Vanuit een bewolkte dag 2 is die $\mathrm{0,4}(\mathrm{0,8})+\mathrm{0,6}(\mathrm{0,3})=\mathrm{0,50}$.

Vermenigvuldig: de producten zijn ongeveer $\mathrm{0,2146}(\mathrm{0,70})=\mathrm{0,1502}$ en $\mathrm{0,7854}(\mathrm{0,50})=\mathrm{0,3927}$. Normaliseer de ongeronde waarden om voor dag 2 een kans op zonnig van 0,2767 te krijgen. De hoge opbrengst op dag 3 maakt een zonnige dag 2 aannemelijker dan de oorspronkelijke gefilterde kans van 0,2146 aangaf.

Ga verder naar dag 1

De achterwaartse aannemelijkheid vanuit zonnig op dag 1 is $\mathrm{0,8}(\mathrm{0,2})(\mathrm{0,70})+\mathrm{0,2}(\mathrm{0,7})(\mathrm{0,50})=\mathrm{0,182}$. Vanuit bewolkt is die $\mathrm{0,4}(\mathrm{0,2})(\mathrm{0,70})+\mathrm{0,6}(\mathrm{0,7})(\mathrm{0,50})=\mathrm{0,266}$. Combineer met $f_1=(2\mathrm{/}9,7\mathrm{/}9)$ en normaliseer. De gegladde kans op zonnig is ongeveer 0,1635, een daling ten opzichte van 0,2222: de volledige toekomst omvat naast de laatste hoge opbrengst ook nog een lage opbrengst.

Latere observaties hoeven niet elke eerdere schatting in dezelfde richting te verschuiven. Op het laatste tijdstip is gladding gelijk aan filtering omdat er geen latere observaties zijn.

Orden de berekening

Het voorwaarts-achterwaarts algoritme slaat eerst alle voorwaartse kansinschattingen op en berekent daarna achterwaartse berichten en genormaliseerde producten. Voor $t$ stappen en $S$ toestanden kost een berekening met een dichte matrix $O(S^{2}t)$ en worden $O(St)$ waarden opgeslagen. Gladding met vaste vertraging geeft de toestand weer van een vast aantal stappen vóór het heden en weegt zo vertraging af tegen meer observaties.

De lijst met observaties omkeren en een gewoon filter uitvoeren is een andere berekening. De achterwaartse recursie gebruikt de oorspronkelijke voorwaartse overgangen en toekomstige aannemelijkheden; ze introduceert geen nieuwe a-prioriverdeling aan het einde van de registratie. Gegladde toestandskansen leveren ook verwachte tellingen voor het leren met Baum-Welch.

Soms is het gewenste antwoord één volledige verklaring voor de observaties. Viterbi-decodering vindt de waarschijnlijkste reeks verborgen toestanden. Ze houdt rekening met overgangen tussen toestanden, die je kunt missen als je op afzonderlijke tijdstippen de waarschijnlijkste toestand kiest.

Verander het doel

Het doel is $\arg {\max }_{x_{1:t}}P(x_{1:t}\mid e_{1:t})$. Elke kandidaat heeft dezelfde noemer voor de observaties, dus maximalisatie van de gezamenlijke score $P(x_{1:t},e_{1:t})$ kiest hetzelfde pad. Deze score verschilt van een a-posteriorikans van een eindtoestand, die alle paden optelt die in die toestand eindigen.

Bij de zonnepaneelobservaties hoog, laag zijn na gladding de waarschijnlijkste afzonderlijke toestanden zonnig op dag 1 en bewolkt op dag 2. Toch is zonnig, zonnig het waarschijnlijkste volledige pad: de a-posteriorikans is ongeveer 0,3282, tegenover 0,2872 voor zonnig, bewolkt. Bij verboden overgangen kunnen afzonderlijk aannemelijke toestanden zelfs een onmogelijk pad vormen.

Bewaar het beste beginpad per eindtoestand

Laat $m_t(j)$ de beste gezamenlijke score van pad en observaties zijn voor een pad dat in toestand $j$ eindigt. Initialiseer $m_1(j)=P(X_1=j)P(e_1\mid j)$. Gebruik daarna:

Sla de voorganger die het maximum oplevert op als terugverwijzing. Paden die in dezelfde toestand eindigen, hebben dezelfde mogelijke vervolgen, dus een beginpad met een lagere score kun je laten vallen. Het voorwaarts algoritme telt concurrerende beginpaden op; Viterbi kiest het maximum.

Vul het toestandsrooster voor laag, laag, hoog

De beginscores zijn (0,10; 0,35). Op dag 2 zijn de kandidaten voor zonnig vóór de emissie $\mathrm{0,10}(\mathrm{0,8})=\mathrm{0,08}$ en $\mathrm{0,35}(\mathrm{0,4})=\mathrm{0,14}$. Bewaar de tweede en vermenigvuldig met 0,2 om 0,028 te krijgen, met een verwijzing naar bewolkt. Vergelijk voor bewolkt 0,02 met 0,21; vermenigvuldiging van de grootste met 0,7 geeft 0,147, ook met een verwijzing naar bewolkt.

Op dag 3 vergelijkt zonnig $\mathrm{0,028}(\mathrm{0,8})=\mathrm{0,0224}$ met $\mathrm{0,147}(\mathrm{0,4})=\mathrm{0,0588}$. Vermenigvuldiging van de grootste met de aannemelijkheid 0,8 voor hoog geeft 0,04704. Bewolkt vergelijkt 0,0056 met 0,0882; vermenigvuldiging van de grootste met 0,3 geeft 0,02646. Beide laatste verwijzingen leiden naar bewolkt op dag 2.

Volg de verwijzingen terug vanaf het einde

De grootste eindscore is 0,04704 bij zonnig. Volg de verwijzing naar bewolkt op dag 2 en vervolgens die verwijzing naar bewolkt op dag 1. Keer deze achterwaartse doorloop om en je krijgt bewolkt, bewolkt, zonnig. Door te delen door de aannemelijkheid van de observatiereeks 0,1113 krijg je de a-posteriorikans, ongeveer 0,4226.

Als je afzonderlijk de grootste score in elke kolom kiest, negeer je de opgeslagen voorgangerrelaties. Ook kun je de eindscorevector niet normaliseren tot een gefilterde kansinschatting: die bewaart slechts één pad per toestand, niet de som van de paden.

Gebruik logaritmen voor lange reeksen

Producten kunnen door onderloop nul worden. Sla in plaats daarvan logaritmische scores op:

Logaritmen behouden de volgorde, dus het pad en de verwijzingen blijven ongewijzigd. Kansen van nul worden min oneindig. Evenzo maken negatieve logaritmische scores van decodering het vinden van een pad met minimale kosten door een graaf met tijdlagen, oftewel een toestandsrooster. Viterbi met een dichte matrix kost $O(S^{2}t)$ tijd en slaat $O(St)$ verwijzingen op. Als paden dezelfde hoogste score hebben, is elk een geldige waarschijnlijkste verklaring.

Een kansentabel wordt moeilijk op te slaan als de toestandsruimte enorm is. Continue kansinschattingen hebben in het algemeen ook geen eindige tabel. Een deeltjesfilter geeft een kansinschatting weer met getrokken toestanden, zodat de berekening zich kan richten op een beheersbare verzameling mogelijkheden.

Geef kansen weer met deeltjes

Elk deeltje is één volledige toestand, geen afzonderlijk fysiek object. Na hertrekking hebben alle deeltjes hetzelfde gewicht en is de geschatte kans op een toestand het aandeel dat zich daarin bevindt. Tien deeltjes, verdeeld in zeven zonnige en drie bewolkte, vertegenwoordigen de kansinschatting (0,7; 0,3).

Trek de begindeeltjes uit $P(X_1)$. Een a-prioriverdeling van (0,5; 0,5) geeft naar verwachting gelijke aantallen, maar dwingt niet af dat elke willekeurige steekproef gelijk verdeeld is. Volgens onze tijdsconventie weeg je deze begindeeltjes met de eerste observatie en trek je opnieuw vóór een overgang plaatsvindt.

Laat tijd verstrijken door overgangen te trekken

Verplaats bij elke latere stap elk deeltje onafhankelijk met de overgangsrij voor de huidige toestand. Met weerrijen (0,8; 0,2) en (0,4; 0,6) hebben zeven zonnige en drie bewolkte deeltjes na verplaatsing een verwacht aantal zonnige deeltjes van $7(\mathrm{0,8})+3(\mathrm{0,4})=\mathrm{6,8}$.

Eén gerealiseerde steekproef kan zes zonnige en vier bewolkte deeltjes bevatten. Een verwacht aantal kan een breuk zijn; een gerealiseerd aantal deeltjes moet een geheel getal zijn. Precies 6,8 deeltjes bewaren zou geen steekproefalgoritme zijn.

Weeg met de meting

Stel dat de nieuwe zonnepaneelopbrengst laag is. Elk zonnig deeltje krijgt aannemelijkheid 0,2; elk bewolkt deeltje krijgt 0,7. De zes zonnige deeltjes hebben totaalgewicht $6(\mathrm{0,2})=\mathrm{1,2}$ en de vier bewolkte deeltjes $4(\mathrm{0,7})=\mathrm{2,8}$. Van het totale gewicht 4,0 heeft zonnig een gewogen kans van 0,3 en bewolkt 0,7.

Zowel de aantallen als de gewichten per deeltje tellen mee. Als je alleen 0,2 en 0,7 normaliseert, negeer je hoeveel voorspelde kans elke groep vertegenwoordigde. Wegen gebruikt dezelfde Bayesactualisatie als exacte filtering op deze met steekproeven gemaakte voorspelling.

Trek een nieuwe verzameling

Trek tien deeltjes met teruglegging, waarbij elk oud deeltje wordt gekozen met een kans die evenredig is aan zijn gewicht. Elke nieuwe trekking is zonnig met kans 0,3 en bewolkt met kans 0,7. Het verwachte aantal zonnige deeltjes is drie, al kan een uitvoering twee, vier of een ander aantal opleveren. Meerdere kopieën zijn toegestaan; ze vertegenwoordigen kansmassa.

Geef de resulterende deeltjes opnieuw gelijke gewichten. De observatie heeft al beïnvloed welke deeltjes zijn gekopieerd, dus als je de oude aannemelijkheidsgewichten behoudt, tel je de observatie opnieuw mee. De volgende iteratie verplaatst deze nieuwe verzameling voordat de volgende observatie wordt verwerkt.

Vergelijk met de exacte actualisatie

Exacte filtering vanuit (0,7; 0,3) voorspelt (0,68; 0,32). Laag geeft daarna de gewichten (0,136; 0,224), dus de exacte a-posteriorikans op zonnig is $\mathrm{0,136}\mathrm{/}\mathrm{0,36}\approx \mathrm{0,3778}$. Het gewogen resultaat van de uitvoering met deeltjes was 0,3 omdat de willekeurige beweging slechts zes zonnige deeltjes opleverde. Hertrekking introduceert nog een bron van variatie.

De cyclus bestaat dus uit initialisatie, weging met de eerste observatie en hertrekking, gevolgd door herhaalde beweging, weging en hertrekking. Lees vóór hertrekking de gewogen aandelen af en daarna de aantallen. Een stap kost ongeveer $O(N)$ voor $N$ deeltjes als het trekken en wegen van een toestand vaste kosten heeft. Voor twee weertoestanden is exacte filtering eenvoudiger. Methoden met deeltjes worden nuttig als voor een grote of continue toestand geen betaalbaar compact exact filter bestaat.

Een schatting met deeltjes is willekeurig, dus de kwaliteit hangt af van zowel het aantal deeltjes als de plaatsen waar ze overleven. Meer deeltjes verbeteren de benadering, maar een grote verzameling kan nog steeds weinig opleveren als vrijwel alle bruikbare informatie bij een paar steekproeven ligt.

Begrijp de schaal van de nauwkeurigheid

Voor een schatting van een kans $p$ met onafhankelijke steekproeven is de standaardfout ongeveer $\sqrt{p(1-p)\mathrm{/}N}$. Met $p=\mathrm{0,3}$ is dit ongeveer 0,046 voor 100 steekproeven en 0,0046 voor 10.000. De fout van een deeltjesfilter heeft vaak ongeveer dezelfde schaal $1\mathrm{/}\sqrt{N}$, al zijn hertrokken deeltjes afhankelijk en speelt de moeilijkheid van het model een rol.

Als je het aantal deeltjes verviervoudigt, halveert de fout ongeveer; verdubbelen doet dat niet. Bij een vaste observatiegeschiedenis nadert een consistent deeltjesfilter de exacte kansinschatting als je het aantal deeltjes vergroot. Daarmee wordt één eindige uitvoering niet exact en verdwijnen fouten in het onderliggende model niet. Zet de beginwaarde van de toevalsgenerator vast voor reproduceerbare vergelijkingen of vergelijk resultaten van meerdere uitvoeringen.

Onderscheid twee tekortkomingen

Zonder hertrekking kan het vermenigvuldigen van aannemelijkheden over veel stappen bijna elk deeltje een verwaarloosbaar gewicht geven. Hertrekking vervangt die verspilling door kopieën van bruikbare toestanden. Maar ze kan ook een alternatieve locatie wissen die tijdelijk minder goed past.

Hertrekking alleen kan een afwezig gebied niet opnieuw creëren. Herstel hangt ervan af of getrokken bewegingen het gebied bereiken of een ander mechanisme daar deeltjes introduceert. Als het gebied door de overgangen bijna onbereikbaar is, kan herstel langzaam verlopen. Kleine willekeurige verstoringen toevoegen of een klein aandeel vervangen door nieuwe deeltjes kan helpen, maar deze keuzes moeten passen bij de toestandsrepresentatie en de beoogde benadering.

Ga om met een totaalgewicht van nul

Als elk deeltje gewicht nul krijgt, zijn de hertrekkingskansen niet gedefinieerd. De observatie kan elders in het model mogelijk zijn, ook al heeft de verzameling steekproeven die toestanden gemist. Initialiseer opnieuw vanuit een geschikte verdeling, zoals de a-prioriverdeling of een uniforme verdeling over geldige toestanden, en controleer het sensormodel. Een uitbijtercomponent met een kans groter dan nul kan deze fouten verminderen. Als het model zelf de observatie overal uitsluit, kunnen meer deeltjes alleen het probleem niet oplossen.

Kies een representatie die bij het model past

Exacte voorwaartse filtering past bij kleine discrete toestandsruimten. Een Kalmanfilter is exact als de a-prioriverdeling Gaussisch is en de overgangs- en sensormodellen lineair zijn met Gaussische ruis; een gemiddelde en covariantie beschrijven dan de kansinschatting. Een deeltjesfilter kan omgaan met niet-lineaire modellen en kansinschattingen met afzonderlijke pieken.

Eén Gaussische verdeling kan niet getrouw weergeven dat een robot waarschijnlijk in elk van twee ver uit elkaar gelegen gangen is, maar waarschijnlijk niet daartussen. Groepen deeltjes kunnen beide mogelijkheden bewaren. Voor een lineair volgmodel met Gaussische ruis voorkomt de Kalmanrepresentatie meestal onnodige steekproefruis.

In een DBN bevat elk deeltje een volledige waardetoekenning aan alle toestandsvariabelen. Trek variabelen voor de volgende stap in topologische volgorde uit hun modellen, geconditioneerd op hun ouderknopen. Factorisatie vermindert het werk per steekproef ten opzichte van het opsommen van elke gezamenlijke toestand, al kunnen hoogdimensionale kansinschattingen nog steeds veel deeltjes vereisen om hun belangrijke gebieden te bestrijken.

Objectvolging combineert onzekere beweging met metingen met ruis. De verborgen toestand kan positie en snelheid bevatten; observaties kunnen van gps, radar of een camera komen. Filtering neemt een verdeling van aannemelijke locaties mee van de ene meting naar de volgende.

Lokaliseer in een gang met vijf vakken

Een robot bevindt zich in een van vijf vakken, met deuren bij vak 1 en 4. De sensor meldt een deur met kans 0,9 bij een deur en 0,2 elders. Begin uniform, met kans 0,2 per vak. Een deurmelding geeft de gewichten (0,18; 0,04; 0,04; 0,18; 0,04), met totaal 0,48.

De geactualiseerde kansinschatting is $(\mathrm{0,375};1\mathrm{/}12;1\mathrm{/}12;\mathrm{0,375};1\mathrm{/}12)\mathrm{.}$ Beide vakken met een deur blijven aannemelijk. Als je slechts één piek kiest, gooi je de symmetrie weg die de sensor nog niet heeft doorbroken.

Verplaats de volledige kansinschatting

De robot probeert één vak naar rechts te bewegen. Dat lukt met kans 0,8 en met kans 0,2 blijft hij staan; vanuit vak 5 blijft hij bij de muur zeker staan. Elk vak ontvangt bijdragen van alle beginvakken van waaruit het bereikbaar is.

Vak 1 krijgt $\mathrm{0,375}(\mathrm{0,2})=\mathrm{0,075}$. Vak 2 krijgt $\mathrm{0,375}(\mathrm{0,8})+(1\mathrm{/}12)(\mathrm{0,2})\approx \mathrm{0,3167}$. Vak 3 en 4 krijgen ongeveer 0,0833 en 0,1417. Vak 5 krijgt $(\mathrm{0,375})(\mathrm{0,8})+1\mathrm{/}12\approx \mathrm{0,3833}$: zowel de aankomsten vanuit vak 4 als alle bestaande kansmassa in vak 5 blijven daar.

De voorspelling is ongeveer (0,0750; 0,3167; 0,0833; 0,1417; 0,3833). Als je de grens als nog een gewone beweging met kans 0,8 behandelt, verlies je kans buiten de gemodelleerde gang.

Neem geen deur waar

De aannemelijkheid van geen deur is 0,1 in vak 1 en 4 en 0,8 elders. Vermenigvuldiging van de ongeronde voorspelling geeft een totaalgewicht van ongeveer 0,6483. Normalisatie levert (0,0116; 0,3907; 0,1028; 0,0219; 0,4730) op.

De waarschijnlijke locaties zijn nu vak 2 en 5, direct na de twee deuren. De kansinschatting blijft multimodaal, met afzonderlijke pieken. Eén sensormeting is een observatie, geen meting van de werkelijke positie; door alternatieven te behouden, krijgen latere bewegingen en metingen de kans om ze te onderscheiden.

Breid uit naar realistische robots

Bij Monte-Carlo-lokalisatie is een deeltje een positie en oriëntatie: positie in meters en kijkrichting. Verplaats elke positie en oriëntatie met de opgedragen beweging plus ruis en weeg die daarna op basis van de overeenkomst tussen waargenomen afstanden en afstanden die een bekende kaart voorspelt. Een geconcentreerde beginverzameling volgt een bekende startlocatie; een brede verzameling ondersteunt globale lokalisatie.

Als ook de kaart onbekend is, neem je die op in de verborgen toestand. Gelijktijdige lokalisatie en kaartopbouw, oftewel SLAM, schat kaart, positie en oriëntatie samen. Bij meerdere objecten speelt ook gegevensassociatie: bepalen welke detectie bij welk object hoort. Verschillende toewijzingen leveren verschillende trajecthypothesen op.

Voertuigvolging kan een bewegingsvoorspelling combineren met gps-metingen. Bij 15 m/s en stappen van één seconde is de verwachte verplaatsing tussen metingen ongeveer 15 m. Een geschikt Kalmanmodel combineert onzekere beweging en meting om het effect van meetruis te verminderen. Een overgangsmodel dat geen rekening houdt met werkelijke variatie in beweging kan het ware traject uitsluiten, zelfs als de berekeningen kloppen.

Modellen voor reeksen kunnen zowel labels als fysieke toestanden afleiden. Een spraakherkenner verbindt een veranderend geluidssignaal met mogelijke woorden. Een systeem voor woordsoorttoekenning verbindt waargenomen woorden met verborgen grammaticale labels. Beide moeten keuzes in hun context over de tijd beoordelen.

Combineer overeenkomst met het geluid en taalkans

Spraakherkenning zoekt de woordreeks met de grootste a-posteriorikans:

Het akoestisch model $P(s\mid w)$ beoordeelt hoe goed woorden het geluid verklaren; het taalmodel $P(w)$ beoordeelt hun aannemelijkheid vooraf. De gemeenschappelijke noemer $P(s)$ beïnvloedt de rangorde niet. Een akoestische aannemelijkheid is op zichzelf geen a-posteriorikans van woorden.

Vergelijk voor fictieve scores “de leiders” met “de lijders”. Het akoestisch model geeft aannemelijkheden 0,0004 en 0,0005; de taalkansen zijn 0,00002 en 0,000001. Het eerste product is $8\times {10}^{-9}$ en het tweede $5\times {10}^{-10}$. Door de taalcontext wint de eerste woordgroep ondanks haar iets lagere akoestische aannemelijkheid volgens het model.

Maak van audio een tijdreeks

Een gebruikelijke opzet gebruikt overlappende fragmenten van 25 ms die elke 10 ms beginnen, wat ongeveer 100 kenmerkvectoren per seconde oplevert. De vectoren zijn observaties. Verborgen toestanden vertegenwoordigen delen van spraakklanken, oftewel fonen, vaak met een begin-, midden- en eindtoestand. Een uitspraakwoordenboek verbindt woorden met fonen.

Lussen naar dezelfde toestand laten een klanktoestand meerdere fragmenten duren. Zonder flexibiliteit in duur zou een verandering van spreeksnelheid een vaste en vaak ongeschikte uitlijning tussen fragmenten en klanktoestanden vereisen. Verschillende toestandsreeksen geven verschillende uitlijningen van dezelfde waargenomen opname weer.

Geef korte taalcontext weer

Een bigrammodel benadert een woordreeks met $P(w_1){\prod }_{i=2}^{n}P(w_i\mid w_{i-1})$. Een trigram gebruikt de twee vorige woorden. Schat deze voorwaardelijke kansen op basis van tellingen in tekst. De Markovaanname is hier een praktische benadering: grammaticale en semantische relaties op grotere afstand kunnen verder reiken dan één of twee voorgaande woorden.

Viterbi kan het beste toestandsverloop vinden door gekoppelde foon- en woordmodellen. Bij een grote woordenschat laat bundelzoeken minder veelbelovende gedeeltelijke paden vallen om werk te verminderen. Een eenmaal weggelaten pad kan later niet meer winnen, dus een smalle bundel kan het beste volledige pad missen. Ook verschilt het doel van het beste afzonderlijke toestandspad voor een woordreeks van het optellen van alle mogelijke uitlijningen ervan.

Gebruik dezelfde structuur voor labels

Bij woordsoorttoekenning zijn toestanden labels en observaties woorden. Overgangen beoordelen $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})$; emissies beoordelen $P({\mathrm{w}\mathrm{o}\mathrm{o}\mathrm{r}\mathrm{d}}_i\mid {\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}}_i)$. In “zij zag vliegen” kan “vliegen” een werkwoord of een zelfstandig naamwoord zijn. Het labelpad moet rekening houden met zowel woordaannemelijkheden als overgangen tussen labels.

Plaats HMM's in de spraakpraktijk

Systemen met een grote woordenschat uit de jaren 1980 tot het begin van de jaren 2010 combineerden doorgaans HMM's met akoestische Gaussische mengmodellen. Rond 2010–2012 werden neurale akoestische modellen belangrijk in hybride DNN-HMM-systemen. Moderne neurale systemen kunnen audio rechtstreeks naar tekst omzetten zonder expliciet HMM. De gemeenschappelijke ideeën van onzekere uitlijning, beoordeling van reeksen en dynamisch programmeren blijven nuttig, en HMM's komen ook voor in toepassingen zoals het vinden van genen in DNA.