隱馬爾科夫模型(《統(tǒng)計學(xué)習(xí)方法》課件)

1、第十章隱馬爾科夫模型Andrey Markov中文名 馬爾科夫 國籍 俄國 出生地 梁贊 出生日期 1856年6月14日 逝世日期 1922年7月20日 主要成就 開創(chuàng)了隨機(jī)過程這個新領(lǐng)域 HMM應(yīng)用人臉識別語音識別入侵檢測例：隱馬爾可夫模型是關(guān)于時序的概率模型;描述由一個隱藏的馬爾可夫鏈隨機(jī)生成不可觀測的狀態(tài)隨機(jī)序列(state sequence)，再由各個狀態(tài)生成一個觀測而產(chǎn)生觀測隨機(jī)序列(observation sequence )的過程,序列的每一個位置又可以看作是一個時刻。隱馬爾科夫模型的定義組成初始概率分布狀態(tài)轉(zhuǎn)移概率分布觀測概率分布Q：所有可能狀態(tài)的集合V：所有可能觀測的集合I:

2、 長度為T的狀態(tài)序列O：對應(yīng)的觀測序列隱馬爾科夫模型組成A：狀態(tài)轉(zhuǎn)移概率矩陣隱馬爾科夫模型組成B：觀測概率矩陣 ：初始狀態(tài)概率向量隱馬爾科夫模型三要素兩個基本假設(shè)齊次馬爾科夫性假設(shè)，隱馬爾可分鏈t的狀態(tài)只和t-1狀態(tài)有關(guān)：觀測獨立性假設(shè)，觀測只和當(dāng)前時刻狀態(tài)有關(guān)；隱馬爾科夫模型盒子： 1 2 3 4紅球： 5 3 6 8白球： 5 7 4 2轉(zhuǎn)移規(guī)則：盒子1 下一個 盒子2盒子2或3 下一個 0.4 左，0.6右盒子4 下一個 0.5 自身，0.5盒子3 重復(fù)5次： O= 紅，紅，白，白，紅 例：盒子和球模型狀態(tài)集合：Q=盒子1，盒子2，盒子3，盒子4， N=4觀測集合：V=紅球，白球 M=2

3、初始化概率分布：狀態(tài)轉(zhuǎn)移矩陣： 觀測矩陣：例：盒子和球模型觀測序列的生成過程1、概率計算問題 給定： 計算：2、學(xué)習(xí)問題 已知： 估計： ，使 最大3、預(yù)測問題（解碼） 已知： 求：使 最大的狀態(tài)序列 隱馬爾科夫模型的三個基本問題直接計算法給定模型： 和觀測概率：計算：最直接的方法：列舉所有可能的長度為T狀態(tài)序列 ，求各個狀態(tài)序列I與觀測序列 的聯(lián)合概率然后對所有可能的狀態(tài)序列求和，得到概率計算方法直接計算法狀態(tài)序列 概率：對固定的狀態(tài)序列I，觀測序列O的概率：O和I同時出現(xiàn)的聯(lián)合概率為：對所有可能的狀態(tài)序列I求和，得到觀測O的概率：復(fù)雜度概率計算方法前向概率定義：給定隱馬爾科夫模型，定義到時

4、刻t部分觀測序列為： ，且狀態(tài)為qi的概率為前向概率，記作：初值：遞推：終止：前向算法因為：所以：遞推：復(fù)雜度前向算法減少計算量的原因在于每一次計算，直接引用前一個時刻的計算結(jié)果，避免重復(fù)計算。復(fù)雜度前向算法例：例：例：定義10.3 后向概率：給定隱馬爾科夫模型，定義在時刻t狀態(tài)為qi的條件下，從t+1到T的部分觀測序列為： 的概率為后向概率，記作：后向算法后向算法前向后向統(tǒng)一寫為：（ t=1 和t=T-1分別對應(yīng)）后向算法一些概率和期望值的計算一些概率和期望值的計算一些概率和期望值的計算監(jiān)督學(xué)習(xí)方法：假設(shè)訓(xùn)練數(shù)據(jù)是包括觀測序列O和對應(yīng)的狀態(tài)序列I可以利用極大似然估計法來估計隱馬爾可夫模型參數(shù)

5、。非監(jiān)督學(xué)習(xí)方法：假設(shè)訓(xùn)練數(shù)據(jù)只有S個長度為T的觀測序O1,O2,Os,采用Baum-Welch算法學(xué)習(xí)算法監(jiān)督學(xué)習(xí)方法已知：1、轉(zhuǎn)移概率aij的估計：設(shè)樣本中時刻t處于狀態(tài)i，時刻t+1轉(zhuǎn)移到狀態(tài)j的頻數(shù)為Aij，那么狀態(tài)轉(zhuǎn)移概率aij的估計是：監(jiān)督學(xué)習(xí)方法已知：2、觀測概率bj(k)的估計：設(shè)樣本中狀態(tài)為j并觀測為k的頻數(shù)是Bj(k)，那么狀態(tài)為j觀測為k的概率3、初始狀態(tài)概率 的估計 為S個樣本中初始狀態(tài)為qi的頻率。往往人工標(biāo)注數(shù)據(jù)很貴假定訓(xùn)練數(shù)據(jù)只包括O1,O2,Os,求模型參數(shù)=（A,B,)實質(zhì)上是有隱變量的概率模型：EM算法1、確定完全數(shù)據(jù)的對數(shù)似然函數(shù) 完全數(shù)據(jù) 完全數(shù)據(jù)的對數(shù)

6、似然函數(shù) Baum-Welch算法2、EM的E步則：對序列總長度T進(jìn)行Baum Welch算法3、EM算法的M 步，極大化 求模型參數(shù)A,B,第一項：由約束條件： 利用拉格朗日乘子：求偏導(dǎo)數(shù)，并結(jié)果為0 得：Baum Welch算法3、EM算法的M 步，極大化 求A,B,第二項可寫成： 由約束條件 ，拉格朗日乘子法：得：學(xué)習(xí)算法 Baum Welch算法3、EM算法的M 步，極大化 求A,B,第三項：由約束條件： Baum Welch算法將已上得到的概率分別用 表示：學(xué)習(xí)算法 Baum Welch算法 學(xué)習(xí)算法 Baum Welch算法近似算法想法：在每個時刻t選擇在該時刻最有可能出現(xiàn)的狀態(tài)

7、，從而得到一個狀態(tài)序列 ，將它作為預(yù)測的結(jié)果，在時刻t處于狀態(tài)qi的概率：在每一時刻t最有可能的狀態(tài)是：從而得到狀態(tài)序列：得到的狀態(tài)有可能實際不發(fā)生預(yù)測算法Viterbi 方法用動態(tài)規(guī)劃解概率最大路徑，一個路徑對應(yīng)一個狀態(tài)序列。最優(yōu)路徑具有這樣的特性：如果最優(yōu)路徑在時刻t通過結(jié)點 ，那么這一路徑從結(jié)點 到終點 的部分路徑，對于從 到 的所有可能的部分路徑來說，必須是最優(yōu)的。只需從時刻t=1開始，遞推地計算在時刻t狀態(tài)為i的各條部分路徑的最大概率，直至得到時刻t=T狀態(tài)為i的各條路徑的最大概率，時刻t=T的最大概率即為最優(yōu)路徑的概率P*，最優(yōu)路徑的終結(jié)點 也同時得到。之后，為了找出最優(yōu)路徑的各個

8、結(jié)點，從終結(jié)點開始，由后向前逐步求得結(jié)點 ，得到最優(yōu)路徑維特比算法導(dǎo)入兩個變量和，定義在時刻t狀態(tài)為i的所有單個路徑 中概率最大值為：由定義可得變量的遞推公式：定義在時刻t狀態(tài)為i的所有單個路徑中概率最大的路徑的第t-1個結(jié)點為維特比算法Viterbi 方法Viterbi 方法例1、初始化：在t=1時，對每一個狀態(tài)i，i=1,2,3，求狀態(tài)i觀測O1為紅的概率，記為： 代入實際數(shù)據(jù)：例例2、在t=2時，對每一個狀態(tài)i，i=1,2,3，求在t=1時狀態(tài)為j觀測O1為紅并在t=2時狀態(tài)為i觀測O2位白的路徑的最大概率，記為同時，對每個狀態(tài)i，記錄概率最大路徑的前一個狀態(tài)j例3、以P*表示最優(yōu)路徑的

9、概率：最優(yōu)路徑的終點是：4、由最優(yōu)路徑的終點 ，逆向找到 于是求得最優(yōu)路徑，即最優(yōu)狀態(tài)序列：例人臉檢測人臉圖像預(yù)處理光線補償中值濾波歸一化處理人臉檢測人臉識別HMM訓(xùn)練步驟： 對每個人臉建立一個HMM1、人臉特征向量提取2、建立公用的HMM模型3、HMM初始參數(shù)確定4、初始模型參數(shù)訓(xùn)練，主要是運用Viterbi算法訓(xùn)練均勻分割得到參數(shù)，求得最佳分割點，然后重新計算模型初始參數(shù)，直到模型收斂為止。5、 人臉模型訓(xùn)練過程，將(1)中得到的觀測向量代入(4)中得到的模型參數(shù)進(jìn)行訓(xùn)練，使用迭代方法調(diào)整模型參數(shù)達(dá)到最優(yōu)。1、人臉特征向量提?。夯谄娈愔捣纸獾奶卣魈崛‰x散余弦變換多維尺度分析(MDS )

10、人臉等密度線分析匹配方法、彈性圖匹配方法。人臉檢測SVD 穩(wěn)定性：由于奇異值特征向量具有良好的穩(wěn)定性，所以它對圖像噪音、圖像光照條件引起的灰度變化具有不敏感的特性; 轉(zhuǎn)置不變性：A和A轉(zhuǎn)置具有相同的奇異值; 旋轉(zhuǎn)不變性：圖像A和旋轉(zhuǎn)后的圖像有相同的特征向量; 唯一不變性：對矩陣A換兩行或者兩列仍然具有相同的特征向量; 鏡像變換不變形：人臉檢測HMM模型 狀態(tài)人臉檢測人臉檢測人臉檢測3、初始參數(shù)確定： A矩陣：B矩陣：用混合高斯模型，則是將均勻分割后得到的五個部分中的每個部分，使用K均值聚類，將每個狀態(tài)聚成M類，然后分別計算每一類的均值和方差，將這兩個值分別賦給高斯模型。初始模型參數(shù)訓(xùn)練：人臉檢

11、測人臉檢測語音識別語音識別隱馬爾科夫模型在入侵檢測中的應(yīng)用 隱馬爾科夫模型在入侵檢測中的應(yīng)用 兩種正常系統(tǒng)調(diào)用序列數(shù)據(jù)集。Sendmail正常系統(tǒng)調(diào)用序列數(shù)據(jù)集Sendmail的正常訓(xùn)練數(shù)據(jù)集是由1571583個系統(tǒng)調(diào)用構(gòu)成的序列,這些系統(tǒng)調(diào)用分屬147個不同的進(jìn)程(在本實驗中只考慮系統(tǒng)調(diào)用,不考慮進(jìn)程)。Sendmail正常系統(tǒng)調(diào)用序列中包含48個唯一系統(tǒng)調(diào)用,這些系統(tǒng)調(diào)用的調(diào)用號為(按照序列中出現(xiàn)的順序):4,2,66, 138, 5,23,45,27,167, 85,59,105, 104, 106, 56, 19, 155, 83, 93, 94, 112, 100, 50, 128, 89, 121, 11, 1, 40,38,18, 78,101,102,88,95,6,108, 32,1, 8,9, 14,17,3,124,41,61。數(shù)據(jù)集lpr的正常系統(tǒng)調(diào)用序列數(shù)據(jù)集lpr的正常系統(tǒng)調(diào)用序列由2398個系統(tǒng)調(diào)用構(gòu)成,分屬9個進(jìn)程,長度大約是sendmail 正常系統(tǒng)調(diào)用序列的六百五十五分之一。Lpr正常系統(tǒng)調(diào)用序列包含包含37個唯一系統(tǒng)調(diào)用