異常検知本の読書メモ Part 5(密度比推定による変化検出)

前回に引き続き、密度比を直接推定するコーナー。時系列の変化検出や多変数の依存関係の崩れを捉える構造変化検知の手法を密度比推定で解く。

変化検知問題とカルバックライブラー密度比推定法

変化検知問題は第9節で取り扱った。ある時点tを含む前後で分布がどれくらい異なるかの異常度をはかりたいというのがやりたいことであった(分布変化検知とも呼ばれる)。

式(9.8)a^{(t)} \propto k (1 - {{\mathbf{u}}^{(t)}}^T \mathbf{q}^{(t)})では、前後それぞれ確率密度のパラメータ(uとqがそれ)を計算したが、密度比推定ではそれぞれのパラメータを推定するのではなく、KLダイバージェンスを用いて直接密度比を推定する。これは勾配法を使って簡単に解くことができ、(12.3)式

\alpha(D, D^\prime) = \frac{1}{N} \sum_{i=1}^N \log \hat{r}(\mathbf{x}_i)

のように異常度が計算できる。

KLダイバージェンスの問題点と代替のダイバージェンス

↑のKLダイバージェンスを用いた方法で問題が全て解決すればよいのだが、なかなかそうはいかない。KLダイバージェンスによる異常度は対数関数が入るため、0周辺で微小な変化が敏感に捉えられる反面、ノイズの影響を受けやすく、特にセンサーデータなどでは困ってしまう。そこで、代替となるダイバージェンスがいくつかある。

  • ピアソンダイバージェンス
    • (t-1)2という形をしており、対数関数を含まないためKLダイバージェンスよりロバストに動く
  • 相対ピアソンダイバージェンス
    • 割り算の分母が0になるときがあるので、それをなまして使おうというアイディア
    • 分母がp^\prime(\mathbf{x})だったものを\beta p(\mathbf{x}) + (1 - \beta p^\prime(\mathbf{x}))と置き換える
    • 最小二乗密度比推定と同じような形で閉じて解が得られる
    • ハイパーパラメータのβが増えているので、チューニングの手間は増える

確率分布の構造変化検知

次に、第10章でやった疎構造学習による異常検知(特に異常解析や構造変化検知)を密度比推定で解く。

疎構造学習によってDとD'でそれぞれ確率密度を推定することができるが、実は以下のような問題がある。

  • 構造変化検知をするためにDとD'でそれぞれ精度行列を求めると、本当は辺の重みが変化していない場合でもそれぞれの推定誤差により変化したと検知してしまう場合がある

これをどうにか防ぎたい。ここで、変化前後の密度比が

\frac{N(\mathbf{x} | 0, \Lambda^{-1})}{N(\mathbf{x} | 0, {\Lambda^\prime}^{-1})} \propto \exp(- \frac{1}{2} \mathbf{x}^T (\Lambda_{m, m^\prime} - \Lambda_{m, m^\prime}^\prime) \mathbf{x})

と書けること(式(12.6))に注目する。これから、正規分布による密度比推定をデータから推定することで精度行列の差が直接推定できる。規格化条件を自動的に満たすようなパラメトリックなモデルとして

r_\boldsymbol\Theta(\mathbf{x}) \propto \exp(- \frac{1}{2} \mathbf{x}^T \boldsymbol\Theta \mathbf{x})

を考える(正規化項書くの面倒なのではしょった)。このモデルを元に、pとrp'のKLダイバージェンスを考え、L1の正則化付きで最適化問題として定式化できる。その最適化問題の解き方は元論文を参照のこと。こいつを使うと誤検知を減らすことができる。

また、理論的な解析もAAAI2015でされているらしく、密度比で構造変化検出する方法に必要なサンプル数は、グラフ全体のの辺の数ではなく変化した辺の数によって決まるらしい(そんなに変化してなければサンプル数がオーダー的にはそんなにはいらないということか)。

疎密度比推定の高次拡張

ガウス型のグラフィカルモデルでは共分散相当の構造(つまり二次まで)しか見ることができないが、非線形な特徴ベクトルを使うとより高次の関係も捉えることができる。少しこみいっているが、定式化の手順はさほど変わらずシンプルにできる。

参考

異常検知と変化検知 (機械学習プロフェッショナルシリーズ)

異常検知と変化検知 (機械学習プロフェッショナルシリーズ)

入門 機械学習による異常検知―Rによる実践ガイド

入門 機械学習による異常検知―Rによる実践ガイド