凭虚临风

凭虚临风 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

凭虚临风 发布了文章 · 2017-10-29

HMM(隐马尔科夫模型)的训练

HMM的训练

隐马尔科夫模型的训练。上篇文章讲述了,已知模型(初始矩阵,状态转移矩阵,发射矩阵)求某一观察序列的几率。但没有提及如何获取模型参数,这篇文章就概略的讲述HMM的训练。

极大似然估计(Maximum Likelihood Estimate)

在很多网上文章里,提到如果有标注数据可以通过极大似然估计对HMM的参数进行计算。
极大似然估计其实就是在已经概率分布形式的情况下,对参数进行估算的一种方法。

  1. 写出似然函数
  2. 加入对数(方便求导,不会影响结果)
  3. 设导数为0
  4. 求解方程(如果有多个参数,会联立求方程组)

通过隐马尔可夫模型中最大似然估计的推导过程
[https://wenku.baidu.com/view/...]()

  • 可以推出

状态转换概率:
$$P(t | s) = \frac{Count(t,s)}{Count(s)}$$
发射概率:
$$P(w | t) = \frac{Count(w,t)}{Count(t)}$$

里边的Count(t,s) 就是隐藏状态t,s在训练集中得出现次数。Count(w,t)是隐藏状态t和观察状态w一起出现的次数。
其实这个也很符合常识,不用上边复杂的推导过程,根据经验(大数定律), 我们也能知道频率近似于概率。

Baum–Welch算法

很多时候我们并没有标注数据,只有很多组观察数据(未标注), 在进行极大似然估计计算的时候,根本无法进行(维数等于样本数据)。
但我们能比较两组不同的参数,判断谁得到样本集的概率更高。EM(Expectation-maximization)算法能帮助我们在这种情况下,得到概率分布参数的局部最优解。从某种意义上来说,EM算法可以看做求极大似然的一种特殊算法。

回到HMM上,Baum–Welch算法就是EM算法在HMM上的具体实现。
顺便说下,Baum–Welch算法(1960s)比EM算法(1977)早出现, 但EM总结这类算法的一般步骤。所以现在都把Baum–Welch看成EM的特殊实现。

Baum–Welch算法的步骤。

  1. 随机构造初始化参数。
  2. E-step,通过前向后向计算,得到参数的数据期望
  3. M-step,通过E(X)更新参数。
  4. 迭代2-3步。直到参数稳定,得到局部最优解。

算法先假定一组概率参数,然后利用向前向后计算,计算出符合目前观察现象的概率的数学期望,
然后再拿这组数学期望去更新参数,逐渐逼近局部最优解。

现在让我们看看E-STEP到底怎么做的,在此前我们得先弄明白向前变量和向后变量。

  • 向前变量
    $$\alpha_{t}(i)=P(O_{1},O_{2},...,O_{t},q_{t}=S_{i}|\theta )$$

给定模型下,观察序列为$O_{1},O_{2},...,O_{t}$ 和 t时刻隐藏状态为$S_{i}$的联合概率。

  • 向后变量
    $$\beta_{t}(i)=P(O_{t+1},O_{t+2},...|q_{t}=S_{i},\theta )$$

给定模型下,t时刻隐藏状态为$S_{i}$并且后续观察序列为$O_{t+1},O_{t+2},...$的概率。

注意两个定义都可以使用我们前一篇文章所说的前向后向算法进行计算。就是一个递归计算的过程。

这两个变量合在一起就可以表示.在给定观察序列下,t时刻隐藏状态为i的概率。
$$\gamma_{t}(i)=P(q_{t}=S_{i}|O,\theta)=\frac{\alpha_{t}(i)*\beta_{t}(i)}{P(O|\theta)}=\frac{\alpha_{t}(i)*\beta_{t}(i)}{\sum_{i=1}^{n}\alpha_{t}(i)*\beta_{t}(i)}$$

又定义, 在给定观察序列下,t时刻从隐藏状态 i 转移到 j的概率。
$$\xi_{t}(i,j)=P(q_{t}=S_{i},q_{t+1}=S_{j}|O,\theta) = \frac{\alpha_{t}(i)*a_{i,j}*b_{j,O_{t+1}}*\beta_{t+1}(j)}{\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_{t}(i)*a_{i,j}*b_{j,O_{t+1}}*\beta_{t+1}(j)}$$

隐藏状态为i的数学期望,其实就是算个平均值
$$E(i)=\frac{\sum_{t=1}^{T-1}\gamma_{t}(i)} {T-1}$$

隐藏状态从 i 转移到 j 的数学期望(是t时刻为i,t+1时刻为j的联合概率)
$$E(i,j)=\frac{\sum_{t=1}^{T}\xi_{t}(i,j)} {T-1}$$

所以自然可以推出
$$估算初始概率=\gamma_{1}(i)$$
$$估算转移概率=\frac{E(i,j)}{E(i)}$$
$$估算发射概率=\frac{E(i,O=为O_{x})}{E(i)}$$
上边$(O=为O_{x})$是指只计算隐藏状态为i,发射后的观察状态为x的情况$

然后使用上边计算的估算值,替换初始的参数。反复进行迭代,直到得到局部最优解。


E=> M=> E=> ...直到稳定
查看原文

赞 3 收藏 2 评论 0

凭虚临风 发布了文章 · 2017-10-14

HMM(隐马尔科夫模型)

HMM(隐马尔科夫模型)

隐马尔科夫模型是统计模型在机器学习中的典型应用,即使在目前神经网络飞速发展的当下,也被认为是NLP领域相当有效的方法。

转移概率,发射概率

现实生活中,我们可以观察到很可见状态,这些可见状态是已发生的,确定的。
这些可见状态会依赖于一些隐藏状态,隐藏状态之间会存在转移概率(transition probality), 而从隐藏状态到可见状态则存在发射概率(emission probality)

马尔科夫链

马尔科夫假设

实际情况中,某一时刻的状态其实是由已发生的多个状态决定的.
$$P(X_{n} | X_{n-1},X_{n-2}... )$$
但这样对于计算太过于复杂,所以建立一种假设,当前状态只依赖于上一个状态。而与其他状态无关。
$$P(X_{n} | X_{n-1})$$
这个假设虽然不太符合实际,但在实际应用中发现,相当有效。

隐马尔科夫模型解决的问题

  1. 已知一种模型(隐含状态数量,转移概率,发射概率),求一可见状态链的概率。(Forward算法)
  2. 已知一种模型(隐含状态数量,转移概率,发射概率),求最可能的隐藏状态链。(Veterbi 算法)
  3. 已知一组可见状态链,求模型(转移概率,发射概率)。(EM 算法)

Forward 算法

针对第一类问题,如果状态空间较小,可以通过穷举各种可能的组合,然后进行累加。
但这在样本空间较大后,变成不可能完成的任务。
Forward则采取迭代计算的方式层层计算,直至得到最后结果。

假设现在有:

隐含状态:$X \in (X_{1},X_{2})$

初始概率:假设均匀分布,都为1/2

转移概率:$ P(X_{1}->X_{2}) =1/3$ $ P(X_{1}->X_{1}) =2/3$ $ P(X_{2}->X_{1}) =7/8$ $P(X_{2}->X_{2})=1/8 $

发射概率:$ P(X_{1}->S_{1}) =1/2$ $P(X_{1}->S_{2})=1/2 $ $P(X_{2}->S_{1})=3/8 $ $P(X_{2}->S_{2})=5/8 $

观察状态链: $S_{1}->S_{2}->S_{2}->S_{1}$

计算过程:

S(X)$S_{1}$$S_{2}$$S_{2}$$S_{1}$
$X_{1}$1/2 * 1/8$S_{1}(X_{1})$ * 2/3 * 1/2 + $S_{1}(X_{2})$ * 7/8 * 5/8......
$X_{2}$1/2 * 3/8$S_{1}(X_{2})$ * 1/8 * 1/4 + $S_{1}(X_{1})$ * 7/8 * 1/4......
Total0.250.14......

Veberbi 算法

针对第二类问题,解决办法就是在Forward计算的基础,只是不是累加概率,而是挑选最大的概率。
其实有点动态规划的意思,算出$S_{n-2}$到$S_{n-1}$的各种情况下的概率,然后挑选出最大概率的串,用于$S_{n}$的迭代计算。
计算过程:

S(X)$S_{1}$$S_{2}$$S_{2}$$S_{1}$
$X_{1}$1/2 * 1/8Max($S_{1}(X_{1}) * 2/3 * 1/2$ , $S_{1}(X_{2}) * 7/8 * 5/8 $)......
$X_{2}$1/2 * 3/8Max($S_{2}(X_{2}) * 1/8 * 1/4$ , $S_{1}(X_{1}) * 7/8 * 1/4 $)......

在迭代计算的过程,保存最大概率的串。在最后一个隐藏状态计算中,最大概率的串就是结果。

EM 算法

无监督算法。 to be continued...

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 3 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2017-10-13
个人主页被 189 人浏览