posts - 30,  comments - 3,  trackbacks - 0
          <2012年3月>
          26272829123
          45678910
          11121314151617
          18192021222324
          25262728293031
          1234567

          常用鏈接

          留言簿

          隨筆檔案

          搜索

          •  

          最新評論

          閱讀排行榜

          評論排行榜

          用途:對我來說,學習HMM是為了對以后的詞性或概念標注打下理論基礎
          符號說明:
          S:表示狀態集合。S=[S1,S2,S3....]。其中Si表示第i個狀態(第i種狀態)
          Q:表示系統實際的狀態序列,Q=[q1,q2,....,qT]。q1表示t=1時,系統所處的狀態,如:q1=S3表示t=1時刻,系統狀態為S3

          1.離散馬爾可夫過程
          (1)定義:一個系統,在任一時刻t,可能處于N個不同狀態S1,S2...SN中的某一個。系統變化服從某種統計規律。如果系統狀態序列滿足下列無后效的條件,則稱(qt,t1)為離散的馬爾可夫過程。
                                                  P[qt+1=Sj|qt=Si,qt-1=Sk,...]=P[qt+1=Sj|qt=Si]
              可見系統將來的狀態僅與現在所處狀態有關,與過去無關,這種情況稱之為“無后效”。
              如果進一步有P[qt+1=Sj|qt=Si]與時刻t無關,則稱相應的馬爾可夫過程是齊決的或是時齊的,引入記號:
                                                  aij=P[qt+1=Sj|qt=Si],1≤i,j≤N
              注:這里有人也稱aij為SiSj的發射概率,也稱轉移概率。

          (2)初始概率分布:         
          πi=P[q1=Si],   1≤i,j≤N 
              k步轉移概率:
                  aij(k)=P[qt+k=Sj|qt=Si]
          當k=1時,aij(k)=aij(1)=aij

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

          2.隱馬爾可夫模型
              當狀態本身是不可觀察,從而得到隱馬爾可夫模型(HMM)。值得一提的是,隱馬爾可夫模型(HMM)包含了雙重隨機過程:一是系統狀態變化的過程,即前面所述的馬爾可夫過程,另一個是由狀態決定觀察的隨機過程。
          舉例:碗、球模型
              假設N只碗,每個碗中放著數量與比例均不同的各種色彩的球,不同的彩色球為M。先隨機選一個碗,再從碗中隨機拿一個球,報告球的顏色得到一個觀察O1,然后將球放回到碗中,繼續這個過程,得到一系列觀察O=O1O2O3...OT
              在這個模型中,碗(狀態)是不可觀察的,只有球的顏色是可觀察的。這里引入M,指不同觀察值的數目 。所有不同觀察值記為V={V1,V2,....VM}。
              對于第一種隨機過程(選碗),時齊馬爾可夫過程的轉移概率矩陣:A={aij},初始分布:π=(πi)
              對于第二種隨機過程,有多項分布B={bj(k)},其中
                      bj(k)=P[時刻t時觀察值為Vk|qt=Sj]
              給定一組N,M,A,B和π后,一個HMM即確定了,為緊縮起見,今后將用λ=(A,B,π)表示一個HMM。

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

          解法:
          (1)前向算法:
              定義αt(i)=P(O1O2....Ot,qt=Si|λ)
              
          αt可用遞推算法完成計算:
              ①初始化:α1(i)= πibi(O1)
              ②遞推:
              ③終止:

          (2)后向算法:
              定義βt(i)=P(Ot+1,Ot+2,...,OT|qt=Si,λ)
          βt可用遞推算法計算:
              ①初始化:βT(i)=1
              ②遞推:
              ③終止:


          問題2:
              給定一個觀察序列O=O1O2...OT和一個模型
          λ=(A,B,π),如何選擇一個相應狀態Q=q1q2...qT使得在某種意義下,它能最好地說明觀察序列O
          兩個準則:
          準則1:對每個時刻t,逐個選取狀態qt使
              
          γt(i)=P(qt=Si|O,λ)=max
          其中:

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

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

              整個遞推算法(Viterbi算法)描述如下:
              ①初始化
                  δ1(i)=πibi(O1)
                  φ1(i)=0
              ②遞推
                   
                   
              ③終止
                  
              ④回溯最佳路徑
                  qt*=φt+1(qt+1*)

              將其應用到詞性自動標注中。在自動標注中,每個詞是可觀察的,一個詞串W=w1w2....wT即相當這里的一個觀察序列O=O1O2...OT。不可觀察的狀態相當于詞性或概念標記,即狀態序列Q=q1q2....qT相當于上一節中的一個標記序列。
              可以看出準則1相當于詞級評價,準則2相當于句子級評價。


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

          參考文獻:
          [1] 吳立德: 大規模中文文本處理[M]. 復旦大學出版社,1993.
          posted on 2012-03-07 13:56 Seraphi 閱讀(1324) 評論(0)  編輯  收藏

          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          主站蜘蛛池模板: 杭锦后旗| 黑龙江省| 肥城市| 海林市| 乐都县| 龙海市| 甘肃省| 高清| 大新县| 涿鹿县| 化德县| 巴林左旗| 全椒县| 兴山县| 东阳市| 漳浦县| 和林格尔县| 定远县| 郑州市| 郎溪县| 彭泽县| 孝义市| 阜城县| 礼泉县| 宁远县| 方山县| 陆川县| 明溪县| 海晏县| 阳新县| 称多县| 枞阳县| 沙坪坝区| 本溪市| 平南县| 泸西县| 江源县| 建瓯市| 武陟县| 修武县| 西峡县|