鮑姆-韋爾奇算法

佇咧電氣的工程、計算機科學、統計算佮生物信息學中，鮑姆-韋爾奇算法是用佇咧走揣隱馬爾可夫模型無知影參數的上大向望算法，伊利用頭前向-後向算法來計算 E-Step 的統計信息。

歷史

鮑姆-韋爾奇算法是以其發明者倫納德・埃紹・鮑姆佮勞埃德・理察・韋爾奇的名字號的。鮑姆-韋爾奇算法佮隱馬爾可夫模型佇二十世紀六空年代尾佮七空年代初由鮑姆佮伊的同事佇國防分析研究所的一系列文章中頭擺描述。HMMs 頭起主要應用佇語音處理領域。二十世紀八空年代，HMMs 開始成做分析生物系統佮信息，特別是遺傳信息的有用工具。此後，𪜶成做基因組序列概率建模的重要工具。

介紹

隱馬爾有可夫模型來講一組「隱含」變量佮會當縮短的離散隨機變量的聯合概率。伊依賴佇假設：第 $ i $ 一个藏的變量干焦佮第 $ i 影一 $ 隱含變量相關，佮其他進前的隱藏變量無關係，當前觀測著的狀態干焦依賴佇當前的隱藏狀態。

鮑姆-韋爾奇算法利用上大向望算法，會予定一組觀測特徵向量的情況下，求出隱馬爾可夫模型參數的上大若親像估計。

記離散的隱含隨機變量為 $ X _ { t } $，伊攏總有 $ N $ 種狀態 ( $ X _ { t } $ 有 $ N $ 個無仝的值 )。設 $ P ( X _ { t } | X _ { t 影一 } ) $ 佮時間無關係，得著佮時間無關係的隨機變量轉移矩陣：

$ A=\ { a _ { ij } \ }=P ( X _ { t }=j | X _ { t 影一 }=i ) $ 初始的狀態 ( 即 $ t=一 $ ) 分佈由下式共出：

$ $ \ pi _ { i }=P ( X _ { 一 }=i ) $ $

記觀測著的變量為 $ Y _ { t } $，攏總有 $ K $ 種取值。仝款假影由隱含變量得著的可觀測變量佮時間無關係。佇時間 $ t $，由隱含變量 $ X _ { t }=j $ 得著的會當觀察變量 $ Y _ { t }=y _ { i } $ 的概率是：

$ $ b _ { j } ( y _ { i } )=P ( Y _ { t }=y _ { i } | X _ { t }=j ) $ $

由所有可能著 $ X _ { t } $ 和 $ Y _ { t } $ 的取值，咱會當得著這个 $ N \ times K $ 矩陣 $ B=\ { b _ { j } ( y _ { i } ) \ } $，其中 $ b _ { j } $ 屬於所有可能愛含狀態，$ y _ { i } $ 屬於所有的會當觀測狀態。

予出觀測序列：$ Y=( Y _ { 一 }=y _ { 一 } , Y _ { 二 }=y _ { 二 } , \ cdots , Y _ { T }=y _ { T } ) $。

咱會當用 $ \ theta ( A , B , \ pi ) $ 咧講隱馬爾科夫鏈，鮑姆-韋爾奇算法走揣 $ \ theta ^ { * }=\ arg { \ underset { \ theta } { max } } P ( Y | \ theta ) $ 的局部真大值，也就是會當予觀測著的序列出現的概率上大的 HMM 的參數 $ \ theta $。

算法

初初化的參數 $ \ theta ( A , B , \ pi ) $，會當隨機初化的，抑是根據先驗智識初始化。

前向過程

記 $ \ alpha _ { i } ( t )=P ( Y _ { 一 }=y _ { 一 } , Y _ { 二 }=y _ { 二 } , \ cdots , Y _ { t }=y _ { t } , X _ { t }=i | \ theta ) $ 是參數 $ \ theta $ 的條件下跤，觀測的序列是 $ y _ { 一 } , y _ { 二 } , \ cdots , y _ { t } $，時刻 $ t $ 的狀態是 $ i $ 的概率。會當通過遞歸計算：

一 . $ \ alpha _ { i } ( 一 )=\ pi _ { i } b _ { i } ( y _ { 一 } ) $ 二 . $ \ alpha _ { i } ( t + 一 )=b _ { i } ( y _ { t + 一 } ) \ sum _ { j=一 } ^ { N } \ alpha _ { j } ( t ) a _ { ji } $

後向過程

記 $ \ beta _ { i } ( t )=P ( Y _ { t + 一 }=y _ { t + 一 } , \ cdots , Y _ { T }=y _ { T } | X _ { t }=i , \ theta ) $ 是參數是 $ \ theta $，在時刻 $ t $ 的狀態是 $ i $ 的條件下跤，下跤的部份的觀測序列是 $ y _ { t + 一 } , \ cdots , y _ { T } $ 的概率。

一 . $ \ beta _ { i } ( T )=一 $ 二 . $ \ beta _ { i } ( t )=\ sum _ { j=一 } ^ { N } \ beta _ { j } ( t + 一 ) a _ { ij } b _ { j } ( y _ { t + 一 } ) $

更新

根據貝葉斯公式計算臨時變量。
佇予定觀測序列 $ Y $ 佮參數 $ \ theta $ 的狀況之下，佇時間 $ t $ 狀態是 $ i $ 的概率 : $ \ gamma _ { i } ( t )=P ( X _ { t }=i | Y , \ theta )={ \ frac { P ( X _ { t }=i , Y | \ theta ) } { P ( Y | \ theta ) } }={ \ frac { \ alpha _ { i } ( t ) \ beta _ { i } ( t ) } { \ sum _ { j=一 } ^ { N } \ alpha _ { j } ( t ) \ beta _ { j } ( t ) } } $
佇予定觀測序列 $ Y $ 佮參數 $ \ theta $ 的狀況之下，佇時間 $ t $ 狀態是 $ i $，佇時間 $ t + 一 $ 狀態是 $ j $ 的概率 : $ \ xi _ { ij } ( t )=P ( X _ { t }=i , X _ { t + 一 }=j | Y , \ theta )={ \ frac { P ( X _ { t }=i , X _ { t + 一 }=j , Y | \ theta ) } { P ( Y | \ theta ) } }={ \ frac { \ alpha _ { i } ( t ) a _ { ij } \ beta _ { j } ( t + 一 ) b _ { j } ( y _ { t + 一 } ) } { \ sum _ { i=一 } ^ { N } \ sum _ { j=一 } ^ { N } \ alpha _ { i } ( t ) a _ { ij } b _ { j } ( y _ { t + 一 } ) \ beta _ { j } ( t + 一 ) } } $
$ \ gamma _ { i } ( t ) $ 和 $ \ xi _ { ij } ( t ) $ 的分母仝款，表示予定參數 $ \ theta $ 得著觀測序列 $ Y $ 的概率。
閣更新參數：
$ \ pi _ { i } ^ { * }=\ gamma _ { i } ( 一 ) $，佇時間 $ 一 $ 狀態是 $ i $ 的概率
$ a _ { ij } ^ { * }={ \ frac { \ sum _ { t=一 } ^ { T 影一 } \ xi _ { ij } ( t ) } { \ sum _ { t=一 } ^ { T 影一 } \ gamma _ { i } ( t ) } } $，等於向望的對狀態 $ i $ 轉換著狀態 $ j $ 的數量除了愛對狀態 $ i $ 開始的轉換的總數。
$ b _ { i } ^ { * } ( v _ { k } )={ \ frac { \ sum _ { t=一 } ^ { T } 一 _ { y _ { t }=v _ { k } } \ gamma _ { i } ( t ) } { \ sum _ { t=一 } ^ { T } \ gamma _ { i } ( t ) } } $，其中 $ 一 _ { y _ { t }=v _ { k } }={ \ begin { cases } 一 { \ text { if } } y _ { t }=v _ { k } , \ \ 零 { \ text { otherwise } } \ end { cases } } $，$ b _ { i } ^ { * } ( v _ { k } ) $ 是向望的對狀態 $ i $ 得著的觀察值等於 $ v _ { k } $ 的數量除了愛對狀態 $ i $ 開始的轉換的總數。
重複頂懸的工課一直到收斂。算法可能過擬合，嘛無保證收斂著全局上大的。
其中計算 $ \ gamma _ { i } ( t ) $ 和 $ \ xi _ { ij } ( t ) $ 佮上大的向望算法的 E-Step，若更新 $ \ pi _ { i } ^ { * } \ alpha _ { ij } ^ { * } , b _ { i } ^ { * } ( v _ { k } ) $ 的過程比上大向望算法的 M-Step。

例

假使講咱有一隻會生卵的雞，逐工中晝阮攏會去抾雞卵。雞敢是生卵依賴一寡未知影的隱含狀態，遮阮簡單的假使干焦兩種隱含狀態會決定伊是毋是生卵。咱毋知影遮的隱含狀態的初始值，毋知影𪜶之間的轉換概率，嘛毋知佇逐種狀態會生雞會生卵的概率。阮隨機初共化𪜶來開始咧臆。

假使咱得著的觀測序列是 ( E=eggs , N=no eggs ) : N , N , N , N , N , E , E , N , N , N。

按呢阮同時嘛得著觀測狀態的轉移：NN , NN , NN , NN , NE , EE , EN , NN , NN。

通過頂懸的信息來重新估計狀態轉移矩陣。

重新估計 $ S _ { 一 } $ 到 $ S _ { 二 } $ 轉移概率為 $ { \ frac { 空九二二 } { 二嬸四二三四 } }=空九空八 $ ( 下表中的 " Pseudo probabilities " )，重新計算所有的轉移概率，得著下跤的轉移矩陣：

紲落來重新估計 Emission Matrix :

重新估計對隱含狀態 $ S _ { 一 } $ 得著觀察結果 E 的概率是 $ { \ frac { 空九二三九四 } { 空九二七三空 } }=空空八七六九 $，得著新的 Emission Matrix

為著估計初狀態的概率，咱分別假做序列的開始狀態是 $ S _ { 一 } $ 和 $ S _ { 二 } $，然後求出上大的概率，閣歸一化了後更新初狀態的概率。

一直重複頂懸的步數，一直到予人收縮。

代碼