Machine Learning for
Control Engineering
马尔可夫链
一个系统有N个状态 S1，S2，· · · ，Sn，随着时间推移，系 统从某一状态转移到另一状态，设qt为时刻t的状态，系统在时 刻t处于状态Sj 的概率取决于其在时间 1 ，2，· · · ，t-1 的状态， 该概率为： 如果系统在t时间的状态只与其在时间 t -1的状态相关，则 该系统构成一个离散的一阶马尔可夫链(马尔可夫过程)：
主要内容
• • • • 马尔可夫模型 隐马尔可夫模型 隐马尔可夫模型的三个基本问题 三个基本问题的求解算法
1.前向算法 2.Viterbi算法 3.向前向后算法
• 隐马尔可夫模型的应用 • 隐马尔可夫模型的一些实际问题 • 隐马尔可夫模型总结
Machine Learning
Peng Kaixiang 2014. All rights reserved. Date: File: 15.10.2018 ML11.2
令 O = O1,...,OT 为观测值序列，则有关于隐马尔可 夫模型（HMM）的三个基本问题： 1.评估问题：对于给定模型，求某个观测值序列的概 率P(O|λ) ；
2.解码问题：对于给定模型和观测值序列，求可能性 最大的状态序列maxQ{P(Q|O,λ)}； 3.学习问题：对于给定的一个观测值序列O，调整参数 λ，使得观测值出现的概率P(O|λ)最大。
Peng Kaixiang 2014. All rights reserved.
Date: File:
15.10.2018 ML11.6
Machine Learning for
Control Engineering
例（续）
如果第一天为晴天，根据这一模型，在今后七天中天气为 O=“晴晴雨雨晴云晴”的概率为：
Machine Learning for
Control Engineering
T 1
T 1
Date: File:
15.10.2018 ML11.9
隐马尔可夫模型
• 在MM中，每一个状态代表一个可观察的 事件 • 在HMM中观察到的事件是状态的随机函数， 因此该模型是一双重随机过程，其中状态转移 过程是不可观测（隐蔽）的(马尔可夫链)，而 可观测的事件的随机过程是隐蔽的状态转换过 程的随机函数(一般随机过程)。
Machine Learning
Peng Kaixiang 2014. All rights reserved. Date: File: 15.10.2018 ML11.15
Machine Learning for
Control Engineering
状态转移概率矩阵
Machine Learning
Peng Kaixiang 2014. All rights reserved.
Date: File:
15.10.2018 ML11.16
Machine Learning for
Control Engineering
观察值概
Peng Kaixiang 2014. All rights reserved.
Peng Kaixiang 2014. All rights reserved.
Date: File:
15.10.2018 ML11.13
Machine Learning for
Control Engineering
HMM的三个假设
对于一个随机事件，有一观察值序列： O=O1,O2,…OT 该事件隐含着一个状态序列： Q = q1,q2,…qT。 假设1：马尔可夫性假设（状态构成一阶马尔可夫链） P(qi|qi-1…q1) = P(qi|qi-1)
Machine Learning for
Control Engineering
观察序列产生步骤
• 给定HMM模型 λ = (A， B， π) ，则观察序列 O=O1,O2,…,OT 可由以下步骤产生： • 1.根据初始状态概率分布π= πi,选择一初始状态 q1=Si； • 2.设t=1； • 3.根据状态 Si的输出概率分布bjk,输出Ot=vk； • 4.根据状态转移概率分布aij,转移到新状态 qt+1=Sj； • 5.设t=t+1,如果t<T，重复步骤3、4，否则结束。
k ( q 1 Si ) k
K
• 转移概率的估计：
#{Si到S j的移} ) aij ＝ ＃{Si移}
Machine Learning
Peng Kaixiang 2014. All rights reserved.
k k ( q S andq t i t 1 S j ) k t 1 k ( q t Si ) k t 1
第9章 隐马尔可夫模型
(Hidden Markov Models)
Machine Learning
Peng Kaixiang 2014. All rights reserved.
Date: File:
15.10.2018 ML11.1
Machine Learning for
Control Engineering
Peng Kaixiang 2014. All rights reserved.
Date: File:
15.10.2018 ML11.8
Machine Learning for
Control Engineering
如何学习得到π、A
• 给定K个长度为T的序列，初始概率估计：
#{以Si 始的序列} i ＝ #{序列} )
即：给定当前的状态，未来的系统状态独立于过去的状态
Machine Learning
Peng Kaixiang 2014. All rights reserved. Date: File: 15.10.2018 ML11.3
Machine Learning for
Control Engineering
Machine Learning
Peng Kaixiang 2014. All rights reserved. Date: File: 15.10.2018 ML11.20
Machine Learning for
Control Engineering
公平骰子A与灌铅骰子B的区别:
骰子A 骰子B
1点 2点 3点 4点 5点 6点
i P(q1 Si )
• 有:

i 1
N
i
1
• 若有一可观测序列O，它是状态序列O=Q= ｛q1,q2,q3,…,qT｝的概率为：
P(O Q | A, ) P(q1 ) P(qt | qt 1 ) q1aq1q 2 ...aqT 1qT
i 2 N
Machine Learning
Date: File:
15.10.2018 ML11.5
Machine Learning for
Control Engineering
例：
假定一段时间的气象可由一个三状态的马 尔可夫模型M描述，S1：下雨，S2：多云，S3： 晴天，状态转移概率矩阵为：
下雨 多云 晴天
Machine Learning
Machine Learning for
Control Engineering
马尔可夫模型可视为随机有限状态自动机
• 该有限状态自动机的每一状态转换都有一相应 概率，表示自动机采样这状态转换的可能性
Machine Learning
Peng Kaixiang 2014. All rights reserved.
Machine Learning
Peng Kaixiang 2014. All rights reserved. Date: File: 15.10.2018 ML11.10
Machine Learning for
Control Engineering
实例
一房间有N只容器，每只容器中有M种不同颜色 的球。根据某一概率分布随机地选择一个初始容器， 根据不同颜色球的概率分布从中随机取出一个球，并 报告球的颜色。然后根据某一概率分布随机地选择另 一只容器，再根据不同颜色球的概率分布从中随机取 出一个球，并报告球的颜色，⋯。对房间外的观察者， 可观察的过程是不同颜色球的序列，而容器的序列是 不可观察的。 这里每只容器对应HMM模型中的状态，球的颜 色对应于状态的输出符号，从一只容器转向另一只容 器对应于状态转换，从一只容器中取球对应于从一状 态输出观察符号。
Date: File:
15.10.2018 ML11.12
Machine Learning for
Control Engineering
实验中几个要点
不能直接观察容器间的转移； 从容器中所选取的球的颜色和容器并不是一一 对应的； 每次选取哪个容器由一组转移概率决定。
Machine Learning
Machine Learning
Peng Kaixiang 2014. All rights reserved. Date: File: 15.10.2018 ML11.11
Machine Learning for
Control Engineering
实例（续）
Machine Learning
Peng Kaixiang 2014. All rights reserved.
马尔可夫模型
如果只考虑独立于时间t的随机过程：
ai , j
其中状态转移概率 aij 必须满足 aij>=0 , 且 ，则该随机过程称为马尔可夫模型。 独立于时间t：从状态Si到状态Sj的状态转移具有相同 的概率，无论这个转移在观测序列中的何时或何地发生。