学习算法—预测模型参数$\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})\}$,而不是状态
求和函数求导
求解:$\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$求导
$\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$才成立