隐马尔科夫
马尔可夫性质
设{X(t), t ∈ T}是一个随机过程,E为其状态空间,若对于任意的t1<t2< ...<tn<t,任意的x1,x2,...,xn,x∈E,随机变量X(t)在已知变量X(t1)=x1,...,X(tn)=xn之下的条件分布函数只与X(tn)=xn有关,而与X(t1)=x1,...,X(tn-1)=xn-1无关,即条件分布函数满足下列等式,此性质称为马尔可夫性;如果随机过程满足马尔可夫性,则该过程称为马尔可夫过程。
马尔可夫链
马尔可夫链是指具有马尔可夫性质的随机过程。在过程中,在给定当前信息的情况下,过去的信息状态对于预测将来状态是无关的。
在马尔可夫链的每一步,系统根据概率分布,可以从一个状态变成另外一个状态,也可以保持当前状态不变。状态的改变叫做转移,状态改变的相关概率叫做转移概率。
马尔可夫链中的三元素:状态空间S、转移概率矩阵P、初始概率分布π。
如:现给定一矩阵P如下
今/明 | 晴 | 阴 | 雨 |
---|---|---|---|
晴 | 0.75 | 0.125 | 0.125 |
阴 | 0.5 | 0.25 | 0.25 |
雨 | 0.25 | 0.5 | 0.25 |
第N+1天的天气状态为j的概率为:
因此,矩阵P即为条件概率转移矩阵。
矩阵P的第i行元素表示,在上一个状态为i的时候的分布概率,即每行元素的和必须为1。
隐马尔科夫
隐马尔可夫模型(Hidden Markov Model, HMM)是一种统计模型(也是基于概率的)。与时间连续性是相关的。
HMM是关于时序的概率模型,描述一个含有未知参数的马尔可夫链所生成的不可观测的状态随机序列,再由各个状态生成观测随机序列的过程。HMM是一个双重随机过程---具有一定状态的隐马尔可夫链和随机的观测序列。
HMM随机生成的状态随机序列被称为状态序列;每个状态生成一个观测,由此产生的观测随机序列,被称为观测序列。
z1,z2...,zn是不可观测的状态(隐藏的条件),x1,x2,...xn是可观测到的序列。
也就是我们无法观测到状态,但是我们可以观测到由于这个状态而产生的类别。
HMM包括隐含状态S、可观测状态O、初始状态概率矩阵π、隐含状态转移概率矩阵A、可观测值转移矩阵B(又称为混淆矩阵,Confusion Matrix);
π和A决定了状态序列,B决定观测序列,因此HMM可以使用三元符号表示,称为HMM的三元素:
参数说明
S是所有可能的状态集合:
O是所有可能的观测集合:
I是长度为T的状态序列,Q是对应的观测序列
A是隐含状态转移概率矩阵:
aij是在时刻t处于状态si的条件下时刻t+1转移到状态sj的概率。
B是可观测值转移概率矩阵:
bij是在时刻t处于状态si的条件下生成观测值oj的概率。
π是初始状态概率向量:
πi是在时刻t=1处于状态si的概率。
两个重要公式:
只和前驱有关,而其他任何值都无关。
HMM三个问题
概率计算问题:前向-后向算法
给定模型λ=(A,B,π)和观测序列Q={q1,q2,...,qT},计算模型λ下观测到序列Q出现的概率P(Q|λ)
学习问题:Baum-Welch算法(状态未知)
已知观测序列Q={q1,q2,...,qT},估计模型λ=(A,B,π)的参数,使得在该模型下观测序列P(Q|λ)最大。
预测问题:Viterbi算法
给定模型λ=(A,B,π)和观测序列Q={q1,q2,...,qT},求给定观测序列条件概率P(I|Q,λ) 最大的状态序列I
概率计算问题
直接计算法
按照概率公式,列举所有可能的长度为T的状态序列I={i1,i2,...,iT},求各个状态序列I与观测序列Q={q1,q2,...,qT}的联合概率P(Q,I;λ),然后对所有可能的状态序列求和,从而得到最终的概率P(Q;λ)。
前向概率-后向概率
前向算法
定义:给定λ,定义到时刻t部分观测序列为q1,q2,...,qt且状态为si的概率为前向概率。记做:
是一个迭代类型的算法。
初值:
递推:
最终:
后向算法
定义:
给定λ,定义到时刻t状态为si的前提下,从t+1到T部分观测序列为qt+1,qt+2,...,qT的概率为后向概率。记做:
初值:
递推:对于 t = T - 1, T - 2 ... , 1
最终:
学习问题
1、若训练数据包含观测序列和状态序列,则HMM的学习问题非常简单,是监督学习算法。
2、若训练数据只包含观测序列,则HMM的学习问题需要使用EM算法求解,是非监督学习算法。
监督学习
直接利用大数定理的结论“频率的极限是概率”,直接给出HMM的参数估计。
无监督学习
若训练数据中只有观测序列,则HMM的学习问题需要使用EM算法,属于非监督算法;此时一般使用Baum-Welch算法。
所有的观测数据为 Q={q1,q2,...,qT} ,所有的隐状态为 I={i1,i2,...,iT} ,则完整的数据为 (O,I) ,完整数据的对数似然函数为 ln(p(Q,I;λ)) ; 然后直接使用EM算法的方式来进行参数估计。
极大化L函数,分别可以求得π、a、b的值。
预测问题
Viterbi算法
Viterbi算法实际是用动态规划的思路求解HMM预测问题,求出概率最大的 “路径” ,每条 “路径” 对应一个状态序列。
也就是贪心策略,但是是相反的,先选择最大可能的最后的概率,然后逐步往前推。
这个真的很难。。。。