非制約最小二乗密度比推定法 uLSIF を用いた外れ値検出
20 likes21,635 views
「異常検知と変化検知」 輪読会 第11章 密度比推定による異常検知 http://connpass.com/event/35625/ LT 資料
非制約最小二乗密度比推定法 uLSIF を用いた外れ値検出
- 2. 本?日紹介する論論?文 ?? “Statistical Outlier Detection Using Direct Density Ratio Estimation” 直接密度度?比推定を?用いた統計的外れ値検出 ?? Shohei Hido (?比?戸 ?将平) et al. 元 IBM Researcher 現 ?PFN Chief Research Officer ?? Knowledge and Information Systems 2011 2
- 3. この論論?文を選んだ理理由 ?? 井?手剛 杉?山将『異異常検知と変化検知』 ?? Chapter 11 ?密度度?比推定による異異常検知 –?カルバック?ライブラー密度度?比推定法 ?? KLIEP (Sugiyama+ 2008) –?最?小２乗密度度?比推定法 ?? LSIF (Kanamori+ 2009) ?? ?非制約最?小?二乗密度度?比推定法 ? –?uLSIF (Kanamori+ 2009) ?? ?本に載ってない最新?手法が！ 3
- 4. 論論?文概要 ?? 【内容】 統計的外れ値検出法として、既存?手法お よび確率率率密度度?比を?用いた?手法を網羅羅的に ?比較した ?? 【結論論】 確率率率密度度?比を ?uLSIF ?で求める?手法が、 精度度が良良く、速度度も速い 4
- 5. 発表の流流れ 1.? 研究背景 2.? 確率率率密度度?比による外れ値検出 3.? 直接密度度?比推定法の?比較 4.? やってみた 5.? 既存?手法 6.? 実験 5
- 6. 研究背景 ?? 外れ値検出の問題として、inlier-based outlier detection という問題がある ?? この問題に対して、One-Class SVM や ? Local Outlier Factor が使われる ?? これに対して次を提案する 1. 密度度?比を外れ値のスコアに使う 2. 密度度?比の推定法に ?uLSIF ?を使う 6
- 7. Inlier-based Outlier Detection ?? 外れ値を検出したい場合、外れ値を含ま ない ?(inlier) ?データを持っている場合が ? 多い ?? 例例：機器の正常データ ?? 外れ値を含まないデータ ?(inlier) ?と外れ値 を含むデータ ?(contains outlier) ?を持って いる場合に、外れ値を検出する問題を扱 う 7
- 8. Inlier-based Outlier Detection 8 この期間は実際に問題なかった (正常データ ?inlier) 故障の予兆？(outlier)
- 9. 発表の流流れ 1.? 研究背景 2.? 確率率率密度度?比による外れ値検出 3.? 直接密度度?比推定法の?比較 4.? やってみた 5.? 既存?手法 6.? 実験 9
- 10. 問題設定 ?? 外れ値を含まないデータ ?xtr ?? 外れ値を含むデータ ?xte ?? このとき ?xte の中で外れ値を検出したい ?? 提案①： 外れ値のスコアとして確率率率密度度?比を使う 10
- 12. 密度度?比を?用いた外れ値検出 ?? 外れ値は密度度?比が?小さくなる ?? 密度度?比を外れ値のスコアとしたい ?? 密度度?比を求める?手法は?色々ある ?? 提案②： 密度度?比を求める?方法として ?uLSIF を使う 12
- 13. 発表の流流れ 1.? 研究背景 2.? 確率率率密度度?比による外れ値検出 3.? 直接密度度?比推定法の?比較 4.? やってみた 5.? 既存?手法 6.? 実験 13
- 14. 密度度?比を割り算で求めてはいけない ?? xtr と ?xte それぞれの確率率率密度度を求め、? それを割り算する ? ?誤差が?大きい！ ?? バプニックの原理理(Vapnik's principle) 「ある問題を解くときにそれよりも?一般的な問 題を途中段階で得べきでない」 ?? 密度度?比 ?w(x) ?を直接推定する 14
- 15. 直接密度度?比推定法 ?? 直接密度度?比を推定する?手法を紹介する ①? KMM ②? LogReg ③? KLIEP ④? LSIF ⑤? uLSIF 15
- 16. 基本的な考え?方 ?? 密度度?比 ?? 下式両辺が同じになるように ?w(x) ?を推定 16 ? ?同じとは何か？の違いが?手法の違いとなる
- 17. ① KMM (Kernel Mean Matching) ?? Huang et al. 2007 ?? 再?生核ヒルベルト空間上で ?ptr(x) と ? w(x)pte(x) ?の期待値の差を最?小にする ?? w(x) ?の関数形でなく ?xte における w を推定 ?? クロスバリデーションが使えないのが?欠点 17
- 18. ② Logistic Regression (LogReg) ?? 左項 ?p(η=-1) / p(η=1) = nte / ntr で推定 ?? 右項の ?p(η | x) はそれぞれロジスティック 回帰で求める 18
- 19. ③ KLIEP ?? カルバックライブラー密度度?比推定法 ?? 密度度?比を次の式で近似 ?? ptr(x) と ?w(x)pte(x) の ?KL ?ダイバージェン スを最?小にする 19 カーネル
- 21. ④ LSIF ?? Least-Square Importance Fitting ?? w(x) と w-hat(x) の2乗誤差を最?小にする 21 凸?二次計画問題
- 22. ⑤ uLSIF (unconstrained LSIF) ?? LSIF の α ≧ 0 の制約を除去 ?? 解析的に解が求まる 22 ? ?α < 0 ?となった場合は強制的に 0 にする
- 23. ⑤ uLSIF (unconstrained LSIF) ?? LOOCV ?も解析的に求まる ?? カーネルパラメータの選択が?高速化！ 23
- 24. 直接密度度?比推定法まとめ 24
- 25. 直接密度度?比推定法の?比較 ?? KMM ? CV ができない ?? LogReg & KLIEP ? CV ?できるけど遅い ?? LSIF ? CV 可 & 速い、けど解が不不安定 ?? uLSIF ? CV 可 & 速い ?& ?安定 ?? 結論論： ?uLSIF 最強 25
- 26. 発表の流流れ 1.? 研究背景 2.? 確率率率密度度?比による外れ値検出 3.? 直接密度度?比推定法の?比較 4.? やってみた 5.? 既存?手法 6.? 実験 26
- 28. 28
- 29. USPS ?データセット ?? U.S. Postal Service の?手書き数字データ ?? 16 ? 16 = 256 次元 ?? ?人間に読みにくいものが検出された 29
- 30. 発表の流流れ 1.? 研究背景 2.? 確率率率密度度?比による外れ値検出 3.? 直接密度度?比推定法の?比較 4.? やってみた 5.? 既存?手法 6.? 実験 30
- 31. 既存?手法 ?? 提案?手法が良良いのか?比較実験を?行行いたい ?? 密度度?比を使った外れ値検出?手法だけでな く、他の?手法も?比較したい ①?Kernel Density Estimator (KDE) ②?One-class SVM (OSVM) ③?Local Outlier Factor (LOF) 31
- 32. ① Kernel Density Estimator (KDE) ?? pnu(x) と ?pde(x) の密度度をそれぞれ推定 ?? 割り算した値を密度度?比として、外れ値スコ アにする ?? 次元の呪いにより?高次元でうまくいかない 32
- 33. ② One-class SVM (OSVM) 33
- 34. ③ Local Outlier Factor (LOF) 34
- 35. 既存?手法との?比較 ?? 提案した ?uLSIF を使った?方法は、 ?? ①KDE には勝つだろう ?? ②OSVM, ③LOF はパラメータ選択が必要 –?OSVM ? ?ガウスカーネルの ?σ –?LOF ? k-近傍の k ?? uLSIF は、LOOCV で最適なパラメータ選 択ができるのが強み。あと速い。 35
- 36. 発表の流流れ 1.? 研究背景 2.? 確率率率密度度?比による外れ値検出 3.? 直接密度度?比推定法の?比較 4.? やってみた 5.? 既存?手法 6.? 実験 36
- 37. 実験 ?? 3 ?つのデータセットに対して実験 ①? R ?atsch’s ベンチマーク(?二値分類) ②? ハードディスク異異常 ?(SMART) ③? ?ローンリスク (Real Finance) 37
- 38. 実験① ?? R ?atsch’s Benchmark Repository ?? ?二値分類データセット (12個) ?? 訓練データから負例例を全部消去 ?? テストデータには?比率率率 ?ρ ?で負例例を?入れる ?? 検出率率率(true positive) と ?検出精度度(false positive) で ROC 曲線が描かれるので、 その ?AUC で評価する 38
- 40. 40 既存?手法密度度?比を使った?手法 Comp. time ?は ?uLSIF を ?1 とした時の計算時間 表の中の数字は AUC
- 41. ?? uLSIF はおおむね良良い ?? KLIEP も良良いが遅い ?? LogReg は良良いときと悪いときがある 41
- 42. ?? KMM と OSVM は ?σ ?に全サンプル間の距 離離の中央値を使った ?? 遅すぎて使い物にならない 42
- 43. ?? LOF は k を?大きくすれば AUC が?高くなる。 ?? しかし、最適な k を決める?方法はない。 ?? KDE もたまに良良いが遅い 43
- 44. 実験①まとめ ?? uLSIF ?は他の?手法と同じくらい良良い精度度 を出すし、なにより速い。 ?? ooO( 精度度の?比較をしていたはずが、既存 ?手法遅すぎプギャー m9(^Д^) ?としか?言っ てないような?? ?) 44
- 45. 実験② ?? SMART データ ?? ハードディスクのセルフモニタリング ?? 369 サンプル中 178 “good”, 191 “failed” ?? 59 変数中 25 個を使う (Murray+2005) ?? “good” だけの訓練データ ?? ρ ?だけ “failed” を混ぜたテストデータ 45
- 46. ?? AUC は k を?大きくした LOF が良良いが、 めっちゃ遅いので ?uLSIF ?が良良い 46
- 47. 実験③ ?? Real Finance ?データ ?? ローン顧客の7ヶ?月間?行行動データ(11変数) ?? 6ヶ?月後にリスク ?“high”, ?“low” ?か判定 ?? これが正解データになる ?? 訓練 “low” のみ、テスト ?ρ ?だけ “high” ?? 7ヶ?月間のデータでリスク “high” を検出 ?? 4ヶ?月間のデータでリスク “high” を検出 47
- 48. ?? AUC ?は LOF ?に勝利利！ ?? uLSIF 最強！ 48
- 49. まとめ ?? 密度度?比を?用いた外れ値検出?手法を提案 ?? 密度度?比推定には ?uLSIF ?を使う ?? 解が解析的に求まるのでめっちゃ速い ?? ハイパーパラメータの選定も ?LOOCV ?で できるしめっちゃ速い ?? 既存?手法遅すぎ ?m9(^Д^) 49
- 50. おまけ 50 ?? R ?で実装してみた ?(densratioパッケージ) > ?install.packages("densratio") ? > ?vignette("densratio")
- 52. 参考?文献 ?? KLIEP Sugiyama, M., Suzuki, T., Nakajima, S., Kashima, H., von Bünau, P. & Kawanabe, M. Direct importance estimation for covariate shift adaptation. AISM 2008. ?? OSVM, LOF 「異異常検知技術のビジネス応?用最前線」 http://www.slideshare.net/shoheihido/fit2012 52