疎な相関グラフの学習による 相関異常の検出

Slides:



Advertisements
Similar presentations
Maxent model への挑戦 - 驚きとドキドキ感の理論 - 大野ゆかり Phillips et al. (2006) Maximum entropy modeling of species geographic distributions. Ecological Modeling 190:
Advertisements

Maximal likelihood 法に基づく Matched filter について 田越秀行(阪大理) LCGT コヒーレンス解析 WG 修正 Ref: Finn, PRD63, (2001) Pai, Dhurandhar, Bose, PRD64,
生物統計学・第 5 回 比べる準備をする 標準偏差、標準誤差、標準化 2013 年 11 月 7 日 生命環境科学域 応用生命科学 類 尾形 善之.
『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日: 5 月 23 日(金) 発表者:時田 陽一.
土木計画学 第3回:10月19日 調査データの統計処理と分析2 担当:榊原 弘之. 標本調査において,母集団の平均や分散などを直接知ることは できない. 母集団の平均値(母平均) 母集団の分散(母分散) 母集団中のある値の比率(母比率) p Sample 標本平均 標本分散(不偏分散) 標本中の比率.
マルチレベル共分散構造分析 清水裕士 大阪大学大学院人間科学研究科日本学術振興会. 本発表の概要・目的 個人 - 集団データの階層性 個人 - 集団データの階層性 階層的データは従来の方法では十分な分析が できない 階層的データは従来の方法では十分な分析が できない 従来の方法は何が不十分なのか?
2016 年度 計量経済学 講義内容 担当者: 河田 正樹
エクセルと SPSS による データ分析の方法 社会調査法・実習 資料. 仮説の分析に使う代表的なモデ ル 1 クロス表 2 t検定(平均値の差の検定) 3 相関係数.
近傍保存原理による異常検知 Anomaly Detection with Neighborhood Preservation Principle 井手剛 IBM東京基礎研究所 | 2007/11/07 | IBIS 2007 |
グラフィカル多変量解析 ----目で見る共分散構造分析----
看護学部 中澤 港 統計学第5回 看護学部 中澤 港
コンピュータビジョン特論 第8回対象追跡 2006年11月22日 加藤丈和.
確率・統計Ⅰ 第12回 統計学の基礎1 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
多変量解析 -重回帰分析- 発表者:時田 陽一 発表日:11月20日.
Pattern Recognition and Machine Learning 1.5 決定理論
第4回 (10/16) 授業の学習目標 先輩の卒論の調査に協力する。 2つの定量的変数間の関係を調べる最も簡単な方法は?
Bassモデルにおける 最尤法を用いたパラメータ推定
統計的仮説検定の考え方 (1)母集団におけるパラメータに仮説を設定する → 帰無仮説 (2)仮説を前提とした時の、標本統計量の分布を考える
Bias2 - Variance - Noise 分解
第3章 重回帰分析 ー 計量経済学 ー.
第3章 重回帰分析 ー 計量経済学 ー.
「データ学習アルゴリズム」 第2章 学習と統計的推測 報告者 佐々木 稔 2003年5月21日 2.1 データと学習
確率・統計輪講資料 6-5 適合度と独立性の検定 6-6 最小2乗法と相関係数の推定・検定 M1 西澤.
固有空間における コンピュータシステムの障害検知
回帰モデル・クラス分類モデルを 評価・比較するための モデルの検証 Model validation
高次元データにおける幾つかの検定統計量の漸近分布について
脳活動に関するデータ データの種類 データの特徴 脳波・脳磁図・fMRI画像 脳活動とパフォーマンスの関係はきわめて冗長。
スペクトル・時系列データの前処理方法 ~平滑化 (スムージング) と微分~
ガウス過程による回帰 Gaussian Process Regression GPR
第6章 カーネル法 修士2年 藤井 敬士.
相関分析.
高次元データの解析 -平均ベクトルに関する検定統計量の 漸近分布に対する共分散構造の影響-
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
確率・統計Ⅰ 第3回 確率変数の独立性 / 確率変数の平均 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
Online Decoding of Markov Models under Latency Constraints
P3-12 教師が真の教師のまわりをまわる場合のオンライン学習 三好 誠司(P)(神戸高専) 岡田 真人(東大,理研,さきがけ)
T2統計量・Q統計量 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
第14章 モデルの結合 修士2年 山川佳洋.
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
訓練データとテストデータが 異なる分布に従う場合の学習
主成分分析 Principal Component Analysis PCA
多変量解析 ~主成分分析~ 1.主成分解析とは 2.適用例と解析の目的 3.解析の流れ 4.変数が2個の場合の主成分分析
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
Data Clustering: A Review
Black Litterman Modelによる最適化
パターン認識特論 担当:和田 俊和 部屋 A513 主成分分析
部分的最小二乗回帰 Partial Least Squares Regression PLS
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
ガウシアン確率伝搬法の 近似精度に対する理論解析
知識科学研究科 知識システム構築論講座 林研究室 佛明 智
データの型 量的データ 質的データ 数字で表現されるデータ 身長、年収、得点 カテゴリで表現されるデータ 性別、職種、学歴
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
第3章 線形回帰モデル 修士1年 山田 孝太郎.
「アルゴリズムとプログラム」 結果を統計的に正しく判断 三学期 第7回 袖高の生徒ってどうよ調査(3)
データ解析 静岡大学工学部 安藤和敏
第5回 確率変数の共分散 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
情報の集約 記述統計 記述統計とは、収集したデータの分布を明らかにする事により、データの示す傾向や性質を要約することです。データを収集してもそこから情報を読み取らなければ意味はありません。特に膨大な量のデータになれば読みやすい形にまとめて要約する必要があります。
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
藤本翔太1, 狩野裕1, Muni.S.Srivastava2 1大阪大学基礎工学研究科
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆(東大・新領域)
人工知能特論II 第8回 二宮 崇.
ベイズ音声合成における 事前分布とモデル構造の話者間共有
スパース構造学習の 異常検知への応用 IBM東京基礎研究所 井手 剛 | 2008/10/30 | IBIS 2008.
プログラミング論 相関
分枝カット法に基づいた線形符号の復号法に関する一考察
パターン認識特論 カーネル主成分分析 和田俊和.
わかりやすいパターン認識 第6章 特徴空間の変換 6.5 KL展開の適用法 〔1〕 KL展開と線形判別法 〔2〕 KL展開と学習パターン数
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

疎な相関グラフの学習による 相関異常の検出 IBM東京基礎研究所 井手 剛 | 2009/03/03 | 第9回 DMSM

内容 やりたいこと グラフィカル・ガウシアン・モデルと関連研究 疎構造学習の方法 相関異常度の定義 実験結果 まとめ 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

内容 やりたいこと グラフィカル・ガウシアン・モデルと関連研究 疎構造学習の方法 相関異常度の定義 実験結果 まとめ | 2009/03/03 | 第9回DMSM

やりたいこと: 変数同士の「関係の崩れ」を検出したい x2 「x2 と x4の関係がどうもおかしい」 x4 変数個別に見ているだけでは検知できない異常を捉えたい (「アクセルを踏んでもうまく吹けない」 など) 「本当の不具合は x2 に潜んでいる可能性が高い」 reference data | 2009/03/03 | 第9回DMSM

正常時のデータを元にして、個々の変数の相関異常度を計算したい x2 各変数の相関異常度を計算したい x4 variable 異常度 reference data | 2009/03/03 | 第9回DMSM

何が難しいか: ノイジーなセンサーデータでは変数同士の関係は非常に不安定。 Actual spot rates データの例(1/2) 各国通貨の対ドルレートの変動を表した時系列データ ほとんどの相関係数の値は非常に不安定 経済メカニズム自体は変わっていないはずだが、値は安定してない 世界経済のメカニズムは変わっていないという前 | 2009/03/03 | 第9回DMSM

何が難しいか: ノイジーなセンサーデータでは変数同士の関係は非常に不安定。 Actual spot rates データの例(2/2) 相関の強いペアについては関係が安定している 個々の変数の「近傍」だけ見ればノイズにだまされないはず ここにしか真実がない。 | 2009/03/03 | 第9回DMSM

本質的なつながりだけを残すように、変数の依存関係を表すグラフを学習したい → 疎な構造を学習したい 入力: (今回は)実数値の、多次元データ 出力: つながりを表す重み付きグラフ 頂点は各変数 辺は変数間の関連 2つの頂点間に辺がない=他を与えた時に両者は独立 | 2009/03/03 | 第9回DMSM

全体の方針: 疎な構造学習によって近傍を選択する。 そしてその近傍に基づき各変数の異常度スコアを計算する 問題 多変量データふたつを比べて、その相違に対する個々の変数の寄与度を計算 スパース構造学習 各変数の スコアリング reference data | 2009/03/03 | 第9回DMSM

内容 やりたいこと グラフィカル・ガウシアン・モデルと関連研究 疎構造学習の方法 相関異常度の定義 実験結果 まとめ | 2009/03/03 | 第9回DMSM

Graphical Gaussian Model (GGM) におけるグラフの定義: 「精度行列の行列要素がゼロなら辺なし」 例: Λ1,2 = 0 なら x1 と x2 は条件付き独立で、頂点1と2の間には辺はない なぜなら exp の部分が因子化されるから: 例2: 6変数の場合の例 | 2009/03/03 | 第9回DMSM

疎な精度行列が得られるようにしたい。しかし、ノイジーなデータでは、行列要素が厳密にゼロになることは決してない 素朴な方法: Sの逆行列を求めて、ある閾値以下の要素をゼロとしてしまう ダメ。確率モデルじゃなくなってしまう。 例えば、そういう精度行列は正定値ではなくなる 伝統的な方法: 共分散構造選択(Dempster 1972) ざっくり言えば以下の繰り返し 小さい行列要素をひとつゼロにする それを拘束として、確率モデルを推定しなおす その上で小さい行列要素をひとつゼロにする ... | 2009/03/03 | 第9回DMSM

グラフィカル・ガウシアン・モデル(GGM)の学習には最近大きな動きがあった: 「手作業」によるスパース化から、L1正規化へ 共分散構造選択(古典理論) Dempster (1972): 小さい偏相関係数から順に枝狩りをする Drton & Perlman (2008): 辺を枝狩りする時の統計的検定を改良 L1正規化に基づく方法(盛り上がり中) Meinshausen & Bühlmann (2006): ラッソ回帰に基づくスパース構造学習の一致性を証明 Barnergee (2006): ブロック勾配法により精度行列を直接求める Friedman et al. (2008): ブロック勾配法から計算効率のよい固定点方程式を導く その他いろいろ 共分散行列の逆行列の存在を仮定しているので、変数の数が増えると実質的に計算不能! 変数の数 > 標本数 の時ですら構造学習が可能 (でもそう甘くはない...) | 2009/03/03 | 第9回DMSM

その他の関連研究 2標本検定: ふたつのデータセット同士の相違を仮説検定する 相関係数の検定 非線形への拡張は今後の課題 問題が違う: 個々の変数のスコアリングまではしない 伝統的には漸近分布での仮説検定: ノイジーで小標本なデータだと使いにくい 相関係数の検定 Wishart 分布論に基づく検定の手法がある たとえば Anderson, “An Introduction to Multivariate Statistical Analysis”, Willy 参照 が、ノイジーで小標本なデータには使い物にならない 非線形への拡張は今後の課題 GGMに基づく以上、今回は線形な相関異常のみに着目している 理論的には可能だと思われるが、うまい実例が見つかるかが(論文的には)カギ | 2009/03/03 | 第9回DMSM

内容 やりたいこと グラフィカル・ガウシアン・モデルと関連研究 疎構造学習の方法 相関異常度の定義 実験結果 まとめ | 2009/03/03 | 第9回DMSM

L1正規化項付きの最尤方程式を解くことでスパース構造学習を行うことにする 入力: 共分散行列 S 平均ゼロ、分散1に標準化したデータが前提 普通、ランク落ちしているので逆は存在せず 出力: スパースな精度行列 Λ 精度行列 = 共分散行列の逆行列 正定でスパースなΛを何とかして求める必要がある 方法: L1正規化項付きの最尤方程式を解く 対数尤度 正規化項 | 2009/03/03 | 第9回DMSM

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.) | 2009/03/03 | 第9回DMSM

正規化項の係数ρは相関係数の閾値と解釈できる 今の問題設定では、異常検知性能を最大化するようにρを決める ρは、「相関係数のどの値までを有意な相関とみなすか」の指標と解釈できる 2×2の問題を解析的に解くことで、次の結果を導ける(Idé et al., 2009) 相関係数 r が ρ よりも小さいと、対応する偏相関係数はゼロになる つまり、ρより小さい |相関係数| はゼロセットされるというような感じ (T. Idé et al., “Proximity-Based Anomaly Detection using Sparse Structure Learning,” SDM 2009, to appear.) | 2009/03/03 | 第9回DMSM

内容 やりたいこと グラフィカル・ガウシアン・モデルと関連研究 疎構造学習の方法 相関異常度の定義 実験結果 まとめ | 2009/03/03 | 第9回DMSM

GGMとして学習された確率モデルを使って、 各変数の異常度をKL距離として定義する データAとデータBを比べた時の、第 i 番目の変数のスコアの定義 GGMの範囲では解析的に計算ができる diAB = (xi の近傍グラフの次数の変化を表す項) + (xi の近傍グラフの密集度を表す項) + ( xi それ自身の分散の変化を表す項) 条件付き分布同士のKL距離 データAにおける xi の近傍 データBにおける xi の近傍 | 2009/03/03 | 第9回DMSM

内容 やりたいこと グラフィカル・ガウシアン・モデルと関連研究 疎構造学習の方法 相関異常度の定義 実験結果 まとめ | 2009/03/03 | 第9回DMSM

実験1: 共線形性が強いデータでの構造学習 実験の設定 為替レートデータ@UCR Archive いくつかの変数がほぼ完全相関 ノイズを入れる前後における構造の変化を測定 データから構造学習 各変数に、標準偏差の10%分のノイズを混ぜてもう一度構造学習 比較した手法 “Glasso” Friedman, Hastie, & Tibshirani., Biostatistics, 2008 “Lasso” Meinshausen & Bühlmann, Ann. Stats. 2006 “AdaLasso” 上記のアルゴリズムにおいて、回帰をAdaptive Lasso [H. Zou, JASA, 2006] で行ったもの | 2009/03/03 | 第9回DMSM

実験1: 共線形性が強いデータでの構造学習: Graphical lassoアルゴリズムは、Lasso回帰に基づく他の構造学習法に比べて圧倒的にノイズに頑強である sparsity: グラフがどれだけスパースか flip prob.: ノイズ印加前後でどれだけ辺が変わるかの確率(辺の発生 or 消滅) Meinshausen & Bühlmann の方法は、共線形性の下で結果が不安定 Dempsterの伝統的な共分散構造選択の欠点を引き継いでいる これはL1回帰で構造学習をやる際の避けがたい問題 相関が強い変数の中のどれかひとつを強制的に選ぶので、どれが選択されるかはほとんど偶然による | 2009/03/03 | 第9回DMSM

実験2: sensor_error データでの異常度のスコアリング 実験の設定 正常時 異常時 sensor_error データ ある機械システムの実測定データ(M=44変数) 79個の正常時データと20個の異常データ 異常データでは、2つの変数が相関異常を呈している(右図) 79×20個の正常-異常ペアで異常検知をしてROC曲線を描かせる 2つの異常変数が常にトップ2を占めることを期待 この時、AUC (area under curve)はほぼ1となる | 2009/03/03 | 第9回DMSM

実験2: sensor_error データでの異常度のスコアリング 構造学習による近傍選択を組み込むことで、擬陽性を大幅に減らせる 3つの別のスコアと比較 尤度に基づくもの 近傍グラフを素朴に k-NN法で作ったもの あるヒューリスティックスに基づいたスコア定義を用いたもの [Idé et al, ICDM 07] KL距離によるスコアが最も良い成績 しかも理論的に素性正しい | 2009/03/03 | 第9回DMSM

内容 やりたいこと グラフィカル・ガウシアン・モデル 関連研究 疎構造学習の方法 相関異常度の定義 実験結果 まとめ | 2009/03/03 | 第9回DMSM

まとめ 相関異常のスコアリングという問題に対して、疎な構造学習を始めて適用した 最近提案された疎構造学習の手法の比較検討を行い、代表的な手法と目されるMeinshausen-Bühlmann の方法が、共線形性の下では破綻すること、また、精度行列を直接L1正規化する方法はそのような弱点を持たないことを示した 疎なGGMに対して計算される条件付き期待KL距離を異常度尺度とすることにより、実問題において、相関異常の検知性能を顕著に上げられることを示した | 2009/03/03 | 第9回DMSM