異常検知と変化検知 9章 部分空間法による変化点検知
18 likes15,919 views
機械学習プロフェッショナルシリーズ輪読回の資料 2015-11-18 異常検知と変化検知 井手剛／杉山将?著 http://www.kspub.co.jp/book/detail/1529083.html
![変化度の定義 (続き)
異常状態が続くと，異常度は継続して正の値を取るた
め，時刻tにおける変化度は漸化式の形にできる
a
(t)
+ ?
h
a
(t 1)
+ + a(?(t)
)
i
+
(9.3)
=
h?
a
(t 2)
+ + a(?(t 1)
)
?
+
+ a(?(t)
)
i
+
=
h?
[a
(t 3)
+ + a(?(t 2)
)]+ + a(?(t 1)
)
?
+
+ a(?(t)
)
i
+
= ...
[?]+はカッコの中が正なら何
もせず，負ならゼロにする
Section 9.1](https://image.slidesharecdn.com/random-151118085648-lva1-app6891/85/9-12-320.jpg)
![特徴的なパターンの自動抽出
(1/N)
NX
n=1
x(n)
最も素朴には総和平均の
だが，ここでは特徴的な方向を各窓の一次結合で表現する
(一次結合にすると何が良いかは後で説明します)
最も強めあう方向を求めるには
νTν=1の元で，??Xν??2を最大化すれば良い (9.11)
Section 9.4.2
X? = x(1)
?1 + x(2)
?2 + · · · + x(N)
?N (9.10)
X = [x(1)
, . . . , x(N)
], ? ? [?1, . . . , ?N ]T](https://image.slidesharecdn.com/random-151118085648-lva1-app6891/85/9-34-320.jpg)
![特徴的なパターンの自動抽出
(1/N)
NX
n=1
x(n)
最も素朴には総和平均の
だが，ここでは特徴的な方向を各窓の一次結合で表現する
(一次結合にすると何が良いかは後で説明します)
最も強めあう方向を求めるには
νTν=1の元で，??Xν??2を最大化すれば良い (9.11)
二乗ノルムになっているのは計算上の都合?
Section 9.4.2
X? = x(1)
?1 + x(2)
?2 + · · · + x(N)
?N (9.10)
X = [x(1)
, . . . , x(N)
], ? ? [?1, . . . , ?N ]T](https://image.slidesharecdn.com/random-151118085648-lva1-app6891/85/9-35-320.jpg)
![特異値分解(続き)
U [u1,..,uM] と V [ν1,..νM] と置くと9.14の右の式
から XT
U = VΓ1/2
となる．これをXについて整理すると．式9.15が得
られる，これをXの特異値分解 (singular value decomposition SVD)と呼ぶ
X = U 1/2
VT
(9.15)
{u 左特異ベクトル
{ν 右特異ベクトル
{ γ 特異値
Section 9.4.2
XT
ui =
p
i?i](https://image.slidesharecdn.com/random-151118085648-lva1-app6891/85/9-43-320.jpg)
![変化度の定義
X(t)においてr本，Z(t)においてm本の左特異ベクトルを選ぶ
U(t)
r ? [u(t,1)
, u(t,2)
, . . . , u(t,r)
] (9.18)
Q(t)
m ? [q(t,1)
, q(t,2)
, . . . , q(t,m)
] (9.19)
過去側と現在側で1本だけ特異ベクトルを選ぶ場合，変化度
は式(9.9)から
a(t) = 1 u(t,1)T
q(t,1)
(9.20)
(係数κは省略)
Section 9.4.3](https://image.slidesharecdn.com/random-151118085648-lva1-app6891/85/9-47-320.jpg)
![[DL輪読会]Flow-based Deep Generative Models](https://cdn.slidesharecdn.com/ss_thumbnails/20190307-190328024744-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Wasserstein GAN/Towards Principled Methods for Training Generative Adv...](https://cdn.slidesharecdn.com/ss_thumbnails/wgan-1-170224021826-thumbnail.jpg?width=560&fit=bounds)
![SSII2021 [OS2-02] 深層学習におけるデータ拡張の原理と最新動向](https://cdn.slidesharecdn.com/ss_thumbnails/os2-03latest-210610045610-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://cdn.slidesharecdn.com/ss_thumbnails/yokota20190621dlhack-190621022108-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://cdn.slidesharecdn.com/ss_thumbnails/swintransformer-210514020542-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Understanding Black-box Predictions via Influence Functions](https://cdn.slidesharecdn.com/ss_thumbnails/dlhacksinffunc-170822055634-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Set Transformer: A Framework for Attention-based Permutation-Invariant...](https://cdn.slidesharecdn.com/ss_thumbnails/20200221settransformer-200221020423-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]A closer look at few shot classification](https://cdn.slidesharecdn.com/ss_thumbnails/acloserlookatfew-shotclassification-190304034759-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Similar to 異常検知と変化検知 9章 部分空間法による変化点検知 (20)
![[DL輪読会]SOLAR: Deep Structured Representations for Model-Based Reinforcement L...](https://cdn.slidesharecdn.com/ss_thumbnails/20190816-190816001737-thumbnail.jpg?width=560&fit=bounds)
More from hagino 3000 (20)
Recently uploaded (11)
異常検知と変化検知 9章 部分空間法による変化点検知
- 1. 9章 部分空間法による変化検知 機械学習プロフェッショナルシリーズ輪読会 異常検知と変化検知 2015-11-18 @hagino3000 (Takashi Nishibayashi)
- 2. お前だれよ Twitter @hagino3000 facebook Takashi Nishibayashi work at VOYAGE GROUP 普段扱ってるデータ ネット広告配信のログ
- 3. 9章の内容 ? 扱うデータ ? 時系列データ ? やりたい事 ? 図1.1の下二つの異常を捉える事
- 4. 9章の流れ ? 古典技法である累積和法を紹介 ? 近傍法 (部分時系列の導入) ? やっぱり密度比問題で考える ? 特異スペクトル変換法 ? 特異スペクトル変換の高速化
- 5. 9.1 累積和法
- 6. 例:化学プラント反応器 ? 化学プラント反応器で特定の化学物質の濃度を時々 刻々監視しているとする ? たまたま局所的に濃度が高かったり低かったりする ? 「観測1回ごとにひとつひとつ異常度を計算する」 タイプの監視技術は不適切かもしれない ? ここでは，継続して何らかの異常状態が発生してい るかどうかを検知したい．すなわち変化検知． Section 9.1
- 7. 正常時と異常時のモデル ? ある量ξが，正常時には安定してμという値を取る とわかっている ? 正常値から上にν+振れるようなら何かが起ってい ると判断する N(?|?, 2 ) N(?|? + ?+, 2 ) 正常時のモデル 異常時のモデル Section 9.1
- 8. 正常時と異常時のモデル ? ある量ξが，正常時には安定してμという値を取る とわかっている ? 正常値から上にν+振れるようなら何かが起ってい ると判断する N(?|?, 2 ) N(?|? + ?+, 2 ) 正常時のモデル 異常時のモデル 確率分布の比較により 状態変化を検知できる Section 9.1
- 9. 変化度の定義 a(x0 ) = ln p(x0 |y = 1, D) p(x0|y = 0, D) (1.2) を使うと a(?(t) ) ? ln N(?(t) |? + ?+, 2 ) N(?(t)|?, 2) (9.1) = ( ?+ ) ?(t) ? (?+/2) (9.2) 一つの方法は，単発の異常度を束ねて状態変化を表す 指標に仕立てる Section 9.1
- 10. 変化度の定義 a(x0 ) = ln p(x0 |y = 1, D) p(x0|y = 0, D) (1.2) を使うと 1章 p5 ネイマン?ピアソン決定則 a(?(t) ) ? ln N(?(t) |? + ?+, 2 ) N(?(t)|?, 2) (9.1) = ( ?+ ) ?(t) ? (?+/2) (9.2) 一つの方法は，単発の異常度を束ねて状態変化を表す 指標に仕立てる Section 9.1
- 11. 変化度の定義 a(x0 ) = ln p(x0 |y = 1, D) p(x0|y = 0, D) (1.2) を使うと 1章 p5 ネイマン?ピアソン決定則 a(?(t) ) ? ln N(?(t) |? + ?+, 2 ) N(?(t)|?, 2) (9.1) = ( ?+ ) ?(t) ? (?+/2) (9.2) 時刻tにおける観測地ξの 単発の異常度(正誤あり) 一つの方法は，単発の異常度を束ねて状態変化を表す 指標に仕立てる Section 9.1
- 12. 変化度の定義 (続き) 異常状態が続くと，異常度は継続して正の値を取るた め，時刻tにおける変化度は漸化式の形にできる a (t) + ? h a (t 1) + + a(?(t) ) i + (9.3) = h? a (t 2) + + a(?(t 1) ) ? + + a(?(t) ) i + = h? [a (t 3) + + a(?(t 2) )]+ + a(?(t 1) ) ? + + a(?(t) ) i + = ... [?]+はカッコの中が正なら何 もせず，負ならゼロにする Section 9.1
- 13. 累積和 ? 式(9.3)のように定義される変化度を，一般に? 累積和 (cumulative sum, CUMSUM)と呼ぶ． ? 上側(μ+ν+)の累積和は上側累積和 ? 下側(μ-ν-)の累積和は下側累積和 ? 図の9.1 Section 9.1
- 14. 累積和法の問題 ? 上振れと下振れのνをどのように決めるか ? 累積和の閾値をどのように決めるか ? 観測値の値について事前知識が必要 Section 9.1
- 15. 9.2 近傍法による異常部位検出
- 17. スライド窓と部分時系列 観測値として長さTの時系列 D = {?(1) , ?(2) , ..., ?(T ) } があった時に，M個の隣接する観測値をまとめて x(1) ? 0 B B B @ ?(1) ?(2) ... ?(M) 1 C C C A , x(2) ? 0 B B B @ ?(2) ?(3) ... ?(M+1) 1 C C C A , . . . (9.5) のM次元ベクトルの集りとして表わす. この時Mは N = T M + 1 (9.6) 本のベクトルに変換される Section 9.2
- 18. スライド窓と部分時系列 (続き) 3 1 4 1 5 9 2 6 5 3 5 8 9 7 0 (例)長さ15の時系列データについて5個の隣接した観測値をまとめる 3 1 4 1 5 9 2 6 5 3 5 8 9 7 0 x(1) x(2) … 15本の5次元ベクトルができる Section 9.2
- 19. スライド窓と部分時系列 (続き) 3 1 4 1 5 9 2 6 5 3 5 8 9 7 0 (例)長さ15の時系列データについて5個の隣接した観測値をまとめる 3 1 4 1 5 9 2 6 5 3 5 8 9 7 0 x(1) x(2) … 15本の5次元ベクトルができる スライド窓(sliding window) もしくは滑走窓と呼ぶ 移動平均を出したり，信号処理でフィ ルタかけたりするのによく使う Section 9.2
- 20. スライド窓と部分時系列 (続き) t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 観測値 3 1 4 1 5 9 2 6 5 3 5 8 9 7 0 x x x x x x x x x x x 3 1 4 1 5 9 2 6 5 3 5 1 4 1 5 9 2 6 5 3 5 8 4 1 5 9 2 6 5 3 5 8 9 1 5 9 2 6 5 3 5 8 9 7 5 9 2 6 5 3 5 8 9 7 0 これを普通の多変量データと区別するために部分時系列と呼ぶ Section 9.2
- 21. 近傍法での外れ値検出 ? ベクトルの集りに変換できたので1 8章の手法が使える． ? k = 1とした近傍法による外れ値検出が異常部位検出の文 献に多く見られる 例:M=2とした場合の 各windowをプロット Section 9.2
- 22. 近傍法での外れ値検出 ? ベクトルの集りに変換できたので1 8章の手法が使える． ? k = 1とした近傍法による外れ値検出が異常部位検出の文 献に多く見られる 例:M=2とした場合の 各windowをプロット 最近傍標本までの距離を使っ て異常度が計算できる Section 9.2
- 23. 自己一致 (self match) ? スライド窓で生成したベクトルは統計的独立性の仮定を満たさない ? ある程度滑らかな時系列データは隣りあった部分時系列の要素の値は ほとんど等しくなる． ? 時間的に近接した部分時系列同士は比較しない，といった工夫が必要 前のスライドのスパイクの 高解像度版 Section 9.2
- 24. 9.3 変化検知問題と密度比
- 26. 時刻 t p(t)(x) 確率分布 p (t)(x) 分布の相違度 = 変化度 Section 9.3
- 27. 分布間の相違度 時刻tにおける過去の確率分布と，現在の確率分布の差を計算 する． a(t) = Z dx p(t) (x)ln p(t) (x) p0(t)(x) (9.8) Section 9.3
- 28. 分布間の相違度 時刻tにおける過去の確率分布と，現在の確率分布の差を計算 する． a(t) = Z dx p(t) (x)ln p(t) (x) p0(t)(x) (9.8) 確率分布間の距離を測る式の一つ Kullback Librar divergence Section 9.3
- 29. 9.4 特異スペクトル変換法
- 30. 密度比が必要になった ? 式(9.8)で確率密度とその比が必要になった ? 確率密度推定 ? ノンパラ: カーネル密度推定など ? パラメトリック: 特定の分布にあてはめる ? 9.4章ではフォンミーゼス?フィッシャー分布を仮 定する Section 9.4
- 31. フォンミーゼス?フィッシャー分布 ? 7章の復習 ? http://www.slideshare.net/nakanotomofumi/7-54766192 ? von Mises分布の多次元版 ? 方向データの分布を表現するのに使える ? 平均方向(μ)と集中度(κ)の2つがパラメータ M(x|?, ?) = ?M/2 1 (2?)M/2IM/2 1(?) exp(??T x)
- 32. フォンミーゼス?フィッシャー分布 を使った変化度の計算 p(t) (z) = M(z|u(t) , ?), p0(t) (z) = M(z|q(t) , ?) を使って式(9.8)を展開 過去側，現在側それぞれの部分 時系列から求めた 特徴的な方向ベクトル 集中度は同じと仮定 Section 9.4.1 a(t) = Z dz M(z|u(t) , ?)?zT (u(t) q(t) ) = ?(1 u(t)T q(t) ) (9.9)
- 33. フォンミーゼス?フィッシャー分布 を使った変化度の計算 p(t) (z) = M(z|u(t) , ?), p0(t) (z) = M(z|q(t) , ?) を使って式(9.8)を展開 過去側，現在側それぞれの部分 時系列から求めた 特徴的な方向ベクトル 過去と現在の部分集合の特徴がパターン同じなら異常度ゼロ 直行している時に最大値κ 集中度は同じと仮定 Section 9.4.1 a(t) = Z dz M(z|u(t) , ?)?zT (u(t) q(t) ) = ?(1 u(t)T q(t) ) (9.9)
- 34. 特徴的なパターンの自動抽出 (1/N) NX n=1 x(n) 最も素朴には総和平均の だが，ここでは特徴的な方向を各窓の一次結合で表現する (一次結合にすると何が良いかは後で説明します) 最も強めあう方向を求めるには νTν=1の元で，??Xν??2を最大化すれば良い (9.11) Section 9.4.2 X? = x(1) ?1 + x(2) ?2 + · · · + x(N) ?N (9.10) X = [x(1) , . . . , x(N) ], ? ? [?1, . . . , ?N ]T
- 35. 特徴的なパターンの自動抽出 (1/N) NX n=1 x(n) 最も素朴には総和平均の だが，ここでは特徴的な方向を各窓の一次結合で表現する (一次結合にすると何が良いかは後で説明します) 最も強めあう方向を求めるには νTν=1の元で，??Xν??2を最大化すれば良い (9.11) 二乗ノルムになっているのは計算上の都合? Section 9.4.2 X? = x(1) ?1 + x(2) ?2 + · · · + x(N) ?N (9.10) X = [x(1) , . . . , x(N) ], ? ? [?1, . . . , ?N ]T
- 36. 復習 ? ラグランジュ関数 ? ある制約条件の元で目的関数を最大化するのに使える ? 6章に出てきた http://www.slideshare.net/ shotarosano5/in-54205735 ? ベクトルの微分 Section 9.4.2 d dx (xT a) = d dx (aT x) = a
- 37. ラグランジュ関数を使って 特徴的な方向を求める ? ラグランジュ関数を最大化するνを求めたい? 上に凸なので微分してゼロになるνが解 から式(9.12)が得られる Section 9.4.2 d d? {?T XT X? ?T ?} = 0 XT X? = ? (9.12)
- 38. ラグランジュ関数を使って 特徴的な方向を求める ? ラグランジュ関数を最大化するνを求めたい? 上に凸なので微分してゼロになるνが解 から式(9.12)が得られる この式だけ見ても解けない気がする……が Section 9.4.2 d d? {?T XT X? ?T ?} = 0 XT X? = ? (9.12)
- 39. 固有値方程式 ? の時 ? 行列Aの固有ベクトルがx，スカラ値λが固有値 ? xとλは求まる ? http://qiita.com/kenmatsu4/items/ 2a8573e3c878fc2da306 Ax = x Section 9.4.2
- 42. 特異値分解 からさらに別の固有値方程式が導ける．左からXをかけて ? u = Xν/ γと置く まとめると9.12の解 (γ1,ν1), (γ2,ν2),.. から {νi}と{ui}が得 られた，これらは を満たす Section 9.4.2 XT X? = ? (9.12) XXT u = u (9.13) X?i = p iui, XT ui = p i?i (9.14)
- 43. 特異値分解(続き) U [u1,..,uM] と V [ν1,..νM] と置くと9.14の右の式 から XT U = VΓ1/2 となる．これをXについて整理すると．式9.15が得 られる，これをXの特異値分解 (singular value decomposition SVD)と呼ぶ X = U 1/2 VT (9.15) {u 左特異ベクトル {ν 右特異ベクトル { γ 特異値 Section 9.4.2 XT ui = p i?i
- 45. ここまでの流れ ? 過去の部分時系列と現在の部分時系列の確率密度の差を取れば良 いのでは ? フォンミーゼス フィッシャー分布を仮定して? KL-divergenceを求めた ? 変化度の式(9.9)は κ(1-u (t)T q (t) ) になった． ? 2つの部分時系列から特徴的なパターンを求めれば良い ? 特異値分解で求まった ? NEXT -> これらから変化度を求める
- 46. 時刻 t {u(t,1),..u(t,r)} 特異ベクトル {q(t,1),..q(t,m)} 両者の食い違い = 変化度 特異スペクトル変換法 X(t) Z(t) L 履歴行列 テスト行列
- 47. 変化度の定義 X(t)においてr本，Z(t)においてm本の左特異ベクトルを選ぶ U(t) r ? [u(t,1) , u(t,2) , . . . , u(t,r) ] (9.18) Q(t) m ? [q(t,1) , q(t,2) , . . . , q(t,m) ] (9.19) 過去側と現在側で1本だけ特異ベクトルを選ぶ場合，変化度 は式(9.9)から a(t) = 1 u(t,1)T q(t,1) (9.20) (係数κは省略) Section 9.4.3
- 48. 復習 ? ノルム ? 長さの一般化 ? ベクトル空間に距離を与える ? ? ベクトル2ノルムはユークリッドノルム ||x||p ? (|x1|p + |x2|p + · · · + |xM |p )1/p (9.22)
- 49. 変化度の定義 (続き) 複数選ぶ場合 ここまでの手続を特異スペクトル変換もしくは特異スペクト ル解析と呼ぶ Section 9.4.3 行列2ノルムは? → 行列の最大特異値(9.4.2より)
- 50. 変化度の定義 (続き) 複数選ぶ場合 ここまでの手続を特異スペクトル変換もしくは特異スペクト ル解析と呼ぶ 2乗ノルムを使う流儀もある Section 9.4.3 行列2ノルムは? → 行列の最大特異値(9.4.2より)
- 51. 心電図データでのテスト ? データは http://www.cs.ucr.edu/ eamonn/ discords/ から入手できる ? 間にあわず ? 図9.5の通りになるはず Section 9.4.3
- 54. 定義9.2 (固有射影計算問題) M次元実対象行列Cと，aTa = 1 を満たすM次元ベクトルaが与 えられている．Cの固有ベクトル u(1), u(2),.. とするとき．これら とaとの内積 ? を計算せよ． hi(C, a) ? aT u(i) (9.24) a(t) = 1 v u u t rX i=1 hi(XXT, q(t,1))2 (9.25) のように，変化度の計算はq(t,1)の計算と内積の計算に帰着され ます. 特異スペクトル変換の変化度(9.21)でm = 1とすれば p123の真ん中あたりを引用 Section 9.5
- 55. 定義9.2 (固有射影計算問題) M次元実対象行列Cと，aTa = 1 を満たすM次元ベクトルaが与 えられている．Cの固有ベクトル u(1), u(2),.. とするとき．これら とaとの内積 ? を計算せよ． hi(C, a) ? aT u(i) (9.24) a(t) = 1 v u u t rX i=1 hi(XXT, q(t,1))2 (9.25) のように，変化度の計算はq(t,1)の計算と内積の計算に帰着され ます. 特異スペクトル変換の変化度(9.21)でm = 1とすれば XXTの固有ベクトルの計算は?? p123の真ん中あたりを引用 Section 9.5
- 56. XXTの固有値分解を行なわずに? hi(XXT, a)を求めたい ? 3重対角行列の固有値分解は速い ? ATXXTA = T が3重対角行列になるようなAを求め Tの固有ベクトルを使ってhi(XXT, a)を求める ? hi(XXT, a) = aTAbi ? Aはランチョス法で求める ? biはTの固有ベクトル (この計算は速い) Section 9.5
- 57. Question?