隨筆檔案

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

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

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

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

2.隱馬爾可夫模型
    當狀態本身是不可觀察，從而得到隱馬爾可夫模型（HMM）。值得一提的是，隱馬爾可夫模型（HMM）包含了雙重隨機過程：一是系統狀態變化的過程，即前面所述的馬爾可夫過程，另一個是由狀態決定觀察的隨機過程。
舉例：碗、球模型
    假設N只碗，每個碗中放著數量與比例均不同的各種色彩的球，不同的彩色球為M。先隨機選一個碗，再從碗中隨機拿一個球，報告球的顏色得到一個觀察O_1，然后將球放回到碗中，繼續這個過程，得到一系列觀察O=O₁O₂O₃...O_T
    在這個模型中，碗（狀態）是不可觀察的，只有球的顏色是可觀察的。這里引入M，指不同觀察值的數目 。所有不同觀察值記為V={V₁,V₂,....V_M}。
    對于第一種隨機過程（選碗），時齊馬爾可夫過程的轉移概率矩陣：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,π)，如何選擇一個相應狀態Q=q₁q₂...q_T使得在某種意義下，它能最好地說明觀察序列O。
兩個準則：
準則1：對每個時刻t，逐個選取狀態q_t使
    γ_t(i)=P(q_t=S_i|O,λ)=max
其中：

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

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

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

    將其應用到詞性自動標注中。在自動標注中，每個詞是可觀察的，一個詞串W=w₁w₂....w_T即相當這里的一個觀察序列O=O₁O₂...O_T。不可觀察的狀態相當于詞性或概念標記，即狀態序列Q=q₁q₂....q_T相當于上一節中的一個標記序列。
    可以看出準則1相當于詞級評價，準則2相當于句子級評價。


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

參考文獻：
[1] 吳立德: 大規模中文文本處理[M]. 復旦大學出版社,1993.