« December 2007 | Main | February 2008 »

2008.01.15

HMMの文字列分解による高速化

今年もよろしく
読んで面白かった研究紹介を。

"Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions" [pdf] S. Mozes, et. al.
CPM 2007の best paper

HMM(隠れマルコフモデル)は、観測できる状態の列(s1, s2, ..., sn)が与えられたとき、隠れ状態の列(h1, h2, .., hn)を次の確率が最大になるものとして求めます。
Π_{i =1to n} p(s_i|h_i) p(h_i | h_{i-1}) ・・・(1)
各隠れ状態は直前の隠れ状態にのみ依存した確率分布で生成され、観測された各状態は、各隠れ状態から生成されます。隠れマルコフモデルは非常に広い分野で使われており、音声認識やら、品詞推定やら、最近では生物情報など(DNAの列が与えられたら、どこが遺伝子発現部位かを推定する)で使われています。

で問題となるのは、この(1)が最大になるものを求める部分で、Viterbi法を使えば隠れ状態数をk、列の長さをnとした時、O(nk^2)で求まるのですが例えばバイオとかだとnが数千から数万とかで非常に大きくなります。長くなくても小さいことに越したことはありません。

タイトルだけで推測できる人もいるかもしれませんが、この論文では入力文が同じ文字が繰り返される、同じ部分文字列が繰り返される場合が多いことに着目し、入力文をはじめに連長圧縮や、LZ78(増分分解法)などで分解し、頻出する部分はあらかじめまとめておきます。
s1 s2 s3 s4 s5 s6 を [s1 s2 s3] = m1 [s4] = m2 [s5 s6] = m3という感じ
で、この単語内をそれぞれ学習しときます。具体的には、まとめたやつの中で隠れ状態 j から入って、k で出て行くのはどれだけの確率かというのを前もって計算できます。
で、 s1 s2 s3 .. sn の代わりに m1 m2 m3 でビタビを行う。
この単語内の経路の確率をあらかじめ求めておくのも連長圧縮の場合は [a a a] は [a a] * [a] というふうに再帰的に計算でき、LZ78も増分分解しているので再帰的に計算できます。

で分解すると大抵短くなっているので、デコードが数倍早くなりめでたいというわけです。
Viterbi, Forward-Backwardを使った学習も殆ど同じようにして高速化することもできます。

実験ではバイオしかしてないけど、自然言語処理とかでも頻出する単語とかあるわけなので高速化できそうですよね。HMM以外でもいろいろできるでしょうね。

| | Comments (0) | TrackBack (0)

« December 2007 | Main | February 2008 »