02 隱馬爾可夫模型 - HMM的三個問題 - 概率計算問題

HMM案例回顧：

假設(shè)有三個盒子，編號為1,2,3；每個盒子都裝有黑白兩種顏色的小球餐曼，球的比例。如下：

按照下列規(guī)則的方式進行有放回的抽取小球鲜漩，得到球顏色的觀測序列：
1源譬、按照π的概率選擇一個盒子，從盒子中隨機抽取出一個球孕似，記錄顏色后放回盒子中踩娘；
2、按照某種條件概率選擇新的盒子喉祭，重復(fù)該操作养渴；
3雷绢、最終得到觀測序列：“白黑白白黑”

例如： 每次抽盒子按一定的概率來抽，也可以理解成隨機抽理卑。
第1次抽了1號盒子①翘紊，第2次抽了3號盒子③，第3次抽了2號盒子②.... 藐唠；最終如下：
①→③→②→②→③ 狀態(tài)值
白→黑→白→白→黑觀測值

1帆疟、狀態(tài)集合： S={盒子1，盒子2宇立，盒子3}
2踪宠、觀測集合： O={白，黑}
3泄伪、狀態(tài)序列和觀測序列的長度 T=5 (我抽了5次)
4殴蓬、初始概率分布： π 表示初次抽時，抽到1盒子的概率是0.2蟋滴，抽到2盒子的概率是0.5，抽到3盒子的概率是0.3痘绎。
5津函、狀態(tài)轉(zhuǎn)移概率矩陣 A：a11=0.5 表示當前我抽到1盒子，下次還抽到1盒子的概率是0.5孤页；
6尔苦、觀測概率矩陣 - 混淆矩陣 - 為了不和之前的混淆矩陣概念沖突，可以稱之為發(fā)射矩陣行施，即從一個狀態(tài)發(fā)射到另一個狀態(tài)： B：如最初的圖允坚，b11=第一個盒子抽到白球概率0.4，b12=第一個盒子抽到黑球概率0.6;

HMM案例思考

在給定參數(shù)π蛾号、A稠项、B的時候，得到觀測序列為“白黑白白黑”的概率是多少?

這個時候鲜结，我們不知道隱含條件展运，即不知道狀態(tài)值：①→③→②→②→③ ；
我們?nèi)绾胃鶕?jù)π精刷、A拗胜、B求出測序列為“白黑白白黑”的概率？
下面給出解決方案怒允。

引入HMM的三個問題：

$\color{red}{1埂软、概率計算問題:}$
前向-后向算法 給定模型λ=(A,B,π)和觀測序列Q={q1,q2,...,qT}，計算模型λ下觀測到序列Q出現(xiàn)的概率P(Q|λ)纫事；

回顧上面的案例勘畔，λ=(A,B,π)已知迷殿。觀測到序列 Q=白→黑→白→白→黑，但我們不知道 狀態(tài)序列 I=①→③→②→②→③咖杂；我們要求解P(Q|λ)庆寺，即Q=白→黑→白→白→黑這個觀測序列發(fā)生的概率。可以用前向-后向算法來實現(xiàn)诉字。

$\color{red}{2懦尝、學(xué)習問題:}$
Baum-Welch算法(狀態(tài)未知) 已知觀測序列Q={q1,q2,...,qT}，估計模型λ=(A,B,π)的參數(shù)壤圃，使得在該模型下觀測序列P(Q|λ)最大陵霉。

Baum-Welch算法是EM算法的一個特例，專門用來求解隱馬爾科夫中隱狀態(tài)參數(shù)λ=(A,B,π)伍绳。即：根據(jù)已知的觀測到序列 Q=白→黑→白→白→黑踊挠，去尋找整個模型的一組隱狀態(tài)參數(shù)λ=(A,B,π)，使得在模型中觀測序列發(fā)生的可能性P(Q|λ)最大冲杀。

$\color{red}{3效床、預(yù)測問題：}$
Viterbi算法 給定模型λ=(A,B,π)和觀測序列Q={q1,q2,...,qT}，求給定觀測序列條件概率P(I|Q权谁，λ)最大的狀態(tài)序列I剩檀。

已知觀測到序列 Q=白→黑→白→白→黑，當我們得到λ=(A,B,π)后旺芽，我們用Viterbi算法 求出在哪一種狀態(tài)序列發(fā)生的可能性最大沪猴，即，求出狀態(tài)序列 I=①→③→②→②→③采章；即运嗜，抽取什么樣的盒子順序，更可能得到白→黑→白→白→黑這種結(jié)果悯舟。

$\color{red}{請先理解算法思路担租，再進入下面HMM三問題的算法學(xué)習。}$

六图谷、HMM的三個問題 - 概率計算問題

1翩活、直接計算法(暴力算法)
2、前向算法
3便贵、后向算法

1菠镇、直接計算法(暴力算法)

類似KNN計算最近鄰時候的算法〕辛В《01 KNN算法 - 概述》
也就是說利耍，暴力算法需要一個個遍歷所有的狀態(tài)去計算當前狀態(tài)發(fā)生的概率。

按照概率公式，列舉所有可能的長度為T的狀態(tài)序列I={i1,i2,...,iT}隘梨，求各個狀態(tài)序列I與觀測序列Q={q1,q2,...,qT}的聯(lián)合概率P(Q,I;λ)程癌，然后對所有可能的狀態(tài)序列求和，從而得到最終的概率P(Q;λ)轴猎；

分析： 先思考這樣一個問題：生成“白-黑-白-白-黑”這樣的結(jié)果嵌莉，是不是會有很多種盒子組合的序列來抽取，都會生成這樣一個結(jié)果捻脖？我把這些可能出現(xiàn)“白-黑-白-白-黑”結(jié)果的盒子序列的聯(lián)合概率求出來-P(Q,I;λ)锐峭，即∑P(Q,I) = P(Q) ，P(Q) 是我們觀測到“白-黑-白-白-黑”結(jié)果時可婶，符合這個結(jié)果的所有狀態(tài)序列I出現(xiàn)的概率沿癞。

公式運用：

$\color{red}{步驟1：求各個狀態(tài)序列I與觀測序列Q={q1,q2,...,qT}的聯(lián)合概率P(Q,I;λ)；}$
設(shè)狀態(tài)序列 I=③→②→①→①→②矛渴； T=5椎扬；
P(I;λ) = π₃a₃₂a₂₁a₁₁a₁₂

因為：在給定狀態(tài)序列I后，Q中的每個觀測值都獨立具温。（貝葉斯網(wǎng)絡(luò)原理）貝葉斯網(wǎng)絡(luò)
所以： P(Q|I;λ)可以用聯(lián)乘的方式表示 (獨立可以使用聯(lián)合概率)
I = ③→②→①→①→②
Q=白→黑→白→白→黑
P(Q|I;λ) = b_3白b_2黑b_1白b_1白b_2黑

P(Q,I;λ) = P(Q|I;λ) × P(I;λ)
= b_3白b_2黑b_1白b_1白b_2黑 × π₃a₃₂a₂₁a₁₁a₁₂

$\color{red}{步驟2：對所有可能的狀態(tài)序列求和蚕涤，從而得到最終的概率P(Q;λ)；}$
若：
I₁ = ③→②→①→①→②
I₂ = ①→②→③→①→②
...
I_T = ②→②→①→③→②
都能得出：
Q = 白→黑→白→白→黑
因為我所有的盒子都能取出黑球和白球桂躏，所以T的值=3⁵;

∑P(Q,I;λ) 計算的是 I₁ ~ I_T 這些狀態(tài)序列情況下钻趋，求出的P(Q,I;λ)的和。

結(jié)論：暴力計算法的計算量非常龐大剂习。

2、前向概率-后向概率

前向和后向算法是運用某種遞歸(遞推)的方式较沪，幫助我們盡快得求解最終結(jié)果鳞绕。

前向概率-后向概率

解析: 如果 t 這一時刻觀察到的狀態(tài)是 q_t = 雨天；其中y={干尸曼，濕们何，濕... 濕}共t個狀態(tài)。
先不考慮λ控轿。
α_t 是1時刻~t時刻 所有觀測值y1冤竹，y2，...yt 茬射，qt 出現(xiàn)的聯(lián)合概率鹦蠕。
β_t 是t+1時刻~T時刻 所有觀測值y_t+1，y_t+2在抛，...y_T出現(xiàn)的聯(lián)合概率钟病。

解析

前向概率-后向概率指的其實是在一個觀測序列中，時刻t對應(yīng)的狀態(tài)為si的概率值轉(zhuǎn)換過來的信息。

先不考慮λ

分析2~3步的推導(dǎo)： 因為q₁ ~ q_t 這些條件對 q_t+1 ~ q_T的產(chǎn)生沒有影響 (理由：貝葉斯網(wǎng)絡(luò))肠阱，所以這些條件可以去掉票唆。

結(jié)合上面的公式，回顧該圖

2.1 前向算法：

定義：給定λ屹徘，定義到時刻t部分觀測序列為q1,q2,...,qt且狀態(tài)為si的概率為前向概率走趋。
記做：

2.2 HMM案例-前向算法：

在給定參數(shù)π、A噪伊、B的時候簿煌，得到觀測序列為“白黑白白黑”的概率是多少?

2.3 后向算法

定義：給定λ，定義到時刻t狀態(tài)為si的前提下酥宴，從t+1到T部分觀測序列為qt+1,qt+2,...,qT的概率為后向概率啦吧。
記做：

分析上面的公式：
如果一共只有t個時間點，t+1的時刻不存在拙寡。那么t+1以后發(fā)生的是必然事件授滓。
所以 β_t(i) = P(q_t+1，q_t+2肆糕，...般堆，q_T) = 1;
如果實在不理解也沒關(guān)系，我們姑且認為認為定義了一個初始值诚啃，即β_T(i) = 1淮摔；

$\color{red}{然后我們要一步步得往前去推導(dǎo)。}$ 從T-1時刻始赎，倒推到1時刻和橙。
首先，β_t+1(j)是什么造垛？是t+1時刻魔招，在狀態(tài)sj的前提下，下圖中圈起來這部分的聯(lián)合概率五辽。