1、机器学习隐马尔可夫模型目 录 HMM的由来 马尔可夫性和马尔可夫链 HMM实例 HMM的三个基本算法 主要参考文献n1870年，俄国有机化学家Vladimir V. Markovnikov第一次提出马尔科夫模型n马尔可夫模型n马尔可夫链 n隐马尔可夫模型Andrei A Markov Gifted Russian mathematician June 14, 1856 -July 20, 1922 St Petersburg University Doctoral Advisor: Pafnuty ChebyshevAndrei A Markov Research field: number
2、theory continuous fraction theory differential equations probability theory statistics Markov is best known for his work in probability and for stochastic processes especially Markov chains. At the age of 30 Markov became a professor at St. Petersburg University and a member of St. Petersburg Academ
3、y of Sciences More than 120 scientific papers Classical textbook “Calculus of Probabilities”Pafnuty Chebyshev One of the founding fathers of Russian mathematicsHis famous students : Dmitry GraveAleksandr Korkin,Aleksandr Lyapunov Andrei MarkovAccording to the Mathematics Genealogy Project, Chebyshev
4、 has about 4,000 mathematical descendants.His famous work in the field of probability, statistics and number theory 马尔可夫性如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马尔可马尔可夫性夫性,或称此过程为马尔可夫过程马尔可夫过程X(t+1) = f( X(t) )独立事件概率 设想我們再作一连串的实验，而每次实验所可能发生的結果定为 E1,E2, En,。（可能是有限也可能是無限）。每一個結果 Ek，我們若能給定一個出現的可能性 pk（即概率），则对某一特定
5、样本之序列 Ej1 Ej2 Ejn，我們知道它出現的概率是 p(Ej1 Ej2 Ejn) =pj1 pjn。马可夫链 一般及常用的统计中，彼此相互独立大概是最有用的一個观念。用简单的术语來说，互相独立就是彼此毫不相干，一點牵涉都沒有。 但是实际生活中很多事件是相互关联的 不是互相獨立也就是說互相关联的意思，但是要怎样相关呢？如何在相关中作一些简单的分类呢？馬可夫连就是要描述在相关這个概念中最简单的一种。但即使如此，有关马可夫链的理论已经相当丰富了。在概率理論中，它几乎占了绝大的部分。马可夫链 在马可夫鏈中我們考虑最简单的相关性。在在这种情况下，我们不能给任一個事件 Ej 一個概率 pj 但我们
6、给一对事件 (Ej,Ek) 一個概率 pjk，这个时候 pjk 的解释是一种条件概率，就是假设在某次实验中 Ej 已经出现，而在下一次实验中 Ek 出現的概率。除了 pjk 之外，我們还需要知道第一次实验中 Ej 出現的機率 aj。有了这些资料后，一個样本序列 Ej0 Ej1 Ejn（也就是说第零次实验结果是Ej0，第一次一次是 Ej1第 n 次实验是 Ejn）的概率就很清楚的是 P(Ej0,Ej1,Ejn) =aj pj0j1 pj1j2 pjn-1jn。 马尔科夫链 时间时间和状态状态都离散的马尔科夫过程称为马尔科夫链 记作Xn = X(n), n = 0,1,2, 在时间集T1 = 0,
7、1,2,上对离散状态的过程相继观察的结果 链的状态空间记做I = a1, a2, aiR. 条件概率Pij ( m ,m+n)=PXm+n = aj|Xm = ai 为马氏链在时刻m处于状态ai条件下，在时刻m+n转移到状态aj的转移概率转移概率。 Weather: A Markov ModelExample of Markov ModelSnowySunnyRainy60%2%38%20%75%5%80%15%5%Markov Model States: State transition probabilities: represents the probability of moving
8、from state i to state j 12 ,.,NS SS1(|)ijtjtiaP qSqS101;1,1NijijjaaiN:transition probability matrix ijAa Initial state distribution:1iiSqP101,1;1NiijiN Markov Model Begins ( t=1) in some initial state(s). At each time step (t=1,2,) the system moves from current to next state (possibly the same as th
9、e current state) according to transition probabilities associated with current state.( , )AStates: State transition probabilities:Initial state distribution:)05.25.7 . (,snowyrainysunnySSS2 .05.75.02.6 .38.05.15.8 .AWeather Markov Model Given the weather on the first day , what is the probability th
10、at the weather for consecutive six days Basic Calculations-1SnowySunnyRainyRainyRainyt=1 t=2 t=3 t=4 t=5 t=6Snowy0001512. 02 . 002. 06 . 06 . 015. 07 . 0(,|)()(|)(|)(|)(|)(|)sunnyrainyrainyrainysnowysnowysunnyrainysunnyrainyrainyrainyrainysnowyrainysnowysnowyP SSSSSSModelP SP SSP SSP SSP SSP SS Basi
11、c Calculations-2 lGiven that the system is in a known wheather e.g. ,what is the probability that it stays in the same wheather for consecutive d days:iS111111,1111,1 ,.,(|,)(,|) /()(, ,.,|) /()()(|)(|) /()(1)iiiijdiiiNiiiiijijjidNdiiijiijjidiiiiQs s ss sijp Q Model qsp qs Q Modelp qsp qss s ss sMod
12、elp qsp qsp ssp ssp qsaa ( )ip dBasic Calculations-3 Conditioned on starting the weather e.g. , compute the expected number of duration in weather Expected number of consecutive days is 5.1111()(1)1diiiiiiddiiddpddaaa The World is not fully observable!Hidden Markov ModelNot Observable-Hidden60%2%38%
13、20%75%5%80%15%5%Example of Hidden Markov Model50%0%50%60%10%30%65%5%30%HMM实例 Observed Ball SequenceUrn 3Urn 1Urn 2Veil又一个HMM实例HMM实例描述 设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下 根据初始概率分布，随机选择N个缸中的一个开始实验 根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O1，并把球放回缸中 根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。 最后得到一个描述球的颜色的序列O1,O2,，称为观察值序列O。
14、HMM实例约束 在上述实验中，有几个要点需要注意：在上述实验中，有几个要点需要注意： 不能被直接观察缸间的转移不能被直接观察缸间的转移 从缸中所选取的球的颜色和缸并不是从缸中所选取的球的颜色和缸并不是 一一对应的一一对应的 每次选取哪个缸由一组转移概率决定每次选取哪个缸由一组转移概率决定 HMM概念 HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来 观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系 HMM是一个双重随机过程，两个组成部分： 马尔可夫链马尔可夫链：描述状态的转移，用转移概转移概率率描述。 一般随机过程一般随机过程：描述状态与观察序列间的关系， 用
15、观察值概率观察值概率描述。Markov链链（ , A）随机过程随机过程（B）状态序列状态序列观察值序列观察值序列q1, q2, ., qTo1, o2, ., oTHMM的组成示意图的组成示意图HMM组成HMM的基本要素 用模型五元组 （ N, M, ，A，B）用来描述HMM，或简写为 =( ，A，B)HMM可解决的问题 问题1：给定观察序列O=O1,O2,OT,以及模型 , 如何计算P(O|)？ 问题2：给定观察序列O=O1,O2,OT以及模型,如何选择一个对应的状态序列 S = q1,q2,qT，使得S能够最为合理的解释观察序列O？ 问题3：如何调整模型参数 , 使得P(O|)最大？ (
16、, , )A B( , , )A B解决问题1 基础方法 给定一个固定的状态序列S=(q1，q2，q3) 表示在qt状态下观测到Ot的概率 N=5, M=100, = 计算量1072TtTqqqttObObObqOPSOPt121)()()(),/(),/(21)(tqObtS)/(),/()/(所有SPSOPOP解决问题1 前向法 动态规划 定义前向变量 初始化： 递归： 终结：TtqOOOPiittt1)/,()(21TtObiii1)()(11NjTtObaijtjijNiit1 , 11)()()(111NiTiOP1)()/(前向法示意图 1 . t t+1 .a1jt1qN.qi.
17、qj.q1tNtiaNjaij1jt解决问题1 后向法 与前向法类似 定义后向变量 初始化： 递归： 终结：11)/,()(21TtqOOOPiitTtttTtiT11)(NiTTtjObaittNijijt1 , 1,.,2, 1)()()(111NiiOP11)()/(Viterbi算法算法 目的：给定观察序列O以及模型,如何选择一个对应的状态序列S ，使得S能够最为合理的解释观察序列O？ N和T分别为状态个数和序列长度定义：我们所要找的，就是T时刻最大的 所代表的那个状态序列1211211,2,.( )max.,| tttttq qqiP q qqqi O OO( )TiViterbi算
18、法算法(续续) 初始化： 递归： 终结： 求S序列：Ni1, 0)(Ni1),()(111iObiiiNjTtaijNjTtObaijijtNitijijtNit1 ,2,)(maxarg)(1 ,2),()(max)(1111)(maxarg)(max1*1*iqiPTNiTTNi1,.,2, 1),(*11*TTtqqtttBaum-Welch算法算法(模型训练算法模型训练算法) 目的：给定观察值序列O，通过计算确定一个模型 ， 使得P(O| )最大。 算法步骤：1. 初始模型（待训练模型） 0,2. 基于0 以及观察值序列O，训练新模型 ；3. 如果 log P(X|) - log(P(
19、X|0) Delta，说明训练已经达到预期效果， 算法结束。4. 否则，令0 ，继续第2步工作 Baum-Welch算法算法(续续) 定义：1111111i11i1ij( , )( , )(,|, )( )()( )( )()( )( )( , )S( )S( , )tttttijjttNNtijjttijNttjTttti ji jP si sj Xi a b Oji a bxjii jtii j给定模型 和观察序列条件下，从 到 的转移概率定义为时刻处于状态 的概率整个过程中从状态转出的次数(number of time)的预期1ij1SSTt从跳转到次数的预期Baum-Welch算法算法
20、(续续2) 参数估计：,Oexpectednumberoftimesinstateandobservingsymbol( )expectednumberoftimesinstate( )( )tjttkttjkb kjjjReestimate :expected count of transitions from i to jexpected count of stays at i( , )( , )ijttttjai ji j1t1( )iiSi当 时 处 于的 概 率几种典型形状的马尔科夫链HMM的应用领域 语音识别 机器视觉 人脸检测 机器人足球 图像处理 图像去噪 图像识别 生物医学分
21、析 DNA/蛋白质序列分析作业作业4 States: Observations: State transition probabilities: emission probability : Initial state distribution:,snowyrainysunnySSS,skirtcoatumbrellaOOO2 .05.75.02.6 .38.05.15.8 .A5 .5 .065.3 .05.1 .3 .6 .B)05.25.7 . ( Given:O: 1. 出现次序列的概率为多少出现次序列的概率为多少(前向算法前向算法)? 2. 此序列对应的天气状况序列是什么此序列对应的天气状况序列是什么? 问题问题:个人收集整理，仅供交流学习！
