Online Decoding of Markov Models under Latency Constraints ICML 2006 読む会資料 † Online Decoding of Markov Models under Latency Constraints Mukund Narasimhan, Paul Viola, Michael Shilman @ Microsoft Corp. 論文紹介者： 中田貴之 @ NEC † Appearing in proceedings of the 23 rd International Conference on Machine Learning, Pittsburgh, PA, 2006.
はじめに Viterbiアルゴリズムはlinear-chain Markov Modelsをdecodingするのに効率的で最適な手法である しかし，状態を推定するためには全入力データを観測する必要がありオンラインアルゴリズムでの適用が難しい 固定windowを用いると, 広いwindowはAccuracyが上がるがlatencyが大きくなる そこでAccuracy と Latency のトレードオフを考慮する手法を提案 応用例は，ネットワークのパケットストリームを解析し，早期に悪意ある行動を検出するアプリケーションなど
準備 S = {s1, s2 , . . . , sk} ： マルコフモデルの状態 Sn ： 長さ n の状態系列 観測系列 o が与えられたときの状態系列 s = s(0)s(1)s(2) . . . s(n−1) の確率 (for a linear-chain CRF) ： ポテンシャル関数 ： f ∈F ： 特徴を表す関数 , lf ： 重み
Viterbi アルゴリズム (for Decoding CRFs) 最適状態系列（長さ t +1，最終状態 r ∈ S） のスコア 前から後へ再帰的に計算 最適状態系列（全観測データ） のスコア 最適状態（最終時刻 n ） 最適状態系列（後から前へ再帰的に計算）
Viterbi アルゴリズム (for Decoding CRFs) (cont’d) 例 図 1. 最終時刻 4 の最適状態 C から後ろ向きに最適状態系列（緑）を求める
LatencyとAccuracyのトレードオフ - 1. Simple Chunking - 図 2. 時刻 3 までのデータから求まる最適状態 固定Windowから求まる最適状態（誤り） サイズ 3の固定Window
LatencyとAccuracyのトレードオフ - 2. Pruning by Transitive Closure - 図 3. 時刻 3 を観測した時点で時刻 0 と 1 の状態は C C に一意に確定 それ以前の後ろ向きポインタを捨ててよい 時刻 3 までのデータから求まる最適状態
LatencyとAccuracyのトレードオフ - 3. Online Step （提案手法1） - 時刻 T > t0 までの観測データが得られたとき，時刻 t0 に状態 a となる確率 ： 時刻 t0 の状態推定の不確かさを表す関数 以下を満たす T を求める（ l ： トレードオフのパラメータ） min 時刻 T に状態 b のとき，到達可能な時刻 t0 の状態 Accuracy Latency 時刻 t0 の状態の推定の精度を評価している
LatencyとAccuracyのトレードオフ - 4. Online Variable Window （提案手法2） - 時刻 T において状態 b の代わりに状態 a を選んだ場合の損失関数 （状態系列 s(t0). . . s(T) における推定結果の異なり数を損失とする）： 時刻 T において状態 a を選んだ場合の期待損失 期待損失を最小化する状態 a 以下を満たす T を求める（ l ： トレードオフのパラメータ） min LossT + l・(T − t0) 時刻 T に状態 b のとき， 時刻 T - k の状態 Accuracy Latency 時刻 t0,…,T の状態系列の推定の精度を評価している
実験結果 latency-error-rates y 軸はViterbiアルゴリズム（最適）に対する精度の減少度を表す 図 5.
実験結果 (cont’d) Online Step アルゴリズムにおいて，状態の推定精度の減少度を 0.1% とするために必要な追加観測データ数 図 6.
まとめ Online Step および Online Variable Window アルゴリズムが，固定Windowと比較して高い性能を発揮することを示した． これらのアルゴリズムを用いると少ないリソースで Viterbiアルゴリズムに近い性能が得られる