隠れマルコフモデルデータベースの高速ゆう度検索

摘要

本論文では与えられた問合せシーケンスに対してHMM（Hidden Markov Model）のデータ集合の中からモデルを探索する問題を対象とする．我々の知る限り，本論文はHMMのデータ集合に対する探索結果の厳密性と高速な探索処理を両立させた最初の取組みである．本論文ではHMMの探索手法としてSCREWを提案する．SCREWは（1）モデルの状態を結合し，ゆう度の上限値により高速に解候補を絞り込み，（2）モデルを様々な近似の粒度で探索し，（3）モデルのゆう度計算を打ち止めて，ゆう度の低いモデルを高速に枝刈りする．ナイーブな手法と実験比較して，提案手法の有効性を確認した．