Baum-walesisk algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 oktober 2019; kontroller kräver 2 redigeringar .

Den Baum-Welsh-algoritmen används inom datavetenskap och statistik för att hitta okända parametrar för en dold Markov-modell (HMM). Den använder framåt-bakåt-algoritmen och är ett specialfall av den generaliserade EM-algoritmen .

Den Baum-walesiska algoritmen för att uppskatta en dold Markov-modell

En dold Markov- modell är en probabilistisk modell av en uppsättning slumpvariabler . Variabler är kända diskreta observationer och är "dolda" diskreta storheter. Inom ramen för den dolda Markov-modellen finns det två oberoende uttalanden som säkerställer konvergensen av denna algoritm: ${\displaystyle \{Y_{1},\;\ldots ,\;Y_{t},\;Q_{1},\;\ldots ,\;Q_{t}\))$ ${\displaystyle Y_{t))$ $Q_{t}$

$t$ -th dolda variabel med en känd -th variabel är oberoende av alla tidigare variabler, det vill säga ; $(t-1)$ $(t-1)$ $P(Q_{t}\mid Q_{t-1},\;Y_{t-1},\;\ldots ,\;Q_{1},\;Y_{1})=P(Q_ {t}\mid Q_{t-1})$
$t$ Den e kända observationen beror endast på det e tillståndet, d.v.s. beror inte på tiden, . $t$ $P(Y_{t}\mid Q_{t},\;Q_{t-1},\;Y_{t-1},\;\ldots ,\;Q_{1},\;Y_{ 1})=P(Y_{t}\mid Q_{t})$

Därefter kommer en algoritm av "antaganden och maximeringar" att föreslås för att hitta den maximala probabilistiska uppskattningen av parametrarna för den dolda Markov-modellen för en given uppsättning observationer. Denna algoritm är också känd som Baum-Welsh-algoritmen.

$Q_{t}$ är en diskret slumpvariabel som tar ett av värdena . Vi kommer att anta att denna Markov-modell, definierad som , är homogen i tiden, det vill säga oberoende av . Sedan kan den specificeras som en tidsoberoende stokastisk förskjutningsmatris . Sannolikheterna för tillstånd vid en tidpunkt bestäms av den initiala fördelningen . $N$ $(1\ldots N)$ $P(Q_{t}\mid Q_{t-1})$ $t$ $P(Q_{t}\mid Q_{t-1})$ $A=\{a_{ij}\}=p(Q_{t}=j\mid Q_{t-1}=i)$ $t=1$ $\pi _{i}=P(Q_{1}=i)$

Vi kommer att anta att vi är i ett tillstånd vid tidpunkten om . Sekvensen av tillstånd uttrycks som , var är tillståndet för tillfället . $j$ $t$ $Q_{t}=j$ $q=(q_{1},\;\ldots ,\;q_{T})$ $q_{t}\in \{1\ldots N\}$ $t$

En observation vid en tidpunkt kan ha ett av de möjliga värdena, . Sannolikheten för en given vektor av observationer vid en tidpunkt för ett tillstånd definieras som ( är en matris på ). Sekvensen av observationer uttrycks som . ${\displaystyle Y_{t))$ $t$ $L$ $y_{t}\in \{o_{1},\;\ldots ,\;o_{L}\}$ $t$ $j$ $b_{j}(o_{i})=P(Y_{t}=o_{i}\mid Q_{t}=j)$ $B=\{b_{ij}\}$ $L$ $N$ $y$ $y=(y_{1},\;\ldots ,\;y_{T})$

Därför kan vi beskriva den dolda Markov-modellen med . För en given observationsvektor finner den Baum-walesiska algoritmen . maximerar sannolikheten för observationer . $\lambda =(A\;,B,\;\pi )$ $y$ $\lambda ^{*}=arg\max _{\lambda }P(y\mid \lambda )$ $\lambda ^{*}$ $y$

Algoritm

Inledande data: med slumpmässiga initiala villkor. $\lambda =(A,\;B,\;\pi )$

Algoritmen uppdaterar parametern iterativt tills den konvergerar vid en punkt. $\lambda$

Direkt procedur

Beteckna med sannolikheten för förekomsten av en given sekvens för tillståndet vid tidpunkten . $\alpha _{i}(t)=p(Y_{1}=y_{1},\;\ldots ,\;Y_{t}=y_{t},\;Q_{t}=i \mid\lambda )$ ${\displaystyle y_{1},\;\ldots ,\;y_{t))$ $i$ $t$

$\alpha _{i}(t)$ kan beräknas rekursivt:

$\alpha _{i}(1)=\pi _{i}\cdot b_{i}(y_{1});$
$\alpha _{j}(t+1)=b_{j}(y_{t+1})\summa _{i=1}^{N}{\alpha _{i}(t)\ cdot a_{ij}}.$

Omvänd procedur

Denna procedur tillåter oss att beräkna sannolikheten för en ändlig given sekvens , förutsatt att vi startade från initialtillståndet vid tidpunkten . $\beta _{i}(t)=p(Y_{t+1}=y_{t+1},\ldots ,Y_{T}=y_{T}\mid Q_{t}=i, \lambda )$ ${\displaystyle y_{t+1},\;\ldots ,\;y_{T))$ $i$ $t$

Kan beräknas : $\beta _{i}(t)$

$\beta _{i}(T)=p(Y_{T}=y_{T}\mid Q_{t}=i,\lambda )=1;$
$\beta _{i}(t)=\sum _{j=1}^{N}{\beta _{j}(t+1)a_{ij}b_{j}(y_{t+ en })}.$

Med hjälp av och kan du beräkna följande värden: $\alfa$ $\beta$

$\gamma _{i}(t)\equiv p(Q_{t}=i\mid y,\;\lambda )={\frac {\alpha _{i}(t)\beta _{i }(t)}{\displaystyle \sum _{j=1}^{N}\alpha _{j}(t)\beta _{j}(t)))),$
$\xi _{ij}(t)\equiv p(Q_{t}=i,\;Q_{t+1}=j\mid y,\;\lambda )={\frac {\alpha _ {i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}{\displaystyle \sum _{i=1}^{N}\ displaystyle \sum _{j=1}^{N}\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})} }.$

Med och kan vi beräkna nya värden för modellparametrarna: $\gamma$ $\xi$

${\bar {\pi }}_{i}=\gamma _{i}(1),$
${\bar {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}\xi _{ij}(t)}{\displaystyle \sum _{t=1}^{T-1}\gamma _{i}(t)}},$
${\bar {b}}_{i}(o_{k})={\frac {\displaystyle \sum _{t=1}^{T}\delta _{y_{t},\; o_{k}}\gamma _{i}(t)}{\displaystyle \sum _{t=1}^{T}\gamma _{i}(t))).$ ,

var

\delta _{y_{t},\;o_{k}}={\begin{cases}1&{\text{if }}y_{t}=o_{k},\\0&{\text {annat}}\end{cases}}

indikativ funktion, och det förväntade antalet värden av det observerbara som är lika i tillstånd som det totala antalet tillstånd . $b_{i}^{*}(o_{k})$ ${\displaystyle o_{k))$ $i$ $i$

Genom att använda nya värden för , och , fortsätter iterationerna tills konvergens. $A$ $B$ $\pi$

Se även

Viterbi algoritm