月別アーカイブ: 2015年7月

Incremental SVDおよび類似手法の比較・検討

担当:北澤 拓也
題目:Incremental SVDおよび類似手法の比較・検討

概要:
 本発表ではデータの増分を考慮した逐次更新可能な特異値分解(Incremental SVD)[1]と、それに類似する行列の近似手法[2,3]を紹介する。さらに実データによる実験結果や各手法の応用可能性に関する議論からそれらを比較・検討する。
 インターネット上に投稿される画像やツイート、Webページのような時刻順に絶えず到来するデータをリアルタイムに解析することは、応用上重要な課題である。たとえばSVDによる行列の低ランク近似はデータの次元削減や未観測値の外挿などに利用されるが、新たなデータが到来する度に過去の全データに対して再度SVDを実行することはメモリ空間、処理時間の両面で非効率的である。そこで本発表で扱う手法はいずれも、新たに到来したベクトルによって行列が列(または行)方向に伸びていく環境を考え、既知の近似行列をいかに効率的に更新するかという問題設定をしている。
 Brand[1]は、過去のSVDから得られた直交行列によって新たなベクトルを射影するという視点から理論を展開した。一方Zhouら[2]はColumn Samplingに基づく近似手法を提案し、実験では[1]の手法と比較を行なっている。他方Liberty[3]が提案した手法は、逐次到来するベクトルの頻出方向から行列の近似(スケッチ)を求めるものであり、アプローチが[1,2]とは大きく異なる。

参考文献:
[1] M. Brand. Incremental Singular Value Decomposition of Uncertain Data with Missing Values, Proc. of ECCV 2002, pp. 707–720 (May 2002).

[2] X. Zhou, et al. SVD-Based Incremental Approaches for Recommender Systems, Journal of Computer and System Sciences, Vol. 81, Issue 4, pp. 717–733 (June 2015).

[3] E. Liberty. Simple and Deterministic Matrix Sketching, Proc. of KDD 2013, pp. 581–588 (Aug. 2013).