HMM数学推导—开篇

2022-01-19 本文已影响0人 PrivateEye_zzy

本章涉及到的知识点清单：

1、HMM定义

2、变量定义

3、两个假设

4、三个基本问题

5、极大似然优化失效

一、HMM定义

隐马尔可夫模型（Hidden Markov Model，HMM）：由一个隐藏的马尔科夫链随机生成一个不可观测的状态序列（隐变量序列），再由各个状态（隐变量或者骰子）随机生成一个观测，由此产生一个观测序列的随机过程，属于生成模型

二、变量定义

HMM生成模型

其中： $i{t}$ 表示第 $t$ 时刻的状态（隐变量或者骰子），则定义状态序列 $I$ 为：

$I = \{i_{1},i_{2},...,i_{t},i_{t+1},...,i_{T}\}$

每个状态均有相同的取值范围，可以理解成每个骰子都有N面取值结果，则定义状态值集合 $Q$ 为：

$Q = \{q_{1},q_{2},...,q_{N} \}$

且：对于任意 $i{t}$ ，均有： $i{t}\in Q$

同理： $o{t}$ 表示第 $t$ 时刻由状态 $i{t}$ 产生的观测（类似量子力学中的本征态），则定义观测序列 $O$ 为：

$O = \{o_{1},o_{2},...,o_{t},o_{t+1},...,o_{T} \}$

每个观测均有相同的取值范围，只是取值的概率各不相同，类似波函数的概率分布，则定义观测集合V为：

$V = \{v_{1},v_{2},...,v_{M} \}$

且：对于任意 $o{t}$ ，均有： $o{t}\in V$

HMM模型将参数分为三类，分别是：

（1）初始状态的概率分布： $\pi$ ，表示初始时刻的第一个状态分别取每一个状态集合的概率，即第一个状态的概率分布，用 $N*1$ 的向量表示，即

$\pi = P(i_{1} = q_{i}),i=1,2,...,N$

（2）状态转移矩阵： $A$ ，表示从 $t$ 时刻的状态 $i_{t}$ 转移到 $t+1$ 时刻的状态 $i_{ t+1 }$ 的概率，即隐变量之间的转移概率，用 $N*N$ 的矩阵表示，即

$A = [a_{ij}]_{i\leq N,j\leq N}$ ，其中： $a_{ij} = P(i_{t+1}=q_{j}|i_{t}=q_{i})$

（3）观测矩阵： $B$ ，表示从 $t$ 时刻的状态 $i_{t}$ 观测到具体 $o_{t}$ 的概率，即当前隐变量产生观测的概率，用 $N*M$ 的矩阵表示，即

$B = [b_{j}(k)]_{j\leq N,k\leq M}$ ，其中： $b_{j}(k) = P(o_{t}=v_{k}|i_{t}=q_{j})$

综上：统一使用 $\lambda = (\pi,A,B)$ 代表HMM的参数集合

三、两个假设

HMM涉及到大量的概率计算，为了使得推导简化和概率计算简化，HMM约定了以下2个假设

（1）齐次Markov假设：任意时刻的状态，只依赖于前一时刻的状态，与其它时刻的状态均无关，即

$P(i_{t+1}|i_{1},...,i_{t},o_{1},...,o_{t})= P(i_{t+1}|i_{t})$

特别的，初始时刻的状态概率分布由参数 $\pi$ 决定

（2）观测独立假设：任意时刻的观测，只依赖于该时刻的状态，与其他无关，即

$P(o_{t}|i_{1},...,i_{t},o_{1},...,o_{t-1})= P(o_{t}|i_{t})$

以上2个假设在后续的推导中经常会用到，能帮助我们很大程度上简化推导

四、三个基本问题

HMM只要解决以下三个基本问题

（1）Evaluation：概率计算问题，即：已知：模型参数 $\lambda$ 和观测序列 $O$ ，求概率： $P(O|\lambda)$

（2）Learning：学习模型参数问题，即：已知观测序列 $O$ ，求最优模型参数： $\hat{\lambda } = \argmax P(O|\lambda)$

学习问题也是HMM基础问题中相对最复杂的，在MLE优化失效的情况下，通过EM优化算法来估计模型参数

（3）Decoding：解码问题，即：已知：模型参数 $\lambda$ 和观测序列 $O$ ，求最优隐变量序列： $\hat{I } = \argmax P(I|O,\lambda)$

HMM的其余问题，都可以基于这三个基本问题变形出来

五、极大似然优化失效

下面我们以Evaluation问题为例，尝试应用MLE来推导概率的求解过程

很自然的将隐变量 $I$ 引入待求解的概率 $P(O|\lambda)$

$P(O|\lambda) = \sum_{I} P(O,I|\lambda) \\= \sum_{I} P(I|\lambda) P(O|I,\lambda)$

将积分中的 $P(I|\lambda)$ 展开和应用齐次Markov假设：

化简1

将积分中的 $P(O|I,\lambda)$ 展开：

化简2

则 $P(O|\lambda)$ 可以写为：

时间复杂度

其中 $\sum_{I} = \sum_{i_{1}}\sum_{i_{2}}...\sum_{i_{T}}$ ，是一个 $T$ 重积分，可见即使不考虑内部计算， $P(O|\lambda)$ 的计算也至少是 $O(N^{T})$ 阶的时间复杂度，我们需要更有效的算法来求解Evaluation

HMM数学推导—开篇

猜你喜欢

热点阅读