我家小花儿

这个屌丝很懒，什么也没留下！

热门标签

统计学习方法——第10章隐马尔可夫模型（HMM）_em算法例题小球盒子模型

作者：我家小花儿 | 2024-04-01 06:34:00

踩

em算法例题小球盒子模型

介绍：

隐马尔可夫模型（Hidden Markov Model,HMM）是关于时序的概率模型，描述了由隐藏的马尔科夫链随机生成的不可观测的状态随机序列，再由各个状态生成一个观测而产生的观测随机序列的过程。其中，隐藏的马尔科夫链随机生成的不可观测的状态随机序列称为状态序列（state sequence），每个状态生成一个观测，而由此产生的观测的随机序列称为观测序列（observation sequence）。

举例：盒子和球模型。假设有四个盒子，每个盒子里面装有红色和白色的小球，小球的数量如下：

盒子和球模型
盒子	1	2	3	4
红球	5	3	6	8
白球	5	7	4	2

抽样规则如下：开始从四个盒子中等概随机选取一个盒子，从这个盒子中随机选取一个小球，记录小球颜色，然后将小球放回。规则为：如果选取的为1号盒子，则下次只能从2号盒子中抽取；如果抽取的盒子为2号或者3号盒子，分别以0.4和0.6的概率从左边盒子和右边盒子中抽取；如果选取的为4号盒子，则以0.5的概率从4号盒子或者1号盒子中抽取，记录小球的颜色，然后放回。如此下去，重复进行5次试验，得到小球的观测结果为（红球记为R,白球记为W）：

$O = \{R, R, W,W,R\}$

在这个过程中，观察者只能观察到小球的颜色序列，观测不到盒子序列，讨论的问题是根据结果预测可能的盒子序列。

形式化描述：

设 $N$ 为可能的状态数（如4个盒子）， $M$ 为可能的观测数（如红球和白球）;

设 $I$ 是长度为 $T$ 的状态序列， $O$ 是对应的观测序列： $I=\{i_1, i_2,...,i_T \}$ , $O = \{o_1, o_2, ..., o_T \}$

设状态转移概率矩阵： $A=[a_{ij}]_{N\times N}$ 。其中， $a_{ij} = P(i_{t+1}=q_j|i_t=q_i)$ ，即t时刻状态 $q_i$ 到 $q_j$ 转移概率

设观测概率矩阵： $B=[b_j(k)]_{N\times M}$ 。其中， $b_j(k)=P(o_t=v_k|i_t=q_j)$ ，即t时刻状态 $q_j$ 生成观测 $v_k$ 的概率

设初始状态概率向量： $\pi=(\pi_{i})$ 。其中， $\pi_i = P(i_1=q_i)$ ，即t=1时刻状态 $q_j$ 的概率

由此，隐马尔可夫模型的三要素： $\lambda=(A,B,\pi)$

图形化描述：

马尔科夫模型的基本假设：

齐次马尔科夫假设：假设隐藏的马尔科夫链在任意时刻t的状态只依赖前一时刻的状态，与其他时刻的观测和状态无关；
观测独立性假设：假设任意时刻的观测只依赖该时刻马尔科夫链的状态，与其他观测和状态无关；

马尔科夫模型的基本问题：

1）概率计算问题

给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O = \{o_1, o_2, ..., o_T \}$ ，计算在模型参数 $\lambda$ 下的观测序列 $O$ 出现的概率 $P(O|\lambda)$ 。

2）学习问题

已知观测序列 $O = \{o_1, o_2, ..., o_T \}$ ，使用最大似然准则估计模型参数 $\lambda=(A,B,\pi)$ ，使得 $P(O|\lambda)$ 最大。

3）预测问题

给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O = \{o_1, o_2, ..., o_T \}$ ，求使得 $P(I|\lambda)$ 最大时对应的状态序列。

1）概率计算问题 <---->前向后向算法

令 $\alpha_T(i)=P(o_1,o_2, ...,o_T,i_T=q_i|\lambda)$ ，则 $P(O|\lambda)=\sum_{i=1}^N\alpha_T(i) \ \ \ \ (1)$

令 $\beta_t(i)=\sum_{i=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j)$ ，则 $P(O|\lambda)=\sum_{i=1}^N\pi_ib_j(o_1)\beta_1(t) \ \ \ \ (2)$

合并式：

$P(O|\lambda) = \sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j))$

当t=1时对应(1)式前向算法，当t=T-1时对应(2)式后项算法。

2）学习问题<---->Baum-Welch算法（EM算法）

设 $\hat\lambda$ 是隐马尔可夫模型当前的估计参数， $\lambda$ 是要极大化的隐马尔可夫模型参数，定义Q函数：

$Q(\lambda, \hat\lambda)=\sum_I\log(P(O,I|\lambda)P(O,I|\hat\lambda))$

EM算法：

E步： $Q(\lambda, \hat\lambda)=\sum_I\pi P(O,I|\hat\lambda))+\sum_IAP(O,I|\hat\lambda))+\sum_IBP(O,I|\hat\lambda))$

M步：极大化 $Q(\lambda, \hat\lambda)$ ，求模型参数 $(A,B,\pi)$

$\pi_i = \dfrac{P(O,i_1|\hat\lambda)}{P(O|\hat\lambda)}=\gamma_1(i)$

$a_{ij} = \dfrac{\sum_i^{T-1}P(O,i_t=i, i_{t+1}=j|\hat\lambda)}{\sum_i^{T-1}P(O,i_t=i|\hat\lambda)}=\dfrac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}$

$b_{j}(k) = \dfrac{\sum_t^{T}P(O, i_{t}=j|\hat\lambda)I(o_t=v_k)}{\sum_t^{T}P(O,i_t=j|\hat\lambda)}=\dfrac{\sum_{t=1,o_t=v_k}^{T-1}\gamma_t(j)}{\sum_{t=1}^{T-1}\gamma_t(j)}$

3）预测问题<---->维特比算法

定义在时刻t的状态为i的所有单个路径 $(i_1,i_2,...,i_t)$ 中概率最大的为: $\delta_t(i)=\max_{i_1,...,i_{t-1}}P(i_t=i,i_{t-1}, ..., i_1, o_t, ...,o_1|\lambda)$

变量 $\delta_t(i)$ 的递推公式： $\delta_{t+1}(i)=\max_{i_1,...,i_{t}}P(i_{t+1}=i,i_{t-1}, ..., i_1, o_{t+1}, ...,o_1|\lambda)=\max_{1\leq j\leq N}[\delta_t(j)a_{ji}]b_i(o_{t+1})$

定义在时刻t的状态为i的所有单个路径 $(i_1,i_2,...,i_t)$ 中概率最大的路径的第（t-1）个节点为： $\Psi _t(i) = \max_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}]$

终止条件：

$P^*=\max_{1 \leq i \leq N}\delta_T(i)$

$i_T^*=\max_{1\leq i \leq N}[\delta_t(i)]$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/347698

统计学习方法——第10章 隐马尔可夫模型（HMM）_em算法例题小球盒子模型

统计学习方法——第10章隐马尔可夫模型（HMM）_em算法例题小球盒子模型