统计学习笔记2: HMM
目录
2. E步：求Q函数\( Q(\lambda, \bar \lambda) \)
隐马尔可夫模型（hidden Markov model, HMM）
属于生成式模型: 隐藏的马尔可夫链生成观测序列. (CRF判别式)
用于标注问题
| 序列标注可参考: https://zhuanlan.zhihu.com/p/54574188 序列标注 对若干时间或空间上有关联的样本进行“批量分类”的任务 对于分词任务, 已知文本\( x=\left(x_{1}, x_{2}, \ldots, x_{\tau}, \ldots, x_{T}\right) \), 其中 \( x_t \)表示第t个字符,T是文本的长度(即字符个数) 如“我是中国人。”, T=6, \( \mathrm{x}_{1}=^{\prime}\text { 我 }^{\prime}, \mathrm{x}_{2}=^{\prime} \text { 是 }^{\prime}, \mathrm{x}_{3}=^{\prime} \text { 中 }^{\prime}, \mathrm{x}_{4}=^{\prime} \text { 国 }^{\prime}, \mathrm{x}_{5}=^{\prime} \text { 人 }^{\prime}, \mathrm{x}_{6}=^{\prime} \text { 。}^{\prime} \) (分词任务需要考虑标点符号) 用特定的符号进行标注:
该句字符类型: y=(S,S,B,M,E,S) 对应分词结果:“我/是/中国人/。” 分词任务->序列标注(时间关联的样本批量)分类任务, 即判断每个字符是(S,B,M,E)中的哪一类. |
基本概念
HMM的定义
隐藏的马尔可夫链--生成->不可观测的状态随机序列（state sequence）--生成->观测序列（observation sequence）
1个状态->1个观测, 观测值之间相互独立
HMM三要素
初始概率分布、状态转移概率分布以及观测概率分布
λ=(A, B, π)
符号定义
| 状态(state)的集合(值域) | $$ Q = \{q_1,q_2,...,q_N\} $$ |
| 观测(observation)的集合(定义域) | $$ V =\{v_1,v_2,...v_M\} $$ |
| 状态数 | $$ N $$ |
| 观测数 | $$ M $$ |
| 状态序列 | $$ I = \{i_1,i_2,...,i_T\}, i_t\in Q$$ |
| 对应的观测序列 | $$ O =\{o_1,o_2,...o_T\}, o_t\in V $$ |
| 序列长度 | $$ T $$ |
| 状态转移矩阵A: qi->qj的概率 (行号为原状态, 列号为新状态) | $$ A=\Big [a_{ij}\Big ]_{N \times N} , a_{ij} = P(i_{t+1} = q_j | i_t= q_i) $$ |
| 观测概率矩阵: qi->vk的概率 (行号为状态, 列号为观测) | $$ B = \Big [b_j(k) \Big ]_{N \times M}, b_j(k) = P(o_t = v_k | i_t= q_j) $$ |
| 状态初始概率向量: t=1时, qi的概率 | $$ \pi = \Big [ \pi(i)\Big ]_N \; 其中 \;\pi(i) = P(i_1 = q_i) $$ |
初始状态π+转移A->状态序列I
I+观测B->观测序列
HMM的两个基本假设
1） 齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态
$$ P\left(i_{t} \mid i_{t-1}, o_{t-1}, \cdots, i_{1}, o_{1}\right)=P\left(i_{t} \mid i_{t-1}\right), \quad t=1,2, \cdots, T $$
2） 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态
$$ P\left(o_{t} \mid i_{T}, o_{T}, i_{T-1}, o_{T-1}, \cdots, i_{t+1}, o_{t+1}, i_{t}, i_{t-1}, o_{t-1}, \cdots, i_{1}, o_{1}\right)=P\left(o_{t} \mid i_{t}\right) $$
例子
已知有4个盒子
即状态集合Q:
$$ Q＝\{盒子1,盒子2,盒子3,盒子4\}，N＝4 $$
每个盒子里都有红色和白色两种球
即观测集合V:
$$ V＝\{红,白\}，M＝2 $$
盒子里球的数量分别是
| 盒子 | 1 | 2 | 3 | 4 |
| 红球数 | 5 | 3 | 6 | 8 |
| 白球数 | 5 | 7 | 4 | 2 |
即观测概率矩阵B:
$$ B=\left[\begin{array}{ccc} 0.5 & 0.5 \\ 0.3 & 0.7 \\ 0.6 & 0.4 \\ 0.8 & 0.2 \end{array}\right] $$
开始(第一次抽球)，从4个盒子里以等概率随机选取1个盒子，从这个盒子里随机抽出1个球，记录其颜色后，放回.
即初始状态向量π:
$$ \pi=(0.25,0.25,0.25,0.25)^{\mathrm{T}} $$
每次抽球后, 从当前盒子随机转移到下一个盒子，规则是：如果当前盒子是盒子1，那么下一盒子一定是盒子2，如果当前是盒子2或3，那么分别以概率0.4和0.6转移到左边或右边的盒子，如果当前是盒子4，那么各以0.5的概率停留在盒子4或转移到盒子3.
即状态转移矩阵A:
$$ A=\left[\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0.4 & 0 & 0.6 & 0 \\ 0 & 0.4 & 0 & 0.6 \\ 0 & 0 & 0.5 & 0.5 \end{array}\right] \\ $$
重复进行5次:
即序列长度T=5.
得到球的颜色的观测序列：
$$ O＝\{红,红,白,白,红\} $$
观测序列的生成过程
(和抽球类似)
输入: HMM的模型λ=(A, B, π),观测序列的长度T;
输出: 观测序列O={o1,o2,...oT}
1）按照初始状态分布π生成隐藏状态\( i_1 \)
2) 令t=1
a. 按照状态\( i_t \)的观测概率分布\( b_{i_t}(k) \)生成观察状态\( o_t \)
b. 按照状态\( i_t \)的状态转移概率分布\( a_{i_t i_{t+1}} \)产生隐藏状态\( i_{t+1} \)
c. 令t++, 如果t<T, 转步a; 否则终止. 得到的ot构成O={o1,o2,...oT}.
HMM的3个基本问题
经常需要求解的3个基本问题：
（1）概率计算问题
给定模型λ=(A, B, π)和观测序列O. 计算在模型λ下观测序列O出现的概率P(O|λ)
（2）学习问题
已知观测序列O, 估计模型λ=(A, B, π)参数. 目标是最大化(问题1的概率) P(O|λ)
(极大似然估计+EM算法)
（3）预测/解码（decoding）问题
给定模型λ和观测序列O下，求最可能出现的对应的状态序列I. (即P(I|O,λ))
(维比特算法)
概率计算算法
直接计算法
时间复杂度: \( O(TN^T) \)
求所有可能的状态序列I与观测序列O联合概率P(O，I|λ)，然后对所有可能状态序列求和，得到P(O|λ)
| 根据联合概率与边缘概率的关系 $$ P(X=a)=\sum_{b} P(X=a,Y=b) \\ \Rightarrow P(O|λ)=\sum_{I}P(O，I|λ) $$ 参考: https://blog.csdn.net/tick_tock97/article/details/79885868 |
要求P(O|λ)首先要求联合概率P(O，I|λ), 根据联合概率、边缘概率与条件概率之间的关系:
| $$ P(X=a|Y=b)=\frac{P(X=a,Y=b)}{P(Y=b)}\\ \Rightarrow P(O,I|\lambda) = P(I|\lambda)P(O|I, \lambda) $$ |
分解得到的两项分别计算
已知模型, 得到状态序列的概率(初始状态π&转移A->状态序列I):
$$ P(I|\lambda) = \pi_{i_1} a_{i_1i_2} a_{i_2i_3}... a_{i_{T-1}\;\;i_T} $$
已知模型π和状态I, 得到观测序列的概率(每个状态对应的观测概率):
$$ P(O|I, \lambda) = b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T) $$
两项分别带入, 可得联合概率P(O，I|λ):
$$ P(O,I|\lambda) = P(I|\lambda)P(O|I, \lambda) = \pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}\;\;i_T}b_{i_T}(o_T) $$
联合概率求和得边缘概率:
$$ P(O|\lambda) = \sum\limits_{I}P(O,I|\lambda) \\= \sum\limits_{i_1,i_2,...i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}\;\;i_T}b_{i_T}(o_T) $$
前向算法
时间复杂度: \( O(TN^2) \)
前向概率定义
给定HMM模型λ ，到时刻t时, 出现观测序列{o1,o2,…,ot}且第t个状态为qi的概率
$$ \alpha_t(i) = P(o_1,o_2,...o_t, i_t =q_i | \lambda) $$
观测序列概率P(O|λ)的前向算法(算法10.2)
输入：HMM模型λ=(A,B, π)，观测序列O=(o1,o2,...oT)
输出：观测序列概率P(O|λ)
1) 初始状态(t=1)的各个隐藏状态前向概率(t=1时的观测o1已经给定)：
$$ \alpha_1(i) = \pi_ib_i(o_1),\; i=1,2,...N $$
2) 递推时刻2,3,...T时刻的前向概率：
$$ \alpha_{t+1}(i) = \Big[\sum\limits_{j=1}^N\alpha_t(j)a_{ji}\Big]b_i(o_{t+1}),\; i=1,2,...N $$
3) 最终结果(时刻t=T)
$$ P(O|\lambda) = \sum\limits_{i=1}^N\alpha_T(i) $$
即对所有状态qi的情况求和
$$ \alpha_{T}(i)=P\left(o_{1}, o_{2}, \cdots, o_{T}, i_{T}=q_{i} \mid \lambda\right)\\ \Rightarrow \sum\limits_{i=1}^N\alpha_T(i)= \sum\limits_{i=1}^N P\left(O, i_{T}=q_{i} \mid \lambda\right) $$
前向算法减少计算量的原因
利用了状态序列的路径结构进行递推.
直接计算法:
前向算法:
讲每层交汇处的概率值存为α, 可以复用.
例子
| 盒子和球模型 | λ=(A, B, π), |
| 状态集合 (可以从哪些盒中抽) | Q={1，2，3}，N=3 |
| 观测集合 (可以抽到哪种球) | V={红，白}，M=2 |
| 状态转移矩阵 (下一个盒是该盒的概率, 如a12是从第一个盒转移到第二个盒) | $$ A = \left( \begin{array} {ccc} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 &0.5 \end{array} \right) $$ |
| 概率分布矩阵 (从该盒抽到每种球的概率) | $$ B = \left( \begin{array} {ccc} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{array} \right) $$ |
| 初始状态向量 (第一次可能是哪个盒) | $$ \pi = (0.2,0.4,0.4)^T $$ |
| 观测序列 (最后抽的结果) | O={红，白，红} |
| 观测序列和状态序列的长度 | T=3. |
前向算法计算观测序列概率P(O|λ)
按照算法10.2
输入模型λ=(A, B, π), 观测序列O={红，白，红}.
(1)初值α1:
已知第一次拿到红球(观测), 从该盒拿(状态)的概率分别为
| 第一次从盒1拿到红球 | $$ \alpha_1(1) = \pi_1b_1(o_1) = 0.2 \times 0.5 = 0.1 $$ |
| 第一次从盒2拿到红球 | $$ \alpha_1(2) = \pi_2b_2(o_1) = 0.4 \times 0.4 = 0.16 $$ |
| 第一次从盒3拿到红球 | $$ \alpha_1(3) = \pi_3b_3(o_1) = 0.4 \times 0.7 = 0.28 $$ |
(2)递推αt:
已知第二次白球(观测)，第二次从盒1拿(状态)概率为
从盒1/2/3 转到盒i*从盒i抽到白球
| 第二次从盒1拿到白球 | $$ \alpha_2(1) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i1}\Big]b_1(o_2) = [0.1*0.5+0.16*0.3+0.28*0.2 ] \times 0.5 = 0.077 $$ |
| 第二次从盒2拿到白球 | $$ \alpha_2(2) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i2}\Big]b_2(o_2) = [0.1*0.2+0.16*0.5+0.28*0.3 ] \times 0.6 = 0.1104 $$ |
| 第二次从盒3拿到白球 | $$ \alpha_2(3) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i3}\Big]b_3(o_2) = [0.1*0.3+0.16*0.2+0.28*0.5 ] \times 0.3 = 0.0606 $$ |
递推第三次的前向概率, 同理得:
$$ \alpha_3(1) =0.04187 \\ \alpha_3(2) =0.03551 \\ \alpha_3(3) =0.05284 $$
(3)终止
$$ P(O|\lambda) = \sum\limits_{i=1}^3\alpha_3(i) = 0.13022 $$
后向算法
后向概率定义
给定HMM模型λ ，在时刻t之后, 出现观测序列{ot+1,ot+2,…,oT}且第t个状态为qi的概率
$$ \beta_t(i) = P(o_{t+1},o_{t+2},...o_T| i_t =q_i , \lambda) $$
观测序列概率P(O|λ)的后向算法(算法10.3)
输入：HMM模型λ=(A,B, π)，观测序列O=(o1,o2,...oT)
输出：观测序列概率P(O|λ)
1) 最初时刻(t=T)的各个隐藏状态后向概率(规定为1, 与前向概率的初始不同)：
$$ \beta_T(i) = 1,\; i=1,2,...N $$
2) 递推时刻T-1, T-2,...1时刻的后向概率：
βt=P(时刻t+1之后的观测序列为ot+1,ot+2,…,oT|在时刻t状态为qi)
$$ \beta_{t}(i) = \sum\limits_{j=1}^{N}a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\; i=1,2,...N $$
3) 最终结果(时刻t=1)：
$$ P(O|\lambda) = \sum\limits_{i=1}^N\pi_ib_i(o_1)\beta_1(i) $$
前向后向算法
(forward-backward algorithm）
一些需要用到的概率.
1）给定模型λ和观测序列O,在时刻t处于状态qi的概率
定义这个概率为符号γ:
根据联合概率、边缘概率与条件概率之间的关系
$$ \gamma_t(i) = P(i_t = q_i | O,\lambda) = \frac{P(i_t = q_i ,O|\lambda)}{P(O|\lambda)} $$
代入前向概率和后向概率的定义
| 前向概率: 给定HMM模型λ ，到时刻t时, 出现观测序列{o1,o2,…,ot}且第t个状态为qi的概率 $$ \alpha_t(i) = P(o_1,o_2,...o_t, i_t =q_i | \lambda) $$ 后向概率: 给定HMM模型λ ，在时刻t之后, 出现观测序列{ot+1,ot+2,…,oT}且第t个状态为qi的概率 $$ \beta_t(i) = P(o_{t+1},o_{t+2},...o_T| i_t =q_i , \lambda) $$ |
即分子可化为两概率相乘, 分母可根据联合概率与边缘概率关系的公式化为分子的形式:
$$ P(i_t = q_i ,O|\lambda) = \alpha_t(i)\beta_t(i)\\ \gamma_t(i) = \frac{ \alpha_t(i)\beta_t(i)}{\sum\limits_{j=1}^N \alpha_t(j)\beta_t(j)} $$
2）给定模型λ和观测序列O,在时刻t处于状态qi，且时刻t+1处于状态qj的概率
定义这个概率为符号ξ:
类似地, 根据联合概率、边缘概率与条件概率之间的关系
$$ \xi_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)} $$
分母可根据联合概率与边缘概率关系的公式, 化为与分子相同形式的累加. 因为这个分子每次固定两个时刻的状态\( i_t, i_{t+1} \) , 所以分母也要分布对两个时刻的状态q累加:
$$ \xi_t(i,j) = \frac{\alpha_t(i) a_{ij}b_j(o_{t+1}) \beta_{t+1}(j) }{\sum\limits_{r=1}^N\sum\limits_{s=1}^N \alpha_t(r)a_{rs}b_s(o_{t+1}) \beta_{t+1}(s)} $$
接下来代入前向概率与后向概率:
$$ P(i_t = q_i, i_{t+1}=q_j , O|\lambda) = \alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j) $$
分母按这个形式每项带入求和, 得到的公式也就是观测序列概率P(O|λ)的一般计算公式.
$$ P(O|\lambda) = \sum\limits_{r=1}^N\sum\limits_{s=1}^N\alpha_t(r)a_{rs}b_s(o_{t+1})\beta_{t+1}(s) $$
代入分子分母, 即得到概率ξ:
$$ \xi_t(i,j) = \frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum\limits_{r=1}^N\sum\limits_{s=1}^N\alpha_t(r)a_{rs}b_s(o_{t+1})\beta_{t+1}(s)} $$
3) 将γt(i)和ξt(i,j)在各个时刻t求和，得到几个求解HMM模型λ的参数需要使用的期望值:
| 在观测序列O下状态i出现的期望值 | $$ \sum\limits_{t=1}^T\gamma_t(i) $$ |
| 在观测序列O下由状态i转移的期望值 (由状态i转移, 下一个状态不需要是状态I, 所以最后T时刻的γT不需要) | $$ \sum\limits_{t=1}^{T-1}\gamma_t(i) $$ |
| 在观测序列O下由状态i转移到状态j的期望值 (由状态i转移到状态j, 状态i是t时刻, 状态j是t+1时刻, 所以最后T时刻的ξT不需要) | $$ \sum\limits_{t=1}^{T-1}\xi_t(i,j) $$ |
学习算法
模型学习, 也就是求解模型参数. 根据状态序列的已知和未知, 分为监督学习(已知)和无监督学习(未知).
监督学习
极大似然估计法求模型参数
已知样本:
$$ \{(O_1, I_1), (O_2, I_2), ...(O_S, I_S)\} $$
其中O为观测序列, I为状态序列, 样本个数为S.
λ=(A, B, π), 分别求解A, B, π三个参数.
求A
根据频数, 估计转移概率aij
Aij为从状态qi转移到qj的频率计数. 分母为从qi转移到所有状态的频数和.
$$ A = \Big[a_{ij}\Big], \;其中a_{ij} = \frac{A_{ij}}{\sum\limits_{s=1}^{N}A_{is}} $$
求B
根据频数, 估计观测概率bj(k)
Bjk为样本隐藏状态为qj且观测状态为vk的频率计数, 分母为状态qj所有观测的频数和
$$ B= \Big[b_{j}(k)\Big], \;其中b_{j}(k) = \frac{B_{jk}}{\sum\limits_{s=1}^{M}B_{js}} $$
求π
根据频数, 估计初始状态概率πi
C(i)为所有样本中初始状态为qi的频率计数, 分母为所有状态出现在初始的频数和
$$ \pi(i) = \frac{C(i)}{\sum\limits_{s=1}^{N}C(s)} $$
无监督学习
训练数据{O1,O2,…,OS}
其中包含S个样本, 每个样本只有观测序列O(长度为T), 没有状态序列I.
目标: 学习模型参数λ=(A, B, π)
学习方法: EM算法(即Baum-Welch)估计\( \bar \lambda \)
观测序列的生成式模型
观测序列O->可观测变量，状态序列I->隐藏变量, HMM->含有隐变量的概率模型
(与直接计算法处的分解方法相同)
$$ \begin{aligned}P(O|\lambda) & & \\= \sum\limits_{I}P(O,I|\lambda) & &根据 P(X)=\sum_{Y} P(X,Y) \\ =\sum\limits_{I}P(O|I, \lambda) P(I|\lambda) & & 根据P(X|Y)=\frac{P(X,Y)}{P(Y)}\end{aligned} $$
EM算法分为3步
1. 确定完全数据的对数似然
观测序列O->可观测变量，状态序列I->隐藏变量
可观测变量O＝(o1，o2,…,oT)，隐藏变量I＝(i1，i2,…,iT)，完全数据(O,I)＝(o1，o2,…,oT,i1，i2,…,iT)
完全数据的对数似然函数:
$$ \log P(O,I|\lambda) $$
2. E步：求Q函数\( Q(\lambda, \bar \lambda) \)
E步求出Q函数, 按照Q函数的定义: 完全数据的对数似然logP(O,I|λ)关于给定观测O和当前估计参数\( \bar \lambda \)下对隐变量I的条件概率\( P(I|O,\bar \lambda) \)的期望
$$ Q(\lambda, \overline{\lambda}) = \sum\limits_{I}logP(O,I|\lambda)P(I|O,\overline{\lambda}) \\ =\sum\limits_{I}logP(O,I|\lambda)\frac{P(O,I|\overline{\lambda})}{P(O|\overline{\lambda})}\\ \mathop\Longrightarrow\limits^{\frac{1}{P(O|\overline{\lambda})}对\lambda为常数,忽略}\sum\limits_{I}logP(O,I|\lambda)P(O,I|\overline{\lambda})$$
| 其中完全数据P(O, I | λ)可以根据估计参数计算: $$ P(O, I \mid \lambda)=\pi_{i_{1}} b_{i_{1}}\left(o_{1}\right) a_{i_{1} i_{2}} b_{i_{2}}\left(o_{2}\right) \cdots a_{i_{T-1} i_{T}} b_{i_{T}}\left(o_{T}\right) $$ |
将上式代入原式log中可化连乘为累加, 整理将相同类型参数放在一起(这样做极大化的时候, 可以单独对其中一个求和项做极大化) 得:
$$ \begin{aligned} Q(\lambda, \bar{\lambda})=& \sum_{I} \log \pi_{i_{1}} P(O, I \mid \bar{\lambda})+ \sum_{I}\left( \sum_{t=1}^{T-1} \log a_{i_{t} i_{t+1}}\right) P(O, I \mid \bar{\lambda})+\\ & \sum_{I}\left(\sum_{t=1}^{T} \log b_{i_{t}}\left(o_{t}\right)\right) P(O, I \mid \bar{\lambda}) \end{aligned} $$
3. M步：求模型参数, 使极大化这个期望, 即Q函数.
目标:
$$ \overline{\lambda} = \arg\max_{\lambda}\sum\limits_{I}P(I|O,\overline{\lambda})\log P(O,I|\lambda)\\=\arg\max_{\lambda}\sum\limits_{I}\log P(O,I|\lambda)P(O,I|\overline{\lambda}) $$
因为三个参数A, B, π分别出现在其中一项, 将上一步得到的3个求和项分别极大化
1)第1项对π求该式极大
$$ \overline{\pi_i} = arg\;\max_{\pi_{i_1}} \sum\limits_{I}P(O,I|\overline{\lambda})log\pi_{i_1} \\ \mathop\Longrightarrow\limits^{i_1 =i}\arg\;\max_{\pi_{i}} \sum\limits_{i=1}^NP(O,i_1 =i|\overline{\lambda})log\pi_{i} \\ s.t. \sum\limits_{i=1}^N π_i=1$$
| 求有约束的极值, 用拉格朗日乘子法. 拉格朗日函数为: $$ arg\;\max_{\pi_{i}}\sum\limits_{i=1}^NP(O,i_1 =i|\overline{\lambda})log\pi_{i} + \gamma(\sum\limits_{i=1}^N\pi_i -1) $$ 其中γ为拉格朗日乘子. 上式对πi求偏导数并令结果为0 $$ \frac{\partial\sum\limits_{i=1}^NP(O,i_1 =i|\overline{\lambda})log\pi_{i} + \gamma(\sum\limits_{i=1}^N\pi_i -1)}{\partial\pi_i}=0\\ \Rightarrow P(O,i_1=i|\overline{\lambda}) + \gamma\pi_i = 0 $$ 对i求和得γ： $$ \sum_{i=1}^N (P(O,i_1=i|\overline{\lambda}) + \gamma\pi_i )= 0 \\ \Rightarrow P(O|\overline{\lambda}) + \gamma = 0 \\ \Rightarrow \gamma = -P(O|\overline{\lambda})$$ 所得γ代回到求偏导结果: $$ \begin{aligned} \left\{\begin{array}{ll}P(O,i_1=i|\overline{\lambda}) + \gamma\pi_i = 0 \\ \gamma = -P(O|\overline{\lambda}) \end{array}\right. \end{aligned} \\ \Rightarrow \pi_i =\frac{P(O,i_1 =i|\overline{\lambda})}{P(O|\overline{\lambda})} $$ |
即求得π的迭代公式
$$ \pi_i =\frac{P(O,i_1 =i|\overline{\lambda})}{P(O|\overline{\lambda})} $$
| 这与前向后向算法一节得到的第一个常用概率相同 给定模型λ和观测序列O,在时刻t处于状态qi的概率 $$ \gamma_t(i) = P(i_t = q_i | O,\lambda) = \frac{P(i_t = q_i ,O|\lambda)}{P(O|\lambda)} $$ |
2)第2项对a求该式极大
同理, 对第2项整理, 代入所有状态情况
$$ \sum\limits_{I}P(O,I|\overline{\lambda})\sum\limits_{t=1}^{T-1}\log a_{i_t,i_{t+1}} \\ = \sum\limits_{i=1}^N\sum\limits_{j=1}^N\sum\limits_{t=1}^{T-1}P(O,i_t = i, i_{t+1} = j|\overline{\lambda})log\;a_{ij} $$
用拉格朗日乘子法求得aij的迭代表达式
$$ a_{ij} = \frac{\sum\limits_{t=1}^{T-1}P(O, i_t = i, i_{t+1} = j|\overline{\lambda})}{\sum\limits_{t=1}^{T-1}P(O, i_t = i|\overline{\lambda})} $$
| 所求结果代入常用概率: $$ a_{ij} = \frac{\sum\limits_{t=1}^{T-1}\xi_t(i,j)}{\sum\limits_{t=1}^{T-1}\gamma_t(i)} $$ 由状态i转移到状态j的期望值/由状态i转移的期望值 |
3)第3项对b求该式极大
$$ \sum\limits_{I}P(O,I|\overline{\lambda})\sum\limits_{t=1}^{T}log\;b_{i_t}(o_t) = \sum\limits_{j=1}^N\sum\limits_{t=1}^{T}P(O,i_t = j|\overline{\lambda})log\;b_{j}(o_t) $$
同理用拉格朗日乘子法求得bj(k)的迭代表达式
$$ b_{j}(k) = \frac{\sum\limits_{t=1}^{T}P(O,i_t = j|\overline{\lambda})I(o_t=v_k)}{\sum\limits_{t=1}^{T}P(O,i_t = j|\overline{\lambda})} \\ I(o_t=v_k)=\left\{\begin{array}{ll}1, if \ o_t=v_k \\ 0, if \ o_t\neq v_k \end{array}\right. $$
指示函数保证观测不为v_k时, 偏导数为0.
| 代入常用概率 $$ b_{j}(k) = \frac{\sum\limits_{t=1, o_t=v_k}^{T}\gamma_t(j)}{\sum\limits_{t=1}^{T}\gamma_t(j)} $$ 观测为vk时状态j出现的期望值/状态j出现的期望值 |
鲍姆-韦尔奇算法流程
输入：观测序列\( O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\)
输出：HMM模型参数
1) 初始化. 设迭代次数n=0时的初始模型参数\(a_{i j}^{(0)}, b_{j}(k)^{(0)}, \pi_{i}^{(0)}\)
2) 利用迭代公式递推. 对\( n=1,2, \cdots \)
更新模型参数：
$$ \begin{aligned} a_{i j}^{(n+1)}=\frac{\sum_{t=1}^{T-1} \xi_{t}(i, j)}{\sum_{t=1}^{T-1} \gamma_{t}(i)}\\ {b_{j}(k)^{(n+1)}=\frac{\sum_{t=1, o_{t}=v_{k}}^T \gamma_{t}(j)}{\sum_{t=1}^{T} \gamma_{t}(j)}} \\ {\pi_{i}^{(n+1)}=\gamma_{1}(i)} \end{aligned} $$
3) 当参数值收敛，终止, 得到模型参数\( \lambda^{(n+1)}=\left(A^{(n+1)}, B^{(n+1)}, \pi^{(n+1)}\right) \)
预测算法
给定模型λ和观测O={o1,o2,...oT}，求状态I∗使P(I∗|O)最大化
近似算法, 维特比(Viterbi)算法
近似算法
每个时刻t都选择最可能的隐藏状态i∗t作为预测结果.
缺点: 不能保证整体是最可能的状态序列，因为预测的状态序列中, 某些相邻的隐藏状态可能存在转移概率为0.
即求状态i*:
$$ i_t^* = arg \max_{1 \leq i \leq N}[\gamma_t(i)], \; t =1,2,...T $$
| 其中γ为第一个常用概率: 在给定模型λ和观测序列O时，在时刻t处于状态qi的概率是γt(i) $$ \gamma_t(i) = P(i_t = q_i | O,\lambda) = \frac{P(i_t = q_i ,O|\lambda)}{P(O|\lambda)} $$ |
维特比算法
用动态规划（dynamic programming）求概率最大路径(最优路径). 路径对应状态序列.
近似算法类似最优路径的贪心,维特比类似动态规划.
贪心很好理解, 就是每一步都求下一步的最优, 而动态规划有一个回溯的过程.
| 动态规划 参考: https://zhuanlan.zhihu.com/p/111134524 动态规划适用可以分解的问题: 大规模问题的答案可以由小规模问题的答案递推得到 多段图的最短路径问题是求从源点到终点的最小代价路径 多段图将顶点划分为k个互不相交的子集(k段). 10 个顶点的多段图:
算法流程参考: https://zhuanlan.zhihu.com/p/163010698 1.建立状态转移方程. 当做已经知道f(1)~f(n-1)求f(n) 2.缓存并复用以往结果 求f(n)时需要复用f(n-1)结果 3.按顺序从小往大递推f(1)…f(n)
需要求解的路线是由 A 到 G，这就意味着 A 要先到 B，再到 C，再到 D，再到 E，再到 F。每一轮都需要做不同的决策，而每次的决策又依赖上一轮决策的结果 例如，做 D2 -> E 的决策时，D2 -> E2 的距离为 1，最短。但这轮的决策，基于的假设是从 D2 出发，这就意味着前面一轮的决策结果是 D2 其中, 第一轮决策的状态是 S1，可选的值是 A，第二轮决策的状态是 S2，可选的值就是 B1 和 B2 步骤: 1.分阶段：从 A 到 G，可以拆分为 A -> B、B -> C、C -> D、D -> E、E -> F、F -> G，6 个阶段。 2.找状态：第一轮的状态 S1 = A，第二轮 S2 = {B1,B2}，第三轮 S3 = {C1,C2,C3,C4}，第四轮 S4 = {D1,D2,D3}，第五轮 S5 = {E1,E2,E3}，第六轮 S6 = {F1,F2}，第七轮 S7 = {G}。 3.做决策：决策变量就是上面图中的每条边。以第四轮决策 D -> E 为例来看，可以得到 u4(D1)，u4(D2)，u4(D3)。其中 u4(D1) 的可能结果是 E1 和 E2。 4.写出状态转移方程： \( s_{k+1}=u_{k}\left(s_{k}\right) \) 5.定目标：目标是总距离最短。定义 dk(sk,uk) 是在第k段的状态为 sk 时，选择 uk 动作的距离，如 d5(E1,F1) = 3. 此处总段数 n = 7，则有如下为最终要优化的目标： $$ \mathrm{v}_{\mathrm{k}, 7}\left(\mathrm{~s}_{1}=\mathrm{A}, \mathrm{s}_{7}=\mathrm{G}\right)=\sum_{\mathrm{k}=1}^{7} \mathrm{~d}_{\mathrm{k}}\left(\mathrm{s}_{\mathrm{k}}, \mathrm{u}_{\mathrm{k}}\right) $$ 6.寻找终止条件：起止条件分别是，s1 = A 和 s7 = G 7.求子问题最优解: 原问题的最优解所包括的子问题的解也是最优的=> 如果 A -> ... -> F1 -> G 是全局 A 到 G 最优的路径，那么此处 A -> ... -> F1 也是 A 到 F1 的最优路径, 即是 A 到 F1 到 G 的路径和 A 到 F2 到 G 的路径中更短的那个. 核心代码 输入m x m二维数组表示距离
|
维特比原理
1.求各条部分路径概率与终结点
从时刻t＝1开始，递推地计算在时刻t状态为i的各条部分路径的最大概率，直至得到时刻t＝T状态为i的各条路径的最大概率。时刻t＝T的最大概率即为最优路径的概率P*，最优路径的终结点\( i^*_T \)也同时得到
2.求路径(与普通动态规划求最优路径步骤同)
为了找出最优路径的各个结点，从终结点\( i^*_T \)开始，由后向前逐步求得结点\( i_{T-1}^{*}, \cdots, i_{1}^{*} \)得到最优路径\( I^{*}=\left(i_{1}^{*}, i_{2}^{*}, \cdots, i_{T}^{*}\right) \)
定义变量
| 给定时刻t状态为i, 从时刻1到时刻t-1的状态不确定, 存在多条可能路径\( (i_{1}, i_{2}, \cdots, i_{T}) \) 其中概率最大的一条路径的概率为δ_t(i) | $$ \delta_t(i) = \max_{i_1,i_2,...i_{t-1}}\;P(i_t=i, i_{t-1}...i_1,o_t,...o_1|\lambda),\; i =1,2,...N $$ |
| δ的递推公式 由已知t时刻最优的j转移到t+1时刻的i, 并观测到\( o_{t+1}\) | $$ \delta_{t+1}(i) = \max_{i_1,i_2,...i_{t}}\;P(i_{t+1}=i, i_{t},...,i_1,o_{t+1},...o_1|\lambda) \\ = \max_{1 \leq j \leq N}\;[\delta_t(j)a_{ji}]b_i(o_{t+1})\\ i =1,2,...N ;T=1,...,T-1 $$ |
| 给定时刻t状态为i, 比较所有路径\( (i_{1}, i_{2}, \cdots, i_{T}) \) 其中概率最大的一条路径的第t-1个结点 | $$ \Psi_t(i) = arg \; \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}];\\i =1,2,...N $$ |
维特比算法流程
算法10.5（维特比算法）
输入：模型λ=(A, B, π)和观测序列\( O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\)
输出：最优路径(最有可能的隐藏序列) \( I^*= \{i_1^*,i_2^*,...i_T^*\} \)
（1）初始化
t=1时, 路径(只有一个初始点)的概率即为初始状态概率πi*观测bi; t-1个结点不存在令其为0
$$ \delta_1(i) = \pi_ib_i(o_1),\;i=1,2...N \\ \Psi_1(i)=0,\;i=1,2...N $$
（2）递推
对t＝2,3,…,T分别求到达各个状态结点的最优路径概率
δ已知t-1时间各结点最优路径概率, 再转移, 观测, 即可递推得到该时间结点的概率.
Ψ已知t-1时间各结点最优路径概率, 转移到i结点, 哪个概率最大, 就选哪个作为t-1的最优结点.
$$ \delta_{t}(i) = \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}]b_i(0_{t}),\;i=1,2...N\\ \Psi_t(i) = arg \; \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}],\;i=1,2...N $$
（3）终止
计算时刻T最大的δT(i),即为最可能隐藏状态序列出现的概率
计算时刻T最大δT(i)所用的i,即为时刻T最可能的隐藏状态
$$ P^* = \max_{1 \leq i \leq N}\delta_{T}(i)\\i_T^* = arg \; \max_{1 \leq i \leq N}\;[\delta_{T}(i)] $$
（4）最优路径回溯。
对t＝T-1,T-2,…,1
$$ i_t^* = \Psi_{t+1}(i_{t+1}^*) $$
得最优路径:
$$ I^*= \{i_1^*,i_2^*,...i_T^*\} $$
例子
已知条件与前向算法中的例子相同:
| 盒子和球模型 | λ=(A, B, π), |
| 状态集合 (可以从哪些盒中抽) | Q={1，2，3}，N=3 |
| 观测集合 (可以抽到哪种球) | V={红，白}，M=2 |
| 状态转移矩阵 (下一个盒是该盒的概率, 如a12是从第一个盒转移到第二个盒) | $$ A = \left( \begin{array} {ccc} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 &0.5 \end{array} \right) $$ |
| 概率分布矩阵 (从该盒抽到每种球的概率) | $$ B = \left( \begin{array} {ccc} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{array} \right) $$ |
| 初始状态向量 (第一次可能是哪个盒) | $$ \pi = (0.2,0.4,0.4)^T $$ |
| 观测序列 (最后抽的结果) | O={红，白，红} |
| 观测序列和状态序列的长度 | T=3. |
维特比算法求最优状态序列(最优路径) \( I^*= \{i_1^*,i_2^*,...i_T^*\} \)
按照算法10.5(维特比算法)
输入：模型λ=(A, B, π)和观测序列O={红，白，红}.
（1）初始化t=1
①t=1时, 已知第一次拿到红球(观测) \( o_1=红 \), 状态路径的概率(只有一个初始点状态i, 从i盒拿) 分别为:
$$ \delta_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right)=\pi_{i} b_{i}(\text { 红 }), \quad i=1,2,3 $$
| 第一次从盒1拿到红球 | $$ \delta_1(1) = \pi_1b_1(o_1) = 0.2 \times 0.5 = 0.1 $$ |
| 第一次从盒2拿到红球 | $$ \delta_1(2) = \pi_2b_2(o_1) = 0.4 \times 0.4 = 0.16 $$ |
| 第一次从盒3拿到红球 | $$ \delta_1(3) = \pi_3b_3(o_1) = 0.4 \times 0.7 = 0.28 $$ |
即为初始状态概率πi*观测bi
②t=1时, t-1个结点不存在令其为0:
$$ \Psi_1(1)=\Psi_1(2) =\Psi_1(3) =0 $$
（2）递推各个状态结点的最优路径概率, 最优结点
t＝2时, 已知第二次拿到白球
$$ \delta_{2}(i)=\max _{1 \leqslant j \leqslant 3}\left[\delta_{1}(j) a_{j i}\right] b_{i}\left(o_{2}\right) \\ \Psi_{2}(i)=\arg \max _{1 \leqslant j \leqslant 3}\left[\delta_{1}(j) a_{j i}\right], \quad i=1,2,3 $$
状态i=盒1的最优路径概率, 最优结点
| 第二次从盒1拿到白球 | 第一次为盒1, 转移到盒1 1->1 | $$ \delta_1(1)a_{11}b_1(白)\\= 0.1 \times 0.5 \times 0.5 =0.05 \times 0.5$$ |
| 第一次为盒2, 转移到盒1 2->1 | $$ \delta_1(2)a_{21}b_1(白)\\= 0.16 \times 0.3 \times 0.5 =0.048 \times 0.5$$ | |
| 第一次为盒3, 转移到盒1 3->1为概率最大路径, 路径最大概率为 $$ \delta_2(1) =\delta_1(3)a_{31}b_1(白)=0.028 $$ 盒3为t=2时盒1的最优上一结点 $$ \Psi_2(1)=3 $$ | $$ \delta_1(3)a_{31}b_1(白)\\= 0.28\times 0.2 \times 0.5 =0.056 \times 0.5\\(0.056为最大值\times 0.5)=0.028$$ |
同理可得, 状态i=盒2的最优路径概率, 最优结点
| 第二次从盒2拿到白球 | 第一次为盒1, 转移到盒2 1->2 | $$ \delta_2(2) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j2}]b_2(o_2)\\ = \max_{1\leq j \leq 3}[0.1 \times 0.2, 0.16 \times 0.5, 0.28\times 0.3] \times 0.6\\=0.28\times 0.3 \times 0.6 = 0.0504 $$ |
| 第一次为盒2, 转移到盒2 2->2 | ||
| 第一次为盒3, 转移到盒2 3->2为概率最大路径, 路径最大概率为 $$ \delta_2(2) =\delta_1(3)a_{32}b_2(白)=0.0504 $$ 盒3为t=2时盒1的最优上一结点 $$ \Psi_2(2)=3 $$ |
状态i=盒3的最优路径概率, 最优结点
| 第二次从盒3拿到白球 | 第一次为盒1, 转移到盒3 | $$ \delta_2(3) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j3}]b_3(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.3, 0.16 \times 0.2, 0.28\times 0.5] \times 0.3 = 0.042 $$ |
| 第一次为盒2, 转移到盒3 | ||
| 第一次为盒3, 转移到盒3 3->3为概率最大路径, 路径最大概率为 $$ \delta_2(3) =\delta_1(3)a_{33}b_3(白)=0.042 $$ 盒3为t=2时盒1的最优上一结点 $$ \Psi_2(3)=3 $$ |
t＝3时, 已知第三次拿到红球. 同理可得状态i=盒1, 2, 3的最优路径概率, 最优结点
| 第三次从盒1拿到红球 | $$ \delta_3(1) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j1}]b_1(o_3) \\ = \max_{1\leq j \leq 3}[0.028 \times 0.5, 0.0504 \times 0.3, 0.042\times 0.2] \times 0.5 = 0.00756\\ \Psi_3(1)=2 $$ |
| 第三次从盒2拿到红球 | $$ \delta_3(2) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j2}]b_2(o_3) \\ = \max_{1\leq j \leq 3}[0.028 \times 0.2, 0.0504\times 0.5, 0.042\times 0.3] \times 0.4 = 0.01008\\ \Psi_3(2)=2 $$ |
| 第三次从盒3拿到红球 | $$ \delta_3(3) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j3}]b_3(o_3) \\= \max_{1\leq j \leq 3}[0.028 \times 0.3, 0.0504 \times 0.2, 0.042\times 0.5] \times 0.7 = 0.0147\\ \Psi_3(3)=3 $$ |
（3）终止
取时刻3最大的δT(i),即为最优路径(最可能隐藏状态序列出现)的概率P*:
$$ P^* = \max_{1 \leq i \leq 3}\delta_{3}(i)=\delta_3(3)=0.0147 $$
取时刻3最大δT(i)所用的i,即为最优路径的终点(时刻T最可能的隐藏状态)
$$ i_3^* = arg \; \max_{1 \leq i \leq 3}\;[\delta_{3}(3)]=3 $$
（4）最优路径回溯
已知最优路径的终点 \( i_{3}^{*} \)
对t＝2,1, 根据最优上一结点\( i_{2}^{*}, i_{1}^{*} \)进行回溯
$$ i_t^* = \Psi_{t+1}(i_{t+1}^*) \\t=2, \quad i_{2}^{*}=\Psi_{3}\left(i_{3}^{*}\right)=\Psi_{3}(3)=3 \\t=1, \quad i_{1}^{*}=\Psi_{2}\left(i_{2}^{*}\right)=\Psi_{2}(3)=3 $$
得最优路径:
$$ I^*= \{i_1^*,i_2^*,i_3^*\}= \{3,3,3\} $$
示例代码
代码参考:
https://github.com/Dod-o/Statistical-Learning-Method_Code
维特比为NLP中的经典算法, 此处给出的也是一个分词代码.
隐状态:
| 隐状态标记 | 含义 | 数组中对应的位置 |
| B | 词语的开头 | 0 |
| M | 一个词语的中间词 | 1 |
| E | 一个词语的结果 | 2 |
| S | 非词语，单个词 | 3 |
B->M->E->S
模型学习
模型λ=(A, B, π)学习, 也就是求解模型参数A, B, π, :
| #依据现有训练集统计PI、A、B PI, A, B = trainParameter('HMMTrainSet.txt') |
经过查看训练集数据, 此处已经做了分词, 隐状态也可通过判断字在词中的位置进行标注, 为有监督学习.
生成统计时主要借助以下思路：
1.句中n个词语，隔开后变成一个长度为n的列表，每个元素为一个词语
| #对单行句子按空格进行切割 curLine = line.strip().split() |
2.对每个词语长度进行判断：
如果为1认为该词语是S，即单个字
| label = 'S' |
如果为2则第一个是B，表开头，第二个为E，表结束
如果大于2，则第一个为B，最后一个为E，中间全部标为M，表中间词
| #如果长度不为1，开头为B，最后为E，中间添加长度-2个M #如果长度刚好为2，长度-2=0也就不添加了，反之添加对应个数的M label = 'B' + 'M' * (len(curLine[i]) - 2) + 'E' |
| #在整行的词性标记状态链后添加该单词的状态链 wordLabel.extend(label) |
3. 统计初始状态矩阵π：该句第一个字的词性对应的PI中位置加1
初始化PI = [0， 0， 0， 0]，当本行第一个字是B('词语的开头')时，PI中B对应位置为0，
则PI = [1， 0， 0， 0]，全部统计结束后，按照计数值再除以总数得到概率
统计转移矩阵A：对状态链中位置t和t-1的状态进行统计，在矩阵中相应位置加1，全部结束后生成概率
统计观测矩阵B：对于每个字的状态到字的发射计数，全部结束后生成概率
此处概率计算比频率多了取log过程, 对学习过程代码进行修改, 按照监督学习的公式, 取频率(不取对数)
得到分词结果
| 深圳|有个|打|工者|阅览|室 去年|１|２月|，|我在|广东|深圳|市出|差|，听|说南|山区|工商|分局|为打|工者|建了|个|免费|图书|阅览|室|，|这件|新鲜|事引|起了|我的|兴趣|。 … （本|报|记者|罗|华） |
对比原代码分词结果:
| -------------------分词后---------------------- 深圳|有个|打|工者|阅览室 去年|１２月|，|我|在|广东|深圳|市出|差|，|听|说|南|山区|工商|分局|为|打|工者|建了|个|免费|图书|阅览室|，|这件|新|鲜事|引起|了|我|的|兴趣|。 … （|本报|记者|罗华|） |
看起来还是加log的效果好一些
这是两个实际代码计算中的问题
1.某元素没有出现过，该位置为0，在后续的计算中这是不被允许的
比如说某个汉字在训练集中没有出现过，那在后续不同概率相乘中只要有一项为0，其他都是0了
2. 整条链很长的情况下，太多0-1的概率相乘, 不管怎样最后的结果都会很小，很容易下溢出, 所以在概率上我们习惯将其转换为log对数形式
x大的时候，log也大，x小的时候，log也相应小，(虽然是负值), 我们最后比较的是不同概率的大小，所以使用log没有问题
这在书上是没有讲的
统计初始状态矩阵π
根据频数, 估计初始状态概率πi
C(i)为所有样本中初始状态为qi的频率计数(此处再用log防止连乘下溢), 分母为所有状态出现在初始的频数和
$$ \log \pi(i) = \log \frac{C(i)}{\sum\limits_{s=1}^{N}C(s)} $$
| #初始状态矩阵PI只需要计算单行开头第一个字，PI中对应位置加1, if i == 0: PI[statuDict[label[0]]] += 1 |
| #对PI求和，概率生成中的分母 sum = np.sum(PI) |
| #如果该项为0，则手动赋予一个极小值 if PI[i] == 0: PI[i] = -3.14e+100 如果不为0，则计算概率，再对概率求log PI[i] = np.log(PI[i] / sum) |
其中代码只取了核心计算部分, 循环条件等省略
统计观测矩阵B
根据频数, 估计观测概率bj(k)
Bjk为样本隐藏状态为qj且观测状态为vk的频率计数(此处再用log防止连乘下溢), 分母为状态qj所有观测的频数和
$$ \log B= \Big[\log b_{j}(k)\Big], \;其中\log b_{j}(k) = \log \frac{B_{jk}}{\sum\limits_{s=1}^{M}B_{js}} $$
| #遍历状态链中每一个状态，并找到对应的中文汉字编码，在B中对应位置加1 B[statuDict[label[j]]][ord(curLine[i][j])] += 1# 使用ord(汉字)即可找到其对应编码 |
| sum = np.sum(B[i]) |
| if B[i][j] == 0: B[i][j] = -3.14e+100 else:B[i][j] = np.log(B[i][j] / sum) |
统计转移矩阵A
根据频数, 估计转移概率aij
对状态链中位置t和t-1的状态进行统计，在矩阵中相应位置加1，全部结束后生成概率
Aij为从状态qi转移到qj的频率计数(此处再用log防止连乘下溢). 分母为从qi转移到所有状态的频数和.
$$ \log A = \Big[\log a_{ij}\Big], \;其中\log a_{ij} = \log \frac{A_{ij}}{\sum\limits_{s=1}^{N}A_{is}} $$
| #统计t-1时刻状态->t时刻状态的所有状态组合的出现次数 A[statuDict[wordLabel[i - 1]]][statuDict[wordLabel[i]]] += 1 |
| sum = np.sum(A[i]) |
| if A[i][j] == 0: A[i][j] = -3.14e+100 else: A[i][j] = np.log(A[i][j] / sum) |
分词预测
给定模型λ和观测O={o1,o2,...oT}，求状态I∗使P(I∗|O)最大化
算法依据“10.4.2 维特比算法”
| #新建嵌套列表δ，δ存放四种状态的概率值，因为状态链中每个状态都有 #一个元素内部有四种概率值，长度(元素个数)是该行的长度(文字个数) delta = [[0 for i in range(4)] for i in range(len(line))] |
| 如句子'深圳有个打工者阅览室' |
| 嵌套列表δ形状为 [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] |
（1）初始化
t=1时, 路径(只有一个初始点)的概率即为初始状态概率πi*观测bi; t-1个结点不存在令其为0
$$ \log \delta_1(i) = \log \pi_i+\log b_i(o_1),\;i=1,2...N \\ \Psi_1(i)=0,\;i=1,2...N $$
(原先是概率直接相乘，取完log以后，概率的乘法转换为加法了)
| #初始化δ状态链中第一个状态的四种状态概率 delta[0][i] = PI[i] + B[i][ord(line[0])] |
| #初始化ψ，初始时为0 psi = [[0 for i in range(4)] for i in range(len(line))] |
（2）递推
对t＝2,3,…,T分别求到达各个状态结点的最优路径概率
δ已知t-1时间各结点最优路径概率, 再转移, 观测, 即可递推得到该时间结点的概率.
Ψ已知t-1时间各结点最优路径概率, 转移到i结点, 哪个概率最大, 就选哪个作为t-1的最优结点.
$$ \log \delta_{t}(i) = \max_{1 \leq j \leq N}\;[\log \delta_{t-1}(j)+\log a_{ji}]+\log b_i(0_{t}),\;i=1,2...N $$
先计算δ, 书中的乘法在这里变成了加法，这是由于原先是概率直接相乘，但我们在求得概率时，同时取了log，取完log以后，概率的乘法转换为加法了，同时也简化了运算
| #初始化一个临时列表，用于存放四种概率 tmpDelta = [0] * 4 |
| tmpDelta[j] = delta[t - 1][j] + A[j][i] |
| #找到最大的那个δ_{t-1} * a， maxDelta = max(tmpDelta) #记录最大值对应的状态 maxDeltaIndex = tmpDelta.index(maxDelta) |
| #将找到的最大值乘以b放入， #注意：这里同样因为log变成了加法 delta[t][i] = maxDelta + B[i][ord(line[t])] |
再记录Ψ
$$ \Psi_t(i) = arg \; \max_{1 \leq j \leq N}\;[\log \delta_{t-1}(j)+\log a_{ji}],\;i=1,2...N $$
| #在ψ中记录对应的最大状态索引 psi[t][i] = maxDeltaIndex |
（3）终止
计算时刻T最大的δT(i),即为最可能隐藏状态序列出现的概率
计算时刻T最大δT(i)所用的i,即为时刻T最可能的隐藏状态
$$ P^* = \max_{1 \leq i \leq N}\delta_{T}(i)\\ i_T^* = arg \; \max_{1 \leq i \leq N}\;[\delta_{T}(i)] $$
| #获取最后一个状态的最大状态概率对应的索引 i_opt = delta[len(line) - 1].index(max(delta[len(line) - 1])) |
| #建立一个状态链列表，开始生成状态链 sequence = [] |
| #在状态链中添加索引 #注：状态链0、1、2、3，对应B、M、E、S sequence.append(i_opt) |
（4）最优路径回溯。
对t＝T-1,T-2,…,1
$$ i_t^* = \Psi_{t+1}(i_{t+1}^*) $$
| #不断地从当前时刻t的ψ列表中读取到t-1的最优状态 i_opt = psi[t][i_opt] #将状态放入列表中 sequence.append(i_opt) |
| #因为是从后往前将状态放入的列表，所以这里需要翻转一下，变成了从前往后 sequence.reverse() |
分词任务
| #如果该字是3：S->单个词 或 2:E->结尾词 ，并且没到一句话结尾. 则在该字后面加上分隔符 | if (sequence[i] == 3 or sequence[i] == 2) and i != (len(line) - 1): curLine += '|' |
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
3
0- 0
已为社区贡献13条内容
所有评论(0)