近傍保存原理による異常検知 Anomaly Detection with Neighborhood Preservation Principle 井手剛 IBM東京基礎研究所 | 2007/11/07 | IBIS 2007 |

Presentation on theme: "近傍保存原理による異常検知 Anomaly Detection with Neighborhood Preservation Principle 井手剛 IBM東京基礎研究所 | 2007/11/07 | IBIS 2007 |"— Presentation transcript:

1 近傍保存原理による異常検知 Anomaly Detection with Neighborhood Preservation Principle
井手剛 IBM東京基礎研究所 | 2007/11/07 | IBIS 2007 |

2 発表の内容 問題設定 近傍保存原理 確率的近傍グラフに基づく異常度の定義 実験結果 まとめ
| 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

3 問題設定 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

4 問題設定 (1/2): 「変化分析」という問題を設定する。「変化検出」の一般化に当たる。
問題設定 (1/2): 「変化分析」という問題を設定する。「変化検出」の一般化に当たる。 data set A data set B … x1 x2 xN … 問題 1 (変化検出): AとBが違うかどうかを言う 問題 2 (変化解析 ): AとBが与えられた時，どの変数が両者の相違に効いているのかを言う | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

5 問題設定 (2/2): かなり動的で相関の強い時系列データを想定する。
問題設定 (2/2): かなり動的で相関の強い時系列データを想定する。 data set A data set B 典型的応用例 センサー検査（異常センサーを見つける） … x1 x2 xN … 実データでよくある特徴 高度に動的 時系列間の強い相関 異種混合的 教師情報は与えられない | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

6 ? … … 使える既存手法は乏しい 時系列アラインメント (DTWなど) 2標本検定 PCAなどで潜在構造を求めるもの
[Berndt 94, Keogh 00, …] ? … … 高度に動的なデータだと重ね合わせても無意味 2標本検定 [Friedman 79, Henze 88, Gretton 07, …] 変化検出には有効 変化分析は困難（属性の同定は簡単でない） PCAなどで潜在構造を求めるもの [Papadimitriou 05, Idé 05, …] ある程度データがおとなしくないと安定した潜在構造を抽出できない  実験参照 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

7 Key question: そもそも2つのデータの間の何が共通なのか。
こんなにも違うデータを比較する手段などあるのだろうか？ 「近傍を信じよ」 （近傍しか信じない） data set A data set B … … | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

8 近傍保存原理 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

9 やりたいこと: 各時系列の「異常度」を計算すること
data set A data set B variable 異常度 test data reference data t = (time index) t = (time index) | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

10 相関異常を見つけたい。問題をグラフ比較の問題とみなす。
data set A data set B variable 異常度 test data reference data dissimilarity graph Problem 二つのグラフの相違に，どの頂点が一番効いているだろうか？ x1 x2 .. 0.2 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

11 相違度が満たすべき条件 similarity or correlation
| 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

12 以下では、相関係数の大きさを類似度にとり、それから相違度を定義
もっとも単純な選択 物理的なセンサーの場合，通常の相関係数を考えることは合理的 本定式化は相違度の詳細には特に依存しない 時系列 ｉ と j の間の相関係数 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

13 Key observation: 大局的には何の共通性がなくても，局所的に見ると保存されるものはある
data set A グラフの大局的構造は不安定 時系列が高度に動的なため 強く相関している対の結合は比較的安定 高度な動的なデータでも成り立つ data set B test data reference data dissimilarity graph 近傍保存原理 系が普通に動作していれば、強く相関している変数対の「結合の固さ」はほとんど変わらない | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

14 Our approach (1/2): 相違度グラフを近傍グラフの和に分解し、個々の近傍グラフの「固さ」を評価
k-近傍グラフ test dissimilarity graph graph decomposition Comparison to give anomaly score Evaluation reference | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

15 Our approach (2/2): 異常度 = 近傍グラフの「固さ」の変化
近傍グラフの「固さ」を評価する 「固さ」の変化が異常を示唆する Comparison to give anomaly score Evaluation | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

16 （参考） 近傍グラフを構成する手順例（自明）
k を決める たとえば1 相違度行列の各列に対し， 相違度最小のものから小さい順にk個えらぶ 相手の番号と相違度を記録する x1 x2 x3 x4 0.2 2 8 4.2 1.3 X3 0.6 X4 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

17 確率的近傍グラフによる異常度の定義 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

18 近傍グラフの「固さ」は、ノード間の結合確率 の和として定義できる
近傍グラフの「固さ」は、ノード間の結合確率 の和として定義できる 「固さ」の定義は無数にありえるが、恣意的なものだと値の解釈が難しい。 何かの確率として得られればうれしい。 グラフの辺が、確率的な結合を表していると想像してみる。 : 近傍 j に対する、頂点 i の結合確率 が与えられたとすると、頂点 i まわりの結合の固さは次のように自然に定義できる neighborhood to i | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

19 対応する近傍グラフの固さの差を異常度として定義する。
異常度スコアの定義 Evaluation of tightness Comparison to give anomaly score * （詳細） データセットが2つあるから，各変数の近傍の定義も2通りある。別のデータを使ったとすると異常度は 最終的なスコアは、二つのスコアの最大値として定義される | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

20 パープレキシティーを定数に（Hi: エントロピー）
は確率的近傍の考えを使って定義できる。 次の問題を解くことで を定める 「与えられた近傍ノード数に対し、平均相違度を最小化せよ」  c.f. Hinton-Roweis 03 平均相違度を最小化 パープレキシティーを定数に（Hi: エントロピー） 規格化条件  近傍ノード数を定数ということ この問題の解: ただし 近傍グラフの辺を「ソフト化」したことに対応 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

21 Eスコアの諸性質: p値の差として定義されているので解釈が容易
自己結合項 を含めて結合確率を定義することにより、周りとあまり関係なくふらついているような変数の寄与を自動的に割り引くことができる その場合 近傍グラフの固さとしてはほとんどゼロ  したがって（正常なら）固さの差もまたほとんどゼロ が主要な入力パラメター 原理的には k は局所的なクラスターの最小サイズ p値の差としてスコアが定義されているので解釈がしやすい 上下限が存在するので、たとえば 「0.5」という値がどういう意味を持つのかすぐ分かる | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

22 実験結果 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

23 実験結果 (1/3): 弱く動的なデータと強く動的なデータを比較する
実験結果 (1/3): 弱く動的なデータと強く動的なデータを比較する Motor Current (N=20) UCRアーカイブで入手可能 (a) すべてが “healthy” (b) 下の二つが “1 broken bar”、残りは“healthy” 相関は強いが、あまり動的でない 実際の機械のセンサーデータ (a) 正常時 (b) センサー配線ミスを含むデータ 3つのセンサーの信号が入れ替わっている 相関が強く高度に動的 (a) … (b) … vs “Machine” (N=61) (a) (b) … … vs | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

24 実験結果 (2/3): 両者のデータを多次元尺度構成法的に可視化してみる
実験結果 (2/3): 両者のデータを多次元尺度構成法的に可視化してみる Motor Current (a) と (b) の間で、大局的な構造は保たれている 仕込んだ“1 broken bar”を図から見つけるのは容易 このようなデータならPCAや他の時系列予測のような手法でもOK 大局的には何の共通性もない 図を見ても異常センサー（*，×，+）は分からない PCA系の異常検知手法は適用困難 broken bar “Machine” | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

25 実験結果 (3/3): われわれの異常度は、明瞭に異常センサーを浮き彫りにしている
実験結果 (3/3): われわれの異常度は、明瞭に異常センサーを浮き彫りにしている 実際の機械系の実際のセンサーエラーに対して異常度を計算した 主たるエラーは配線ミス 人の目では見つけるのが困難： センサー自体は生きているため 右図： 異常度の計算例 加速度センサーの3軸が入れ替わっている もっとも検知が難しかった例だが，非常に明瞭に異常センサーを特定している k依存性は、kが小さい限りはあまり重大ではない | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

26 まとめ | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

27 まとめ 「変化解析」というタスクを定式化した。 動的なデータの比較のために、近傍保存原理という見方を提案した。
近傍保存原理を確率的近傍グラフで実現する方法を提案した。 The author acknowledges Spiros Papadimitriou and Michail Vlachos (IBM T.J. Watson Research Center) for fruitful discussions. 機械学習研究グループ T-PRIMAL (Tokyo PRobabilistic Inference and MAchine Learning)での議論に感謝します。 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

28 Backup | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL

29 定義： エントロピーと平均相違度 i の近傍 | 2007/11/07 | IBIS 2007 | 井手剛 powered by T-PRIMAL