大良网站建设价位,谷歌网站,南昌网站建设和推广,平谷区网站建设Hidden Markov Model, HMM 隐马尔可夫模型#xff0c;是一种描述隐性变量(状态)和显性变量(观测状态)之间关系的模型。该模型遵循两个假设#xff0c;隐性状态i只取决于前一个隐性状态i-1#xff0c;而与其他先前的隐形状态无关。观测状态也只取决于当前的隐形状态。因此我们…Hidden Markov Model, HMM 隐马尔可夫模型是一种描述隐性变量(状态)和显性变量(观测状态)之间关系的模型。该模型遵循两个假设隐性状态i只取决于前一个隐性状态i-1而与其他先前的隐形状态无关。观测状态也只取决于当前的隐形状态。因此我们常常将隐马尔科夫模型表现为一种如下图所示链式的模型。 其中xtx_txt代表某一时刻的隐形状态链其N个状态取值集合为{s1,s2,s3,...,N}\{s_1,s_2,s_3,...,_N\}{s1,s2,s3,...,N}。yty_tyt表示为对应的该时刻的显性状态(观测状态)其M个状态取值集合为{o1,o2,o3,...,ok,...,oM}\{o_1,o_2,o_3,...,o_k,...,o_M\}{o1,o2,o3,...,ok,...,oM}。隐马尔科夫模型θ\thetaθ可以由三个矩阵来进行描述θ(A,B,Π)\theta (A,B,\Pi)θ(A,B,Π)。
1. 大小为 N*N (N代表N种隐性的状态)的过渡矩阵 A:
A{aij}{P(xt1sj∣xtsi)}{P(sj∣si)}A \{a_{ij}\} \{P(x_{t1}s_j|x_ts_i)\} \{P(s_j|s_i)\}A{aij}{P(xt1sj∣xtsi)}{P(sj∣si)} 过渡矩阵A中的每一个元素表示由上一个隐性状态sis_isi变为下一个隐性状态的条件概率。
2. 大小为 1*N 的初始概率向量 Π\PiΠ :
ΠπiP(x1si)P(si)\Pi {\pi_i} {P(x_1 s_i)} {P(s_i)}ΠπiP(x1si)P(si) 初始概率向量Π\PiΠ中的每一个元素表示初始隐性状态为sis_isi的概率该向量的长度N与隐性状态的可能取值个数相同。
3. 大小为 M*N 的观测矩阵 B :
B{bki}{P(ytok∣xtsi)}{P(ok∣si)}B \{b_{ki}\} \{P(y_to_k|x_ts_i)\} \{P(o_k|s_i)\} B{bki}{P(ytok∣xtsi)}{P(ok∣si)}
观测矩阵B中的每个元素是用来描述N个隐形状态对应M个观测状态的概率。即在隐形状态为sis_isi 的条件下观测状态为oko_kok的概率。
上述三个矩阵构成了一个完整的隐马尔可夫模型。
掷骰子问题可以帮助我们更好地理解显性状态链和隐性状态链。例如我们有三个面数不一样的骰子可供选择投掷三个骰子一个面数为4一个面数为6一个面数为8。每次选择的骰子是随机的且满足继续选到同一个骰子的概率是选到其他骰子概率的两倍。此时隐性状态链xtx_txt就是我们每次选择的骰子取值集合就是骰子1骰子2骰子3。显性状态链就是我们掷出的一系列数值取值集合为{1,2,3,4,5,6,7,8}\{1,2,3,4,5,6,7,8\}{1,2,3,4,5,6,7,8}。 根据上述的信息我们不难整理出这个骰子问题HMM模型的三个核心矩阵 :
过渡矩阵A
previous state \ current stateD4D6D8D423\frac{2}{3}3216\frac{1}{6}6116\frac{1}{6}61D616\frac{1}{6}6123\frac{2}{3}3216\frac{1}{6}61D816\frac{1}{6}6116\frac{1}{6}6123\frac{2}{3}32
初始概率向量Π\PiΠ 由于一开始是随机选取骰子因此初始抽到三个骰子的概率是相同的13\frac{1}{3}31。
D4D6D813\frac{1}{3}3113\frac{1}{3}3113\frac{1}{3}31
观测矩阵B : 观测矩阵存放了每种隐性状态下各观测状态的条件概率
observed state \ hidden stateD4D6D8114\frac{1}{4}4116\frac{1}{6}6118\frac{1}{8}81214\frac{1}{4}4116\frac{1}{6}6118\frac{1}{8}81314\frac{1}{4}4116\frac{1}{6}6118\frac{1}{8}81414\frac{1}{4}4116\frac{1}{6}6118\frac{1}{8}815016\frac{1}{6}6118\frac{1}{8}816016\frac{1}{6}6118\frac{1}{8}8170018\frac{1}{8}8180018\frac{1}{8}81
使用HMM模型会衍生出三类基础问题 :
第一类问题. 在HMM模型θ\thetaθ确定的情况下针对一组显性状态链y1:Ty_{1:T}y1:T计算出该模型生成这组显性状态链的概率。
还是沿用上述的骰子为例这类问题实际就是在确定了骰子的种类D4D6D8(观测矩阵B)随机选择骰子的方式(过渡矩阵A和初始概率向量Π\PiΠ)的情况下用于计算使用这三个骰子掷出一组数的可能性的问题。计算显性状态链的生成概率也是对模型是否和实际情况吻合的检验。如果多次实验得出的显性状态链由该模型生成的概率很低可以认为构成模型的三个矩阵要素可能与实际情况不符即在该例子中使用的骰子有被掉包的可能或实际随机选取骰子的方式与模型不一致。下面给出计算该问题的其中一个算法 forward algorithm 前向算法与之对应的还有backward algorithm 后向算法由于两者的思路很相似本文中不再对backward algorithm作过多阐述。
forward algorithm 前向算法
计算一组显性状态链 y1,y2,y3,...,yTy_1,y_2,y_3,...,y_Ty1,y2,y3,...,yT (下文中统一称y1:Ty_{1:T}y1:T)生成的概率即计算 P(y1:T)P(y_{1:T})P(y1:T)。我们先定义 αi(t)P(y1:t,xtsi)\alpha_i(t) P(y_{1:t}, x_t s_i)αi(t)P(y1:t,xtsi), 其中sis_isi是该显性状态链最后一个值对应的隐性状态ttt是这个显性状态链的总长度。 αi(t)\alpha_i(t)αi(t)即是掷出该显性状态链且最后一个隐形状态为sis_isi的概率则最终要求的生成概率 P(y1:T)P(y1:T,xts1)P(y1:T,xts2)...P(y1:T,xtsN)∑i1Nαi(T)P(y_{1:T}) P(y_{1:T},x_t s_1) P(y_{1:T},x_t s_2) ... P(y_{1:T},x_t s_N) \\ \sum_{i1}^{N}\alpha_i{(T)}P(y1:T)P(y1:T,xts1)P(y1:T,xts2)...P(y1:T,xtsN)i1∑Nαi(T) 这样我们就把问题转化为了计算αi(T)P(y1:T,xtsi)\alpha_i{(T)} P(y_{1:T},x_ts_i)αi(T)P(y1:T,xtsi)。使用前向算法forward algorithm如下图所示通过去掉最后一个状态的状态链的生成概率αi(t−1)\alpha_i(t-1)αi(t−1)推导至αi(t)\alpha_i{(t)}αi(t)可以归纳为一个递推模型。 首先我们计算生成y1:ty_{1:t}y1:t这个显性状态链且最后一个隐形状态为s1s_1s1的概率α1(t)\alpha_1(t)α1(t)通过这个概率我们就不难推导出同样生成该显性状态链且最后一个隐性状态为s2,s3,...,sNs_2,s_3,...,s_Ns2,s3,...,sN的概率αi(t)\alpha_i(t)αi(t)。
α1(t)P(y1:t,xtsi)P(y1:t−1,xt−1s1)∗P(s1∣s1)∗P(yt∣s1)P(y1:t−1,xt−1s2)∗P(s1∣s2)∗P(yt∣s1)...P(y1:t−1,xt−1xN)∗P(s1∣sN)∗P(yt∣s1)\alpha_1{(t)} P(y_{1:t},x_t s_i) P(y_{1:t-1},x_{t-1}s_1) * P(s_1|s_1) * P(y_t|s_1) \\ P(y_{1:t-1},x_{t-1}s_2) * P(s_1|s_2) * P(y_t|s_1) \\ \\...\\ P(y_{1:t-1},x_{t-1}x_N) * P(s_1|s_N) * P(y_t|s_1)α1(t)P(y1:t,xtsi)P(y1:t−1,xt−1s1)∗P(s1∣s1)∗P(yt∣s1)P(y1:t−1,xt−1s2)∗P(s1∣s2)∗P(yt∣s1)...P(y1:t−1,xt−1xN)∗P(s1∣sN)∗P(yt∣s1)
对于每个前置状态xt−1x_{t-1}xt−1,计算α1(t)\alpha_1(t)α1(t)为三个概率的乘积 : 前一时刻t−1t-1t−1隐形状态为sis_isi且状态链为y1:t−1y_{1:t-1}y1:t−1的概率由前一时刻的隐形状态sis_isi过渡到当前时刻s1s_1s1的过渡概率以及在隐性状态为s1s_1s1的情况下显性状态呈现yty_tyt的概率。 整理可得 : α1(t)α1(t−1)∗a11∗byt,1α2(t−1)∗a21∗byt,1...αN(t−1)∗aN1∗byt,1byt,1∑k1Nαk(t−1)∗ak1\alpha_1(t) \alpha_1(t-1) * a_{11} * b_{yt,1} \\\\ \alpha_2(t-1)*a_{21} * b_{yt,1} \\\\ ... \\\\ \alpha_N(t-1) * a_{N1} * b_{yt,1} \\ b_{yt,1}\sum_{k1}^N\alpha_k(t-1) * a_{k1}α1(t)α1(t−1)∗a11∗byt,1α2(t−1)∗a21∗byt,1...αN(t−1)∗aN1∗byt,1byt,1k1∑Nαk(t−1)∗ak1 tips : aija_{ij}aij是过渡矩阵A中第i行第j列元素aijP(xt−1sj∣xtsi)a_{ij} P(x_{t-1}s_j|x_ts_i)aijP(xt−1sj∣xtsi)即由前一个隐形状态sis_isi过渡到现状态sjs_jsj的概率。
同理可得α2(t)byt,2∑k1Nαk(t−1)∗ak2\alpha_2(t) b_{yt,2}\sum_{k1}^N\alpha_k(t-1) * a_{k2}α2(t)byt,2k1∑Nαk(t−1)∗ak2 不难推出αi(t)byt,i∑k1Nαk(t−1)∗akifor(t2)\alpha_i(t) b_{yt,i}\sum_{k1}^N\alpha_k(t-1) * a_{ki} \space \space for (t2)αi(t)byt,ik1∑Nαk(t−1)∗aki for(t2) 我们就得到了一个计算αi(t)\alpha_i(t)αi(t)的递推模型初始值αi(1)πi∗by1,i\alpha_i(1) \pi_i*b_{y_{1},i}αi(1)πi∗by1,i tips : πi\pi_iπi是初始隐性状态为i的概率(见初始概率向量Π\PiΠ)。
且 P(y1:T)P(y1:T,xts1)P(y1:T,xts2)...P(y1:T,xtsN)∑i1Nαi(T)P(y_{1:T}) P(y_{1:T},x_t s_1) P(y_{1:T},x_t s_2) ... P(y_{1:T},x_t s_N) \\ \sum_{i1}^{N}\alpha_i{(T)}P(y1:T)P(y1:T,xts1)P(y1:T,xts2)...P(y1:T,xtsN)i1∑Nαi(T)易得P(y1:T)∑i1N(byT,1∑k1Nαk(T−1)∗ak1)for(T2)P(y_{1:T} ) \sum_{i1}^N(b_{y_{T,1}}\sum_{k1}^N\alpha_k(T-1) * a_{k1}) \space\space for (\space T2)P(y1:T)i1∑N(byT,1k1∑Nαk(T−1)∗ak1) for( T2) 第二类问题. 在HMM模型θ\thetaθ确定的情况下给出一组显性状态链y1:Ty_{1:T}y1:T找出与其对应的可能性最大 的隐性状态序列x1:Tx_{1:T}x1:T。
这个问题广泛应用于自然语言处理NLP中。例如在我们获取了一组手写符号时找出其最大概率对应的字符。解决这个问题我们就要用到viterbi algorithm 维特比算法。维特比算法仍然利用递推关系,由ttt时刻的状态推出t1t1t1时刻的状态。定义δi(t)\delta_i(t)δi(t)为ttt时刻且显性状态为sis_isi的最优路径的概率。 初始情况非常简单在t1t1t1时刻δi(t)πi∗by1,i\delta_i(t) \pi_i * b_{y_1,i}δi(t)πi∗by1,i每个隐性状态对应的概率均是初始状态概率与对应的显性状态观测概率的乘积。紧接着有递推关系 : δi(t1)[maxjδj(t)aji]∗byt1,i\delta_i(t1) [\max_j\delta_j(t)a_{ji}] * b_{y_{t1},i}δi(t1)[jmaxδj(t)aji]∗byt1,i在这个递推关系中下一时刻t1t1t1每个隐性状态iii的最大概率δi(t1)\delta_i(t1)δi(t1)总是对应上一时刻ttt中最优路径概率δj(t)\delta_j(t)δj(t)与过渡概率ajia_{ji}aji乘积最大的隐性状态jjj。因此最优的隐性状态路径序列$\Psi_i(t) [\argmax_j\delta_i(t)a_{ji}]。下面引用索邦大学课件上的例题作为使用维特比算法的例子 :
给定一个HMM模型θ\thetaθ其中 A∣0.30.50.200.30.7001∣A \left| \begin{matrix} 0.3 0.5 0.2\\ 0 0.3 0.7\\ 0 0 1 \end{matrix} \right| A∣∣∣∣∣∣0.3000.50.300.20.71∣∣∣∣∣∣
Π∣0.60.40∣\Pi \left| \begin{matrix} 0.6\\ 0.4 \\ 0 \end{matrix} \right| Π∣∣∣∣∣∣0.60.40∣∣∣∣∣∣
B∣10.5000.51∣B \left| \begin{matrix} 1 0.5 0\\ 0 0.5 1 \end{matrix} \right| B∣∣∣∣100.50.501∣∣∣∣ 计算显性序列为 y [1,1,2,2] 时对应可能性最大的隐性序列。 结果如下 : 最终的最大概率隐性状态链为[1 2 3 3]对应的概率为0.105。
第三类问题. Baum-Welch算法给定一个序列y1:Ty_{1:T}y1:T估算出能最大化该序列生成概率的HMM模型的参数。
这类问题是非常常见的HMM建模的问题。通过一组给定的显性状态链推测出可能性最大的HMM模型。 首先我们需要用到前向算法中提到的αi(t)\alpha_i(t)αi(t)以及后向算法中的βi(t)\beta_i(t)βi(t)。前向算法的推导过程可以参考之前的部分类似的后向算法如果有兴趣可以自行再查找资料这里不过多赘述只列出使用的公式。 根据之前前向算法部分我们定义了αi(t)P(y1:t,xtsi)\alpha_i(t) P(y_{1:t}, x_t s_i)αi(t)P(y1:t,xtsi)这个可以递推出的概率αi(t)\alpha_i(t)αi(t)代表了观测状态为y1:ty_{1:t}y1:t且第ttt个隐性状态sis_isi的概率。同样在后向算法中我们定义了βi(t)P(yt1,...,yT,xtsi)\beta_i(t) P(y_{t1},...,y_T, x_ts_i)βi(t)P(yt1,...,yT,xtsi)代表了观测状态为yt1:Ty_{t1:T}yt1:T且第ttt个隐性状态为sis_isi的概率。
显然我们有αi(t)βi(t)P(y1:T,xtsi)\alpha_i(t)\beta_i(t)P(y_{1:T},x_ts_i)αi(t)βi(t)P(y1:T,xtsi) 且 P(y1:T)P(y_{1:T})P(y1:T)。
根据贝叶斯公式P(A∣B)P(A,B)P(B)P(A|B) \frac{P(A,B)}{P(B)}P(A∣B)P(B)P(A,B), [2] 我们不难得出在给定观测序列y1:Ty_{1:T}y1:T以及HMM模型θ\thetaθ的情况下在ttt时刻状态是sis_isi的概率 :
γi(t)P(xtsi∣y1:T)P(xtsi,y1:T)P(y1:T)αi(t)βi(t)∑j1Nαj(t)βj(t)\gamma_i(t) P(x_ts_i|y_{1:T}) \frac{P(x_ts_i,y_{1:T})}{P(y_{1:T})}\frac{\alpha_i(t)\beta_i(t)}{\sum_{j1}^{N}\alpha_j(t)\beta_j(t)}γi(t)P(xtsi∣y1:T)P(y1:T)P(xtsi,y1:T)∑j1Nαj(t)βj(t)αi(t)βi(t)
在ttt时刻状态是sis_isi在t1t1t1时刻状态时sjs_jsj的概率 : ξijP(xtsi,xt1sj∣y1:T)P(sj∣si)αi(t)βj(t1)P(yt1∣sj)P(y1:T)aijβj(t1)byt1,jP(y1:T)\xi_{ij} P(x_ts_i,x_{t1} s_j|y_{1:T}) \frac{P(s_j|s_i)\alpha_i(t)\beta_j(t1)P(y_{t1}|s_j)}{P(y_{1:T})} \frac{a_{ij}\beta_j(t1)b_{y_{t1},j}}{P(y_{1:T})}ξijP(xtsi,xt1sj∣y1:T)P(y1:T)P(sj∣si)αi(t)βj(t1)P(yt1∣sj)P(y1:T)aijβj(t1)byt1,j
通过这些基础的概率我们更新θ\thetaθ中的参数。
初始状态是sis_isi的概率向量: Πi∗γi(1)\Pi^*_i \gamma_i(1)Πi∗γi(1)
更新过渡矩阵: aij∗P(sj∣si)∑t1T−1ξij(t)∑t1T−1γi(t)a^*_{ij} P(s_j|s_i) \frac{\sum_{t1}^{T-1}\xi_{ij}(t)}{\sum_{t1}^{T-1}\gamma_{i}(t)}aij∗P(sj∣si)∑t1T−1γi(t)∑t1T−1ξij(t)
更新观测矩阵: bok,i∗∑t1Tαi(t)P(yt∣si)1ytok∑t1Tαi(t)βi(t)b^*_{o_k,i} \frac{\sum_{t1}^T\alpha_i(t)P(y_t|s_i)1_{y_to_k}}{\sum_{t1}^T\alpha_i(t)\beta_i(t)}bok,i∗∑t1Tαi(t)βi(t)∑t1Tαi(t)P(yt∣si)1ytok 其中 1ytok1whenytok1_{y_to_k} 1 \space\space when \space \space y_to_k1ytok1 when ytok 1ytok0whenelse1_{y_to_k} 0 \space\space when \space \space else1ytok0 when else
不断重复上述更新操作直至收敛就得到了新的HMM模型。
\newline \newline \newline \newline \newline
References :
[1] Viterbi AJ (April 1967). “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm”. IEEE Transactions on Information Theory. 13
[2] Baum-Welch algorithm
