Question

1. 隐马尔可夫模型的 3 个基本问题：

   • 概率计算问题：给定模型 $ MathJax-Element-419 $ 和观测序列 $ MathJax-Element-389 $ ，计算观测序列 $ MathJax-Element-319 $ 出现的概率 $ MathJax-Element-214 $ 。即：评估模型 $ MathJax-Element-123 $ 与观察序列 $ MathJax-Element-319 $ 之间的匹配程度。

   • 学习问题：已知观测序列 $ MathJax-Element-389 $ ，估计模型 $ MathJax-Element-419 $ 的参数，使得在该模型下观测序列概率 $ MathJax-Element-214 $ 最大。即：用极大似然估计的方法估计参数。

   • 预测问题（也称为解码问题）：已知模型 $ MathJax-Element-419 $ 和观测序列 $ MathJax-Element-389 $ ， 求对给定观测序列的条件概率 $ MathJax-Element-119 $ 最大的状态序列 $ MathJax-Element-133 $ 。即：给定观测序列，求最可能的对应的状态序列 。

     如：在语音识别任务中，观测值为语音信号，隐藏状态为文字。解码问题的目标就是：根据观测的语音信号来推断最有可能的文字序列。

2.1 概率计算问题

1. 给定隐马尔可夫模型 $ MathJax-Element-419 $ 和观测序列 $ MathJax-Element-389 $ ，概率计算问题需要计算在模型 $ MathJax-Element-123 $ 下观测序列 $ MathJax-Element-319 $ 出现的概率 $ MathJax-Element-214 $ 。

2. 最直接的方法是按照概率公式直接计算：通过列举所有可能的、长度为 $ MathJax-Element-282 $ 的状态序列 $ MathJax-Element-133 $ ，求各个状态序列 $ MathJax-Element-329 $ 与观测序列 $ MathJax-Element-389 $ 的联合概率 $ MathJax-Element-130 $ ，然后对所有可能的状态序列求和，得到 $ MathJax-Element-214 $ 。

   • 状态序列 $ MathJax-Element-133 $ 的概率为：

     $ P(\mathbf I;\lambda)=\pi_{{i}_1}a_{{i}_1,{i}_2}a_{{i}_2,{i}_3}\cdots a_{{i}_{T-1},{i}_T} $

   • 给定状态序列 $ MathJax-Element-133 $ ，观测序列 $ MathJax-Element-389 $ 的条件概率为：

     $ P(\mathbf O\mid \mathbf I;\lambda)=b_{{i}_1}({o}_1)b_{{i}_2}({o}_2)\cdots b_{{i}_T}({o}_T) $

   • $ MathJax-Element-319 $ 和 $ MathJax-Element-329 $ 同时出现的联合概率为：

     $ P(\mathbf O,\mathbf I;\lambda)=P(\mathbf O\mid \mathbf I;\lambda)P(\mathbf I;\lambda)=\pi_{{i}_1}a_{{i}_1,{i}_2}a_{{i}_2,{i}_3}\cdots a_{{i}_{T-1},{i}_T}b_{{i}_1}({o}_1)b_{{i}_2}({o}_2)\cdots b_{{i}_T}({o}_T) $

   • 对所有可能的状态序列 $ MathJax-Element-329 $ 求和，得到观测序列 $ MathJax-Element-319 $ 的概率：

     $ P(\mathbf O;\lambda)=\sum_{\mathbf I} P(\mathbf O,\mathbf I;\lambda)=\sum_{{i}_1,{i}_2,\cdots,{i}_T} \pi_{{i}_1}a_{{i}_1,{i}_2}a_{{i}_2,{i}_3}\cdots a_{{i}_{T-1},{i}_T}b_{{i}_1}({o}_1)b_{{i}_2}({o}_2)\cdots b_{{i}_T}({o}_T) $

   • 上式的算法复杂度为 $ MathJax-Element-139 $ ，太复杂，实际应用中不太可行。

2.1.1 前向算法

1. 给定隐马尔可夫模型 $ MathJax-Element-419 $ ，定义前向概率：在时刻 $ MathJax-Element-417 $ 时的观测序列为 $ MathJax-Element-238 $ ， 且时刻 $ MathJax-Element-417 $ 时状态为 $ MathJax-Element-144 $ 的概率为前向概率，记作： $ MathJax-Element-145 $

2. 根据定义， $ MathJax-Element-146 $ 是在时刻 $ MathJax-Element-417 $ 时观测到 $ MathJax-Element-238 $ ，且在时刻 $ MathJax-Element-417 $ 处于状态 $ MathJax-Element-270 $ 的前向概率。则有：

   • $ MathJax-Element-151 $ ：为在时刻 $ MathJax-Element-417 $ 时观测到 $ MathJax-Element-238 $ ，且在时刻 $ MathJax-Element-417 $ 处于状态 $ MathJax-Element-270 $ ，且在 $ MathJax-Element-373 $ 时刻处在状态 $ MathJax-Element-418 $ 的概率。

   • $ MathJax-Element-158 $ ：为在时刻 $ MathJax-Element-417 $ 观测序列为 $ MathJax-Element-238 $ ，并且在时刻 $ MathJax-Element-373 $ 时刻处于状态 $ MathJax-Element-418 $ 的概率。

   • 考虑 $ MathJax-Element-163 $ ，则得到前向概率的地推公式：

     $ \alpha_{t+1}(i)=\left[\sum_{j=1}^{Q}\alpha_t(j)a_{j,i}\right]b_i(o_{t+1}) $

     

3. 观测序列概率的前向算法：

   • 输入：

     • 隐马尔可夫模型 $ MathJax-Element-419 $
     • 观测序列 $ MathJax-Element-389 $

   • 输出： 观测序列概率 $ MathJax-Element-214 $

   • 算法步骤：

     • 计算初值： $ MathJax-Element-167 $ 。

       该初值是初始时刻的状态 $ MathJax-Element-345 $ 和观测 $ MathJax-Element-226 $ 的联合概率。

     • 递推：对于 $ MathJax-Element-170 $ ：

       $ \alpha_{t+1}(i)=\left[\sum_{j=1}^{Q}\alpha_t(j)a_{j,i}\right]b_i(o_{t+1}),\quad i=1,2,\cdots,Q $

     • 终止： $ MathJax-Element-171 $ 。

       因为 $ MathJax-Element-172 $ 表示在时刻 $ MathJax-Element-282 $ ，观测序列为 $ MathJax-Element-174 $ ，且状态为 $ MathJax-Element-418 $ 的概率。对所有可能的 $ MathJax-Element-176 $ 个状态 $ MathJax-Element-418 $ 求和则得到 $ MathJax-Element-214 $ 。

4. 前向算法是基于 状态序列的路径结构 递推计算 $ MathJax-Element-214 $ 。

   • 其高效的关键是局部计算前向概率，然后利用路径结构将前向概率“递推”到全局。
   • 算法复杂度为 $ MathJax-Element-180 $ 。

2.1.2 后向算法

1. 给定隐马尔可夫模型 $ MathJax-Element-419 $ ，定义后向概率：在时刻 $ MathJax-Element-417 $ 的状态为 $ MathJax-Element-418 $ 的条件下，从时刻 $ MathJax-Element-373 $ 到 $ MathJax-Element-282 $ 的观测序列为 $ MathJax-Element-192 $ 的概率为后向概率，记作： $ MathJax-Element-187 $ 。

2. 在时刻 $ MathJax-Element-417 $ 状态为 $ MathJax-Element-418 $ 的条件下，从时刻 $ MathJax-Element-373 $ 到 $ MathJax-Element-282 $ 的观测序列为 $ MathJax-Element-192 $ 的概率可以这样计算：

   • 考虑 $ MathJax-Element-417 $ 时刻状态 $ MathJax-Element-418 $ 经过 $ MathJax-Element-300 $ 转移到 $ MathJax-Element-373 $ 时刻的状态 $ MathJax-Element-270 $ 。

     • $ MathJax-Element-373 $ 时刻状态为 $ MathJax-Element-270 $ 的条件下，从时刻 $ MathJax-Element-200 $ 到 $ MathJax-Element-282 $ 的观测序列为观测序列为 $ MathJax-Element-202 $ 的概率为 $ MathJax-Element-203 $ 。
     • $ MathJax-Element-373 $ 时刻状态为 $ MathJax-Element-270 $ 的条件下，从时刻 $ MathJax-Element-373 $ 到 $ MathJax-Element-282 $ 的观测序列为观测序列为 $ MathJax-Element-208 $ 的概率为 $ MathJax-Element-209 $ 。

   • 考虑所有可能的 $ MathJax-Element-270 $ ，则得到 $ MathJax-Element-211 $ 的递推公式：

     $ \beta_t(i)=\sum_{j=1}^{Q} a_{i,j}b_j(o_{t+1})\beta_{t+1}(j) $

     

3. 观测序列概率的后向算法：

   • 输入：

     • 隐马尔可夫模型 $ MathJax-Element-419 $
     • 观测序列 $ MathJax-Element-389 $

   • 输出： 观测序列概率 $ MathJax-Element-214 $

   • 算法步骤：

     • 计算初值： $ MathJax-Element-215 $

       对最终时刻的所有状态 $ MathJax-Element-418 $ ，规定 $ MathJax-Element-217 $ 。

     • 递推：对 $ MathJax-Element-424 $ :

       $ \beta_t(i)=\sum_{j=1}^{Q} a_{i,j}b_j(o_{t+1})\beta_{t+1}(j),\quad i=1,2,\cdots,Q $

     • 终止： $ MathJax-Element-219 $

       $ MathJax-Element-220 $ 为在时刻 1， 状态为 $ MathJax-Element-418 $ 的条件下，从时刻 2 到 $ MathJax-Element-282 $ 的观测序列为 $ MathJax-Element-223 $ 的概率。对所有的可能初始状态 $ MathJax-Element-418 $ （由 $ MathJax-Element-311 $ 提供其概率）求和并考虑 $ MathJax-Element-226 $ 即可得到观测序列为 $ MathJax-Element-227 $ 的概率。

2.1.3 统一形式

1. 利用前向概率和后向概率的定义，可以将观测序列概率统一为：

   $ P(\mathbf O;\lambda)=\sum_{i=1}^{Q}\sum_{j=1}^{Q}\alpha_t(i)a_{i,j}b_j(o_{t+1})\beta_{t+1}(j),\quad t=1,2,\cdots,T-1 $

   • 当 $ MathJax-Element-400 $ 时，就是后向概率算法；当 $ MathJax-Element-229 $ 时，就是前向概率算法。

   • 其意义为：在时刻 $ MathJax-Element-417 $ ：

     • $ MathJax-Element-231 $ 表示：已知时刻 $ MathJax-Element-417 $ 时的观测序列为 $ MathJax-Element-238 $ 、 且时刻 $ MathJax-Element-417 $ 时状态为 $ MathJax-Element-418 $ 的概率。
     • $ MathJax-Element-236 $ 表示：已知时刻 $ MathJax-Element-417 $ 时的观测序列为 $ MathJax-Element-238 $ 、 且时刻 $ MathJax-Element-417 $ 时状态为 $ MathJax-Element-418 $ 、且 $ MathJax-Element-373 $ 时刻状态为 $ MathJax-Element-270 $ 的概率。
     • $ MathJax-Element-243 $ 表示： 已知时刻 $ MathJax-Element-373 $ 时的观测序列为 $ MathJax-Element-245 $ 、 且时刻 $ MathJax-Element-417 $ 时状态为 $ MathJax-Element-418 $ 、且 $ MathJax-Element-373 $ 时刻状态为 $ MathJax-Element-270 $ 的概率。
     • $ MathJax-Element-250 $ 表示：已知观测序列为 $ MathJax-Element-251 $ 、 且时刻 $ MathJax-Element-417 $ 时状态为 $ MathJax-Element-418 $ 、且 $ MathJax-Element-373 $ 时刻状态为 $ MathJax-Element-270 $ 的概率。
     • 对所有可能的状态 $ MathJax-Element-256 $ 取值，即得到上式。

2. 根据前向算法有： $ MathJax-Element-257 $ 。则得到：

   $ P(\mathbf O;\lambda)=\sum_{i=1}^{Q}\sum_{j=1}^{Q}\alpha_t(i)a_{i,j}b_j(o_{t+1})\beta_{t+1}(j)\\ =\sum_{j=1}^{Q}\left[\sum_{i=1}^{Q}\alpha_t(i)a_{i,j}b_j(o_{t+1})\right]\beta_{t+1}(j) =\sum_{j=1}^Q\alpha_{t+1}(j)\beta_{t+1}(j)\quad\\ t=1,2,\cdots,T-1 $

   由于 $ MathJax-Element-417 $ 的形式不重要，因此有：

   $ P(\mathbf O;\lambda)=\sum_{j=1}^Q\alpha_{t}(j)\beta_{t}(j),\quad t=1,2,\cdots,T $

3. 给定模型 $ MathJax-Element-419 $ 和观测序列 $ MathJax-Element-319 $ 的条件下，在时刻 $ MathJax-Element-417 $ 处于状态 $ MathJax-Element-418 $ 的概率记作： $ MathJax-Element-263 $

   • 根据定义：

     $ \gamma_t(i)=P(i_t=i\mid \mathbf O;\lambda)=\frac{P(i_t=i,\mathbf O;\lambda)}{P(\mathbf O;\lambda)} $

   • 根据前向概率和后向概率的定义，有： $ MathJax-Element-264 $ ，则有：

     $ \gamma_t(i)=\frac{P(i_t=i,\mathbf O;\lambda)}{P(\mathbf O;\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{P(\mathbf O;\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^{Q}\alpha_t(j)\beta_t(j)} $

4. 给定模型 $ MathJax-Element-419 $ 和观测序列 $ MathJax-Element-319 $ ，在时刻 $ MathJax-Element-417 $ 处于状态 $ MathJax-Element-418 $ 且在 $ MathJax-Element-269 $ 时刻处于状态 $ MathJax-Element-270 $ 的概率记作： $ MathJax-Element-271 $

   • 根据

     $ \xi_t(i,j)=P(i_t=i,i_{t+1}=j\mid \mathbf O;\lambda)=\frac{P(i_t=i,i_{t+1}=j,\mathbf O;\lambda)}{P(\mathbf O;\lambda)}\\=\frac{P(i_t=i,i_{t+1}=j,\mathbf O;\lambda)}{\sum_{u=1}^{Q}\sum_{v=1}^{Q}P(i_t=u,i_{t+1}=v,\mathbf O;\lambda)} $

   • 考虑到前向概率和后向概率的定义有： $ MathJax-Element-272 $ ，因此有：

     $ \xi_t(i,j)=\frac{\alpha_t(i)a_{i,j}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{u=1}^{Q}\sum_{v=1}^{Q}\alpha_t(u)a_{u,v}b_v(o_{t+1})\beta_{t+1}(v)} $

5. 一些期望值：

   • 在给定观测 $ MathJax-Element-319 $ 的条件下，状态 $ MathJax-Element-415 $ 出现的期望值为： $ MathJax-Element-275 $ 。

   • 在给定观测 $ MathJax-Element-319 $ 的条件下，从状态 $ MathJax-Element-415 $ 转移的期望值： $ MathJax-Element-278 $ 。

     • 这里的转移，表示状态 $ MathJax-Element-415 $ 可能转移到任何可能的状态。
     • 假若在时刻 $ MathJax-Element-282 $ 的状态为 $ MathJax-Element-418 $ ，则此时不可能再转移，因为时间最大为 $ MathJax-Element-282 $ 。

   • 在观测 $ MathJax-Element-319 $ 的条件下，由状态 $ MathJax-Element-415 $ 转移到状态 $ MathJax-Element-374 $ 的期望值： $ MathJax-Element-286 $ 。

2.2 学习问题

1. 根据训练数据的不同，隐马尔可夫模型的学习方法也不同：

   • 训练数据包括观测序列和对应的状态序列：通过监督学习来学习隐马尔可夫模型。
   • 训练数据仅包括观测序列：通过非监督学习来学习隐马尔可夫模型。

2.2.1 监督学习

1. 假设数据集为 $ MathJax-Element-287 $ 。其中：

   • $ MathJax-Element-318 $ 为 $ MathJax-Element-315 $ 个观测序列； $ MathJax-Element-290 $ 为对应的 $ MathJax-Element-315 $ 个状态序列。
   • 序列 $ MathJax-Element-316 $ ， $ MathJax-Element-293 $ 的长度为 $ MathJax-Element-317 $ ，其中数据集中 $ MathJax-Element-318 $ 之间的序列长度可以不同。

2. 可以利用极大似然估计来估计隐马尔可夫模型的参数。

   • 转移概率 $ MathJax-Element-300 $ 的估计：设样本中前一时刻处于状态 $ MathJax-Element-415 $ 、且后一时刻处于状态 $ MathJax-Element-374 $ 的频数为 $ MathJax-Element-299 $ ，则状态转移概率 $ MathJax-Element-300 $ 的估计是：

     $ \hat a_{i,j}=\frac{A_{i,j}}{\sum_{u=1}^{Q}A_{i,u}} ,\quad i=1,2,\cdots,Q;j=1,2,\cdots,Q $

   • 观测概率 $ MathJax-Element-307 $ 的估计：设样本中状态为 $ MathJax-Element-374 $ 并且观测为 $ MathJax-Element-378 $ 的频数为 $ MathJax-Element-304 $ ，则状态为 $ MathJax-Element-374 $ 并且观测为 $ MathJax-Element-378 $ 的概率 $ MathJax-Element-307 $ 的估计为：

     $ \hat b_j(k)=\frac{B_{j,k}}{\sum_{v=1}^{V}B_{j,v}},\quad j=1,2,\cdots,Q;k=1,2,\cdots,V $

   • 初始状态概率的估计：设样本中初始时刻（即： $ MathJax-Element-400 $ ）处于状态 $ MathJax-Element-415 $ 的频数为 $ MathJax-Element-310 $ ，则初始状态概率 $ MathJax-Element-311 $ 的估计为： $ MathJax-Element-312 $ 。

2.2.2 无监督学习

1. 监督学习需要使用人工标注的训练数据。由于人工标注往往代价很高，所以经常会利用无监督学习的方法。

   隐马尔可夫模型的无监督学习通常使用 Baum-Welch 算法求解。

2. 在隐马尔可夫模型的无监督学习中，数据集为 $ MathJax-Element-379 $ 。其中：

   • $ MathJax-Element-318 $ 为 $ MathJax-Element-315 $ 个观测序列。
   • 序列 $ MathJax-Element-316 $ 的长度为 $ MathJax-Element-317 $ ，其中数据集中 $ MathJax-Element-318 $ 之间的序列长度可以不同。

3. 将观测序列数据看作观测变量 $ MathJax-Element-319 $ ， 状态序列数据看作不可观测的隐变量 $ MathJax-Element-329 $ ，则隐马尔可夫模型事实上是一个含有隐变量的概率模型： $ MathJax-Element-321 $ 。其参数学习可以由 EM 算法实现。

   • E 步：求 Q 函数（其中 $ MathJax-Element-360 $ 是参数的当前估计值）

     $ Q(\lambda,\bar \lambda)=\sum_{j=1}^N\left(\sum_{\mathbf I} P(\mathbf I\mid \mathbf O=\mathbf O_j;\bar\lambda)\log P(\mathbf O=\mathbf O_j,\mathbf I;\lambda)\right) $

     将 $ MathJax-Element-323 $ 代入上式，有：

     $ Q(\lambda,\bar \lambda)=\sum_{j=1}^N\frac{1}{P(\mathbf O_j;\bar\lambda)}\left(\sum_{\mathbf I} P(\mathbf I,\mathbf O=\mathbf O_j;\bar\lambda)\log P(\mathbf I,\mathbf O=\mathbf O_j;\lambda)\right) $
     • 在给定参数 $ MathJax-Element-360 $ 时， $ MathJax-Element-325 $ 是已知的常数，记做 $ MathJax-Element-326 $ 。
     • 在给定参数 $ MathJax-Element-360 $ 时， $ MathJax-Element-328 $ 是 $ MathJax-Element-329 $ 的函数，记做 $ MathJax-Element-330 $ 。

     根据 $ MathJax-Element-331 $ 得到：

     $ Q(\lambda,\bar \lambda)=\sum_{j=1}^N\frac{1}{\tilde P_j}\left(\sum_{\mathbf I }(\log \pi_{{i}_1})\tilde P_j(\mathbf I)+\sum_{\mathbf I}\left(\sum_{t=1}^{T_j-1}\log a_{i_t,i_{t+1}}\right)\tilde P_j(\mathbf I)\\ +\sum_{\mathbf I}\left(\sum_{t=1}^{T_j}\log b_{{i}_t}({o}_t^{(j)})\right)\tilde P_j(\mathbf I)\right) $

     其中： $ MathJax-Element-332 $ 表示第 $ MathJax-Element-374 $ 个序列的长度， $ MathJax-Element-334 $ 表示第 $ MathJax-Element-374 $ 个观测序列的第 $ MathJax-Element-417 $ 个位置。

   • M 步：求Q 函数的极大值：

     $ \bar\lambda^{}\leftarrow \arg\max_{\lambda} Q(\lambda,\bar\lambda) $

     极大化参数在 Q 函数中单独的出现在3个项中，所以只需要对各项分别极大化。

     • $ MathJax-Element-337 $ ：

       $ \frac{\partial Q(\lambda,\bar\lambda)}{\partial \pi_i}=\frac{\partial (\sum_{j=1}^N\frac{1}{\tilde P_j}\sum_{\mathbf I }(\log \pi_{{i}_1})\tilde P_j(\mathbf I))}{\partial \pi_i}\\ =\sum_{j=1}^N\frac{1}{\tilde P_j} \sum_{i_1=1}^Q P(i_1,\mathbf O=\mathbf O_j;\bar\lambda)\frac{\partial\log \pi_{i_1}}{\partial \pi_i} $

       将 $ MathJax-Element-338 $ 代入，有：

       $ \frac{\partial Q(\lambda,\bar\lambda)}{\partial \pi_i}=\sum_{j=1}^N\frac{1}{\tilde P_j}\left(\frac{P(i_1=i,\mathbf O=\mathbf O_j;\bar\lambda)}{\pi_i}-\frac{P(i_1=Q,\mathbf O=\mathbf O_j;\bar\lambda)}{\pi_Q}\right)=0 $

       将 $ MathJax-Element-339 $ 代入，即有：

       $ \pi_i \propto \sum_{j=1}^N P(i_1=i\mid \mathbf O=\mathbf O_j;\bar\lambda) $

       考虑到 $ MathJax-Element-340 $ ，以及 $ MathJax-Element-341 $ ， 则有：

       $ \pi_i=\frac{\sum_{j=1}^N P(i_1=i\mid \mathbf O=\mathbf O_j;\bar\lambda)}{N} $

       其物理意义为：统计在给定参数 $ MathJax-Element-360 $ ，已知 $ MathJax-Element-361 $ 的条件下， $ MathJax-Element-345 $ 的出现的频率。它就是 $ MathJax-Element-345 $ 的后验概率的估计值。

     • $ MathJax-Element-346 $ ：同样的处理有：

       $ \frac{\partial Q(\lambda,\bar\lambda)}{\partial a_{i,j}}=\sum_{k=1}^N\frac{1}{\tilde P_k}\sum_{t=1}^{T_k-1}\left(\frac{P(i_t=i,i_{t+1}=j,\mathbf O=\mathbf O_k;\bar\lambda)}{a_{i,j}}\\-\frac{P(i_t=i,i_{t+1}=Q,\mathbf O=\mathbf O_k;\bar\lambda)}{a_{i,Q}}\right) $

       得到：

       $ a_{i,j}\propto \sum_{k=1}^N\sum_{t=1}^{T_k-1}P(i_t=i,i_{t+1}=j\mid \mathbf O=\mathbf O_k;\bar\lambda) $

       考虑到 $ MathJax-Element-347 $ ，则有：

       $ a_{i,j}=\frac {\sum_{k=1}^N\sum_{t=1}^{T_k-1}P(i_t=i,i_{t+1}=j\mid \mathbf O=\mathbf O_k;\bar\lambda)}{\sum_{j^\prime=1}^Q \sum_{k=1}^N\sum_{t=1}^{T_k-1}P(i_t=i,i_{t+1}=j^\prime\mid \mathbf O=\mathbf O_k;\bar\lambda)}\\ =\frac {\sum_{k=1}^N\sum_{t=1}^{T_k-1}P(i_t=i,i_{t+1}=j\mid \mathbf O=\mathbf O_k;\bar\lambda)}{ \sum_{k=1}^N\sum_{t=1}^{T_k-1}P(i_t=i\mid \mathbf O=\mathbf O_k;\bar\lambda)} $

       其物理意义为：统计在给定参数 $ MathJax-Element-360 $ ，已知 $ MathJax-Element-361 $ 的条件下，统计当 $ MathJax-Element-350 $ 的情况下 $ MathJax-Element-351 $ 的出现的频率。它就是 $ MathJax-Element-352 $ 的后验概率的估计值。

     • $ MathJax-Element-353 $ ：同样的处理有：

       得到：

       $ b_j(k) \propto \sum_{i=1}^N\sum_{t=1}^{T_i}P(i_t=j,o_t=k\mid \mathbf O=\mathbf O_i;\bar\lambda) $

       其中如果第 $ MathJax-Element-415 $ 个序列 $ MathJax-Element-355 $ 的第 $ MathJax-Element-417 $ 个位置 $ MathJax-Element-357 $ ，则 $ MathJax-Element-358 $ 。

       考虑到 $ MathJax-Element-359 $ ，则有：

       $ b_j(k)= \frac{ \sum_{i=1}^N\sum_{t=1}^{T_i}P(i_t=j,o_t=k\mid \mathbf O=\mathbf O_i;\bar\lambda)}{\sum_{k^\prime=1}^V \sum_{i=1}^N\sum_{t=1}^{T_i}P(i_t=j,o_t=k^\prime\mid \mathbf O=\mathbf O_i;\bar\lambda)}\\ =\frac{ \sum_{i=1}^N\sum_{t=1}^{T_i}P(i_t=j,o_t=k\mid \mathbf O=\mathbf O_i;\bar\lambda)}{\sum_{i=1}^N\sum_{t=1}^{T_i}P(i_t=j\mid \mathbf O=\mathbf O_i;\bar\lambda)} $

       其物理意义为：统计在给定参数 $ MathJax-Element-360 $ ，已知 $ MathJax-Element-361 $ 的条件下，统计当 $ MathJax-Element-362 $ 的情况下 $ MathJax-Element-363 $ 的出现的频率。它就是 $ MathJax-Element-364 $ 的后验概率的估计值。

4. 令 $ MathJax-Element-365 $ ，其物理意义为：在序列 $ MathJax-Element-376 $ 中，第 $ MathJax-Element-417 $ 时刻的隐状态为 $ MathJax-Element-415 $ 的后验概率。

   令 $ MathJax-Element-369 $ ，其物理意义为：在序列 $ MathJax-Element-376 $ 中，第 $ MathJax-Element-417 $ 时刻的隐状态为 $ MathJax-Element-415 $ 、且第 $ MathJax-Element-373 $ 时刻的隐状态为 $ MathJax-Element-374 $ 的后验概率。

   则 M 步的估计值改写为：

   $ \pi_i=\frac{\sum_{s=1}^N P(i_1=i\mid \mathbf O=\mathbf O_s;\bar\lambda)}{N}=\frac{\sum_{s=1}^N\gamma_1^{(s)}(i)}{N}\\ a_{i,j}=\frac {\sum_{s=1}^N\sum_{t=1}^{T_s-1}P(i_t=i,i_{t+1}=j\mid \mathbf O=\mathbf O_s;\bar\lambda)}{ \sum_{s=1}^N\sum_{t=1}^{T_s-1}P(i_t=i\mid \mathbf O=\mathbf O_s;\bar\lambda)}=\frac {\sum_{s=1}^N\sum_{t=1}^{T_s-1}\xi_t^{(s)}(i,j)}{ \sum_{s=1}^N\sum_{t=1}^{T_s-1}\gamma_t^{(s)}(i)}\\ b_j(k)=\frac{ \sum_{s=1}^N\sum_{t=1}^{T_s}P(i_t=j,o_t=k\mid \mathbf O=\mathbf O_s;\bar\lambda)}{\sum_{s=1}^N\sum_{t=1}^{T_i}P(i_t=j\mid \mathbf O=\mathbf O_s;\bar\lambda)}=\frac{ \sum_{s=1}^N\sum_{t=1}^{T_s}\gamma_t^{(s)}(j)\mathbb I(o_t^{(s)}=k)}{\sum_{s=1}^N\sum_{t=1}^{T_i}\gamma_t^{(s)}(j)} $

   其中 $ MathJax-Element-375 $ 为示性函数，其意义为：当 $ MathJax-Element-376 $ 的第 $ MathJax-Element-417 $ 时刻为 $ MathJax-Element-378 $ 时，取值为 1；否则取值为 0 。

5. Baum-Welch算法：

   • 输入：观测数据 $ MathJax-Element-379 $

   • 输出：隐马尔可夫模型参数

   • 算法步骤：

     • 初始化： $ MathJax-Element-380 $ ，选取 $ MathJax-Element-381 $ ，得到模型 $ MathJax-Element-382 $

     • 迭代，迭代停止条件为：模型参数收敛。迭代过程为：

       • 求使得 Q 函数取极大值的参数：

       • 判断模型是否收敛。如果不收敛，则 $ MathJax-Element-383 $ ，继续迭代。

     • 最终得到模型 $ MathJax-Element-384 $ 。

2.3 预测问题

2.3.1 近似算法

1. 近似算法思想：在每个时刻 $ MathJax-Element-417 $ 选择在该时刻最有可能出现的状态 $ MathJax-Element-398 $ ，从而得到一个状态序列 $ MathJax-Element-426 $ ，然后将它作为预测的结果。

2. 近似算法：给定隐马尔可夫模型 $ MathJax-Element-419 $ ，观测序列 $ MathJax-Element-389 $ ，在时刻 $ MathJax-Element-417 $ 它处于状态 $ MathJax-Element-418 $ 的概率为：

   $ \gamma_t(i)=\frac{\alpha_t(i)\beta_t(i)}{P(\mathbf O;\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^{Q}\alpha_t(j)\beta_t(j)} $

   在时刻 $ MathJax-Element-414 $ 最可能的状态： $ MathJax-Element-393 $ 。

3. 近似算法的优点是：计算简单。

   近似算法的缺点是：不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际上不发生的部分。

   • 近似算法是局部最优（每个点最优），但是不是整体最优的。
   • 近似算法无法处理这种情况： 转移概率为 0 。因为近似算法没有考虑到状态之间的迁移。

2.3.2 维特比算法

1. 维特比算法用动态规划来求解隐马尔可夫模型预测问题。

   它用动态规划求解概率最大路径（最优路径），这时一条路径对应着一个状态序列。

2. 维特比算法思想：

   • 根据动态规划原理，最优路径具有这样的特性：如果最优路径在时刻 $ MathJax-Element-417 $ 通过结点 $ MathJax-Element-398 $ ， 则这一路径从结点 $ MathJax-Element-398 $ 到终点 $ MathJax-Element-407 $ 的部分路径，对于从 $ MathJax-Element-398 $ 到 $ MathJax-Element-407 $ 的所有可能路径来说，也必须是最优的。

     

   • 只需要从时刻 $ MathJax-Element-400 $ 开始，递推地计算从时刻 1 到时刻 $ MathJax-Element-417 $ 且时刻 $ MathJax-Element-417 $ 状态为 $ MathJax-Element-403 $ 的各条部分路径的最大概率（以及取最大概率的状态）。于是在时刻 $ MathJax-Element-404 $ 的最大概率即为最优路径的概率 $ MathJax-Element-405 $ ，最优路径的终结点 $ MathJax-Element-407 $ 也同时得到。

   • 之后为了找出最优路径的各个结点，从终结点 $ MathJax-Element-407 $ 开始，由后向前逐步求得结点 $ MathJax-Element-408 $ ，得到最优路径 $ MathJax-Element-426 $ 。

3. 定义在时刻 $ MathJax-Element-414 $ 状态为 $ MathJax-Element-415 $ 的所有单个路径 $ MathJax-Element-412 $ 中概率最大值为：

   $ \delta_t(i)=\max_{i_1,i_2,\cdots,i_{t-1}} P(i_t=i,i_{t-1},\cdots,i_1,o_t,\cdots,o_1;\lambda),\quad i=1,2,\cdots,Q $

   它就是算法导论中《动态规划》一章提到的“最优子结构”

   则根据定义，得到变量 $ MathJax-Element-413 $ 的递推公式：

   $ \delta_{t+1}(i)=\max_{i_1,i_2,\cdots,i_{t}} P(i_{t+1}=i,i_{t},\cdots,i_1,o_{t+1},\cdots,o_1;\lambda)=\max_{1 \le j \le Q} \delta_t(j)\times a_{j,i}\times b_i(o_{t+1})\\ i=1,2,\cdots,Q;t=1,2,\cdots,T-1 $

4. 定义在时刻 $ MathJax-Element-414 $ 状态为 $ MathJax-Element-415 $ 的所有单个路径中概率最大的路径的第 $ MathJax-Element-416 $ 个结点为：

   $ \Psi_t(i)=\arg\max_{1 \le j \le Q} \delta_{t-1}(j)a_{j,i} ,\quad i=1,2,\cdots,Q $

   它就是最优路径中，最后一个结点（其实就是时刻 $ MathJax-Element-417 $ 的 $ MathJax-Element-418 $ 结点） 的前一个结点。

   

5. 维特比算法：

   • 输入：

     • 隐马尔可夫模型 $ MathJax-Element-419 $
     • 观测序列 $ MathJax-Element-420 $

   • 输出：最优路径 $ MathJax-Element-426 $

   • 算法步骤：

     • 初始化：因为第一个结点的之前没有结点 ，所以有：

       $ \delta_1(i)=\pi_ib_i(o_1),\Psi_1(i)=0,\quad i=1,2,\cdots,Q $

     • 递推：对 $ MathJax-Element-422 $

       $ \delta_{t}(i)=\max_{1 \le j \le Q} \delta_{t-1}(j)a_{j,i}b_i(o_{t}),\quad i=1,2,\cdots,Q;t=1,2,\cdots,T\\ \Psi_t(i)=\arg\max_{1 \le j \le Q} \delta_{t-1}(j)a_{j,i}\ ,\quad i=1,2,\cdots,Q $

     • 终止： $ MathJax-Element-423 $ 。

     • 最优路径回溯：对 $ MathJax-Element-424 $ ： $ MathJax-Element-425 $ 。

     • 最优路径 $ MathJax-Element-426 $ 。