2007年8月29日 星期三

Hidden Markov Model

最近被迫得讀 Hidden Markov Model (HMM) 相關的內容,我入門的方法是參考下面這三篇:

最近學新東西,愈來愈習慣先看完WikiPedia的介紹再開始,WikiPedia上的介紹通常比書裡寫得還要清楚,真方便。

個人認為最好理解HMM的例子是語音辨識,摘錄Viterbi algorithm裡的一段例子:

For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the “hidden cause” of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.

每個文字代表一個state,state和state之間有條件機率,稱為state transition,即文字的連續關連性,比方「駱」下個字出現「駝」的機率很高,出現「馬」的機率很低,丟個文章集統計一下就可以得知state transition。主要的差別是這裡假設每個state只會被上個state影響,所以不會直接統計「王八」下個字出現的機率,得先算出「王」到「八」才行。這點和 N-gram 的做法不同,以文字為例子的話,可以將state transition看成是 2-gram 而已。

單純文字之間的關聯已有很多發展空間,比方套用 Markov chain ,算出給定第一個字的情況,第五個字最有可能出現什麼字?或是無論開頭為何,第三個字最有可能出現什麼字?而在語音辨識的例子裡,除了 state (=文字)外,還有 symbol 。

每個 state 會產生一個 symbol ,打個比方,可以想成在數位電路裡的 Finite State Machine 中的 Moore Machine ,跟著一連串的 state 轉換,每個 state 都有伴隨輸出的資訊,但在 HMM 裡,每個 state 不會只輸出一種 symbol ,而是各個 symbol 有對應的輸出機率,所以不只 state 和 state 之間有條件機率, state 和 symbol 之間也有條件機率。在語音辨識的例子裡, symbol 是聲音訊號。畫圖太麻煩了,麻煩各位發揮想像力, HMM 的架構可看成兩層,上層是一個 graph , vertex 表示 state, edge 表示 state 間的條件機率;下層是數排 vertices 每個上層的 vertex 對應到下層一排 vertices ,之間有個有向邊由上層指向下層, edge一樣是條件機率,表示在這個 state 下,會產生的 symbol 機率為何。

那麼 HMM 要解決的問題為何呢?直接從語音辨識來看比較容易理解,我們可以取得一連串的聲音訊號,經過處理後斷成一個個文字的聲音,但我們不知道每個聲音對應到的文字為何?考慮這個例子(喔,注音文的正當使用):

ㄌㄨㄛˋ ㄊㄨㄛˊ ㄏㄨㄟˋ ㄈㄟ

這個例子對應的文字可能是「落鴕會妃」,也可能是「駱駝會飛」,那一個組合較合理,得看文字間的接連出現的機率夠不夠高。在 Markov chain 的例子裡,我們是直接由 state 找出 state sequence,而HMM的例子裡,我們不知道 state 為何,所以稱為 Hidden State ,我們必須由 observation ( symbol sequence ) 來推測原來最有可能的 state sequence。

注意上述的說明都是假設 model 是正確的, model = initial state probability + state transition probability + symbol probability (emission probability)。在 Machine Learning 裡有些方法說明如何找出最有可能的 model ,有空再來看看吧。

沒有留言:

張貼留言