马尔科夫转移.ppt

1、/Markov的几个模型,陆俊华,2020/7/8,2020/7/8,马尔科夫链,天气预测,定义,如果推广到m阶,计算,一个隐士不能直接观察天气来预测天气, 但是他有一些水藻. 民间传说, 水藻的状态与天气有一定关系 于是有了两组状态: 观测状态水藻的状态 隐藏状态天气状况,隐马尔科夫模型,隐士的预测,Hidden Markov Model, HMM,Hidden Markov Model, HMM,seaweed,sun,cloud,rain,weather,隐状态的转移矩阵,隐状态对应的观测状态的概率矩阵,=( ) 初始状态的概率向量 A=( )=Pr( | 1 ) (隐)状态的转移矩阵

2、B= =Pr( | ) 混淆矩阵 假设所有状态转移概率和混淆概率在整个系统中都是一成不变的,Hidden Markov Model, HMM,1.评估: 根据已知的HMM找出一个观测序列的概率 2.解码: 根据观察序列找到最有可能出现的隐状态序列 3.学习: 从观察序列中得出HMM,2020/7/8,HMM的三个应用,背景: 穷举法计算某一观察序列的概率,2020/7/8,评估: 前向算法(Forward Algorithm),部分概率: 达到观察状态序列 ( 1 , 2 , )并且为一定状态j的概率,2020/7/8,评估: 前向算法(Forward Algorithm),最后的观察状态的部

3、分概率表示这些状态所经过的所有可能路径的概率. 最后的部分概率的和即为网络中所有可能路径的和, 也就是当前HMM下观察序列的概率,2020/7/8,评估: 前向算法(Forward Algorithm),定义长度为T的观察序列为 ( 1 , 2 , ) 初始状态(t=1)部分概率: 1 = b 1 t 1时 部分概率: +1 = +1 =1 ,2020/7/8,评估: 前向算法(Forward Algorithm),定义 ()表示在时间t观测到 ( 1 , 2 , )并且t时刻处于隐状态j的部分概率: = Pr 观测 隐状态为 Pr(所有在时间通向的路径),部分概率: 达到观察状态序列 ( 1

4、 , 2 , )并且为一定状态j的概率,2020/7/8,评估: 前向算法(Forward Algorithm),我们可以通过穷举的方式列出所有可能隐含状态序列，并算出每一种隐状态序列组合对应的观察状态序列的概率。,2020/7/8,解码,最有可能的隐状态序列是使得概率： Pr(dry,damp,soggy | sunny,sunny,sunny), Pr(dry,damp,soggy | sunny,sunny,cloudy), Pr(dry,damp,soggy | sunny,sunny,rainy), . . . . Pr(dry,damp,soggy | rainy,rainy,ra

5、iny)得到最大值的序列。,2020/7/8,解码,核心原理: 如果最优路径在时刻t通过结点 , 那么这一路径从结点 到终点 的部分路径, 对于从 到 所有可能的部分路径来说, 必须是最优的. 对于网格中的每一个中间及终止状态, 都有一个到达该状态的最可能路径. 举例来说, 在t=3时刻的3个状态中的每一个都有一个到达此状态的最可能路径, 比如,2020/7/8,解码: Viterbi算法,我们将这些路径称为局部最佳路径, 其对应一个概率. 令 是t时刻达到状态i的所有序列概率中最大的概率. 同样的, 当t=1时, 1 = 1,2020/7/8,解码: Viterbi算法,t1时, 我们考虑如

6、下网络 假如AX这样一条路径, 那么定是 Pr (到达状态A最可能的路径)Pr (X|A)Pr (观察状态|X) 泛化该公式, 即为 = max ( 1 ),2020/7/8,解码: Viterbi算法,我们计算每一步这样的最大值之后, 还需要一个记录这样路径的方式. 定义一个反向指针 =argma x ( 1 ),2020/7/8,解码: Viterbi算法,又叫前向-后向算法, 就是用来估计HMM参数的. 前面的局部概率 ()改名前向变量: = Pr 1 2 , = 类似的定义一个后向变量 = Pr +1 +2 = , . 它可以用类似于前向算法那种递归的方式计算,2020/7/8,学习: Baum-Welch算法,对于给定观察序列O, 没有任何一种方法可以精确的找到一组最优的HMM参数(A, B, )使得Pr(O|). 定义两个变量: =Pr( = |,) , =Pr( = , +1 = |,),2020/7/8,学习: Baum-Welch算法,若对于时间轴t上所有 ()相加,我们可以得到一个总和，它可以被解释为从其他隐藏状态访问 S 的期望值. 相似地, 如果对 , 在时间轴t上求和(从t=1到t=T-1), 那么该和可以