Tokyo Research Laboratory 行列の圧縮による変化点検出の高速化 IBM東京基礎研究所 井手 剛 | 2006/11/01 | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory 変化点とは、データ生成機構にある変化が生じた時点。 変化度とはその変化の度合い。 時系列データ 変化度 変化点検出 ≒ 知識発見 ≒ マイニング Page 2 異常検知 評判分析 etc 変化点の現れ方は多様である。 | 2006/11/01 | T.Idé | IBIS 2006 「きめ打ち」は避けたい なるべく無垢な心で変化点を捉えたい © Copyright IBM Corporation 2006 Tokyo Research Laboratory 特異スペクトル変換法（Singular Spectrum Transformation; SST）は “model-free”な変化点検出手法。「過去」と「今」のパターンを比べる。 各時刻ごとに移動 特徴ベクトル SV D 特徴ベクトル 変化度 SV D •Moskvina & Zhigljavsky 2003 •Ide & Inoue 2005. Page 3 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory SSTは計算が遅い！ 100×100くらいのSVDを、各時刻でやる必要がある。 time t テスト行列 H 2 履歴行列 H1 H1 SVD ここが最も重い SVD 左特異ベクトル 上位 r 個 最大左特異ベクトル 両者の食い違い＝変化度 Page 4 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory 問題： 特異ベクトル同士のカーネル関数を、高速に計算せよ 変化度の定義 ただし μは数値的に簡単に求まる 最大特異ベクトルだけなら、数値的に安定かつ高速に計算可能。 μが与えられたとして、Kをどう求めるか考えたい 生の固有ベクトルを求めずに、Kを評価したい。 Page 5 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory ふたつの着眼点: (1) 内積をじかに求めたい、(2) 必要な情報を事前に圧縮したい (1) 知りたいのは内積（＝射影）だけだから、あらわに特異ベクトルを計算するのは無駄 特異ベクトルの計算を省略して、内積を直接求めることはできないか？ (2) 必要な特異ベクトルの個数は履歴行列の次元よりはるかに小さい。フルSVDをやるの は無駄 特異値の高い特異ベクトルの成分が「濃く」なるように、行列を圧縮はできないか？ この二つを同時に満たす行列圧縮手法が、ある！ Page 6 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory の上位の固有ベクトルを濃縮するような部分空間を作ろう。 μで張られる1次元空間から出発して、次々に基底を付け加えることで、 上位の固有ベクトルを濃く含む空間を構成したい。 だから、Rの最急方向を付け加えればよい！ 第1項はすでにあるから、第2項を付加すればOK! Page 7 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory μを出発ベクトルとすることで、μと関係する成分だけを抜き出せる。 この論法を続けると、 という k 次元空間は、ρの上位の固有 ベクトルの成分を最も濃く含む部分空間であることがわかる。 べき乗法的 なノリ Krylov部分空 間と呼ばれる しかも、μと関係する成分だけを抜き出していることに対応。 Page 8 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory Implicit kernel 近似 ── 元の固有値問題が k×k の問題に帰着され、 しかも内積計算が自動実行される の正規直交基底でρの固有値問題を書き表す k×k の固有値問題に帰着（近似） • 高々5×5くらいのサイズ。 固有ベクトル μを第1基底に取っておけば、第1成分が カーネル関数になる（陰なカーネル計算） Page 9 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory 計算手順まとめ。2種類の特異ベクトル同士の比較は陰になされる。 しかも、面倒なことすべてが、圧縮された空間内で行われる。 time t μに無関係な成分は自動 的に軽視される。 Krylov部分空間近似で圧縮。 3重対角化行列 T に。 出発ベクトル に対する反復法で 最大固有値を求める 最大固有ベクトル 次のテスト行列における反 復法の初期値 圧縮された行列 T の固有値分解 変化度 Page 10 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory パラメターによっては、計算速度が100倍に。しかも目立った誤差はない。 従来 本手法 Page 11 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory まとめ 変化点検出は、知識発見工学の興味深い問題である。 特異スペクトル変換（SST）は、model-freeな変化点検出手法であり、多様な変化点に対 応する能力がある。 しかし、とんでもなく遅い。 Implicit kernel近似という新しいアルゴリズムにより、SSTの計算速度を数10倍高速化 することに成功した SSTの実用度は格段に増すことになる。 Implicit kernel近似は、SSTのみならず、固有状態への遷移確率の計算などの用途に 使える汎用技術である。 Page 12 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory 命 名 FELIX-SST FEedback impLIcit kernel approXimation-SST Thank you. Page 13 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006 Tokyo Research Laboratory （参考） いわゆるオンラインSVDじゃだめなのか？ Folding-in的仮定に基づくものは軒並み不可。 情報検索の分野では逐次更新式のSVDがよく 研究されているが、変化点検出問題には不適。 仮定が成り立たない • 「文書をためたDBがあまり時間変化しない」 • 「行列は疎な高次元行列」 代表的な手法 • “folding-in”： t-1での特異ベクトルを使って、t での特異ベクトルを表す近似的更新算法 • Zha-Simon ［SIAM J. Sc. Com. 1999］： いわ ば改良folding-in。応用例多数。 いにしえなSVD諸手法を単に使っても、速度向 上には限界がある。 学習手法ごとに、適切にサボりながら PCA/SVDをやる手法は地味ながらそこそこ関 心を集めている 間引く • Nyström 法 [Williams-Seeger, NIPS 00] • Channubhotla-Jepson [NIPS 04] • いろいろなrandomized algorithms 圧縮する • Krylov部分空間法 - 数学的にはいにしえだが、 KDD業界では あまり知られていない（らしい） 何らかの方法で3重対角化し、QR反復などを使う のが定番 • 密行列： ハウスホルダー変換 • 疎行列： ランチョス法 計算量的上限が決まっている。越えられない壁が ある。 Page 14 | 2006/11/01 | T.Idé | IBIS 2006 © Copyright IBM Corporation 2006
© Copyright 2024 ExpyDoc
