• Chapter 15 HMM模型

    1.1 定义

    隐马尔科夫模型：可用于标注问题，在语音识别、NLP、生物信息、模式识别等领域被实践证明是有效的算法。

    HMM是关于时序的概率模型，描述由一个隐藏的马尔科夫链生成不可观测的状态随机序列，再由各个状态生成观测随机序列的过程。(生成模型)

    隐马尔科夫模型随机生成的状态随机序列，称为状态序列；每个状态生成一个观测，由此产生的观测随机序列，称为观测序列。

    z_{1},z_{2}...z_{n+1}是主题，我们需要通过词来确定的对象。

    x_{1},x_{2}...x_{n+1}是词，我们所观察的对象。

    在z_{1},z_{2}不可观察的前提下，x_{1},z_{2}独立。如下图，将右侧部分看作一个整体，作为X’。因此就可以当作贝叶斯网络。当z_{1}不可观察时，x_{1},x'相互独立。

    1.2 HMM模型的确定

    HMM由初始概率分布\pi、状态转移概率分布A以及观测概率分布B确定。

    \lambda =(A,B,\pi )

    Q是所有可能的状态的集合；N是可能的状态数

    V是所有可能的观测的集合；M是可能的观测数

    Q=\left \{ q_{1},q_{2},...,q_{N}\right \}

    V=\left \{ v_{1},v_{2},...v_{M} \right \}

    参数分析：

    • I是长度为T的状态序列，O是对应的观测序列：

               I=\left \{ i_{1},i_{2}...,i_{T} \right \}，O=\left \{ o_{1},o_{2},...,o_{T} \right \}

    • 隐状态：A_{nxn}=\begin{pmatrix} a_{11}& a_{12} & ... & a_{1n}\\ a_{21}& a_{22} & ... & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & ...& a_{nn} \end{pmatrix}，其中a_{i1}+a_{i2}+...+a_{in}=1,i=1,2...n

    其中a_{ij}=P(i_{t+1}=q_{j}|i_{t}=q_{i})是在时刻t处于状态q_{i}的条件下时刻t+1转移到状态q_{i}的概率。

    ps: 隐状态必须是离散的。

    • B_{nxm}=\begin{pmatrix} b_{11} & b_{12} & b_{13} & ... &b_{1m} \\ b_{21}&b_{22} & b_{23} & ...& b_{2m}\\ \vdots &\vdots & \vdots & & \vdots \\ b_{n1}& b_{n2} &b_{n3} & ... & b_{nm} \end{pmatrix}

            可观测序列，值是连续或者离散的都可以。

            n——隐状态的个数   m——可观测的个数

            b_{ik}=P(o_{t}=v_{k}|i_{t}=q_{i})是在时刻t处于状态q_{i}的条件下生成观测v_{k}的概率。

            \pi _{i}=P(i_{1}=q_{i})是时刻t=1处于状态q_{i}的概率。

    • 总结：HMM由初始概率分布\pi（向量）、状态转移概率分布A（矩阵）以及观测概率分布B（矩阵）确定。\pi和A决定状态序列，B决定观测序列。因此，HMM可以用三元符号表示，称为HMM的三要素：\lambda =(A,B,\pi )

    1.3 HMM的两个基本性质

    （1）齐次假设：P(i_{t}|i_{t-1},o_{t-1},i_{t-2},o_{t-2}...i_{1},o_{1})=P(i_{t}|i_{t-1})

    （2）观测独立性假设：P(o_{t}|i_{T},o_{T},i_{T-1},...,i_{1},o_{1})=P(o_{t}|i_{t})

    1.4 HMM的实例

     问题：求解最终得到{红、白、红}的概率？

     设置各个参数如下：
    状态集合：Q={盒子1，盒子2，盒子3}

    观测集合：V={红，白}

    状态序列和观测序列的长度为：T=3+2=5

    初始概率分布：\pi=\begin{pmatrix} 0.2\\ 0.4\\ 0.4 \end{pmatrix}

    状态转移概率分布：A=\begin{bmatrix} 0.5&0.2 &0.3 \\ 0.3 &0.5 &0.2 \\ 0.2 &0.3 &0.5 \end{bmatrix}

    观测概率分布：B=\begin{bmatrix} 0.5 &0.5 \\ 0.4& 0.6\\ 0.7& 0.3 \end{bmatrix}

    求解：见1.6

    1.5 HMM的3个基本问题

    • 概率计算问题（重点）：前向-后向算法——动态规划

    给定模型\lambda =(A,B,\pi )和观测序列O=\left \{ o_{1},o_{2},...,o_{T} \right \}，计算模型\lambda下观测序列O出现的概率P(O|\lambda )。

    • 学习问题：Baum-Welch算法（状态未知）——EM

    已知观测序列O=\left \{ o_{1},o_{2},...,o_{T} \right \}，估计模型\lambda =(A,B,\pi )的参数，使得在该模型下观测序列P(O|\lambda )最大。

    • 预测问题：Viterbi算法——动态规划

    解码问题：已知模型\lambda =(A,B,\pi )和观测序列O=\left \{ o_{1},o_{2},...,o_{T} \right \}，求给定观测序列条件概率P(I|O,\lambda )最大的状态序列I。

    1.6 概率计算问题

    • 直接计算（暴力算法）

    按照概率公式，列举所有可能的长度为T的状态序列I=\left \{ i_{1},i_{2},...,i_{T} \right \},\，求各个状态序列I和观测序列O=\left \{ o_{1},o_{2},o_{3},...,o_{T} \right \}的联合概率P(O,I|\lambda )，然后对所有可能的状态序列求和，从而得到P(O|\lambda )。

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

     

    •  前向算法

    前向算法的定义：给定\lambda，定义到时刻t部分观测序列为o_{1},o_{2}...o_{t}，且状态为q_{i}的概率称为前向概率，记作：\alpha _{t}(i)=P(o_{1},o_{2},...,o_{t},i_{t}=q_{i}|\lambda )

    计算观测序列概率P(O|\lambda )：

    （1）初值：\alpha _{1}(i)=\pi _{i}b_{io_{1}}

    （2）递推：对于t=1,2,...,T-1，\alpha _{t+1}(i)=(\sum_{j=1}^{N}\alpha _{t}(j)a_{ji})b_{io_{t+1}}

    （3）最终：P(O|\lambda )=\sum_{i=1}^{N}\alpha _{T}(i)

    时间复杂度是O(N^{2}T)

    1.4实例可以通过前向算法求解：

     

    （1）计算初值

    \alpha _{1}(1)=\pi _{1}b_{1o_{1}}=0.2\times 0.5=0.1

    \alpha _{1}(2)=\pi _{2}b_{2o_{1}}=0.4\times 0.4=0.16

    \alpha _{1}(3)=\pi _{3}b_{3o_{1}}=0.4\times 0.7=0.28

    (2)递推

    \alpha _{2}(1)=(\sum_{j=1}^{N}\alpha _{1}(j)a_{j1})b_{1o_{2}}=(0.1\times 0.5+0.16\times 0.3+0.28\times 0.2 )=0.077

    同理：\alpha _{2}(2)=0.1104,\alpha _{2}(3)=0.0606

    \alpha _{3}(1)=0.04187,\alpha _{3}(2)=0.03551,\alpha _{3}(3)=0.05284

    （3）最终

    P(O|\lambda )=\sum_{i=1}^{3}\alpha _{3}(i)=0.04187+0.03551+0.05284=0.13022

    • 后向算法

    给定\lambda，定义到时刻t状态为qi的前提下，从t+1到T的部分观测时序为o_{t+1},o_{t+2},...,o_{T}的概率为后向概率，记作：\beta _{t}(i)=P(o_{t+1},o_{t+2},...,o_{T}|i_{t}=q_{i},\lambda )

    计算观测序列概率P(O|\lambda )：

    （1） 初值\beta _{T}(i)=1

    （2）递推，对于t=T-1,T-2,...,1，\beta _{t}(i)=\sum_{j=1}^{N}(a_{ij}b_{jo_{t+1}}\beta_{t+1} (j))

    （4）最终：P(O|\lambda )=\sum_{i=1}^{N}\pi _{i}b_{io_{1}}\beta _{1}(i)

    • 前向概率、后向概率的关系

    P(i_{t}=q_{i},O|\lambda )=P(O|i_{t}=q_{i},\lambda )P(i_{t}=q_{i}|\lambda ) =P(o_{1},...,o_{t},o_{t+1},...,o_{T}|i_{t}=q_{i},\lambda )P(i_{t}=q_{i}|\lambda ) =P(o_{1},...,o_{t}|i_{t}=q_{i},\lambda)P(o_{t+1},...,o_{T}|i_{t}=q_{i},\lambda)P(i_{t}=q_{i}|\lambda )=P(o_{1},...,o_{t},i_{t}=q_{i}|\lambda)P(o_{t+1},...,o_{T}|i_{t}=q_{i},\lambda)=\alpha_{t} (i)\beta _{t}(i)

    1.7 单个状态的概率

    求给定模型\lambda和观测O，在时刻t处于状态qi的概率：

    记作：\gamma _{t}(i)=P(i_{t}=q_{i}|O,\lambda )

    \gamma _{t}(i)=P(i_{t}=q_{i}|O,\lambda )=\frac{P(i_{t}=q_{i},O|\lambda )}{P(O|\lambda )}=\frac{\alpha_{t} (i)\beta _{t}(i)}{P(O|\lambda )}=\frac{\alpha_{t} (i)\beta _{t}(i)}{\sum_{i=1}^{N}\alpha_{t} (i)\beta _{t}(i)}

    \gamma的意义为：在每个时刻t选择在该时刻最有可能出现的状态i_{t}^{*}，从而得到一个状态序列

    I^{*}=\left \{ i_{1}^{*},i_{2}^{*},...,i_{T}^{*} \right \}将它作为预测的结果。

    例如：对于一句话“今天我吃了一个火龙果”，划分词是可能出现的状态有（begin,mid,end,single）

    若这么划分词：今天|我|吃|了|一个|火龙果。

    则：

    begin:“今”，“一”、“火”

    mid:“龙”

    end:“天”、“个”

    single:“我”、“吃”、“了”

    期望：在观测O下状态i出现的期望：\sum_{t=1}^{T}\gamma _{t}(i)

    1.8 两个状态的联合概率

    求给定模型\lambda和观测O，在时刻t处于状态qi的概率并且时刻t+1处于状态qi的概率：
    \zeta _{t}(i,j)=P(i_{t}=q_{i},i_{t+1}=q_{j}|O,\lambda )

    \zeta _{t}(i,j)=P(i_{t}=q_{i},i_{t+1}=q_{j}|O,\lambda )=\frac{P(i_{t}=q_{i},i_{t+1}=q_{j},O|\lambda )}{P(O|\lambda )}=\frac{P(i_{t}=q_{i},i_{t+1}=q_{j},O|\lambda )}{\sum_{i=1}^{N}\sum_{j=1}^{N}P(i_{t}=q_{i},i_{t+1}=q_{j},O|\lambda )}

    其中：P(i_{t}=q_{i},i_{t+1}=q_{j},O|\lambda )=\alpha _{t}(i)a_{ij}b_{jo_{t+1}}\beta _{t+1}(j )

    期望：在观测O下状态i转移到状态j的期望：\sum_{t=1}^{T-1}\zeta _{t}(i,j)

    1.9 学习算法

    若训练数据包括观测序列和状态序列，则HMM的学习非常简单，是监督学习；

    若训练数据只有观测序列，则HMM的学习需要使用EM算法，是非监督学习。

    （1）监督学习

    假设已经给定训练数据包括S个长度相同的观测序列和对应的状态序列\left \{ (O_{1},I_{1}),(O_{2},I_{2}),...,(O_{s},I_{s}) \right \}，那么可以直接利用Bernoulli大数定理的结论“频率的极限是概率”，给定HMM的参数估计。

    初始概率\widehat{\pi _{i}}=\frac{|q_{i}|}{\sum_{i}|q_{i}|}

    转移概率\widehat{a_{ij}}=\frac{|q_{ij}|}{\sum_{j=1}^{N}|q_{ij}|}

    观测概率\widehat{b_{ik}}=\frac{|s_{ik}|}{\sum_{k=1}^{M}|s_{ik}|}

    (2)非监督学习

    Baum-Welch算法：

    所有观测数据为O=(o_{1},o_{2},...,o_{T})，所有隐数据为I=(i_{1},i_{2},...,i_{T})，完全数据是(O,T)=(o_{1},o_{2},...,o_{T},i_{1},i_{2},...,i_{T})，完全数据的对数似然函数为lnP(I|O,\lambda )。

    假设\overline{\lambda }是HMM参数的当前估计值，\lambda为待求的参数。

    Q(\lambda ,\overline{\lambda })=\sum_{I}(lnP(O,I|\lambda ))P(I|O,\overline{\lambda } )=\sum_{I}(lnP(O,I|\lambda ))\frac{P(O,I|\lambda )}{P(O,\overline{\lambda })}

    EM过程：

    因为P(O,I|\lambda )=P(O|I,\lambda )P(I|\lambda )=\pi _{i_{1}}b_{i_{1}o_{1}}a_{i_{1}i_{2}}...a_{i_{T-1}i_{T}}b_{i_{T}o_{T}}

    所以Q(\lambda ,\overline{\lambda })=\sum_{I}(lnP(O,I|\lambda ))P(I|O,\overline{\lambda } )=\sum_{I}ln\pi _{i_{1}}P(O,I|\lambda )+\sum_{I}(\sum_{t=1}^{T-1}lna_{i_{t}i_{t+1}})P(O,I|\overline{\lambda })+\sum_{I}(\sum_{t=1}^{T}lnb_{i_{t}o_{t}})P(O,I|\overline{\lambda })

    拉格朗日乘子法：
    \sum_{i=1}^{N}(ln\pi _{i})P(O,i_{1}=i|\overline{\lambda} )+\gamma (\sum_{i=1}^{N}\pi _{i}-1)，其中\sum_{i=1}^{N}\pi _{i}=1

    先对\pi_{i}求偏导：

    P(O,i_{1}=i|\overline{\lambda })+\gamma \pi _{i}=0

    ∴    \sum_{i=1}^{T}P(O,i_{1}=i|\overline{\lambda })+\sum_{i=1}^{T}\gamma \pi _{i}=0

    ∴\gamma =-P(O|\overline{\lambda })

    ∴初始状态概率为\pi_{i}=\frac{P(O,i_{1}=i|\overline{\lambda })}{P(O|\overline{\lambda })}= \frac{P(O,i_{1}= i|\overline{\lambda })}{\sum_{i=1}^{N}P(O,i_{1}=i|\overline{\lambda })}=\gamma _{1}(i)

    转移概率和观测概率：

    1.10 Viterbi算法

    Viterbi算法实际是用动态规划解HMM预测问题，用DP求概率最大的路径（最优路径），这是一条路径对应一个状态序列。

    定义变量\delta _{t}(i)：在时刻t状态为i的所有路径中，概率的最大值。

    \delta _{t}(i)=\underset{i_{1},i_{2},...,i_{t-1}}{max}P(i_{t}=i,i_{t-1},...,i_{1},o_{t},...o_{1}|\lambda )

    递推：\delta _{1}(i)=\pi _{i}b_{io_{1}}

    \delta _{t+1}(i)=\underset{i_{1},i_{2},...,i_{t}}{max}P(i_{t+1}=i,i_{t},...,i_{1},o_{t+1},...o_{1}|\lambda )=\underset{1\leq j\geq N}{max}(\delta _{t}(j)a_{ji})b_{io_{t+1}}

    终止：P^{*}=\underset{1\leq i\leq N}{max}\delta _{T}(i)

    1.11 举例

     

     

     

     

  • 相关阅读:
    LeetCode_二分搜索_中等_2594.修车的最少时间
    5.10.WebRTC接口宏
    DETR纯代码分享（三）coco_panoptic.py
    IB课程 EE怎么写？
    C++ Reference: Standard C++ Library reference: Containers: list: list: ~list
    CF1286E-Fedya the Potter Strikes Back【KMP,RMQ】
    Java项目：SSM校园共享自行车出租管理系统
    7.10 操作系统的启动
    paddleocr关闭log日志打印输出
    linux mysql5.7.25 主从复制_生产版本
  • 原文地址：https://blog.csdn.net/qwertyuiop0208/article/details/126224190