問題設定

: 状態 (0は平常状態, 1以上はバースト状態の段階を表す)
: 状態遷移確率 (cで状態を遷移し,(1-c)でとどまる)
: シグナルの到着間隔

から,を予測する問題.

指数混合分布推定

各状態におけるシグナルの到着間隔は,指数分布に従うとする.つまり,

そして,シグナルの到着間隔を指数混合モデルで表す:

を最尤推定する.

最適化問題は,以下で表される.

ただし,

の中にsumがいるよく見る形. Jensenの不等式で下界を導出する.

ただし,. 下界に関して最大化し,の近似を得る. 以下の最適化問題を解く.

Lagrangianは以下で表される.

ただし,. 最適解は以下を満たす.

よって,

これで,の近似を得た.次はこれを,に関して最大化する. 以下の最適化問題を解く.

Lagrangianは以下のようになる.

最適解は以下を満たす.

よって,

以下の順番でパラメータを更新していく. これはいわゆるEMアルゴリズムなんだと思う.

さて,こうしてが得られたわけですが,このままだとどれが平常状態でどれがバースト状態なのかわかりません. しかし,指数分布の期待値がで表されることから,この値が小さい,つまりが大きいものがより強いバースト状態を表しているとして良いでしょう. よって,バースト検出で使う場合,バースト強さの段階を,ただし,とすれば良さそうです. この場合,を平常状態としています.

バースト検出への応用

バースト検出への応用の仕方は,ウェブデータの機械学習 (機械学習プロフェッショナルシリーズ)の2章を参照してください.

人工データで実験をしてみた. 実験結果を以下に示す.

横軸が時間で,縦軸が青い線の場合出現回数で,赤の線の場合が状態を示しています. 一つ目の図が真の値で,二つ目の図が推定結果です. ほぼ完璧に推定できました.

今回は指数混合分布推定をバースト検出に応用してみた. 実際にバースト検出に応用する場合,状態数を2にして,推定したの値をチェックしたほうが良いと思われます. これは,バーストしてないデータでも,無理やりバースト状態を仮定しているためです. 例えば,の時,このデータはバースト状態を持つと仮定するなどです.

実験に使ったコードはgistに置いてます.