Baum-Welsh-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 17. lokakuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Baum-Welsh-algoritmia käytetään tietojenkäsittelytieteessä ja tilastoissa piilotetun Markov-mallin (HMM) tuntemattomien parametrien löytämiseen . Se käyttää eteenpäin-taakse-algoritmia ja on yleisen EM-algoritmin erikoistapaus .

Baum-Welsh-algoritmi piilotetun Markov-mallin arvioimiseksi

Piilotettu Markovin malli on satunnaismuuttujien joukon todennäköisyysmalli . Muuttujat ovat tunnettuja diskreettejä havaintoja, ja ne ovat "piilotettuja" diskreettejä suureita. Piilotetun Markov-mallin puitteissa on kaksi riippumatonta lausetta, jotka varmistavat tämän algoritmin konvergenssin: ${\displaystyle \{Y_{1},\;\ldots ,\;Y_{t},\;Q_{1},\;\ldots ,\;Q_{t}\))$ ${\näyttötyyli Y_{t))$ $Q_{t}$

$t$ -th piilomuuttuja tunnetulla muuttujalla -th on riippumaton kaikista aikaisemmista muuttujista, eli ; ${\näyttötyyli (t-1)}$ ${\näyttötyyli (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$ Tunnettu havainto riippuu vain tilasta, eli ei riipu ajasta, . $t$ $P(Y_{t}\mid Q_{t},\;Q_{t-1},\;Y_{t-1},\;\ldots ,\;Q_{1},\;Y_{ 1})=P(Y_{t}\mid Q_{t})$

Seuraavaksi ehdotetaan "oletusten ja maksimointien" algoritmia piilotetun Markov-mallin parametrien suurimman todennäköisyyden arvioimiseksi tietylle havaintojoukolle. Tämä algoritmi tunnetaan myös nimellä Baum-Welsh-algoritmi.

$Q_{t}$ on diskreetti satunnaismuuttuja, joka ottaa yhden arvoista . Oletetaan, että tämä Markovin malli, joka määritellään muodossa , on homogeeninen ajassa, eli riippumaton . Sitten se voidaan määritellä ajasta riippumattomana stokastisena siirtymämatriisina . Alkujakauma määrittää tilojen todennäköisyydet tietyllä hetkellä . $N$ ${\näyttötyyli (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)$

Oletetaan, että olemme tilassa tällä hetkellä, jos . Tilasarja ilmaistaan muodossa , missä on tila tällä hetkellä . $j$ $t$ $Q_{t}=j$ $q=(q_{1},\;\ldots ,\;q_{T})$ $q_{t}\in \{1\ldots N\}$ $t$

Ajankohtaisella havainnolla voi olla yksi mahdollisista arvoista, . Tietyn havaintovektorin todennäköisyys tietyllä hetkellä tilalle määritellään seuraavasti: ( on matriisi päällä ). Havaintojen sarja ilmaistaan muodossa . ${\näyttötyyli 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})$

Siksi voimme kuvata piilotettua Markov-mallia käyttämällä . Tietylle havaintovektorille Baum-Welsh-algoritmi löytää . maksimoi havaintojen todennäköisyyden . $\lambda =(A\;,B,\;\pi )$ $y$ $\lambda ^{*}=arg\max _{\lambda }P(y\mid \lambda )$ $\lambda ^{*}$ $y$

Algoritmi

Alkutiedot: satunnaisilla alkuehdoilla. $\lambda =(A,\;B,\;\pi )$

Algoritmi päivittää parametria iteratiivisesti, kunnes se konvergoi yhdessä kohdassa. $\lambda$

Suora menettely

Merkitään tietyn sekvenssin esiintymistodennäköisyydellä tilalle hetkellä . $\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)$ voidaan laskea rekursiivisesti:

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

Käänteinen menettely

Tämän menettelyn avulla voimme laskea äärellisen tietyn sekvenssin todennäköisyyden edellyttäen, että aloitimme alkutilasta ajankohtana . $\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$

Voidaan laskea : $\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+ yksi })}.$

Käyttämällä ja voit laskea seuraavat arvot: $\alpha$ $\beeta$

$\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}\ näyttötyyli \sum _{j=1}^{N}\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})} }.$

Kun ja , voimme laskea mallin parametrien uudet arvot: $\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))).$ ,

missä

\delta _{y_{t},\;o_{k}}={\begin{cases}1&{\text{if }}y_{t}=o_{k},\\0&{\text {muuten}}\loppu{tapaukset}}

suuntaa-antava funktio ja havaittavan arvojen odotettu määrä, joka on yhtä suuri kuin tilojen kokonaismäärä . $b_{i}^{*}(o_{k})$ ${\displaystyle o_{k))$ $i$ $i$

Käyttämällä uusia arvoja , ja iteraatiot jatkuvat konvergenssiin asti. $A$ $B$ $\pi$

Katso myös

Viterbi-algoritmi

Baum-Welsh-algoritmi