Hidden Markov Models and the Variants

教科書：Automatic Speech Recognition - A Deep Learning Approach
報告章節：Chapter 3   Hidden Markov Models and the Variants


這個章節主要是在介紹HMM，但在介紹HMM之前，會先講一下什麼是 馬可夫鏈 ( Markov chain )

介紹大綱如下：

1. Markov Chains
2. Hidden Markov Sequences and Models  
(1)Evaluation
(2)Learning
(3)Decoding

【1.  Markov Chains】

<定義>

馬可夫鏈，簡單來說就是一個狀態集合，這個集合中的狀態 (1) 轉移關係只要機率分布的描述即可、(2)下一個狀態分布只和當前狀態有關  就符合馬可夫鏈的條件。

最有名的例子就是布朗運動，布朗運動是花粉在水面上移動的位置只是當前位置有關係，和過去位置沒有關係(因為花粉的下個位置是被周圍花粉碰撞所造成的，因此是目前位置關係到未來位置)。

<Transition Probabilities (轉移機率) >

假設我們有個馬可夫鏈，

他的轉移機率定義如下

(公式1)

公式1簡單來說就是在 t-1 時刻狀態為 i 轉移到 t 時刻狀態為 j 的機率定義為aij，但若是這個馬可夫鏈的轉移機率獨立於t (和t無關係)，我們便稱這個馬可夫鏈為homogeneous Markov chain(齊次馬可夫鏈)，

<Transition Matrix (轉移矩陣) >

我們常常將(齊次)馬可夫鏈的轉移機率寫成轉移矩陣的形式，公式定義如下

(公式2)

公式2主要是在講，轉移矩陣A，是轉移機率aij所組成的，而第i的狀態轉移到其他狀態的機率何必須為1，如下圖範例

<The State-Occupation Probability>

這個我把它翻譯成當前狀態機率，就是指在t時刻第i個狀態出現的機率，我們的當前狀態機率可以寫成

聰明如你，如果我們給予一個轉移機率，我們現在就可以用遞迴(recursive)來換個方式表示

上面這個公式，我們用下面的例子來講解

這裡我們要求t+1個時刻狀態在i的機率，公式裡的j代表所有有可能轉移到i狀態的狀態集合，因此我們只要把所有t時刻狀態在j的機率 * aij相加，就是我們要求的Pi(t+1)

<Stationary distribution(平穩分布)>

用blog編輯真的挺難打公式的，簡單來說，如果𝜋 ̃(𝑠^((𝑖)))是該鏈的初始分布且是平穩分布，那麼在任何一個時間點上面，該鏈的分布都該是平穩分布

而Markov Chain Monte Carlo (MCMC) methods. (馬可夫鏈蒙地卡羅法) 就是設計一個轉移矩陣，讓馬可夫鏈的初始分布滿足平穩分布。

馬可夫鏈的介紹就到這邊，如果有想更加了解的話，推薦去研究"隨機分布"，或是去看原文書 :)

準備好的話，讓我們接下來來挑戰HMM(隱馬可夫模型)囉~

【Hidden Markov Sequences and Models】

<定義>

HMM 通常來說，會有兩個狀態鍊，一個是觀察狀態鏈，另一個是隱藏狀態鏈，在隱藏狀態鏈中，每個子狀態的轉移都有個轉移機率(Transition Probability)，而該子狀態會產生出某個觀察狀態的機率稱為觀察機率(Emission Probability/Observation probability distribution)

讓我們用個例子來講解，以下所以介紹也都會用到這個例子

有一個宅男，他足不出戶，但是他想要知道外面的天氣變化，因此他養了一堆水藻，水藻的的狀態可分為四種(乾、微乾、微濕、濕)，在這裡稱為"觀察狀態"；而外面的天氣變化，我們分為三種(晴天、陰天、雨天)，在這裡稱為"隱藏狀態"(因為宅男看不到也不知道)

天氣的變化就是轉移機率(Transition Probability)，如：晴天變晴天的機率、雨天變音天的機率

而天氣造成水藻狀態的機率就是觀察機率(Emission Probability/Observation probability distribution)，如晴天的狀態下水藻呈現乾燥的機率(因為有可能會有水藻濕潤等狀態，這不是唯一的，所以要用機率表示)，陰天的狀態下水藻呈現乾燥的機率

而第一天是晴天的機率或是第一天是陰天的機率等，這個我們就稱為初始狀態機率(Initial Markov chain state-occupation probabilities)。

上面這三個就是HMM的主要三元素，課本上的公式，我就直接放ppt了(如下)

aij：隱藏狀態 i 轉移到隱藏狀態 j 的機率

𝜋i：初始隱藏狀態為 i 的機率

bi(k)：隱藏狀態 i 造成觀察狀態為 k 的機率 ，如：b晴天(水藻乾燥) ,i = 晴天，k = 乾燥

而HMM又可分為離散(discrete)和連續(continuous)兩種，連續型HMM就稱為Guassian-mixture HMM，而其觀察機率公式為下：

<Simulation of a Hidden Markov Model>

下面這個演算法，如果剛剛講的觀念都清楚的話，應該看得懂，這裡就不多做解釋

< HMM 要解決的三個問題 >

接下來要來進入我們的重頭戲了！！！這個部分我之前爬了很多文才懂😭😭😭

HMM主要需要解決的三個問題如下：

1. 評估（Evaluation）：對於一個給定的HMM其生成一個給定的觀察序列的概率是多少。前向演算法可以有效的解決此問題。

簡單來說，就是假如宅男觀察到一周的水藻狀態分布為：O(1~7) = 乾、濕、微乾、...、濕

我想知道O(1~7)出現的機率為多少(假設我們已知轉移機率、初始狀態機率、及觀察狀態機率) 

2. 學習（Learning）：根據觀察序列生成HMM。對於一個給定的觀察序列樣本，什麼樣的模型最可能生成該序列——也就是說，該模型的參數是什麼。這個問題可以通過使用前向-後向演算法解決。

這是HMM裡面最難的部分，會用到EM演算法，但是這部分我不太懂，所以只能介紹個大概

簡單來說，就是假如宅男觀察到一周的水藻狀態分布為：O(1~7) = 乾、濕、微乾、...、濕

會造成O(1~7)觀察分布的 HMM 參數(轉移機率、初始狀態機率、及觀察狀態機率)為何？

3. 解碼（ Decoding）：給定觀察序列搜索最可能的隱藏狀態序列

這我把它定義為三個要解決問題中最簡單的一個：)

假如宅男觀察到一周的水藻狀態分布為：O(1~7) = 乾、濕、微乾、...、濕

會造成這個觀察序列最大可能的天氣狀態序列為何

<評估（Evaluation）>

課本在這一章節下的標題是：Likelihood Evaluation of a Hidden Markov Model

那"Likelihood"是什麼意思呢？

在機率學中，把機率和Likelihood分得很清楚：

機率就是從已知條件推算未知結果

Likelihood(似然函數)就是從結果推算可能造成結果的可能條件

而在這邊，我們的目的就是要計算出 會產生觀察序列O的最大可能機率為多少【P(O)】

先來介紹窮舉搜索 Exhaustive search for solution這個方法就是把所以機率全部乘起來，大概就是greedy的概念！以三張圖片帶過解決之

//因為最近沒有什麼時間整理下面的，就附上當時報告的PPT，有問題可以底下留言 :)