Tokyo Research Laboratory
疎な相関グラフの学習による
相関異常の検出
IBM東京基礎研究所
井手 剛
| 2009/03/03 | 第9回 DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
内容






やりたいこと
グラフィカル・ガウシアン・モデルと関連研究
疎構造学習の方法
相関異常度の定義
実験結果
まとめ

Page 2
Acknowledgement
• This is a joint work with Aurelie C. Lozano, Naoki Abe, and Yan Liu (IBM T. J. Watson
Research Center). The author thanks them for fruitful discussions.
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
内容






やりたいこと
グラフィカル・ガウシアン・モデルと関連研究
疎構造学習の方法
相関異常度の定義
実験結果
まとめ
Page 3
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
やりたいこと: 変数同士の「関係の崩れ」を検出したい
x2
「x2 と x4の関係がどうもおかしい」
x4
変数個別に見ているだけでは検知できない
異常を捉えたい
(「アクセルを踏んでもうまく吹けない」 など)
reference
data
Page 4
| 2009/03/03 | 第9回DMSM
「本当の不具合は x2 に潜んでい
る可能性が高い」
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
正常時のデータを元にして、個々の変数の相関異常度を計算したい
x2
各変数の相関異常度を計算したい
x4
異常度
variable
reference
data
Page 5
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
何が難しいか: ノイジーなセンサーデータでは変数同士の関係は非常に不安定。
Actual spot rates データの例(1/2)
 各国通貨の対ドルレートの変動
を表した時系列データ
 ほとんどの相関係数の値は非常
に不安定

Page 6
経済メカニズム自体は変わってい
ないはずだが、値は安定してない
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
何が難しいか: ノイジーなセンサーデータでは変数同士の関係は非常に不安定。
Actual spot rates データの例(2/2)
 相関の強いペアについては関係が安定している
個々の変数の「近傍」だけ見れば
ノイズにだまされないはず
Page 7
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
本質的なつながりだけを残すように、変数の依存関係を表すグラフを学習したい
→ 疎な構造を学習したい
 入力: (今回は)実数値の、多次元データ
 出力: つながりを表す重み付きグラフ
• 頂点は各変数
• 辺は変数間の関連
• 2つの頂点間に辺がない=
他を与えた時に両者は独立
Page 8
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
全体の方針: 疎な構造学習によって近傍を選択する。
そしてその近傍に基づき各変数の異常度スコアを計算する
 問題

多変量データふたつを比べて、その相違に対する個々の変数の寄与度を計算
スパース
構造学習
各変数の
スコアリング
reference
data
Page 9
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
内容






やりたいこと
グラフィカル・ガウシアン・モデルと関連研究
疎構造学習の方法
相関異常度の定義
実験結果
まとめ
Page 10
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
Graphical Gaussian Model (GGM) におけるグラフの定義:
「精度行列の行列要素がゼロなら辺なし」
 精度行列 Λ = 共分散行列 S の逆行列
 例: Λ1,2 = 0 なら x1 と x2 は条件付き独立で、頂点1と2の間には辺はない

なぜなら exp の部分が因子化されるから:
 例2: 6変数の場合の例
Page 11
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
疎な精度行列が得られるようにしたい。しかし、ノイジーなデータでは、行列要素が
厳密にゼロになることは決してない
 素朴な方法: Sの逆行列を求めて、ある閾値以下の要素をゼロとしてしまう

ダメ。確率モデルじゃなくなってしまう。
• 例えば、そういう精度行列は正定値ではなくなる
 伝統的な方法: 共分散構造選択(Dempster 1972)

ざっくり言えば以下の繰り返し
• 小さい行列要素をひとつゼロにする
• それを拘束として、確率モデルを推定しなおす
• その上で小さい行列要素をひとつゼロにする
• それを拘束として、確率モデルを推定しなおす
• ...
Page 12
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
グラフィカル・ガウシアン・モデル(GGM)の学習には最近大きな動きがあった:
「手作業」によるスパース化から、L1正規化へ
 共分散構造選択(古典理論)


Dempster (1972):
• 小さい偏相関係数から順に枝狩りをする
Drton & Perlman (2008):
• 辺を枝狩りする時の統計的検定を改良
 L1正規化に基づく方法(盛り上がり中)



共分散行列の逆行列の存在を
仮定しているので、変数の数が
増えると実質的に計算不能!

Meinshausen & Bühlmann (2006):
• ラッソ回帰に基づくスパース構造学習の一致
性を証明
Barnergee (2006):
• ブロック勾配法により精度行列を直接求める
Friedman et al. (2008):
• ブロック勾配法から計算効率のよい固定点方
程式を導く
その他いろいろ
変数の数 > 標本数 の時ですら
構造学習が可能
(でもそう甘くはない...)
Page 13
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
その他の関連研究
 2標本検定: ふたつのデータセット同士の相違を仮説検定する


問題が違う: 個々の変数のスコアリングまではしない
伝統的には漸近分布での仮説検定: ノイジーで小標本なデータだと使いにくい
 相関係数の検定


Wishart 分布論に基づく検定の手法がある
• たとえば Anderson, “An Introduction to Multivariate Statistical Analysis”, Willy 参照
が、ノイジーで小標本なデータには使い物にならない
 非線形への拡張は今後の課題


GGMに基づく以上、今回は線形な相関異常のみに着目している
理論的には可能だと思われるが、うまい実例が見つかるかが(論文的には)カギ
Page 14
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
内容






やりたいこと
グラフィカル・ガウシアン・モデルと関連研究
疎構造学習の方法
相関異常度の定義
実験結果
まとめ
Page 15
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
L1正規化項付きの最尤方程式を解くことでスパース構造学習を行うことにする
 入力: 共分散行列 S


平均ゼロ、分散1に標準化したデータが前提
普通、ランク落ちしているので逆は存在せず
 出力: スパースな精度行列 Λ


精度行列 = 共分散行列の逆行列
正定でスパースなΛを何とかして求める必要がある
 方法: L1正規化項付きの最尤方程式を解く
対数尤度
Page 16
| 2009/03/03 | 第9回DMSM
正規化項
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
Graphical lasso algorithm は、L1正規化項付きの最尤方程式を解くための
非常に効率のよいアルゴリズムである
 精度行列を1列(1行)づつ最適化

灰色部分を定数だと思って、青色部分についての最適化問題を導く

青色ベクトルについての最適化問題は、L1正則化項付きの2次計画問題になる
• 劣勾配法により効率のよい固定点方程式を導ける(Friedman et al. 2008)
 スパースな精度行列を、明示的な逆行列計算なしに求めることができる

副産物として、精度行列の逆も(逆行列計算なしに)求まる
• 標本共分散行列Sの修正版のようなもの
(詳しくは: T. Idé et al., “Proximity-Based Anomaly Detection using Sparse Structure Learning,” SDM 2009, to appear.)
Page 17
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
正規化項の係数ρは相関係数の閾値と解釈できる
 今の問題設定では、異常検知性能を最大化するようにρを決める
 ρは、「相関係数のどの値までを有意な相関とみなすか」の指標と解釈できる


2×2の問題を解析的に解くことで、次の結果を導ける(Idé et al., 2009)
相関係数 r が ρ よりも小さいと、対応する偏相関係数はゼロになる
• つまり、ρより小さい |相関係数| はゼロセットされるというような感じ
(T. Idé et al., “Proximity-Based Anomaly Detection using Sparse Structure Learning,” SDM 2009, to appear.)
Page 18
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
内容






やりたいこと
グラフィカル・ガウシアン・モデルと関連研究
疎構造学習の方法
相関異常度の定義
実験結果
まとめ
Page 19
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
GGMとして学習された確率モデルを使って、
各変数の異常度をKL距離として定義する
 データAとデータBを比べた時の、第 i 番目の変数のスコアの定義
条件付き分布同士
のKL距離
 GGMの範囲では解析的に計算ができる

diAB = (xi の近傍グラフの次数の変化を表す項)
+ (xi の近傍グラフの密集度を表す項) + ( xi それ自身の分散の変化を表す項)
データAにおける
xi の近傍
Page 20
| 2009/03/03 | 第9回DMSM
データBにおける
xi の近傍
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
内容






やりたいこと
グラフィカル・ガウシアン・モデルと関連研究
疎構造学習の方法
相関異常度の定義
実験結果
まとめ
Page 21
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
実験1: 共線形性が強いデータでの構造学習
実験の設定
 [email protected] Archive

いくつかの変数がほぼ完全相関
 ノイズを入れる前後における構造の変化を測定


データから構造学習
各変数に、標準偏差の10%分のノイズを混ぜてもう一度構造学習
 比較した手法



“Glasso”
• Friedman, Hastie, & Tibshirani., Biostatistics, 2008
“Lasso”
• Meinshausen & Bühlmann, Ann. Stats. 2006
“AdaLasso”
• 上記のアルゴリズムにおいて、回帰をAdaptive Lasso [H. Zou, JASA, 2006] で行ったもの
Page 22
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
実験1: 共線形性が強いデータでの構造学習: Graphical lassoアルゴリズムは、
Lasso回帰に基づく他の構造学習法に比べて圧倒的にノイズに頑強である
 sparsity:

グラフがどれだけスパースか
 flip prob.:

ノイズ印加前後でどれだけ辺が変わるかの
確率(辺の発生 or 消滅)
 Meinshausen & Bühlmann の方法は、
共線形性の下で結果が不安定


Dempsterの伝統的な共分散構造選択の欠
点を引き継いでいる
これはL1回帰で構造学習をやる際の避け
がたい問題
• 相関が強い変数の中のどれかひとつを
強制的に選ぶので、どれが選択されるか
はほとんど偶然による
Page 23
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
実験2: sensor_error データでの異常度のスコアリング
実験の設定
 sensor_error データ



ある機械システムの実測定データ(M=44変数)
79個の正常時データと20個の異常データ
異常データでは、2つの変数が相関異常を呈している(右図)
正
常
時
 79×20個の正常-異常ペアで異常検知をしてROC曲線を
描かせる

2つの異常変数が常にトップ2を占めることを期待
• この時、AUC (area under curve)はほぼ1となる
Page 24
| 2009/03/03 | 第9回DMSM
異
常
時
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
実験2: sensor_error データでの異常度のスコアリング
構造学習による近傍選択を組み込むことで、擬陽性を大幅に減らせる
 3つの別のスコアと比較



尤度に基づくもの
近傍グラフを素朴に k-NN法で作ったもの
あるヒューリスティックスに基づいたスコア定義を用い
たもの [Idé et al, ICDM 07]
 KL距離によるスコアが最も良い成績

しかも理論的に素性正しい
Page 25
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
内容







やりたいこと
グラフィカル・ガウシアン・モデル
関連研究
疎構造学習の方法
相関異常度の定義
実験結果
まとめ
Page 26
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
Tokyo Research Laboratory
まとめ
 相関異常のスコアリングという問題に対して、疎な構造学習を始めて適用した
 最近提案された疎構造学習の手法の比較検討を行い、代表的な手法と目される
Meinshausen-Bühlmann の方法が、共線形性の下では破綻すること、また、精度行列
を直接L1正規化する方法はそのような弱点を持たないことを示した
 疎なGGMに対して計算される条件付き期待KL距離を異常度尺度とすることにより、実問
題において、相関異常の検知性能を顕著に上げられることを示した
Page 27
| 2009/03/03 | 第9回DMSM
© Copyright IBM Corporation 2008
ダウンロード

グラフィカル・ガウシアン・モデル