隨筆檔案

用途：對我來說，學(xué)習(xí)HMM是為了對以后的詞性或概念標(biāo)注打下理論基礎(chǔ)
符號說明：
S：表示狀態(tài)集合。S=[S₁,S₂,S₃....]。其中S_i表示第i個狀態(tài)（第i種狀態(tài)）
Q：表示系統(tǒng)實際的狀態(tài)序列，Q=[q₁,q₂,....,q_T]。q1表示t=1時，系統(tǒng)所處的狀態(tài)，如：q₁=S₃表示t=1時刻，系統(tǒng)狀態(tài)為S₃。

1.離散馬爾可夫過程
（1）定義：一個系統(tǒng)，在任一時刻t，可能處于N個不同狀態(tài)S₁,S₂...S_N中的某一個。系統(tǒng)變化服從某種統(tǒng)計規(guī)律。如果系統(tǒng)狀態(tài)序列滿足下列無后效的條件，則稱(q_t,t≥1)為離散的馬爾可夫過程。
                                        P[q_t+1=S_j|q_t=S_i,q_t-1=S_k,...]=P[q_t+1=S_j|q_t=S_i]
    可見系統(tǒng)將來的狀態(tài)僅與現(xiàn)在所處狀態(tài)有關(guān)，與過去無關(guān)，這種情況稱之為“無后效”。
    如果進一步有P[q_t+1=S_j|q_t=S_i]與時刻t無關(guān)，則稱相應(yīng)的馬爾可夫過程是齊決的或是時齊的，引入記號：
                                        a_ij=P[q_t+1=S_j|q_t=S_i]，1≤i,j≤N
    注：這里有人也稱a_ij為S_i→S_j的發(fā)射概率，也稱轉(zhuǎn)移概率。

（2）初始概率分布：         π_i=P[q₁=S_i],   1≤i,j≤N 
    k步轉(zhuǎn)移概率：
        a_ij^(k)=P[q_t+k=S_j|q_t=S_i]
當(dāng)k=1時，a_ij^(k)=a_ij⁽¹⁾=a_ij

（3）切普曼—柯爾莫哥洛夫公式（Chapman-Kolmogorol）
            

2.隱馬爾可夫模型
    當(dāng)狀態(tài)本身是不可觀察，從而得到隱馬爾可夫模型（HMM）。值得一提的是，隱馬爾可夫模型（HMM）包含了雙重隨機過程：一是系統(tǒng)狀態(tài)變化的過程，即前面所述的馬爾可夫過程，另一個是由狀態(tài)決定觀察的隨機過程。
舉例：碗、球模型
    假設(shè)N只碗，每個碗中放著數(shù)量與比例均不同的各種色彩的球，不同的彩色球為M。先隨機選一個碗，再從碗中隨機拿一個球，報告球的顏色得到一個觀察O_1，然后將球放回到碗中，繼續(xù)這個過程，得到一系列觀察O=O₁O₂O₃...O_T
    在這個模型中，碗（狀態(tài)）是不可觀察的，只有球的顏色是可觀察的。這里引入M，指不同觀察值的數(shù)目 。所有不同觀察值記為V={V₁,V₂,....V_M}。
    對于第一種隨機過程（選碗），時齊馬爾可夫過程的轉(zhuǎn)移概率矩陣：A={a_ij}，初始分布：π=(π_i)
    對于第二種隨機過程，有多項分布B={b_j(k)}，其中
            b_j(k)=P[時刻t時觀察值為V_k|q_t=S_j]
    給定一組N,M,A,B和π后，一個HMM即確定了，為緊縮起見，今后將用λ=（A,B,π）表示一個HMM。

3.HMM中三個基本問題
問題1：
    給定一個觀察序列O=O₁O₂...O_T和一個模型λ=（A,B,π），如何有效計算P（O|λ），即給定模型λ的條件下，觀察序列O的概率。
    問題1是一個計算概率的問題，也可以看成一個評估給定的模型能否很好地擬合給定的觀察的問題。

解法：
（1）前向算法：
    定義α_t(i)=P(O₁O₂....O_t,q_t=S_i|λ)
    α_t可用遞推算法完成計算：
    ①初始化：α₁(i)= π_ib_i(O₁)
    ②遞推：
    ③終止：

（2）后向算法：
    定義β_t(i)=P(O_t+1,O_t+2,...,O_T|q_t=S_i,λ)
β_t可用遞推算法計算：
    ①初始化：β_T(i)=1
    ②遞推：
    ③終止：


問題2：
    給定一個觀察序列O=O₁O₂...O_T和一個模型λ=(A,B,π)，如何選擇一個相應(yīng)狀態(tài)Q=q₁q₂...q_T使得在某種意義下，它能最好地說明觀察序列O。
兩個準(zhǔn)則：
準(zhǔn)則1：對每個時刻t，逐個選取狀態(tài)q_t使
    γ_t(i)=P(q_t=S_i|O,λ)=max
其中：

求出γ_t(i)后，問題2便迎刃而解。

準(zhǔn)則2（應(yīng)用最為廣泛）：綜合選取一個狀態(tài)序列Q=q₁q₂....q_T使P(Q|O,λ)=max
    對于P(Q|O,λ)=P(Q,O|λ)/P(O|λ)
    而分母P(O|λ)與Q無關(guān)，因此等價于P（Q,O|λ）=max。
    對于全局最優(yōu)問題，使用動態(tài)規(guī)劃方法，這就是Viterbi算法。
    定義
            
    基于HMM特性，
            
    因為我們同樣關(guān)心q₁q₂...q_T的序列，因此引入
            

    整個遞推算法（Viterbi算法）描述如下：
    ①初始化
        δ₁(i)=π_ib_i(O₁)
        φ₁(i)=0
    ②遞推
         
         
    ③終止
        
    ④回溯最佳路徑
        q_t^*=φ_t+1(q_t+1^*)

    將其應(yīng)用到詞性自動標(biāo)注中。在自動標(biāo)注中，每個詞是可觀察的，一個詞串W=w₁w₂....w_T即相當(dāng)這里的一個觀察序列O=O₁O₂...O_T。不可觀察的狀態(tài)相當(dāng)于詞性或概念標(biāo)記，即狀態(tài)序列Q=q₁q₂....q_T相當(dāng)于上一節(jié)中的一個標(biāo)記序列。
    可以看出準(zhǔn)則1相當(dāng)于詞級評價，準(zhǔn)則2相當(dāng)于句子級評價。


問題3.
    如何修正模型參數(shù)λ=(A,B,π)使P(O| λ)=max。
    問題3是最困難的，至少也沒有很好的解法。可參考的方法有基于均值修正的迭代方法等。

參考文獻(xiàn)：
[1] 吳立德: 大規(guī)模中文文本處理[M]. 復(fù)旦大學(xué)出版社,1993.