HMM的細(xì)致推導(dǎo)（下）

解碼

HMM的隱鏈的狀態(tài)在很多情況下都是我們關(guān)心的量，甚至是我們構(gòu)建模型的目標(biāo)；例如：在分詞和語音識別中就是如此隔箍。關(guān)于這個任務(wù)，也有個經(jīng)典的高效算法脚乡，稱為Viterbi算法蜒滩。

給定模型參數(shù)，給定觀測序列 $X = (o_1, ..., o_N)$ 俯艰，我們想要求出與之對應(yīng)的最可能的隱狀態(tài)序列 $Z = (q_1,...,q_N)$ ，即求 $\argmax_{(q_1,...,=q_N)} p(\boldsymbol Z=(q_1,...,=q_N) | \boldsymbol X=(o_1,...o_N))$ 锌订，其中 $q_i,i=1,...,N$ 為鏈的狀態(tài)序列竹握，在 $\{ 1,...,K\}$ 中取值。

因為我們的概率模型是關(guān)于隱變量 $\boldsymbol {\rm Z}$ 和觀測變量 $\boldsymbol {\rm X}$ 的聯(lián)合概率分布辆飘，因此我們希望引入 $p(\boldsymbol {\rm X},\boldsymbol{\rm Z}; \boldsymbol \theta)$ 啦辐，顯然可以由貝葉斯公式得到：

$\begin{aligned}& {\rm argmax}_{(q_1,...,q_N)} p(\boldsymbol Z=(q_1,...,q_N) | \boldsymbol X=(o_1,...o_N)) \\=\ & {\rm argmax}_{(q_1,...,q_N)} \frac{p(\boldsymbol Z=(q_1,...,q_N) , \boldsymbol X=(o_1,...o_N))} {p(\boldsymbol X=(o_1,...o_N))} \\=\ & {\rm argmax}_{(q_1,...,q_N)} p(\boldsymbol Z=(q_1,...,q_N) , \boldsymbol X=(o_1,...o_N))\end{aligned}$

Viterbi算法分為兩步，先計算出 $\max_{(q_1,...,q_N)} p(\boldsymbol Z=(q_1,...,q_N) ,\boldsymbol X=(o_1,...o_N))$ 蜈项，再逆向得到最優(yōu)路徑 $(q_1^*, ..., q_N^*)$ 芹关。為了在第一步中高效地計算出最大概率，先要定義遞歸變量 $\delta(n, j)$ 紧卒，為了使得公式稍微簡介一些侥衬，引入記號：

$\begin{aligned}& \boldsymbol {\rm Z}_{1...n}= (\boldsymbol {\rm z}_1,...,\boldsymbol {\rm z}_n)\\&Q_{1...n} = (q_1,...,q_n)\\&\boldsymbol {\rm X}_{1...n}= (\boldsymbol {\rm x}_1,...,\boldsymbol {\rm x}_n)\\&O_{1...n}=(o_1,...,o_n)\end{aligned}$

則遞歸變量的定義 $\delta(n,j)$ 為:

$\delta(n,j) = \max_{(q_1,...,q_{n-1})} {\rm P} \{ \boldsymbol {\rm Z}_{1...{n-1}}=Q_{1...n-1}, \boldsymbol {\rm X}_{1...n}= O_{1...n}, \boldsymbol {\rm z}_n = j \}$

用語言敘述即： $\delta(n,j)$ 是在遍歷前 $n-1$ 時間步所有狀態(tài)路徑時，看到觀測 $O_{1...n-1}$ 跑芳，并最終在時間步 $n$ 處于狀態(tài) $j$ 進(jìn)而觀測到 $o_n$ 的最大概率浇冰。下面推導(dǎo)變量 $\delta(n,j)$ 的遞歸表達(dá)式：

$\begin{aligned}\delta(n,j) &= \max_{(q_1,...,q_{n-1})} {\rm P} \{ \boldsymbol {\rm Z}_{1...{n-1}}=Q_{1...n-1}, \boldsymbol {\rm X}_{1...n}= O_{1...n}, \boldsymbol {\rm z}_n = j \} \\&= \max_{(q_1,...,q_{n-1})} {\rm P} \{ \boldsymbol {\rm Z}_{1...{n-2}}=Q_{1...n-2}, \boldsymbol {\rm X}_{1...n-1}= O_{1...n-1}, \boldsymbol {\rm z}_{n-1}=q_{n-1}, \boldsymbol {\rm x}_{n}=o_{n}, \boldsymbol {\rm z}_n = j \} \\&= \max_{(q_1,...,q_{n-1})} {\rm P} \{ \boldsymbol {\rm Z}_{1...{n-2}}=Q_{1...n-2}, \boldsymbol {\rm X}_{1...n-1}= O_{1...n-1} | \boldsymbol {\rm z}_{n-1}=q_{n-1}, \boldsymbol {\rm x}_{n}=o_{n}, \boldsymbol {\rm z}_n = j\} \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdot {\rm P}\{ \boldsymbol {\rm x}_{n}=o_{n} | \boldsymbol {\rm z}_{n-1}=q_{n-1}, \boldsymbol {\rm z}_n = j \} \\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdot {\rm P}\{ \boldsymbol {\rm z}_n = j | \boldsymbol {\rm z}_{n-1}=q_{n-1} \} \cdot {\rm P}\{\boldsymbol {\rm z}_{n-1}=q_{n-1} \} \end{aligned}$

到目前為止，只是簡單地應(yīng)用了事件的概率乘法法則將其展開聋亡，看起來比較麻煩的式子肘习。注意到，這里有意分解出了一個遞歸項：

${\rm P} \{ \boldsymbol {\rm Z}_{1...{n-2}}=Q_{1...n-2}, \boldsymbol {\rm X}_{1...n-1}= O_{1...n-1} | \boldsymbol {\rm z}_{n-1}=q_{n-1}, \boldsymbol {\rm x}_{n}=o_{n}, \boldsymbol {\rm z}_n = j\}$

下面我們就可以應(yīng)用一系列條件獨立性將其化簡坡倔，包括：

$\begin {aligned}& {\rm P} \{ \boldsymbol {\rm Z}_{1...{n-2}}=Q_{1...n-2}, \boldsymbol {\rm X}_{1...n-1}= O_{1...n-1} | \boldsymbol {\rm z}_{n-1}=q_{n-1}, \boldsymbol {\rm x}_{n}=o_{n}, \boldsymbol {\rm z}_n = j\} \\& = {\rm P} \{ \boldsymbol {\rm Z}_{1...{n-2}}=Q_{1...n-2}, \boldsymbol {\rm X}_{1...n-1}= O_{1...n-1} | \boldsymbol {\rm z}_{n-1}=q_{n-1} \} \\ \\& {\rm P}\{ \boldsymbol {\rm x}_{n}=o_{n} | \boldsymbol {\rm z}_{n-1}=q_{n-1}, \boldsymbol {\rm z}_n = j \} = {\rm P}\{ \boldsymbol {\rm x}_{n}=o_{n} | \boldsymbol {\rm z}_{n}=j \} \end{aligned}$

代入到上面的 $\delta(n,j)$ 中得到：

$\begin {aligned}\delta(n,j) &= \max_{(q_1,...,q_{n-1})} {\rm P} \{ \boldsymbol {\rm Z}_{1...{n-2}}=Q_{1...n-2}, \boldsymbol {\rm X}_{1...n-1}= O_{1...n-1} | \boldsymbol {\rm z}_{n-1}=q_{n-1} \} \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdot {\rm P}\{ \boldsymbol {\rm x}_{n}=o_{n} | \boldsymbol {\rm z}_{n}= j \} \cdot {\rm P}\{ \boldsymbol {\rm z}_n = j | \boldsymbol {\rm z}_{n-1}=q_{n-1} \} \cdot {\rm P}\{\boldsymbol {\rm z}_{n-1}=q_{n-1} \} \\&=\max_{q_{n-1}} (\max_{(q_1,...,q_{n-2})} {\rm P} \{ \boldsymbol {\rm Z}_{1...{n-2}}=Q_{1...n-2}, \boldsymbol {\rm X}_{1...n-1}= O_{1...n-1} , \boldsymbol {\rm z}_{n-1}=q_{n-1} \} ) \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdot {\rm P}\{ \boldsymbol {\rm x}_{n}=o_{n} | \boldsymbol {\rm z}_{n}= j \} \cdot {\rm P}\{ \boldsymbol {\rm z}_n = j | \boldsymbol {\rm z}_{n-1}=q_{n-1} \} \\&= \max_{q_{n-1}} \delta(n-1, q_{n-1}) \cdot {\rm P}\{ \boldsymbol {\rm x}_{n}=o_{n} | \boldsymbol {\rm z}_{n}= j \} \cdot {\rm P}\{ \boldsymbol {\rm z}_n = j | \boldsymbol {\rm z}_{n-1}=q_{n-1} \} \\\end{aligned}$

這里的 $q_{N-1}\in \{1,...,K\}$ 漂佩，不妨用整數(shù) $k$ 來代替脖含；回想前面定義的轉(zhuǎn)移概率和觀測概率，有 ${\rm P}\{ \boldsymbol {\rm z}_n = j | \boldsymbol {\rm z}_{n-1}=k \} =a_{kj}投蝉， {\rm P}\{ \boldsymbol {\rm x}_{n}=o_{n} | \boldsymbol {\rm z}_{n}=j \} =p(o_{n}| \boldsymbol \phi_j)$ 养葵，所以：

$\begin{aligned}\delta(n, j) &= \max_{k} \delta(n-1, k) \cdot a_{kj} \cdot p(o_{n} | \boldsymbol \phi_j) \\&=p(o_{n} | \boldsymbol \phi_j)\cdot \max_{k} \delta(n-1, k) \cdot a_{kj}\end{aligned}$

Remark：上面推導(dǎo)過程中將求n個狀態(tài)上的聯(lián)合最大值 $\max_{q_1,...,q_n}$ ，化為 $\max_{q_n}\max_{q_1,...,q_{n-1}}$ 這樣的及聯(lián)求最大值是成立的瘩缆。

有了遞歸公式关拒，我們就可以從時間步1開始計算，根據(jù)定義有：

$\begin {aligned}\delta(1, j) &= {\rm P}\{ \boldsymbol {\rm x}_1=o_1,\boldsymbol {\rm z}_1=j\} \\& = {\rm P}\{ \boldsymbol {\rm x}_1=o_1| \boldsymbol {\rm z}_1=j\} {\rm P}\{ \boldsymbol {\rm z}_1=j\} \\&= \pi_j\cdot p(o_1|\boldsymbol \phi_j)\end{aligned}$

最后庸娱，我們回溯得到最優(yōu)序列：

利用上面遞歸式着绊，我們從 $n=1$ 開始計算，在每一時間步n熟尉，對每個狀態(tài) $j$ 計算出 $\delta(n,j)$ 形成一列归露，最后得到一張 $K \times N$ 的表格。而最優(yōu)序列對應(yīng)的概率就在表格的最后一列之中斤儿。

$\begin{aligned}&\max_{q_1,...,q_N} {\rm P} \{ \boldsymbol Z=(q_1,...,q_N) ,\boldsymbol X = (o_1,...,o_N) \} \\=&\max_{q_N} \max_{q_1,...,q_{N-1}} {\rm P} \{ \boldsymbol Z=(q_1,...,q_{N-1}) ,\boldsymbol X = (o_1,...,o_N),\boldsymbol {\rm z}_N=q_N \} \\= & \max_{q_N} \delta(N, q_N) \\\end{aligned}$

設(shè)當(dāng) $q_N = q_N^*$ 時剧包， $\delta(N, q_N)$ 達(dá)到最大值，因此接上面推導(dǎo)有：

$\begin{aligned}= & \max_{q_N} \delta(N, q_N) \\= &\ \delta(N, q_N^*) \\= & p(o_N; \phi_{q_N^*}) \max_{q_{N-1}} \delta(N-1, q_{N-1}) a_{q_{N-1}q_N^*} \\= & p(o_N; \phi_{q_N^*}) \delta(N-1, q_{N-1}^*) a_{q_{N-1}q_N^*}\end{aligned}$

其中： $q_{N-1}^*$ 是使得 $\delta(N-1, q_{N-1}) a_{q_{N-1}q_N^*}$ 取最大值的那個狀態(tài)往果。如此反復(fù)下去疆液，就得到了最優(yōu)狀態(tài)路徑 $(q_1^*, ..., q_N^*)$ 。

最后編輯于：2022.11.17 10:31:19

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末陕贮，一起剝皮案震驚了整個濱河市枚粘，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌飘蚯，老刑警劉巖，帶你破解...
沈念sama閱讀 219,039評論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件福也，死亡現(xiàn)場離奇詭異局骤，居然都是意外死亡，警方通過查閱死者的電腦和手機暴凑，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,426評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門峦甩，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人现喳，你說我怎么就攤上這事凯傲。” “怎么了嗦篱？”我有些...
開封第一講書人閱讀 165,417評論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵冰单，是天一觀的道長。經(jīng)常有香客問我灸促，道長诫欠，這世上最難降的妖魔是什么涵卵？我笑而不...
開封第一講書人閱讀 58,868評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮荒叼，結(jié)果婚禮上轿偎，老公的妹妹穿的比我還像新娘。我一直安慰自己被廓，他們只是感情好坏晦，可當(dāng)我...
茶點故事閱讀 67,892評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著嫁乘，像睡著了一般昆婿。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上亦渗，一...
開封第一講書人閱讀 51,692評論 1贊 305
城市分裂傳說
那天挖诸，我揣著相機與錄音，去河邊找鬼法精。笑死多律，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的搂蜓。我是一名探鬼主播狼荞，決...
沈念sama閱讀 40,416評論 3贊 419
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼帮碰！你這毒婦竟也來了相味？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,326評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤殉挽，失蹤者是張志新（化名）和其女友劉穎丰涉，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體斯碌，經(jīng)...
沈念sama閱讀 45,782評論 1贊 316
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡一死，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,957評論 3贊 337
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了傻唾。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片投慈。...
茶點故事閱讀 40,102評論 1贊 350
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖冠骄，靈堂內(nèi)的尸體忽然破棺而出伪煤，到底是詐尸還是另有隱情，我是刑警寧澤凛辣，帶...
沈念sama閱讀 35,790評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布抱既，位于F島的核電站，受9級特大地震影響扁誓，放射性物質(zhì)發(fā)生泄漏蝙砌。R本人自食惡果不足惜阳堕，卻給世界環(huán)境...
茶點故事閱讀 41,442評論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望择克。院中可真熱鬧恬总，春花似錦、人聲如沸肚邢。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,996評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽骡湖。三九已至贱纠，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間响蕴，已是汗流浹背谆焊。一陣腳步聲響...
開封第一講書人閱讀 33,113評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留浦夷，地道東北人辖试。一個月前我還...
沈念sama閱讀 48,332評論 3贊 373
代替公主和親
正文我出身青樓，卻偏偏與公主長得像劈狐，于是被迫代替她去往敵國和親罐孝。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 45,044評論 2贊 355

HMM的細(xì)致推導(dǎo)（下）

解碼

推薦閱讀更多精彩內(nèi)容