隐马尔可夫模型(二)

学习算法—预测模型参数$\lambda=(A,B,\pi)$

若知$\{(O_1,I_1),(O_2,I_2),\cdots,(O_S,I_S)\}$求$(A,B,\pi)$,用监督学习方法

若知$\{O_1,O_2,\cdots,O_S\}$求$(A,B,\pi)$,用非监督学习方法Baum-Welch算法

监督学习方法

通过转移状态与观测出现的频率来估算参数

但这样就需要人工标注,有时候代价过高

Baum-Welch算法

使用MLE,由于隐变量的存在,很难求,所以用EM算法来近似MLE

假定训练数据为$S$个长度为$T$的观测序列$\{O_1,O_2,\cdots,O_S\}$,不知其状态序列(隐变量)

目标:学习$\lambda=(A,B,\pi)$

需要用到上一篇的公式$\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^N_{j=1}\alpha_t(j)\beta_t(j)}$——①

$\epsilon_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^N_{i=1}\sum^N_{j=1}P(i_t=q_i,i_{t+1}=q_j,O|\lambda)}$——②

手推(键盘推O_O)Baum-Welch公式:

$P(O,I|\lambda)=P((\pi_{i_1} b_{i_1}(o_1)) (a_{i_1i_2}b_{i_2}(o_2)) \cdots(a_{i_{T-1}i_T}b_{i_T}(o_T))$

由$Q(\lambda,\hat \lambda)=\mathbb E_I(\log P(O,I|\lambda)|O,\hat \lambda)$

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

$=\sum_I \log P(O,I|\lambda)\frac{P(I,O|\hat \lambda)}{P(O|\hat \lambda)}$,由于$P(O|\hat \lambda)$为常数,可以省略掉

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

将$P(O,I|\lambda)$代入$Q$函数得:

$Q(\lambda,\hat \lambda)=\sum_I \log \pi_{i} P(O,I|\hat \lambda)+\sum_I\sum_{t=1}^{T-1}\log a_{i_ti_{t+1}}P(O,I|\hat \lambda)+\sum_I\sum_{t=1}^T\log b_{i_t}(o_t)P(O,I|\hat \lambda)$

将三个参数分布归到三个子项后,下面根据参数的需要对$P(O,I|\hat \lambda)$中的$I$变量进行对应的逆边缘化,注意时间和状态空间的关系,是独立的

$=\sum_{i=1}^N \log \pi_i P(O,i_1=i|\hat \lambda)$——③

$+\sum_{i=1}^N\sum_{j=1}^N\sum_{t=1}^{T-1}\log a_{ij}P(O,i_t=i,i_{t+1}=j|\hat \lambda)$——④ 时间连续,但状态空间是任意组合的

$+\sum_j^N\sum_{t=1}^T\log b_j(o_t)P(O,i_t=j|\hat \lambda)$——⑤

由于$\lambda=(A,B,\pi)$中的三个参数变量都相互独立且求得的$Q$的三个子式只包含一个独立的变量,于是

$\max_{A,B,\pi}Q=\{\max_A ④,\max_B ⑤,\max_ \pi ③\}$



于是用拉格日朗子乘数法分别对各变量求0偏导(否则算出负概率)

Ⅰ.对于$\pi_i :\sum_{i=1}^N \log \pi_i P(O,i_1=i|\hat \lambda)$ (③式)

$\sum_{i=1}^N \pi_i=1$ $\pi$是初始概率向量,表初始的时候各状态的概率,别搞混了

$\therefore \mathbb L=\sum_{i=1}^N \log \pi_i P(O,i_1=i|\hat \lambda)+\gamma(\sum_{i=1}^N \pi_i-1)$

令$\frac{\partial \mathbb L}{\partial \pi_i}=0,\therefore \frac{\partial(\sum_{i=1}^N \log \pi_i P(O,i_1=i|\hat \lambda)+\gamma(\sum_{i=1}^N \pi_i-1))}{\partial \pi_i}=0$

$\therefore \frac{1}{\pi_i}P(O,i_1=i|\hat \lambda)+\gamma=0$ (这里容易求错,见下面的求和函数求导

$\therefore P(O,i_1=i|\hat \lambda)+\gamma\pi_i=0$ ——⑥

左右两边同时求和:$\sum_{i=1}^NP(O,i_1=i|\hat \lambda)+\sum_{i=1}^N\gamma\pi_i=0$ ,$I$被边缘化(求和可以使用更多信息以消去$\gamma$)

$\therefore P(O|\hat \lambda)+\gamma=0$

$\therefore \gamma=-P(O|\hat \lambda)$,代入回⑥得:

$P(O,i_1=i|\hat \lambda)-\pi_iP(O|\hat \lambda)=0$

$\therefore \pi_i=\frac{P(O,i_1=i|\hat \lambda)}{P(O|\hat \lambda)}=P(i_t=i_1|O,\lambda)$,由①得:$\pi_i=\gamma_1(i)$ ——⑦

Ⅱ.对于$a_{ij}:\sum_{i=1}^N\sum_{j=1}^N\sum_{t=1}^{T-1}\log a_{ij}P(O,i_t=i,i_{t+1}=j|\hat \lambda)$ (④式)

$\sum_j^Na_{ij}=1$

$\therefore \mathbb L=\sum_{i=1}^N\sum_{j=1}^N\sum_{t=1}^{T-1}\log a_{ij}P(O,i_t=i,i_{t+1}=j|\hat \lambda)+\gamma(\sum_j^Na_{ij}-1)$

令$\frac{\partial \mathbb L}{\partial a_{ij}}=0,\therefore \frac{\sum_{i=1}^N\sum_{j=1}^N\sum_{t=1}^{T-1}\log a_{ij}P(O,i_t=i,i_{t+1}=j|\hat \lambda)+(\sum_j^Na_{ij}-1)}{\partial a_{ij}}=0$

$\therefore \sum_{t=1}^{T-1}\frac{1}{a_{ij}}P(O,i_t=i,i_{t+1}=j|\hat \lambda)+\gamma =0$

$\therefore \sum_{t=1}^{T-1}P(O,i_t=i,i_{t+1}=j|\hat \lambda)+\gamma a_{ij}=0$

两边同时求和:$\sum_j^N\sum_{t=1}^{T-1}P(O,i_t=i,i_{t+1}=j|\hat \lambda)+\gamma \sum_j^Na_{ij}=0$

$\therefore\gamma=-\sum_{t=1}^{T-1}P(O,i_t=i|\hat \lambda)$,回代原式

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

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

由①②得:

$a_{ij}=\frac{\sum_{t=1}^{T-1}\epsilon_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}$ ——⑧

Ⅲ.对于$b_j(o_t):\sum_j^N\sum_{t=1}^T\log b_j(o_t)P(O,i_t=j|\hat \lambda)$ (⑤式)

注意这里有所不同,$b_j(k)$的观测空间为$(o_1,o_2,\cdots,o_M)$。约束条件为$\sum_{k=1}^Mb_j(k)=1$

$\mathbb L=\sum_j^N\sum_{t=1}^T\log b_j(o_t)P(O,i_t=j|\hat \lambda)+\gamma(\sum_{k=1}^Mb_j(k)-1)$

令$\frac{\partial \mathbb L}{\partial b_j(k)}=0,\therefore \frac{\partial(\sum_j^N\sum_{t=1}^T\log b_j(o_t)P(O,i_t=j|\hat \lambda)+\gamma(\sum_{k=1}^Mb_j(k)-1)}{\partial b_j(k)}=0$

仅在$o_t=v_k$的时候$(b_j(o_t)=b_j(k))$,$\frac{\partial b_j(o_t)}{\partial b_j(k)}≠0$,以$I(o_t=v_k)$表示,$I(o_t=v_k)=1,I(o_t≠v_k)=0$

$\therefore \sum_{t=1}^T\frac{1}{b_j(o_t)}P(O,i_t=j|\hat \lambda)I(o_t=v_k)+\gamma =0$

$\therefore \sum_{t=1}^TP(O,i_t=j|\hat \lambda)I(o_t=v_k)+\gamma b_j(k)=0$

左右两边同时求和$\therefore \sum_{k=1}^M\sum_{t=1}^TP(O,i_t=j|\hat \lambda)I(o_t=v_k)+\gamma \sum_{k=1}^Mb_j(k)=0$

$\therefore \sum_{k=1}^M\sum_{t=1}^TP(O,i_t=j|\hat \lambda)I(o_t=v_k)+\gamma =0$

对这个式子进行化简,其等价于:$\sum_{t=1}^TP(O,i_t=j|\hat \lambda)+\gamma=0$ (有疑问)

$\therefore \gamma=-\sum_{t=1}^TP(O,i_t=j|\hat \lambda)$,回代

$\sum_{t=1}^TP(O,i_t=j|\hat \lambda)I(o_t=v_k)-\sum_{t=1}^TP(O,i_t=j|\hat \lambda)b_j(k)=0$

$\therefore b_j(k)=\frac{\sum_{t=1}^TP(O,i_t=j|\hat \lambda)I(o_t=v_k)}{\sum_{t=1}^TP(O,i_t=j|\hat \lambda)}$,由①得

$b_j(k)=\frac{\sum_{t=1,o_t=v_k}^T \gamma_t(j)}{\sum_{t=1}^T \gamma_t(j)}$ ——⑨


综上所述:$\frac{\partial Q}{\partial \pi_i}=⑦,\frac{\partial Q}{\partial a_{ij}}=⑧,\frac{\partial Q}{\partial b_j(k)}=⑨$

于是可以写出Baum-Welch算法:(仅对一个观测序列$O∈\{O_1,O_2,\dots,O_S\}$)

输入观测数据$O=(o_1,o_2,\dots,o_n)$,求$\lambda=(A,B,\pi)$

初始化:对$n=0$,选取$a_{ij}^{(0)},b_j(k)^{(0)},\pi_i^{(0)}$,得到模型$\lambda^{(0)}=(A^{(0)},B^{(0)},\pi^{(0)})$

递推:

(每一个参数矩阵的中要计算出多个上述三式子(所有$i,j$情况)才能得到新迭代的模型参数)

其中各值按观测$O=(o_1,o_2,\dots,o_n)$和模型$\lambda^{(n)}=(A^{(n)},B^{(n)},\pi^{(n)})$计算

最终得到模型参数$\lambda^{(n+1)}=(A^{(n+1)},B^{(n+1)},\pi^{(n+1)})$

预测算法—预测序列状态$I=\arg_I\max\{P(I|O,\lambda)\}$

近似算法

思想:选出在每一个时刻最有可能出现的状态来构成状态序列,用前面正反向算法推导出的单独概率公式求解

由在$t$时刻处于状态$q_i$的概率公式:$\gamma_t(i)=P(i_t=q_i|O,\lambda)=\frac{\alpha_t(i)\beta_t(i)}{\sum^N_{j=1}\alpha_t(j)\beta_t(j)}$

在每一时刻$t$最有可能的状态$i^*_t=\arg\max_{1≤i≤N}[\gamma_t(i)],t=1,2,\dots,T$(计算出当前$t$下哪个$i$使得$\gamma_t(i)$最大)

以此得到状态序列$I^{}=(i^{}_1,i^{}_2,\dots,i^{}_T)$

但存在问题:可能存在$\gamma_t(i)=0$也就是情况不发生的情况,那么该公式就会失效了

但尽管如此近似算法依然是有用的

维比特算法

动态规划,类似传统的Dijkstra算法,本文不细展开了,略

需要注意的就是递推公式的时候,概率最大化的是观测概率也就是$\max\{\delta_i(t)a_{ij}b_j(o_{t+1})\}$,而不是状态

求和函数求导

  1. 求解:$\frac{\partial(\sum_{i=1}^N\log\pi_i)}{\partial\pi_i}$

    将$\sum_{i=1}^N\log\pi_i$展开:

    $\sum_{i=1}^N\log\pi_i=\log \pi_1+\log \pi_2+\cdots+\log \pi_N$

    $\therefore \frac{\partial(\sum_{i=1}^N\log\pi_i)}{\partial\pi_i}=\frac{\partial(\log \pi_1+\log \pi_2+\cdots+\log \pi_N)}{\partial \pi_i}$

    若$i=1$,则$\frac{\partial(\log \pi_1+\log \pi_2+\cdots+\log \pi_N)}{\partial\pi_1}=\frac{1}{\pi_1}$

    若$i=2$,则$\frac{\partial(\log \pi_1+\log \pi_2+\cdots+\log \pi_N)}{\partial\pi_2}=\frac{1}{\pi_2}$

    若$i=i$,则$\frac{\partial(\log \pi_1+\log \pi_2+\cdots+\log \pi_N)}{\partial\pi_i}=\frac{1}{\pi_i}$

    $\therefore \frac{\partial(\sum_{i=1}^N\log\pi_i)}{\partial\pi_i}=\frac{1}{\pi_i}$

    同理$\frac{\partial(\sum_{i=1}^N\pi_i)}{\partial\pi_i}=1$

    一次只能对一个变量求导,其余视为不相关常数

    理解对$\pi_i$求导的意义,即无论被求导式为何,对其结果对$\pi_i$求导

  2. $\sum_y×1=||y||_0×1$

    就像$\sum_{i=1}^nm=nm,\sum_{y}^n×1=n$一样,求和的参数决定了循环求和次数

    于是:$\sum_{y}d=\sum_{x,y}d$,只有当$||y||_0=||(x,y)||_0$才成立