Hidden Markov Model

Hidden Markov Model
August 29th, 2007Goto commentsLeave a comment
最近被迫得讀 Hidden Markov Model (HMM) 相關的內容，我入門的方法是參考下面這三篇：

HMM不負責講座
Hidden Markov model
Viterbi algorithm
最近學新東西，愈來愈習慣先看完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 ，有空再來看看吧。

fcamelAI, All, Computer Science
Comments (1)Trackbacks (0)Leave a commentTrackback

123
March 4th, 2008 at 09:02 | #1 Reply | Quote
you are wrong, in speech recognition, the state does not represent a charactor!