行列の圧縮による変化点検出の高速化 IBM東京基礎研究所 井手 剛 | 2006/11/01 | IBIS 2006

変化点とは、データ生成機構にある変化が生じた時点。 変化度とはその変化の度合い。 時系列データ 変化度 変化点検出 ≒ 知識発見 ≒ マイニング 異常検知 評判分析 etc 変化点の現れ方は多様である。 「きめ打ち」は避けたい なるべく無垢な心で変化点を捉えたい | 2006/11/01 | T.Idé | IBIS 2006

特異スペクトル変換法（Singular Spectrum Transformation; SST）は “model-free”な変化点検出手法。「過去」と「今」のパターンを比べる。 各時刻ごとに移動 特徴ベクトル 特徴ベクトル SVD SVD 変化度 V. Moskvina and A. Zhigljavsky, "An algorithm based on singular spectrum analysis for change-point detection", Communications in Statistics—Simulation and Computation, 32(4):319–352, 2003. T.Ide and K.Inoue, "Knowledge Discovery from Heterogeneous Dynamic Systems using Change-Point Correlations", Proc. 2005 SIAM Intl. Conf. Data Mining (SDM 05), April 21-23, 2005, pp.571-576 Moskvina & Zhigljavsky 2003 Ide & Inoue 2005. | 2006/11/01 | T.Idé | IBIS 2006

SSTは計算が遅い！ 100×100くらいのSVDを、各時刻でやる必要がある。 time 履歴行列 テスト行列 SVD SVD 左特異ベクトル上位 r 個 ここが最も重い 最大左特異ベクトル 両者の食い違い＝変化度 | 2006/11/01 | T.Idé | IBIS 2006

問題： 特異ベクトル同士のカーネル関数を、高速に計算せよ 変化度の定義 ただし μは数値的に簡単に求まる 最大特異ベクトルだけなら、数値的に安定かつ高速に計算可能。 μが与えられたとして、Kをどう求めるか考えたい 生の固有ベクトルを求めずに、Kを評価したい。 | 2006/11/01 | T.Idé | IBIS 2006

ふたつの着眼点: (1) 内積をじかに求めたい、(2) 必要な情報を事前に圧縮したい (1) 知りたいのは内積（＝射影）だけだから、あらわに特異ベクトルを計算するのは無駄 特異ベクトルの計算を省略して、内積を直接求めることはできないか？ (2) 必要な特異ベクトルの個数は履歴行列の次元よりはるかに小さい。フルSVDをやるのは無駄 特異値の高い特異ベクトルの成分が「濃く」なるように、行列を圧縮はできないか？ この二つを同時に満たす行列圧縮手法が、ある！ | 2006/11/01 | T.Idé | IBIS 2006

の上位の固有ベクトルを濃縮するような部分空間を作ろう。 μで張られる1次元空間から出発して、次々に基底を付け加えることで、 上位の固有ベクトルを濃く含む空間を構成したい。 だから、Rの最急方向を付け加えればよい！ 第1項はすでにあるから、第2項を付加すればOK! | 2006/11/01 | T.Idé | IBIS 2006

μを出発ベクトルとすることで、μと関係する成分だけを抜き出せる。 この論法を続けると、 という k 次元空間は、ρの上位の固有ベクトルの成分を最も濃く含む部分空間であることがわかる。 べき乗法的なノリ Krylov部分空間と呼ばれる しかも、μと関係する成分だけを抜き出していることに対応。 | 2006/11/01 | T.Idé | IBIS 2006

Implicit kernel 近似 ── 元の固有値問題が k×k の問題に帰着され、 しかも内積計算が自動実行される の正規直交基底でρの固有値問題を書き表す k×k の固有値問題に帰着（近似） 高々5×5くらいのサイズ。 固有ベクトル μを第1基底に取っておけば、第1成分がカーネル関数になる（陰なカーネル計算） | 2006/11/01 | T.Idé | IBIS 2006

計算手順まとめ。2種類の特異ベクトル同士の比較は陰になされる。 しかも、面倒なことすべてが、圧縮された空間内で行われる。 time に対する反復法で最大固有値を求める μに無関係な成分は自動的に軽視される。 Krylov部分空間近似で圧縮。 3重対角化行列 T に。 最大固有ベクトル 次のテスト行列における反復法の初期値 出発ベクトル 圧縮された行列 T の固有値分解 変化度 | 2006/11/01 | T.Idé | IBIS 2006

パラメターによっては、計算速度が100倍に。しかも目立った誤差はない。 従来 本手法 | 2006/11/01 | T.Idé | IBIS 2006

まとめ 変化点検出は、知識発見工学の興味深い問題である。 特異スペクトル変換（SST）は、model-freeな変化点検出手法であり、多様な変化点に対応する能力がある。 しかし、とんでもなく遅い。 Implicit kernel近似という新しいアルゴリズムにより、SSTの計算速度を数10倍高速化することに成功した SSTの実用度は格段に増すことになる。 Implicit kernel近似は、SSTのみならず、固有状態への遷移確率の計算などの用途に使える汎用技術である。 | 2006/11/01 | T.Idé | IBIS 2006

FELIX-SST 命名 FEedback impLIcit kernel approXimation-SST Thank you. | 2006/11/01 | T.Idé | IBIS 2006

（参考） いわゆるオンラインSVDじゃだめなのか？ Folding-in的仮定に基づくものは軒並み不可。 仮定が成り立たない 「文書をためたDBがあまり時間変化しない」 「行列は疎な高次元行列」 代表的な手法 “folding-in”： t-1での特異ベクトルを使って、tでの特異ベクトルを表す近似的更新算法 Zha-Simon ［SIAM J. Sc. Com. 1999］： いわば改良folding-in。応用例多数。 いにしえなSVD諸手法を単に使っても、速度向上には限界がある。 何らかの方法で3重対角化し、QR反復などを使うのが定番 密行列： ハウスホルダー変換 疎行列： ランチョス法 計算量的上限が決まっている。越えられない壁がある。 学習手法ごとに、適切にサボりながらPCA/SVDをやる手法は地味ながらそこそこ関心を集めている 間引く Nyström 法 [Williams-Seeger, NIPS 00] Channubhotla-Jepson [NIPS 04] いろいろなrandomized algorithms 圧縮する Krylov部分空間法 数学的にはいにしえだが、 KDD業界ではあまり知られていない（らしい） | 2006/11/01 | T.Idé | IBIS 2006