Sparse Gaussian Markov Random Field Mixtures for Anomaly Detectionを読んだ

異常検知の一環で外れ値検知をやっていると「どの事例が外れ値か分かるだけじゃなくて、どの次元がおかしくなったかも教えて欲しい。次元数が100とかあると、どの次元がおかしい動きをしているか人手で見るのは大変」というのをちらほら聞きます。Gaussian Markov Random Field (GMRF)を使うと、どの次元の動きがおかしくなったかも異常検知の枠組みで捉えることができる場合があります。

しかし、この方法は使える状況が限定的で、システムの状態が複数ある(例: 昼と夜で負荷が違うなど)場合にはうまく機能しません。システムに複数の状態が存在することは実データでは珍しくないので、そういった状況にも対応できる方法を探していたところ、ぴったりの論文があったので読みました(ICMD 2016)。GMRFの混合分布に拡張する内容です。

論文、スライド

混合モデルをやるときに難しいのは「混合数Kをいくつにするか?」という問題ですが、この論文では関連度自動決定の枠組みを利用することでモデルに混合数を決定させています(大きめのKを最初に与え、不必要なクラスタを潰す)。提案手法は2ステップからなっており、どちらのステップでも変分ベイズでパラメータ推定を行ないます。

ステップ1: GMRFのパラメータ(混合比率、平均パラメータ、分散共分散パラメータ)を求める
ステップ2: ステップ1で求めたGMRFのパラメータを所与とし、変数毎の重みパラメータgを求める

実データの実験(offshore iol production)でも、PCAやauto-encoderなど既存の方法よりもよい性能を出していました。オイルマネーで5000兆円欲しい!

以下、論文読み会用のメモです。提案手法の前提となるGaussian Markov Random Field/疎構造学習についても前半で簡単に紹介します。

Gaussian Markov Random Field/疎構造学習による異常検知
混合モデルを用いた多峰性への対応
- 問題になること
パラメータ推定
- 変数毎の重みパラメータの推定(Section 3)
- GMRFのパラメータ推定(Section 4)
実験
- 実験: Synthetic data
- 実験: Detecting pump surge failures

Gaussian Markov Random Field/疎構造学習による異常検知

「どこかの変数の動きがおかしい」をどう表現するか?

多変量の変数間の依存関係の崩れ、として表現する
- 一変数だけ見ていても異常かどうかは分からない
依存関係を対マルコフネットワーク(pairwise Markov network)で表わす
- グラフィカル Lasso を用いた異常検知の12ページ
- pairwiseなので3変数以上の相関は考えない(高次は表現も計算も大変…)
- 変数間に関係があればネットワークにエッジがあり、関係なければエッジがない

直接相関と間接相関

変数間の関係を表わす際に、直接相関と間接相関の区別をすることは重要
間接相関
- $p(x_1, x_2)$
- いわゆる疑似相関
- 身長が高ければ算数の能力も高い、ように見える
  - 参考: 統計的消去で擬似相関を見抜こう！ - ほくそ笑む
- 教会の数と殺人事件数に関係があるように見える
- 都市の人口数といった仲介している変数を条件付けして考えなければならない
直接相関
- $p(x_1, x_2 | x_3, \cdots, x_M)$
- これを本来見たい!
- 偏相関係数

直接相関を見るのに都合のよいツール => ガウス分布

我々は直接相関を見たいので、条件付き確率も簡単になるような同時分布を選びたい
- 正規分布は他の変数条件付けた残りの変数も正規分布になるというよい性質があるので、正規分布を使ってマルコフネットワークをモデル化する
- 異常検知本の読書メモ Part 3(疎構造学習による異常検知) - yasuhisa’s blog
補足: 多変量正規分布での条件付き確率
- PRML_2.3.1~2.3.3
- 16ページを睨むと、Gaussian Markov random fields(GMRF)の気持ちが分かってくる

モデル化とパラメータ推定

データは事前に各次元で平均0、分散1に正規化しておく
同時分布をとする
- 精度行列 $\Lambda$ が推定すべきパラメータ
直接相関が分かるように、精度行列の事前分布としてラプラス分布を置く
- ラプラス分布を事前分布として置くと、ノイズがあるようなものは0に潰してスパースにする効果がある
- ちょっとノイズが乗っただけでも検知されると嫌なので、0に潰す
精度行列の要素のとき、とは条件付き独立
- グラフィカル Lasso を用いた異常検知の28ページ
- 精度行列の要素を見ることで、間接相関ではなく直接相関を見ることができる
事後分布を最大にするようなをMAP推定
- 参考: グラフィカル Lasso を用いた異常検知の9ページ
- closed-formでは求まらないので、ブロック座標勾配法で解く
- 他の変数を固定し、ある行について最適化

Gaussian Markov Random Fieldを外れ値検知として使うには?

ある変数についての負の対数尤度を異常度と定義
- $a_i(\mathbf{x}) = - \log p(x_i | \mathbf{x}_{- i})$
- 15ページ目が分かりやすい
  - 個別に見ていると検知できない例
多次元ガウス分布なので、変数毎の異常度は簡単に計算できる
- $a_i(\mathbf{x}) = \frac{1}{2} \log \frac{2 \pi}{\Lambda_{i, i}} + \frac{1}{2 \Lambda_{i, i}} (\sum_{j=1}^M \Lambda_{i, j} x_j)^2$
- 多峰性があると容易ではなくなる

(余談)変化検知

スパース推定の枠組みで変化検知もできる
個別に推定しても差分はスパースにならないので、直接差分を推定する必要がある
- 密度比でやるのが自然
- 今回紹介したい論文には関係ないのでは飛ばす

混合モデルを用いた多峰性への対応

やっと紹介したい論文の内容…
システムの状態が一つの場合、単一のMRF上のスパース推定でよい
しかし、定常でもシステムの状態は複数取る場合がある
- 例: 昼間と夜間、平日と休日、歩いてるとき/走ってるとき/乗り物に乗っているとき
- 論文の6.1. Synthetic data: illustrationなどが分かりやすい
Principled variable-wise scoringとMixture extension of sparse structure learningを一つのモデルで両立しているのが新規性
異常度 $a_i(\mathbf{x}) = - \log p(x_i | \mathbf{x}_{- i})$ はこれまでと同じで、pのモデル化が異なる
K個のMRF(条件付き確率)の重み付き和を考えることで状態が複数あっても大丈夫なようにする
- 論文中の(3)式
- 混合分布
- クラスタの重みが変数毎になっている
$u_i^k$ と $w_i^k$ が唐突に登場して、これは何だという気持ちになるけど、ガウス分布の条件付きのときのことを思い出せば大丈夫

問題になること

混合数Kをどうやって決めるか
- 大き目にKを取っておいて、最適な値はアルゴリズムに決めさせる
- Section 4
ノイズが大きいデータをどう扱うか、学習を安定させるにはどうすればよいか
- sparsity-enforcingな事前分布を入れるとよい

パラメータ推定

変分ベイズで2ステップを繰り返し解く
- 混合分布になった分、推定は複雑にはなっている
ステップ1: GMRFのパラメータを求める
- Section 4
- このステップで変数間の相関やmixture componentがスパースになるようにしている
  - 混合数Kを多めに取っていたので、いらないcomponentをつぶしていく(関連度自動決定がやってくれる)
- 変数間の相関: グラフィカルLassoを繰り返し解く[Friedman+ 08]
  - ブロック座標勾配法かな?
- mixture component: 点推定をすることで関連度自動決定が行なわれる(必要ないクラスタの重みは0に潰れる)
ステップ2: GMRFのパラメータを所与として、変数毎の重みパラメータを求める
- Section 3
- 混合モデルでは変数毎の条件付き確率を出せない?(要出展)ので、このステップで計算する

変数毎の重みパラメータの推定(Section 3)

変数毎の重みパラメータ $g_k^i (\mathbf{x})$ をどう求めていくか
データの生成過程((7)式、(8)式、(9)式)を考えて、変分ベイズで推定
- 生成過程はいたって普通の混合モデル
  - (7)式がvariable-wiseになっているところだけが普通と違う
- パラメータを所与として、隠れ変数の確率分布を求める((13)式)
- 隠れ変数を所与として、パラメータの確率分布を求める((14)式)
これらが求まったら、負の条件付き対数尤度が異常度として計算可能になる

GMRFのパラメータ推定(Section 4)

Section 3で既知として扱っていた、混合ガウスのパラメータを実際に求める
こちらも通常の混合モデルの生成過程と同じように組み立てる
- 異常があった変数間の関係だけ教えて欲しいので、 $\Lambda$ の事前分布にラプラス分布を置いて0に潰れやすいようにする
混合係数に事前分布をおかず、点推定をすることでsparseな解が求められやすいようにしている
- 関連度自動決定と呼ばれる仕組み
- クラスタ数を事前に大きめにしておくと、不必要なクラスタの重みは0になって潰れてくれる
パラメータ/混合重みの推定は変分ベイズ。以下を繰り返す
- パラメータを所与として、混合重みを推定((29)式、(30)式)
- 混合重みを所与として、パラメータ推定((31)式〜(36)式)