隨筆檔案

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

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

（3）切普曼—柯?tīng)柲缏宸蚬剑–hapman-Kolmogorol）
            

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

3.HMM中三個(gè)基本問(wèn)題
問(wèn)題1：
    給定一個(gè)觀察序列O=O₁O₂...O_T和一個(gè)模型λ=（A,B,π），如何有效計(jì)算P（O|λ），即給定模型λ的條件下，觀察序列O的概率。
    問(wèn)題1是一個(gè)計(jì)算概率的問(wèn)題，也可以看成一個(gè)評(píng)估給定的模型能否很好地?cái)M合給定的觀察的問(wèn)題。

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

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


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

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

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

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

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


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

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