スパース構造学習の 異常検知への応用 IBM東京基礎研究所 井手 剛 | 2008/10/30 | IBIS 2008.

Slides:



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

生物統計学・第 5 回 比べる準備をする 標準偏差、標準誤差、標準化 2013 年 11 月 7 日 生命環境科学域 応用生命科学 類 尾形 善之.
『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日: 5 月 23 日(金) 発表者:時田 陽一.
土木計画学 第3回:10月19日 調査データの統計処理と分析2 担当:榊原 弘之. 標本調査において,母集団の平均や分散などを直接知ることは できない. 母集団の平均値(母平均) 母集団の分散(母分散) 母集団中のある値の比率(母比率) p Sample 標本平均 標本分散(不偏分散) 標本中の比率.
マルチレベル共分散構造分析 清水裕士 大阪大学大学院人間科学研究科日本学術振興会. 本発表の概要・目的 個人 - 集団データの階層性 個人 - 集団データの階層性 階層的データは従来の方法では十分な分析が できない 階層的データは従来の方法では十分な分析が できない 従来の方法は何が不十分なのか?
近傍保存原理による異常検知 Anomaly Detection with Neighborhood Preservation Principle 井手剛 IBM東京基礎研究所 | 2007/11/07 | IBIS 2007 |
グラフィカル多変量解析 ----目で見る共分散構造分析----
看護学部 中澤 港 統計学第5回 看護学部 中澤 港
寺尾 敦 青山学院大学社会情報学部 社会統計 第13回 重回帰分析(第11章後半) 寺尾 敦 青山学院大学社会情報学部
疎な相関グラフの学習による 相関異常の検出
多変量解析 -重回帰分析- 発表者:時田 陽一 発表日:11月20日.
データ解析 静岡大学工学部 安藤和敏
統計的仮説検定 基本的な考え方 母集団における母数(母平均、母比率)に関する仮説の真偽を、得られた標本統計量を用いて判定すること。
Pattern Recognition and Machine Learning 1.5 決定理論
第4回 (10/16) 授業の学習目標 先輩の卒論の調査に協力する。 2つの定量的変数間の関係を調べる最も簡単な方法は?
統計解析 第9回 第9章 正規分布、第11章 理論分布.
Bassモデルにおける 最尤法を用いたパラメータ推定
統計的仮説検定の考え方 (1)母集団におけるパラメータに仮説を設定する → 帰無仮説 (2)仮説を前提とした時の、標本統計量の分布を考える
心理統計学 II 第7回 (11/13) 授業の学習目標 相関係数のまとめと具体的な計算例の復習 相関係数の実習.
Bias2 - Variance - Noise 分解
Bias2 - Variance - Noise 分解
臨床統計入門(3) 箕面市立病院小児科  山本威久 平成23年12月13日.
第3章 重回帰分析 ー 計量経済学 ー.
第3章 重回帰分析 ー 計量経済学 ー.
「データ学習アルゴリズム」 第2章 学習と統計的推測 報告者 佐々木 稔 2003年5月21日 2.1 データと学習
応用統計学の内容 推測統計学(inferential statistics)   連続型の確率分布   標本分布   統計推定   統計的検定.
高次元データにおける幾つかの検定統計量の漸近分布について
ガウス過程による回帰 Gaussian Process Regression GPR
第6章 カーネル法 修士2年 藤井 敬士.
相関分析.
高次元データの解析 -平均ベクトルに関する検定統計量の 漸近分布に対する共分散構造の影響-
第9章 混合モデルとEM 修士2年 北川直樹.
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
P3-12 教師が真の教師のまわりをまわる場合のオンライン学習 三好 誠司(P)(神戸高専) 岡田 真人(東大,理研,さきがけ)
T2統計量・Q統計量 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
第14章 モデルの結合 修士2年 山川佳洋.
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
1.標本平均の特性値 2.母分散既知の標本平均の分布 3.大数法則と中心極限定理
標本分散の標本分布 標本分散の統計量   の定義    の性質 分布表の使い方    分布の信頼区間 
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
主成分分析 Principal Component Analysis PCA
多変量解析 ~主成分分析~ 1.主成分解析とは 2.適用例と解析の目的 3.解析の流れ 4.変数が2個の場合の主成分分析
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
Data Clustering: A Review
Black Litterman Modelによる最適化
パターン認識特論 担当:和田 俊和 部屋 A513 主成分分析
ガウシアン確率伝搬法の 近似精度に対する理論解析
知識科学研究科 知識システム構築論講座 林研究室 佛明 智
データの型 量的データ 質的データ 数字で表現されるデータ 身長、年収、得点 カテゴリで表現されるデータ 性別、職種、学歴
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
第3章 線形回帰モデル 修士1年 山田 孝太郎.
「アルゴリズムとプログラム」 結果を統計的に正しく判断 三学期 第7回 袖高の生徒ってどうよ調査(3)
データ解析 静岡大学工学部 安藤和敏
最尤推定・最尤法 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
第5回 確率変数の共分散 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
情報の集約 記述統計 記述統計とは、収集したデータの分布を明らかにする事により、データの示す傾向や性質を要約することです。データを収集してもそこから情報を読み取らなければ意味はありません。特に膨大な量のデータになれば読みやすい形にまとめて要約する必要があります。
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
高次元データにおける2次形式の近似について
藤本翔太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回 二宮 崇.
ベイズ音声合成における 事前分布とモデル構造の話者間共有
データ解析 静岡大学工学部 安藤和敏
ガウス分布における ベーテ近似の理論解析 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
最小二乗法による線形重回帰分析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
プログラミング論 相関
わかりやすいパターン認識 第6章 特徴空間の変換 6.5 KL展開の適用法 〔1〕 KL展開と線形判別法 〔2〕 KL展開と学習パターン数
Jan 2015 Speaker: Kazuhiro Inaba
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

スパース構造学習の 異常検知への応用 IBM東京基礎研究所 井手 剛 | 2008/10/30 | IBIS 2008

構造学習 = 多変数系において変数同士のつながり具合を調べること 入力: (今回は)実数値の、多次元データ 出力: つながりを表す重み付きグラフ クラスタリングとちょっと似ているけど違う つながりは排他的でない 頂点は各変数 辺は変数間の関連 2つの頂点間に辺がない=他を与えた時に両者は独立 | 2008/10/30 | IBIS 2008

スパースな構造学習 = 不要なノイズを除去し、変数間の真の関係を見出すこと スパースな構造学習 = 不要なノイズを除去し、変数間の真の関係を見出すこと ノイズによって、すべての変数は多かれ少なかれつながっている 100%完全に独立、というような関係は、実数値データではまずありえない 実例: 為替レートデータ@UCR Archive 相関係数でつながり方を見てみる 1.つながり具合はノイズの影響に直撃され、値が極めて不安定 2.しかし相関の強いペアについては比較的安定 近傍が大切 ↓ 左と(右)のデータの相関係数の値 (BEF,FRF)以外は非常に不安定である | 2008/10/30 | IBIS 2008

全体の方針: スパース構造学習によって近傍を選択する。 そしてその近傍に基づき各変数の異常度スコアを計算する 問題 多変量データふたつを比べて、その相違に対する個々の変数の寄与度を計算 2標本検定にちょっと似ているけど違う 求めたいのは各変数のスコア。データ全体の相違の有無ではない。 スパース構造学習 各変数の スコアリング | 2008/10/30 | IBIS 2008

グラフィカル・ガウシアン・モデル(GGM)の学習には最近大きな動きがあった: 「手作業」によるスパース化から、L1正規化へ 偏相関係数が非ゼロ ⇒ 2つの変数はつながっている 偏相関係数行列 = 共分散行列の逆行列 GGMによる構造学習の歴史 共分散構造選択 Dempster (1972): 小さい偏相関係数から順に枝狩りをする Drton & Perlman (2008): 辺を枝狩りする時の統計的検定を改良 L1正規化に基づく方法(盛り上がり中) Meinshausen & Bühlmann (2006): ラッソ回帰に基づくスパース構造学習の一致性を証明 Barnergee (2006): ブロック勾配法により精度行列を直接求める Friedman et al. (2008): ブロック勾配法から計算効率のよい固定点方程式を導く | 2008/10/30 | IBIS 2008

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

Graphical lasso algorithm は、L1正規化項付きの最尤方程式を解くための 非常に効率のよいアルゴリズムである 精度行列を1列(1行)づつ最適化 灰色部分を定数だと思って、青色部分についての最適化問題を導く 青色ベクトルについての最適化問題は、L1正則化項付きの2次計画問題になる 劣勾配法により効率のよい固定点方程式を導ける(Friedman et al. 2008) スパースな精度行列を、明示的な逆行列計算なしに求めることができる 副産物として、精度行列の逆も(逆行列計算なしに)求まる 標本共分散行列Sの修正版のようなもの | 2008/10/30 | IBIS 2008

正規化項の係数ρは相関係数の閾値と解釈できる 今の問題設定では、異常検知性能を最大化するようにρを決める ρは、「相関係数のどの値までを有意な相関とみなすか」の指標と解釈できる 2×2の問題を解析的に解くことで、次の結果を導ける(Idé et al., 2009) 相関係数 r が ρ よりも小さいと、対応する偏相関係数はゼロになる つまり、ρより小さい |相関係数| はゼロセットされるというような感じ | 2008/10/30 | IBIS 2008

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

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

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

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

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

謝辞 This work is based on a submitted paper coauthored with Aurelie C. Lozano, Naoki Abe, and Yan Liu (IBM T. J. Watson Research Center). I acknowledge them for fruitful discussions. | 2008/10/30 | IBIS 2008