逐次更新可能な行列近似手法の性能評価および応用可能性に関する一考察

逐次更新可能な行列近似手法の性能評価

および応用可能性に関する一考察

Incremental Approaches for Matrix Approximation:

Performance Evaluations and Their Possible Applications

北澤 拓也

1∗

_{松尾 宇泰}

1,2

Takuya Kitazawa

1

_{Takayasu Matsuo}

1,2

1

_{東京大学大学院 情報理工学系研究科}

1

_{Graduate School of Information Science and Technology, The University of Tokyo}

2

_{CREST, Japan Science and Technology Agency}

Abstract: This paper evaluates three incremental matrix approximation algorithms, Brute Force,

Incremental Singular Value Decomposition (iSVD) and Frequent Directions (FD), in terms of

run-ning time and accuracy. The authors assume that each feature vector comes from data stream one-by-one, and the algorithms try to incrementally update already-known SVD. As a result of experiments for 256-by-7291 dense matrix from a handwritten digits dataset, iSVD ran faster than brute-force algorithm. Importantly, since iSVD is a straightforward incremental technique for SVD updating, the result always gave nearly optimal low-rank approximation. By contrast, FD shrinks from the original 256-by-7291 matrix to a tiny 256-by-ℓ matrix, and provides approximated singu-lar vectors. The singusingu-lar vectors were nearly-optimal to estimate the best low-rank approximation of the original matrix, and running time was much faster than iSVD. As conclusions, this paper discusses possible applications and future directions of these incremental algorithms.

1

はじめに

近年，行列やそれを拡張したテンソルの分解に基づ くデータの近似・予測の研究は大きな成功を収めてい る．その中でも特異値分解 (SVD) による特徴抽出，低 ランク近似はデータの次元削減やノイズ除去，未観測 値の外挿などに広く利用されるが，従来はデータの大 きさ，すなわち行列のサイズを固定した問題設定で議 論がなされてきた．しかし現実のデータは時々刻々と 増え続けており，行または列方向に伸び続ける行列を 想定した手法を検討することが重要である．このとき 想定するデータの具体例としては Web ページやツイー ト，画像投稿 SNS に投稿される画像などが挙げられ， このようなデータの持続的な解析が流行り廃りといっ たコンテクストを捉えた特徴抽出の実現に繋がること が期待される．そこで本稿では，特徴ベクトルひとつ ひとつがデータストリームから絶えず到着する環境を 想定し，そのような環境で動作可能な既存の行列近似 手法を実験に基づき比較する． ∗_{連絡先： 東京大学大学院 情報理工学系研究科}        〒 113-8656 東京都文京区本郷 7-3-1        E-mail: [email protected]

2

特異値分解に基づく問題設定

2.1

特異値分解 (SVD)

行列 A ∈ Rm_{×nが与えられ rank(A) = r であると} き，その行列は 2 つの直交行列 U ∈ Rm_{×r，V ∈ R}n_×r および対角行列 Σ∈ Rr×r_{の積 U ΣV}T _{に分解できる．} これを行列 A の特異値分解 (SVD) といい，U ，V の 各列を特異ベクトル，Σ の各対角要素を特異値と呼ぶ． また，SVD の結果において上位 k 個 (k < r) の特異ベ クトルおよび特異値のみを残して残りを全て 0 とした行 列の積によって行列 A の低ランク近似 Ak = UkΣkVkT が与えられる．これは Truncated SVD と呼ばれ，Ak はフロベニウスノルムでの A の最良近似を与えること が知られている．

2.2

想定する環境およびデータセット

本稿では画像投稿 SNS に投稿される画像を想定し， 画像の特徴ベクトルが絶えず到来する環境を考える．画 像の特徴ベクトル列からなる行列の SVD の結果の応用 範囲は広く，例として顔画像の集合から主成分分析に 人工知能学会研究会資料 SIG-FPAI-B501-05 − 22 −

よって特徴的な情報が抽出される Eigenface が挙げら れる．しかし現実の画像データは特徴ベクトルの生成 そのものが挑戦的なタスクとなるため，ここでは単純 化された画像のデータセットとして USPS normalized handwritten digits dataset1_{の学習用データセットを}

利用する．USPS データセットは 0 から 9 までの 10 種 類の手書き数字のデータセットであり，16× 16 の画 像の画素情報からなる 256 次元の特徴ベクトルを与え る．そして学習用データセットには 7291 枚の手書き 数字画像の特徴ベクトルおよびそのラベルが含まれる． 以後，このデータセットによって得られる行列を考え， A∈ Rm×n_{について m = 256，n = 7291 とする．} なお，実験はすべて Python 2.7.10 および NumPy 1.8.2 による実装の下で行った．NumPy の SVD の実 装は線形計算用のライブラリ LAPACK に基づいてい る．また，マシンの環境は Intel Core i7 @ 2.7 GHz お よび 4GB RAM を搭載した OS X Yosemite 10.10.4 の 動作する MacBook Pro Early 2011 である．

2.3

Brute Force な SVD の逐次更新

逐次更新可能な行列近似アルゴリズムを考慮するに 先立ち，Brute Force な更新手法として新たな特徴ベ クトルが到来する度に SVD を実行することを考える． 具体的には，2.2 節で USPS データセットに基づき定義 した行列 A に対して Algorithm 1 を実行し処理時間を 計測した．その結果，A に対する最終的な SVD の結果 が得られるまでに 4000 秒程度を要した． Algorithm 1 新たな特徴ベクトルが到来する度に SVD を実行して更新 (Brute Force；n0は初期データ数) Input: A∈ Rm×n Output: svd(A) 1: A0← A(:, 1:n0) 2: [U, Σ, V ]← svd(A0) 3: for i = n0+ 1, n0+ 2, ..., n do 4: A1← A(:, i) 5: [U, Σ, V ]← svd([A0, A1]) 6: A0← [A0, A1] 7: return [U, Σ, V ] 特徴ベクトルが逐次到来するとはいえ，現実にはこ れまで蓄積された n0個のデータも存在する．そこで Algorithm 1 ではデータの次元と同数の 256 サンプル はすでに蓄積されているものとして考え (n0 = 256)， 257 番目以降のサンプルが逐次到来すると仮定した．初 期サンプル数が特徴ベクトルの次元と同数であるのは， 最終的な行列 A が取りうるランクの最大値が 256 であ 1_{http://statweb.stanford.edu/ tibs/ElemStatLearn/data.html} ること，また，今回は 10 種類の手書き数字データを利 用していることが既知のため，256 サンプルは過去に 蓄積されたデータとして十分な数とみなせることが理 由である．

3

Incremental SVD

2.3 節で示した通り，新たなデータが到来する度に 行列全体に対してその分解，近似を再計算することは 非効率である．そこで既に得られている SVD の結果 を利用して近似結果を効率的に更新する手法として， Incremental SVD (iSVD) が提案されている [1]． iSVD は新たな特徴ベクトルを既知の直交行列 U の張 る空間へ射影することを基本方針としており，既知の 行列 A0 = U ΣVT ∈ Rm×n0，新たな特徴ベクトル列 A1∈ Rm×n1を用いて以下のように導出される． [A0, A1] = [U ΣVT, A1] = [U Σ, A1] [ VT _O O I ] = [U Σ, U UTA1+ QR] [ VT _O O I ] = [U, Q] [ Σ UT_A 1 O R ] [ VT _O O I ] = [U, Q]U′Σ′V′T [ V O O I ]T = ([U, Q]U′) Σ′ ([ V O O I ] V′ )T (1) ここで QR← qr(A1− UUTA1) と計算される．すなわ ち，新たな特徴ベクトル列 A1を U の張る空間に射影 し，その結果 U に直交する新たな基底 Q が得られたと みなす．そして左右に直交行列を作るように式変形を 行うことで再び SVD の形を復元している．なお式 (1) 第 5 の等号において，右辺の [U′, Σ′, V′] は左辺の中央 の行列に対して SVD を適用した結果を指す． さらに Zhou ら [2] は iSVD として [A0, A1] = U [Σ, UTA1] [ VT _O O I ] = (U U′)Σ′ ([ V O O I ] V′ )T (2) という更新式を元にアルゴリズムを書き起こしている． これは式 (1) において Q = O とおき，[U′_{, Σ}′_{, V}′_{] ←} svd([Σ, UT_A 1]) としたものと読むことができ，A0とし て十分なデータが蓄積されており，新たな特徴ベクト − 23 −

ル列 A1によって基底が増えることはないと仮定して いるものと推測できる． ここで n0= 256，n1= 1 とおき，式 (2) を本稿が想 定する環境に対応するアルゴリズムとして書き起こし たものを Algorithm 2 に示す． Algorithm 2 導出された更新式に基づき SVD の結果 を更新 (Incremental SVD) Input: A∈ Rm×n Output: svd(A) 1: A0← A(:, 1:n0) 2: [U, Σ, V ]← svd(A0) 3: for i = n0+ 1, n0+ 2, ..., n do 4: A1← A(:, i) 5: [U′, Σ′, V′]← svd([Σ, UT_A 1]) 6: [U, Σ, V ]← [UU′, Σ′, ([V, O; O, I]· V′)] 7: A0← [A0, A1] 8: return [U, Σ, V ] 実験の結果，このアルゴリズムの処理時間は 750 秒 程度であり Brute Force と比較すると高速な更新が可 能であった．また，式 (2) は [A0, A1] = [U ΣVT, A1] の 式変形および SVD を利用した対角化のみから導出され るため，数値計算誤差以上の誤差は発生しない．実際に Algorithm 2 の結果得られた特異ベクトルのうち上位 k 個を用いて Projection Error (||A−UkUkTA||2F/||A−

Ak||2F) を計算した結果，その値は k < 256 で常に 1.0 と なり，A に対する Truncated SVD による最良近似 Akを 再現できていることが確認された．なお低ランク近似を 行わない k = 256 の場合，||A − UkUkTA|| 2 F = 2.9e-18， ||A − Ak||2F = 5.5e-22 という非常に小さな数値計算誤 差の間の比較となり，Projection Error の値は意味を 持たない．

4

Frequent Directions

3 章で述べた iSVD はこれまで多くの議論がなされ てきた考え方であり，確率的な要素を取り入れたもの など多様な類似アルゴリズムが存在する．Liberty[3] は それらとは大きく異なる視点で行列の近似手法を提案 した．その手法 Frequent Directions (FD) は行ベ クトルが絶えず到来する環境において，それらをある 一定の行数 ℓ に潰した行列 B∈ Rℓ×m_{で近似する手法} である．FD は行方向へ延びる行列についてアルゴリ ズムが提案されているが，ここでは先の iSVD と設定 を統一するために列方向へ延びる行列を想定し，元行 列 A ∈ Rm×n_{から近似行列 B ∈ R}m×ℓ_{を求めるアル} ゴリズムとして Algorithm 3 に示す．具体的には着目 する特異ベクトルを変更し，原論文で√Σ2− δI · VT と表されていた B の更新を U ·√Σ2_{− δI とした．} Algorithm 3 特徴ベクトルの頻出方向を表現した小 さな行列 B に対して SVD を適用（列ベクトルに対す る Frequent Directions） Input: A∈ Rm×n_{，ℓ (ℓ≪ n)} Output: B∈ Rm×ℓ _{に対する SVD の結果} 1: B← [A(:, 1:ℓ − 1), O256×1_] 2: for i = ℓ, ℓ + 1, ..., n do 3: B(:, ℓ)← A(:, i) 4: [U, Σ, V ]← svd(B) 5: δ← Σ(ℓ, ℓ)2 6: B← U ·√Σ2− δI 7: [U, Σ, V ]← svd(B) 8: return [U, Σ, V ] 小さな行列 B に対して SVD を求めているため，出力 の [U, Σ, V ] が持つ意味は A の SVD を求めていた iSVD とは厳密には異なる．しかし特徴ベクトル列から特徴的 な情報を抽出するという目的は同一であり，B の SVD の結果の上位 k 個の特異ベクトルによる元行列の射影 UkUkTA を考えることでその精度を iSVD と同様に計算 することができる．ここで複数の ℓ に対して FD を実 行し，精度および処理時間を計測した結果を図 1 に示 す．実線は k = 10 として計算された Projection Error， 破線は処理時間を表す． 0.6 0.8 1 1.2 1.4 1.6 1.8 2 0 50 100 150 200 250 0 20 40 60 80 100 120 140 160 180 200 220 240 260 280 300

Projection Error Time (sec.)

ell 図 1: 異なる ℓ (ell) に対する低ランク近似の再現精度 および処理時間 Projection Error の変化を見ると，ℓ が大きいほど削 ぎ落とされる情報が少なくなり，最良近似 Akに近い 結果を B が持つようになることが分かる．一方，Algo-rithm 3 ではループ中で B の SVD を求めているため， 処理時間は B のサイズ，すなわち ℓ に依存する．なお 処理時間が 6 秒程度の ℓ = 32 の段階で既に Projection − 24 −

Error がほぼ 1.0 となっている点は，実アプリケーショ ンを検討する上で特筆すべき結果である．

5

応用可能性に関する考察

5.1

逐次更新可能な SVD の応用と関連研究

機械学習の実用的側面が重視される昨今，新たなデー タが到来する度にモデルを更新するオンライン学習ア ルゴリズムが注目されている．同様に，従来 m× n の 行列に対して静的に行われていた処理を逐次更新可能 なものにするという発想は自然なものであると言える． そしてその応用可能性は，本稿で取り挙げた SVD に 主成分分析 (PCA) や潜在的意味インデキシング (LSI)， 未観測値の外挿による情報推薦といった幅広い応用が 存在するという事実が示している． しかし誰もが思い至る発想であるがゆえに，逐次更 新可能な SVD とそれに類似する手法の先行研究は多数 存在する．たとえば FD[3] は “限られたメモリ空間で その範囲を超える種類のアイテムの頻度カウントを近 似的に行う” という従来研究から着想を得ており斬新な 提案であるように思えるが，より詳細な文献 [4] で議論 されているように，これはアルゴリズムの上では既存 の iSVD と大きな差異が無い．また，[3] では従来の逐 次更新可能な行列近似手法として Hashing，Sampling， Random Projection を挙げ，FD と比較実験を行なっ ているが，それよりも後に執筆された iSVD を扱って いる文献 [2] で提案された手法は，[3] で Sampling と呼 ばれていた手法と酷似するものになっている． このように逐次更新可能な行列近似手法は 2000 年前 後から今日に至るまで，情報推薦 [2, 5] や LSI[6, 7] な ど応用先は異なれど，類似手法とその改良版が次々に 登場している状況にある．その中でどのような問題を 設定し，どの手法を適用すべきか，また，どの既存手 法をどのような方向性で改良していくべきかといった 点には未だ議論の余地がある．

5.2

今後の課題

本稿で検討した iSVD および FD には近似する際の パラメータとしてランク k や行列の列数 ℓ が存在した が，これらの最適な値は自明ではない．さらに，仮にこ れらパラメータの最適値が既知であったとしても，デー タのトレンドが移り変わることを考慮すると動的なパ ラメータ設定を実現するアルゴリズムの提案が期待さ れる．また，過去の情報を量および時間の点でどれだけ 保持し続けるべきかという点も重要な問題であり，オ ンライン学習のみならず，時系列データ解析手法との 関連もうかがえる． なお，SVD の他にも比較的新しい行列の近似・分 解手法として非負値行列分解 (NMF) や Factorization Machines[8] などがあり，これらの逐次更新可能な手法 を検討する上では未だ多くの課題が残されている．逐 次更新可能な行列近似をより実用的なものにするため には，問題設定を明確にした上で，このような発展的 なアルゴリズムの存在も踏まえた追求が重要であると 考えられる．

6

おわりに

本稿では Web ページや SNS への投稿を想定し，絶 えず到来する特徴ベクトルを持続的に解析するための 手段として Incremental SVD およびそれに類似する結 果を与える Frequent Directions を紹介し，それらを相 互に比較するために既存のアルゴリズムに変更を加え たものを書き起こした．そして独自の設定の下，最悪 時の処理時間を与える Brute Force アルゴリズムと共 に実験を行ない，期待通りの結果が得られることを確 認した．さらに，近年の類似手法に関する研究成果を 踏まえ，紹介した手法の応用可能性および今後追求さ れるべき課題について議論した．

参考文献

[1] M. Brand. Incremental Singular Value Decomposi-tion 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 Sketch-ing, Proc. of KDD 2013, pp. 581–588 (Aug. 2013). [4] M. Ghashami, et al. Frequent Directions :

Simple and Deterministic Matrix Sketching,

arXiv:1501.01711 (Jan. 2015).

[5] B. Sarwar, et al. Incremental Singular Value De-composition Algorithms for Highly Scalable Recom-mender Systems, Fifth International Conference on

Computer and Information Science, pp. 27–28 (Dec.

2002).

[6] H. Zha and H. D. Simon. On Updating Problems in Latent Semantic Indexing, SIAM J. Scientific

Com-puting, Vol. 21, No. 2, pp. 782–791 (1999).

[7] E. Vecharynski and Y. Saad. Fast Updating Algo-rithms for Latent Semantic Indexing, SIAM J.

Ma-trix Analysis Applications, Vol. 35, No. 3, pp. 1105–

1131 (2014).

[8] S. Rendle. Factorization Machines, Proc. of ICDM

2010, pp. 995–1000 (Dec. 2010).