隐马尔科夫

隐马尔科夫过程HiddenMarkovModel，HMM小组成员：SX1504059梅晟SX1504058席艺SX1504068董莉SZ1504020刘叶CONTENTPartOne马尔科夫过程.PartTwo隐马尔科夫过程.PartThree解决算法PartFour拓展应用CONTENTPartOne马尔科夫过程.PartTwo隐马尔科夫过程.PartThree解决算法PartFour拓展应用马尔科夫过程1一个系统，在每个时刻都可能处于N个状态中的一个，N个状态集合是{S1,S2,S3,...SN}。我们现在用q1,q2,q3,…qn来表示系统在t=1,2,3,…n时刻下的状态。在t=1时，系统所在的状态q取决于一个初始概率分布PI，PI(Si)表示t=1时系统状态为Si的概率。马尔科夫过程可以看做是一个自动机，以一定的概率在各个状态之间跳转。1马尔科夫模型有两个性质：1.系统在时刻t的状态只与时刻t-1处的状态相关（无后效性）P(qt=Sj|qt-1=Si,qt-2=Sk,…)=P(qt=Sj|qt-1=Si)其中，t为大于1的任意数值，Sk为任意状态2.状态转移概率与时间无关（齐次性或时齐性）P(qt=Sj|qt-1=Si)=P(qk=Sj|qk-1=Si)其中，k为任意时刻。马尔科夫过程CONTENTPartOne马尔科夫过程.PartTwo隐马尔科夫过程.PartThree解决算法PartFour拓展应用隐马尔科夫也比马尔科夫多了一个假设（输出独立性假设），即输出的观察状态仅与当前状态有关，可以用如下公式表示：P(O1,O2,…,Ot|S1,S2,…,St)=P(O1|S1)*P(O2|S2)*...*P(Ot|St)其中，O1,O2,…,Ot为从时刻1到时刻t的观测状态序列，S1,S2,…,St则为隐藏状态序列。隐马尔科夫过程隐藏状态观察状态举例隐马尔科夫过（HMM）2我会在不同天气状态下去做不同事情，做这些事情的概率也不尽相同，天气状态集合为{下雨，阴天，晴天}，事情集合为{宅着，自习，游玩}。假如已知转移概率、输出概率、天气的初始概率，即P(天气A|天气B)、P(事情a|天气A)、P(天气A)那么则有几个问题要问：4.假如我这一周做事序列是自习-宅着-游玩-自习-游玩-宅着-自习，那么这一周的天气变化序列最有可能是什么？1.假如一周内的天气变化是下雨-晴天-阴天-下雨-阴天-晴天-阴天，那么我这一周自习-宅着-游玩-自习-游玩-宅着-自习的概率是多大？2.假如我这一周做事序列是自习-宅着-游玩-自习-游玩-宅着-自习，不知道天气状态的情况下这个做事序列的概率是多大？3.假如一周内的天气变化是下雨-晴天-阴天-下雨-阴天-晴天-阴天，那我这一周最有可能的做事序列是什么？样例问题42基本要素五元组S：隐藏状态集合（天气情况）O：观察状态集合（我的行为）A：隐藏状态间的转移概率(P(天气A|天气B))B：隐藏状态到输出状态的概率（P(事情a|天气A)）PI：初始概率分布（隐藏状态的初始概率分布）基本问题1.给定HMM模型（五元组），求某个观察序列O的概率2.给定HMM模型和观察序列O，求可能性最大的隐藏状态序列3.对于给定的观察序列O，调整HMM的参数，使观察序列出现的概率最大样例问题2隐马尔科夫过（HMM）CONTENTPartOne马尔科夫过程.PartTwo隐马尔科夫过程.PartThree解决算法PartFour拓展应用解决算法31、给定HMM模型（五元组），求某个观察序列O的概率2、给定ＨＭＭ模型和观察序列O，求可能性最大的隐藏状态序列3、对于给定的观察序列O，调整HMM的参数，使观察序列出现的概率最大维特比算法前向算法3前向算法给定模型（五元组），求某个观察序列O的概率分析：对于观察序列O，我们需要找出所有可能的隐藏状态序列S，计算出在给定模型下隐藏状态为S输出为O的概率（就是样例问题一啊），然后计算概率之和。直观上看，假如序列O的长度为T，模型的隐藏状态集合大小为N，那么一共有NT个可能的隐藏状态序列，计算复杂度极高O(NT)，暴力算法太慢了。解决算法3前向算法解决方案：动态规划（DynamicProgramming）假设观察序列为O1,O2,O3,….,Ot.在时刻i（1i=t）时，定义C为产生序列O1,O2,…,Oi且Si=Sk的概率为：其中，Sk为任意一个隐藏状态值。则C(i+1,Sr)的计算公式为：其中，Sr为任意一个隐藏状态值。A为转移概率。B为隐藏状态到观察状态的概率。解决算法给定模型（五元组），求某个观察序列O的概率3C(3,下雨)同时也是C(4,下雨|阴天|晴天)的子问题。C(3,下雨)考虑了t=1和t=2的所有组合情况。在不同天气状态下去做一些事情的概率不同，天气状态集合为{下雨，阴天，晴天}，事情集合为{宅着，自习，游玩}。已知转移概率和输出概率，即P(天气A|天气B)和P(事情a|天气A)。解决算法3从该图可看出C(i+1,Sr)的计算公式利用前向算法我们能够在不知道隐藏状态的情况下求解出某个观察序列的概率，完美解决了基本问题中的第一个C(4,阴天)=[C(3,下雨)*A(下雨,阴天)+C(3,阴天)*A(阴天,阴天)+C(3,晴天)*A(晴天,阴天)]*B(阴天,自习)解决算法3维特比算法给定HMM模型和观察序列O，求可能性最大的隐藏状态序列解决方案：动态规划（DynamicProgramming）假设观察序列为O1,O2,O3,….,Ot.在时刻i（1i=t）时，定义D为观察O1,O2,…,Oi且Si=Sk时产生该观察序列的最大概率其中，S1,S2,….Si-1在此时产生的概率也已经可以得到：解决算法译码3维特比算法给定模型和观察序列O，求可能性最大的隐藏状态序列解决算法CONTENTPartOne马尔科夫过程.PartTwo隐马尔科夫过程.PartThree解决算法PartFour拓展应用评估(Evaluation)解码(Decoding)学习(Learning)评估哪一个HMM最有可能产生了这个给定的观察序列。我们使用前向算法来计算给定隐马尔科夫模型后的一个观察序列的概率，并因此选择最合适的隐马尔科夫模型。给定观察序列搜索最可能的隐藏状态序列。我们使用Viterbi算法确定(搜索)已知观察序列及HMM下最可能的隐藏状态序列。根据观察序列生成隐马尔科夫模型。当转移矩阵不能够直接被(估计)测量时，前向-后向算法被用来进行学习(参数估计)。拓展应用4输入法的整句解码输入法把拼音看做是观察状态，需要得到的汉字为隐藏状态，这样，输入法的整句解码就变成了维特比解码，其转移概率即是二元语言模型，其输出概率即是多音字对应不同拼音的概率。ThankyouforwatchingDesignedbyjourney