DEIM Forum 2014 D1-2

分散 NMF における Adaptive,Incremental 計算手法の適用
牧野 浩之†

鬼塚真†† 日本電信電話株式会社 NTT ソフトウェアイノベーションセンタ 〒 180–8585 東京都武蔵野市緑町 3-9-11
E-mail: †{makino.hiroyuki,onizuka.makoto}@lab.ntt.co.jp
あらまし 非負値行列因子分解 (NMF: Non-negative Matrix Factorization) は，行列表現で表されるテキスト，画像，
音声など様々なデータに対し，指定した基底数に行列を分解し，低ランク表現によって特徴抽出を行う行列近似手法
である．数百万次元以上の大規模な行列を用いて NMF を行うユースケースにおいては，MapReduce 上での処理が不可欠である．しかし既存の MapReduce における分散 NMF 実装では，全体で数百回の多段 Job となるため，膨大な処理時間を要する．本研究では分散 NMF 処理において処理時間を改善するため，収束したレコードの処理をスキッ
プして処理を高速化する Adaptive 計算手法と Incremental 計算手法を提案する．提案手法を適用した実験の結果，処理時間を最大で 1/4 に削減できることが分かった．
キーワード

大規模分散処理, MapReduce, データマイニング, 行列分解

1. は じ め に
NMF(Non-negative Matrix Factorization: 非負値行列因子
分解) は，行列を指定した基底数に分解し，低ランク表現を行う行列近似手法である [1]．テキスト，画像，音声など様々なデータが行列形式で表現でき，これらの行列が持つ潜在的な特図 1 NMF

徴を抽出することを目的とする． 例えば，オンラインショッピ

後の行列は，W(n 行 k 列) の基底行列と，H(k 行 m 列) の重

ングサイトにおける購買履歴をユーザと購入商品という軸でみ行列 (各列は基底をどれだけの重みで結合するかを表現) と隣接行列を作成し，NMF を適用すると，商品カテゴリとそれなる．W と H を掛け合わせると元の行列 A の近似値が得られに属するユーザ群を抽出でき，ユーザに対し次に購入候補となるが，完全に一致する W,H の値を求めるのは困難であるため，る商品の推薦に利用するといったことが可能である．また，扱A と WH の距離 (コスト) 関数を用いて，距離を最小化する探えるデータ量や種類の増加に伴って，数百万次元以上の大規模索問題として解かれる．この探索問題の例として式 (1) は数学

な行列を用いて NMF を行うユースケースが一般的となってき的距離規範におけるフロベニウスノルムの最小化問題として解た．Liu らは大規模な行列に対応できるよう，MapReduce 上

かれる．NMF の解法にはいくつかの数学的解法が提案されてで NMF を行う分散 NMF 手法を提案し，数億次元の大規模ないる．ALS(Alternating Least Squares) [3] や乗法的更新ルー行列においてもスケールすることを確認した [2]．この手法でル [4]，Gradient Descent 法を用いた手法 [5] などが提案されては NMF の 1 回の更新ルール適用イテレーションにつき 10 個いる．補助関数と Jensen の不等式により導出した乗法的更新の MapReduce Job で多段処理となるため，数十回の更新ルー

ルールは最も広く利用されている．更新式の例を式 (2) に示す．

ル適用イテレーションを繰り返し処理し，結果を得るまでに膨大な処理時間を要する．本研究では MapReduce を用いた分散

NMF 処理において処理時間を短縮するため，大半のレコード
が数イテレーション後に収束するという特徴を利用できないか

min||A − W H||2F s.t.W, H >=0
Wnew =

W. ×

TAH
W HH T

Hnew =

H. ×

(1)
T

W A
(2)
WTWH

検討した．そこで，収束したレコードの処理をスキップして処

NMF では，W と H をランダムな値で初期化し，更新式に理を高速化する Adaptive 計算手法と更新差分を用いて加法的従って W と H を交互に更新し，コスト関数が収束するまでイに更新ルールを適用する Incremental 計算手法を提案し，そのテレーションを継続することで最適な解が得られる．乗法的更有効性について実データを用いて評価，考察を行った．

新ルールにおいては，数百万次元以上の大規模な行列に対応で

2. 事前知識: NMF と分散 NMF の計算手法
2. 1 NMF
NMF とは行列が持つ潜在的要素を分析するために用いられきるよう，分散処理基盤 MapReduce を用いた分散 NMF [2] がLiu らによって提案されている．次節で分散 NMF の詳細について述べる．

2. 2 分散 NMF

る低ランク近似手法の一つであり，非負値行列を 2 つの非負値

MapReduce を用いた分散 NMF 計算手法では，NMF の 1行列に分解する行列分解アルゴリズムである．具体的には，図イテレーション処理を 10 個の MapReduce Job へのフェーズ

1 に示すように分解前の行列を A(n 行 m 列) とすると，分解分割によって処理できる．式 (2) に示した更新式では，図 2 に

示す処理フローで反復的に計算される．
1

W と H をランダムな値で初期化．

2

イテレーションを r 回繰り返す {3//Update H

4

Phase1 Job(H1)，Phase2 Job(H2): X = W T A の計算

5

Phase3 Job(H3): Q=W T W

6Phase4 Job(H4): Y=QH

7

Phase5 Job(H5): H=H. ∗ X/Y

8//Update W

9Phase1 Job(W1)，Phase2 Job(W2): X=AH T の計算

10

Phase3 Job(W3): Q=HH T

11Phase4 Job(W4): Y=WQ

12Phase5 Job(W5): W=W. ∗ X/Y

図 3 各フェーズの平均処理時間

13 }

図 2 分散 NMF の MapReduce 実装

2. 2. 1 分散 NMF のボトルネック解析
本研究では，分散 NMF の処理を高速化する手法を提案するが，どの処理に高速化手法の効果的な適用が可能かを考える上で，分散 NMF のボトルネックについて述べる．まずは，それぞれの MapReduce Job について，どのフェーズの処理が処理上のボトルネックとなるか，机上での処理アルゴリズムの解析と実際のデータセットを用いた実験により解析した．
はじめに，処理アルゴリズムについて机上での解析を行う．Phase1, Phase2 Job で は ，そ れ ぞ れ ，X = W T A と

X = AH T の計算を行うが，行列 W および行列 H は密行列であり，MapReduce 実装における行列同士の乗算では n 行
分の和を m 列分繰り返すため，計算量が O(nm) で変化する．

Phase1, Phase2 の Job を詳細に分析する． Phase1 Job の Map
Input/Output, Reduce Input/Output は，Update H の場合，Map < n,wn >, < (n, m),Anm > → < n, wn ,(m, Anm )∀m ∈On >Reduce < n,wn , (m, Anm )∀m ∈ On > → < m, Anmwn T >Phase1 の Output である < m, Anm wn T > は要素ごとの乗算となるため，CPU intensive な処理となる．同様に Phase2 Jobの Map Input/Output, Reduce Input/Output は，

Map < m, Anmwn T > → < m, Anmwn T >Reduce < m, Anmwn T > → < m, xm >∑xm = n∈Om Anm wn T∑
Phase2 の Output である xm =Anm wn T は，Shuﬄe 量が多くなり I/O intensive な処理となる．

Phase3 以降の処理は，Phase1,Phase2 と比較すると処理オーバーヘッドは小さい．Phase3 の処理は Map 側で分散してQ = wnT wn が行え，出力が k × k の行列となり，Phase4 でもMap 側で Qhm の処理が行える．Phase5 においても，同じ m
列を集約して処理できる．
次に，実際のデータセットを用いて処理特性を解析した．実験に用いたデータセットとして，doc user 行列，Adoc user ∈R350,469×2,663,167
非 零 要 素 率 0.0013%と ，doc word 行 列 ，+Adoc word ∈ R350,256×397,676
非零要素率 0.11%の行列データを+用いて，従来手法の各フェーズの平均処理時間を測定した．デー
タセットの詳細については，4. 1. 2 で詳述する．図 3 は，50 イ

図 4 doc word 行列におけるイテレーション毎のコスト値

テレーションを処理した際の 1 イテレーションあたりの平均処
理時間を示したものである． 測定結果から，Phase1, Phase2の処理 (H1,H2,W1,W2) が全体の 54%(doc user 行列), および94%(doc word 行列) を占めており，非零要素率の変化による影響が大きいことが分かった．

2. 2. 2 分散 NMF の課題
NMF で収束解を求めるためには数十から数百回のイテレー
ションを繰り返す必要があり，数百万次元の規模の大きな行列の処理では，結果を得るまでに数時間から数日の処理時間を必要とする．2. 2. 1 で述べたように Phase1, Phase2 Job では，それぞれ，X = W T A と X = AH T の計算処理を行うが，計算結果が密行列 (k × m 行列，n × k 行列) になる上，基底数 kや行列 A のスパース性に依存して，計算量や出力が変化する．
また，この傾向は大規模な行列を用いた処理においては顕著な
ボトルネックとなる．一方で，式 (1) で表される距離関数の値(コスト値) はイテレーションを経るごとに単調減少し，収束することが知られている [4]．doc word 行列において，式 (1) で評価したイテレーション毎のコスト値の例を図 4 に示す．
式 (1) の ||A − W H||2F が収束することから，WH において，W,H の各要素も変化量が小さくなる可能性が高い．そこで，イ
テレーション間での W,H の各要素の変化量を観測するため，
∑
(j)
(j+1)
イテレーション間の差の絶対値総和， n,k |Wn,k − Wn,k |，
∑
(j)
(j+1)
k,m |Hk,m − Hk,m | を集計したものを図 5 に示す．NMF の更新式は，W と H について交互に更新を行うが，図 5 の結果
から W, H それぞれの更新式について，一定の収束傾向がある
ことが分かる．

→ンク関係行列 A の並び替えと PageRank ベクトル −x (k) の全要素を用いて計算を行う．

3. 1. 2 NMF 計算への Adaptive 計算手法適用
PageRank 計算では式 (3) に示すように，リンク関係行列→
A と PageRank ベクトル −x (k) の乗算であるが，本研究では，
Adaptive 計算手法を NMF の更新式の行列演算に一般化する．
ここで行列演算を行う際の行列演算子と計算を行う際の基本
ルールを表 1 と表 2 に定義する．

図 5 W, H 各要素のイテレーション間の差の絶対値総和

以上で述べた行列の収束傾向を利用して，計算量や中間デー

表1

タの入出力量を削減し，イテレーション処理を高速化する手法を提案する．

3. 提 案 手 法
2. 2. 2 で述べた MapReduce 処理の課題に対して，イテレー

行列演算子

行列演算子

セマンティクス×

行列乗算 zij =.×

要素単位の乗算 zij = xij × yij/

要素単位の除算 zij = xij /yij

表2∑k xik × ykj

計算ルール

計算ルール

計算式

ションを経るごとに分解後の行列も収束する特徴を利用して，AM(Arithmetic Multiplication) ルール(X. × Y )i∗ = Xi∗ . × Yi∗

計算を省略する手法を検討する．提案手法は，Adaptive 計算手

AM(Arithmetic Multiplication) ルール(X. × Y )∗i = X∗i . × Y∗i

AD(Arithmetic Division) ルール(X/Y )i∗ = Xi∗ /Yi∗

AD(Arithmetic Division) ルール(X/Y )∗i = X∗i /Y∗i

CMM(Column Matrix Multiplication) ルール(X × Y )∗i = X × Yi

RMM(Row Matrix Multiplication) ルール(X × Y )i∗ = Xi × Y

法と Incremental 計算手法である．Adaptive 計算手法は，Wおよび H 行列において各イテレーションごとに収束した行ベク
トル，列ベクトルの更新式適用をスキップし，Incremental 計
算手法は W および H 行列の変更差分を用いて更新式を適用す

式 (2) に示す乗法的更新ルールにおいて，Adaptive な W のる手法である．それぞれの手法について詳しく述べる．

更新式は，収束判定を行ごとに適用し，収束行を C，非収束行

3. 1 Adaptive 計算手法
Adaptive 計算手法は一度閾値以下に収束した要素は，変化しない前提で，前イテレーションの値を再利用することで計算量・入出力量を削減する手法である．計算全体としては，収束を N とすると，k + 1 イテレーション目の w(k+1) ベクトルは，
{
(
)}
T
(k+1)
wN
= w(k) . × WAH
HH T
N

を行あるいは列単位 (以降ベクトルと呼ぶ) でスキップできるた

AM ルール適用()
T(k)= wN . × WAH
T
HH

め，収束傾向に基づいて Phase1 から Phase4 の処理コストをAD ルール適用判定を行うための計算量は Phase5 で増加するが，更新式適用

N削減できる．

(k)= wN . ×

3. 1. 1 Adaptive 計算の基本方針

RM M ルール適用

収束要素の計算をスキップし処理を高速化する手法として，

PageRank 計算では Adaptive PageRank 手法が提案されている [6]．Adaptive PageRank 計算は乗法的更新ルールに基づいて，次のように計算される．k イテレーションの計算を行った→
PageRank ベクトルを −x (k) ，PageRank ベクトルの収束要素(k)→を C, 非収束要素を N とすると，収束したベクトルは −x C ，非(k)−→
収束ベクトルは xと表せる．またリンク関係行列を A とし，
N

PageRank ベクトルの収束要素と非収束要素に対応するように
A 行列を並び替えると，収束部分行列 AC , 非収束部分行列 AN(k)= wN . ×
(k+1)

wC

(k+1)
−
→
xN
(k+1)
−
→
x
C

)

(k)

= wC

収束列を C，非収束列を N とすると，k + 1 イテレーション目の h(k+1) ベクトルは，{( T )}(k+1)(k)
hN= hN . × WWT WAH

N

AM ルール適用( T )(k)= hN . × WWT WAH() ( (k) )
−
→
AN
xN
=
· −
(k)
→
A
x
C

AN H TwN HH Tとなる．同様に，H の更新式は，収束判定を列ごとに適用し，と表せる．k + 1 イテレーション目の PageRank ベクトルは，((AH T )N(W HH T )NN

AD ルール適用

C

(k)
(k+1)
→
→
と表せ，−
x C はすでに収束しているため，−
xC
の再計算を

(k)

= hN . ×

行わない．従って，(W T A)N(W T W H)N

CM M ルール適用
(k)

(k+1)
−
→
→
xN
= AN −
x (k)

(3)

(k+1)
(k)
−
→
→
xC
=−
xC

(4)

= hN . ×
(k+1)

(k+1)
→
となる．Adaptive PageRank 手法では，−
xNの計算に，リhC

W T ANW T W hN

(k)

= hC

となる．本提案手法では，収束判定に基づき，非収束なベクトルに対応する AN n ，AN m のみ Phase1 Mapper で出力し，非T

T

3. 2. 1 実

装収束ベクトルに該当する AN n H ，W AN m の計算を行い，まず，Liu らによって提案された分散 NMF 計算手法 [2] を収束したベクトルは前のイテレーションと同じ値を用いる．イ

比較手法として実装し，これを拡張し，提案手法である Adap-

テレーション間での収束ベクトルの再利用は，一度収束したベ

tive 計算手法，Incremental 計算手法，両方の手法を組み合わ

クトルは変化しないという前提を置いているため，誤差が生じせた Adaptive+Incremental 計算手法を実装した．それぞれる．そこで，一定のイテレーション回数ごとに収束判定を行い，の手法の実装上の工夫について述べる．Adaptive 計算手法で収束ベクトル wC , hC と非収束ベクトル wN , hN に分ける．何は，数イテレーションごとに，一つ前のイテレーションとのイテレーションごとに収束判定を行うかをパラメータとして与差，W (k+1) − W (k) , H (k+1) − H (k) を計算し，全要素が閾値えることで，許容すべき誤差をトレードオフにし，収束ベクト

ε 以下になったベクトルを収束部分としてマークする．この処

ルのイテレーション間での再利用による高速化が可能である．

理を bitset を用いて，Phase5 の処理の中で実装した．また，

3. 2 Incremental 計算手法

この bitset を Phase1 の A 行列 Mapper 処理時に Distribut-

Incremental 計算手法の基本的なアイデアは，W, H の更新

edCache で全ノードに配布し，収束ベクトルに対応する A 行

式を適用する際に，W, H の差分計算により変更差分を用いて列の要素 < (n, m), Anm > を出力しないようにした．Incre-

計算する手法である．W, H の更新について，具体例を述べる．

mental 計算手法では，Phase5 で，∆W = W (k+1) − W (k) ,N 回のイテレーション処理を行った後の W,H の値，WN ，HN∆H = H (k+1) − H (k) を計算するよう拡張し，イテレーショ

は以下のように表現される．∆WN ，∆HN はイテレーション

ン間の差分計算により，差が収束判定閾値 ε を超える要素のみごとの更新差分となるため，行列の収束の有無を任意の収束判

を非収束要素として取り出す．この差分を Mapper の入力とし

定閾値 ε で判定し非収束要素を対象に更新する．イテレーショて，Phase1 では，∆W T A, A∆H T の計算を行い，Phase2 のンを経るごとに収束要素が増加するため，計算すべき差分 ∆ はReducer で，(W T A)(k−1) + ∆W T A, (AH T )(k−1) + A∆H T

小さくなる．

を計算する実装とした．

WN = W0 + ∆W1 + ∆W2 + ... + ∆WN

4. 評 価 実 験

HN = H0 + ∆H1 + ∆H2 + ... + ∆HN
通常の計算では，W や H は密な行列になるが，Incremen-

本章では，Adaptive 計算手法と Incremental 計算手法を分tal 計 算 手 法 で は ，非 収 束 要 素 を 取 り 出 す こ と で 疎 な 行 列

散 NMF に適用し，Job の処理時間，通常の分散 NMF との誤を構築し，乗算する計算コストを削減できる．特に Phase1

差について評価を行う．

T
では，(n, hTm Anm )，(m, Anm wn ) の乗算となるため，行列4. 1 実 験 条 件の収束に伴って計算量を削減できる．ただし，Phase2 では，

4. 1. 1 実 験 環 境

AH T + A∆H T ，W T A + ∆W T A の加算を行うため，shuﬄe

実験には，1 台の Master ノードと 10 台の Slave ノード

量が増加するというトレードオフがある．

を用いた．個々のマシンスペックは，CPU: Intel Core2Duo

Incremental 計算を行うにあたり，NMF の更新式全体を対E7400 @ 2.8GHz，RAM: 8GB，SATA HDD(I/O: 93.5〜104.1

象に Incremental 計算を行う手法と，更新式の一部を Incre-

MB/sec)， Gigabit Ethernet， OS: CentOS 5.6 x86 64 となっmental に計算する手法が考えられる．本実験では，Phase1,ている．また，ミドルウェアには，Apache Hadoop 1.0.3，Or-

Phase2 Job の処理ボトルネック解消のため，更新式の一部に

acle JDK 1.6.33 を用いた．

Incremental 計算手法を適用した．Incremental 計算手法にお4. 1. 2 データセット

ける更新式を以下に示す．
A(H T +∆H T )W (k+1) = W (k) . ×
W (H +∆H)(H T +∆H T )= W (k) .×

A(H T + ∆H T )Twitter 上の発言を集約して，まとめページを作成できるサー

W (HH T +H∆H T +∆HH T +∆H∆H T )ビスである．各記事におけるユーザの発言頻度を bag of words

TT

H∆H + ∆HH + ∆H∆H

T

≈ 0 とし，

AH T に前イテレーションの値を用いると≈ W (k) . ×(AH T )(k−1) + A∆H T
W HH T

非零要素率 0.0013%と，各記事における単語頻度を出現するドキュメント数で除算し TF-IDF 化したスコアを bag of words と零要素率 0.11%のデータを用いた．それぞれのデータは，行列(W T +∆W T )(W +∆W )H

インデックスを key とし，要素の値を value とした Key Value

形式 < (n, m), Anm > を SequenceFile Format で格納した．
(W + ∆W )A(W T W +W T ∆W +∆W T W +∆W T ∆W )H
4. 1. 3 実 験 条 件
T= H (k) .×

350,469×2,663,167
として表現した doc user 行列，Adoc user ∈ R+

350,256×397,676
して表現した doc word 行列，Adoc word ∈ R+
非

(W T +∆W T )A

H (k+1) = H (k) . ×

実験データセットには，ソーシャルキュレーションサービスである Togetter から得たデータを利用した．Togetter はユーザがT

W T ∆W + ∆W T W + ∆W T ∆W ≈ 0 とし，
W T A に前イテレーションの値を用いると≈ H (k) . ×

T

(k−1)

T

(W A)
+ ∆W A
WTWH

実験ケースとして，Adaptive 計算手法，Incremental 計算手法，Adaptive と Incremental 計算を組み合わせた手法をそれぞれ，Adoc user 行列と Adoc word 行列について実施した．予備実
験の結果からイテレーション数は 50 とし，行列分解する基底数

図 7 合計処理時間 (doc user 行列)
図 6 イテレーションごとの処理時間 (doc user 行列)k は k = 200 とした．Adaptive 計算手法については，収束判定の頻度を 5 イテレーションごとに設定した．また，Incremental
計算手法においては，初めのイテレーションから適用した場合，差分 ∆ が大きくなり，通常の分散 NMF より I/O が増加するため，Incremental 計算を開始するイテレーションを設定し，処理時間と従来手法との誤差 (L2 ノルム) の比較を行った．測定
バリエーションと収束判定閾値 ε(閾値 ε)，Incremental 計算開始イテレーション (開始 Itr.) を表 3 と表 4 に示す．
表 3 doc user 測定バリエーション
手法

従来

Adaptive

Incremental 1 Incremental 2 Adaptive +

閾値 ε

-

1.0E-9

1.0E-9

1.0E-9

1.0E-9

-

1

15

15

Incremental
開始 Itr. -図 8 イテレーションごとの処理時間 (doc word 行列)

表 4 doc word 測定バリエーション
手法

従来

Adaptive

Incremental 1 Incremental 2 Adaptive +

閾値 ε

-

1.0E-9

1.0E-9

1.0E-9

1.0E-9

-

1

15

1

Incremental
開始 Itr. -4. 2 実 験 結 果
各イテレーションの処理時間を図 6 と図 8 に，50 イテレー
ションの合計処理時間を図 7 と図 9 に示す．
実験の結果，W,H 行列の収束傾向に応じて，Incremental 計
算開始イテレーションを調整する方が処理時間が短くなった．
これは，W, H 行列が十分に収束していない場合は差分行列のI/O が増加すること，W T A + ∆W T A を加算するコストが増

図 9 合計処理時間 (doc word 行列)

処理時間の改善率が 74.9%と高かった，doc word 行列のAdaptive+Incremental について，各のフェーズの平均処理時
間 (50 イテレーションの平均) を図 10 に示す．

えることが原因である．

フェーズごとに比較すると，W Phase1, W Phase2 の処理時
表 5 doc user 実験結果

間が大きく改善されているが，H Phase1, H phase2 の改善率

手法

従来

Adaptive

Incremental 1 Incremental 2 Adaptive +処理時間 (分)667.61586.8

627.05616.27585.96

改善率

-

12.1%

6.1%

7.7%

12.2%

誤差 (従来比)-0.000079%-0.023%0.000011%

0.000044%

Incremental

は W 更新式と比較して小さくなっている．この原因を W, Hの要素ごとの収束状況から分析する．図 11 に W 行列, H 行列のイテレーションごとの差を収束判定閾値 (ε=1.0E-9) で非収束要素をカウントしたものを示す． H 行列は 5 イテレーショ
ンまでに非収束要素の割合が 2%と十分収束し，H 行列の差分

表 6 doc word 実験結果
手法

従来

処理時間 (分)3838.01 2739.78

1765.15

1968.55

963.32

改善率

-

28.6%

54.0%

48.7%

74.9%

誤差 (従来比)-2.32%-4.28%

0.66%-1.70%

Adaptive

Incremental 1 Incremental 2 Adaptive +Incremental

を入力とする W 更新式の計算量は減少したが，収束傾向の緩やかな W 行列は，20 イテレーション前後でも非収束要素の割合が 35%となっており，W 行列の差分を入力とする H 更新式の計算量の削減率が低いことが分かった．

図 13 Phase2 Job の Shuﬄe 量 (doc word 行列)
図 10

各フェーズの平均処理時間 (doc word 行列)

4. 3 考察

Adaptive 計算手法，Incremental 計算手法によって，行列の収束傾向に基づいた高速化が行えた．言い換えると，処理時間は収束傾向に依存するが，Incremental 計算の開始イテレー
ションや収束判定閾値の設定が重要であると考えられる．

Adaptive 計算手法では，収束要素に対応する A 行列の再構
築を行うことで，W T A や AH T の計算処理を効率化できるが，

MapReduce では I/O をディスクに依存するため，行列再構築のオーバーヘッドが大きい．このオーバーヘッドは，I/O が高
速なディスクを用いたり，Spark（注 1）などのインメモリアーキテ
図 11

イテレーションごとの非収束要素の割合 (ε=1.0E-9)

クチャを用いる必要がある．

Incremental 計算手法では，Reduce 側で前イテレーションの W T A を読み込み，W T A + ∆W T A の処理を行うため，収束傾向が緩やかな場合，加算によるオーバーヘッドが増加する．
そのため，Incremental 計算を開始するイテレーションを収束
状況により判断するメカニズムが必要である．

5. 関 連 研 究
NMF をはじめとする行列計算の高速化，分散処理手法について関連研究を整理する．
乗法的更新ルールのようにイテレーション処理を効率化する
手法には，大きく分けると，行列の分割やデータ構造の変更，
イテレーションの集約，処理オペレータの最適化が挙げられる．行列の分割について，Liu らは行列のパーティショニングス
図 12 Phase1 Job の CPU 処理コスト (doc word 行列)

キーマとパーティションの効率的なシャッフル方法を工夫するこ次に，2. 2. 1 で述べた Phase1 の CPU コスト，Phase2 のとで NMF や SVM(Support Vector Machine)，PageRank と

Shuﬄe I/O について考察する．各イテレーションごとの Phase1

いった機械学習アルゴリズムを MapReduce 上で効率的に処理の CPU Time Spent(ms) を図 12 に，Phase2 の Reduce shuﬄeできる手法を提案した [7]．Nagy らも同様に分散 NMF についbytes(MB) を図 13 に示す．

てブロック単位で行列を分割することで大規模行列にも対応可

Phase1 の CPU time spent(ms) の比較では，従来手法は行

能な分散 NMF の処理手法を提案した [8]．また，Li らは Spark(列) ベクトルを配列で保持し処理していたが，差分処理の効率上でのデータ構造を Carousel Maps に変えることで大規模な化のため，行 (列) ベクトルごとに ArrayList 形式で保持する行列分解に対応する手法を提案している [9]．

実装としたため，差分 ∆ の多いイテレーションの前半で CPU

次に，イテレーションの集約について，MapReduce のスキーコストが従来より増加した．また，Phase2 の Reduce shuﬄe

ムを用いながらイテレーション処理を高速化する手法も研究

bytes(MB) においても，差分 ∆ の多いイテレーションの前半されている．Myung らは数回のイテレーション処理をデータ

で I/O が増加するが，行列の収束に伴って，I/O が削減できた．
（注 1）：http://spark.incubator.apache.org/

ベースにおける JOIN 処理として集約する手法を提案した [10]．

Kamvar らは，PageRank 処理を Adaptive に更新することで収束ベクトルを複数のイテレーション間で用いることで計算コストを削減している [6]．Adaptive PageRank では，PageRank
ベクトルがリニアとなるが，本研究では，行列同士の乗算に応用する手法を検討し，NMF の更新式の計算を Adaptive に行う手法を提案した．
行列の傾向に応じた処理やオペレータを最適化する研究には，Zhang らによる補助行列を用いて計算処理を効率化する手法 [11] や Sindhwani らによる，辞書学習を用いて行列分解を最適化する手法がある [12]．Yan らは Job 間の Incremental 処理のデータフローに着目し，ローカリティコントロールを効率化することで Incremental 処理を高速化する手法を提案した [13]．

Ewen らもデータフローに着目し，処理プランを書き換え最適化を行う手法を提案した [14]．本研究では，収束傾向によって

Incremental 計算の入力となる更新差分がイテレーションごとに減少する前提を置いているため，ローカリティコントロールを行っていないが，収束傾向が緩やかな行列の処理を行う際には shuﬄe 時の偏りが生じるためローカリティコントロールが有効になる可能性がある．また，Ghoting らは機械学習処理をDML(Declarative Machine learning Language) として定義し，
よりプリミティブな処理オペレータに分解して MapReduce 上
での処理を効率化する手法を提案した [15]．さらに，Low らは行列をグラフ表現にし，グラフの並び替えと非同期処理により処理効率化を図っている [16]．

6. 結

論

分散 NMF は行列分解処理を並列分散環境で行う手法であるが，行列のスパース性や基底数に応じて，処理コストが O(nm)で変化する．本研究では分散 NMF 処理において処理時間を改善するため，Adaptive 計算手法と Incremental 計算手法を提案した．Adaptive 計算手法では，乗法的更新ルールを適用するイテレーション処理の過程で行列が収束する性質を利用して，収束ベクトルの更新ルール適用処理をスキップし，Incremental
計算手法では，前イテレーションで計算した要素の値をベースに，更新差分が発生する非収束要素を加法的に更新する手法である．本提案手法を分散 NMF の処理に適用し，Job の処理時間，従来の分散 NMF との誤差について評価を行った．実験の結果，行列の収束傾向に基づいた処理時間削減が行え，doc word
行列を用いた実験では従来手法と 1.70%の誤差で 74.9%の処理時間の改善効果が得られ，従来の約 1/4 の時間での処理が可能となった．

6. 1 今後の課題
本提案手法の今後の課題として，差分 ∆ の大きさに応じて，Incremental 計算手法の適用を開始するイテレーションを自動決定するアルゴリズムを導入すること．A 行列の再構築を効率的に行えるよう，インメモリアーキテクチャやグラフ処理ミド
ルウェアを用いるなど，ディスクの I/O に依存しない仕組みを構築することなどが挙げられる．

文

献[1] D. Seung and L. Lee, “Algorithms for non-negative matrix
factorization,” Advances in neural information processing
systems, 2001.
[2] C. Liu, H.-c. Yang, J. Fan, L.-W. He, and Y.-M. Wang,“Distributed nonnegative matrix factorization for web-scale
dyadic data analysis on mapreduce,” Proceedings of the
19th international conference on World wide web - WWW’10, p.681, 2010.
[3] P. Paatero and U. Tapper, “Positive matrix factorization:
A non-negative factor model with optimal utilization of error estimates of data values,” Environmetrics, vol.5, no.2,
pp.111–126, 1994.
[4] D.D. Lee and H.S. Seung, “Algorithms for non-negative matrix factorization,” In Advances in Neural Information Processing Systems, pp.556–562, 2000.
[5] P.O. Hoyer, “Non-negative matrix factorization with sparseness constraints,” J. Mach. Learn. Res., vol.5, pp.1457–
1469, Dec. 2004.
[6] S. Kamvar, T. Haveliwala, and G. Golub, “Adaptive methods for the computation of PageRank,” Linear Algebra andits Applications, vol.386, pp.51–65, 2004.
[7] S. Liu, P. Flach, and N. Cristianini, “Generic Multiplicative
Methods for Implementing Machine Learning Algorithms on
MapReduce,” CoRR, 2011.
[8] A. Nagy, M. Coppola, and N. Tonellotto, “Parallelization
Strategies for Distributed Non Negative Matrix Factorization,” world-comp.org, 2012.
[9] B. Li, S. Tata, and Y. Sismanis, “Sparkler: Supporting
large-scale matrix factorization,” Proceedings of the 16th
International Conference on Extending Database Technology, pp.625–636, 2013.
[10] J. Myung and S.-g. Lee, “Matrix chain multiplication via
multi-way join algorithms in mapreduce,” Proceedings of
the 6th International Conference on Ubiquitous Information
Management and Communication, p.53, 2012.
[11] Y. Zhang, M. Zhang, Y. Liu, S. Ma, and S. Feng, “Localized matrix factorization for recommendation based on
matrix block diagonal forms,” Proceedings of the 22Nd International Conference on World Wide Web, pp.1511–1520,
2013.
[12] V. Sindhwani and A. Ghoting, “Large-scale distributed nonnegative sparse coding and sparse dictionary learning,” Proceedings of the 18th ACM SIGKDD international conferenceon Knowledge discovery and data mining - KDD ’12, p.489,
2012.
[13] C. Yan, X. Yang, Z. Yu, M. Li, and X. Li, “IncMR: Incremental Data Processing Based on MapReduce,” 2012
IEEE Fifth International Conference on Cloud Computing,pp.534–541, June 2012.
[14] S. Ewen, K. Tzoumas, M. Kaufmann, and V. Markl, “Spinning fast iterative data flows,” Proc. VLDB Endowment,
vol.5, no.11, pp.1268–1279, July 2012.
[15] A. Ghoting, R. Krishnamurthy, E. Pednault, B. Reinwald,
V. Sindhwani, S. Tatikonda, Y. Tian, and S. Vaithyanathan,“SystemML: Declarative machine learning on MapReduce,”
2011 IEEE 27th International Conference on Data Engineering, pp.231–242, April 2011.
[16] Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola,
and J.M. Hellerstein, “Distributed graphlab: A framework
for machine learning and data mining in the cloud,” Proc.
VLDB Endowment, vol.5, no.8, pp.716–727, 2012.