隱馬爾科夫模型HMM介紹

• 2019 年 10 月 3 日
• 筆記

???????????????????????“???”?????????$t$???$s_t$???????????$t-1$???$s_{t-1}$?????????$t-1$???????????????????????$A$??$$A_{ij}=pleft(s_{t}=j | s_{t-1}=iright),text{ }s_{t} | s_{t-1} sim operatorname{Discrete}left(A_{s_{t-1}, :}right)$$??????$A$??????1?????????$s_1$(??????????)????????????????$left(s_{1}, s_2, dots, s_{t}right)$?

????

???????HMM?????????????????????????????

• ??????????$S$???????$s in {1,2,dots,S}$
• ??????????$X$?????$x in {1,2,dots,X}$
• ??????????$vec{pi}=(pi_1,pi_2,dots,pi_S)$??$s_{1} sim operatorname{Discrete}(vec{pi})$
• ????$s$??????$mathcal{A}$??$mathcal{A}$?$S$?$S$??????$s_{i} |left{s_{i-1}=k^{prime}right} sim operatorname{Discrete}left(mathcal{A}_{k^{prime}, :}right)$
• ????$x$??????$mathcal{B}$??$mathcal{B}$?$S$?$X$??????$x_{i} |left{s_{i}=k^{prime}right} sim operatorname{Discrete}left(mathcal{B}_{k^{prime}, :}right)$

?HMM??????????????

1. ?????????$vec{o}=(x_1,x_2,dots,x_T)$?????????????$vec{pi},mathcal{A},mathcal{B}$??$$vec{pi}_{mathrm{ML}}, mathcal{A}_{mathrm{ML}}, mathcal{B}_{mathrm{ML}}=arg max _{vec{pi},mathcal{A},mathcal{B}} pleft(vec{o} | vec{pi},mathcal{A},mathcal{B}right)$$
2. ?????????$vec{o}$????$vec{pi},mathcal{A},mathcal{B}$?????????$vec{o}$???????????$vec{s}=(s_{1}, ldots, s_{T})$??$$s_{1}, ldots, s_{T}=arg max _{vec{s}} pleft(vec{s} | vec{o}, vec{pi},mathcal{A},mathcal{B}right)$$

????

?????1??????????$pleft(vec{o} | vec{pi},mathcal{A},mathcal{B}right)$?????????$$begin{aligned} p(vec{o} | vec{pi}, mathcal{A}, mathcal{B}) &=sum_{s_{1}=1}^{S} cdots sum_{s_{T}=1}^{S} pleft(vec{o}, s_{1}, ldots, s_{T} | vec{pi}, mathcal{A},mathcal{B}right) &=sum_{s_{1}=1}^{S} cdots sum_{s_{T}=1}^{S} pi_{s_1}mathcal{B}_{s_1,x_1}prod_{i=2}^{T}mathcal{A}_{s_{i-1},s_i}mathcal{B}_{s_i,x_i} end{aligned}$$??????????????????$mathcal{O}(TS^T)$??????????????????????????$mathcal{O}(TS^2)$??????????

1. Forward Algorithm

• ??$alpha_{t}(j)=pleft(x_{1}, x_{2} ldots x_{t}, s_{t}=j | vec{pi}, mathcal{A},mathcal{B}right),text{ }tin{1,2,cdots,T},text{ }jin{1,2,cdots,S}$?????????
  • Initialization: $alpha_{1}(j)=pi_jmathcal{B}_{j,x_1}; quad 1 leq j leq S$
  • Recursion: $alpha_{t}(j)=sum_{i=1}^{S} alpha_{t-1}(i) mathcal{A}_{i j} mathcal{B}_{j,x_t} ; quad 1 leq j leq S, 1<t leq T$
  • Termination: $pleft(vec{o} | vec{pi},mathcal{A},mathcal{B}right)=sum_{i=1}^{S} alpha_{T}(i)$

2. Backward Algorithm

• ??$beta_{t}(i)=pleft(x_{t+1}, x_{t+2} ldots x_{T} | s_{t}=i, vec{pi}, mathcal{A},mathcal{B}right),text{ }tin{1,2,cdots,T},text{ }iin{1,2,cdots,S}$?????????
  • Initialization: $beta_{T}(i)=1; quad 1 leq i leq S$
  • Recursion: $beta_{t}(i)=sum_{j=1}^{S} mathcal{A}_{i j} mathcal{B}_{j,x_{t+1}} beta_{t+1}(j) ; quad 1 leq i leq S, 1 leq t < T$
  • Termination: $pleft(vec{o} | vec{pi},mathcal{A},mathcal{B}right)=sum_{j=1}^{S} pi_{j} mathcal{B}_{j,x_1} beta_{1}(j)$

??EM????$vec{pi}_{mathrm{ML}}, mathcal{A}_{mathrm{ML}}, mathcal{B}_{mathrm{ML}}$???EM????????????EM?????????GMM??????????????Forward-Backward Algorithm(i.e., Baum-Welch Algorithm)?

• ??????????$mathcal{Lambda}^*=[vec{pi}^*,mathcal{A}^*,mathcal{B}^*]$???
  • E-step: ??$q(vec{s})=p(vec{s} | vec{o}, mathcal{Lambda}^*)$??$mathcal{L}(mathcal{Lambda})=mathbb{E}_{q}[ln p(vec{o}, vec{s} |  mathcal{Lambda})]$?????$$ln p(vec{o}, vec{s} | mathcal{Lambda})= underbrace{ln pi_{s_1}}_{text{ initial state }} +sum_{t=2}^{T} underbrace{ln mathcal{A}_{s_{t-1}, s_t}}_{text { Markov chain }} + sum_{t=1}^{T} underbrace{ln mathcal{B}_{s_t, x_t}}_{text { observations }}$$??$mathcal{L}$??????$$mathcal{L}(mathcal{Lambda})=sum_{k=1}^{S} gamma_{1}(k) ln pi_{k}+sum_{t=2}^{T} sum_{j=1}^{S} sum_{k=1}^{S} xi_{t}(j, k) ln mathcal{A}_{j, k}+sum_{t=1}^{T} sum_{k=1}^{S} gamma_{t}(k) ln mathcal{B}_{k, x_{t}}$$??$gamma_t(k)=p(s_t=k | vec{o}, mathcal{Lambda}^*),text{ }xi_t(j,k)=p(s_{t-1}=j,s_t=k | vec{o}, mathcal{Lambda}^*); quad 1 leq t leq T$?????????$$begin{cases} gamma_t(k)=frac{p(vec{o}, s_t=k | mathcal{Lambda}^*)}{p(vec{o} | mathcal{Lambda}^*)}=frac{alpha_t(k)beta_t(k)}{sum_{m=1}^Salpha_t(m)beta_t(m)} xi_t(j,k)=frac{p(vec{o}, s_{t-1}=j, s_t=k | mathcal{Lambda}^*)}{p(vec{o} | mathcal{Lambda}^*)}=frac{alpha_{t-1}(j)mathcal{A}_{jk}^*mathcal{B}_{k,x_t}^*beta_t(k)}{sum_{m=1}^Salpha_t(m)beta_t(m)} end{cases}$$?????$alpha_t(.)$??$beta_t(.)$??????????$mathcal{Lambda}^*$?????
  • M-step: ????????$mathcal{Lambda}^*=argmax_{mathcal{Lambda}}mathcal{L}(mathcal{Lambda})$??$$pi_{k}^*=frac{gamma_{1}(k)}{sum_{j=1}^S gamma_{1}(j)}, quad mathcal{A}_{jk}^*=frac{sum_{t=2}^{T} xi_{t}(j, k)}{sum_{t=2}^{T} sum_{l=1}^{S} xi_{t}(j, l)}, quad mathcal{B}_{kv}^*=frac{sum_{t=1}^{T} gamma_{t}(k) Ileft(x_{t}=vright)}{sum_{t=1}^{T} gamma_{t}(k)}$$?????????????1???????$N$????????????$T_n,text{ }nin{1,2,cdots,N}$??????????????$gamma_t,xi_t$???$gamma_t^{(n)},xi_t^{(n)}$???????$$pi_{k}^*=frac{sum_{n=1}^{N} gamma_{1}^{(n)}(k)}{sum_{n=1}^{N} sum_{j=1}^S gamma_{1}^{(n)}(j)}, quad mathcal{A}_{jk}^*=frac{sum_{n=1}^{N} sum_{t=2}^{T_{n}} xi_{t}^{(n)}(j, k)}{sum_{n=1}^{N} sum_{t=2}^{T_{n}} sum_{l=1}^{S} xi_{t}^{(n)}(j, l)}, quad mathcal{B}_{kv}^*=frac{sum_{n=1}^{N} sum_{t=1}^{T_{n}} gamma_{t}^{(n)}(k) Ileft(x_{t}^{(n)}=vright)}{sum_{n=1}^{N} sum_{t=1}^{T_{n}} gamma_{t}^{(n)}(k)}$$

• ????????????

????????

??????2???????????(Viterbi Algorithm)???$v_{t}(j)=max _{s_{1}, ldots, s_{t-1}} pleft(s_{1}, ldots s_{t-1}, x_{1}, x_{2}, ldots x_{t}, s_{t}=j | mathcal{Lambda}right)$???????$b_t(j)$????$v_{t}(j)$???$s_{t-1}$????????

• Initialization: $$v_1(j)=pi_jmathcal{B}_{j,x_1},text{ }b_1(j)=0; quad 1 leq j leq S$$
• Recursion: $$begin{aligned} v_{t}(j) &=max _{iin{1,2,cdots,S}} v_{t-1}(i) mathcal{A}_{i j} mathcal{B}_{j,x_t} ; quad 1 leq j leq S, 1<t leq T b_{t}(j) &= underset{iin{1,2,cdots,S}}{arg max } v_{t-1}(i)  mathcal{A}_{i j} mathcal{B}_{j,x_t} ; quad 1 leq j leq S, 1<t leq T end{aligned}$$
• Termination: $$begin{aligned} & text { The best score: }  P^*=max _{vec{s}} pleft(vec{s},vec{o} | mathcal{Lambda} right)=max _{iin{1,2,cdots,S}} v_{T}(i) & text { The start of backtrace: } s_{T}^*=underset{iin{1,2,cdots,S}}{operatorname{argmax}} v_{T}(i) end{aligned}$$ 
• Backtrace: $$s_{t}^*=b_{t+1}(s_{t+1}^*); quad 1 leq t<T$$?$s_1^*,s_2^*,ldots,s_T^*$??$argmax _{vec{s}} pleft(vec{s},vec{o} | mathcal{Lambda} right)$?????$argmax _{vec{s}} pleft(vec{s},vec{o} | mathcal{Lambda} right)=argmax _{vec{s}} pleft(vec{s} | vec{o}, mathcal{Lambda} right)$

????????HMM?????????????????????fair, ??0?????????loaded, ??1????????????????????????????????????????????????????????????????????????????????????????????????

?????????????????Viterbi??????????????????????????????????????????????????????????????????????