分散NMFにおけるAdaptive,Incremental計算手法の適用

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 処理において処理時間を短縮するため，大半のレコード
が数イテレーション後に収束するという特徴を利用できないか
Wnew =
min||A − W H||2F s.t.W, H >
(1)
=0
T
T
AH
W A
W. ×
Hnew = H. × T
(2)
W HH T
W WH
検討した．そこで，収束したレコードの処理をスキップして処
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
6
Phase4 Job(H4): Y=QH
7
Phase5 Job(H5): H=H. ∗ X/Y
8
//Update W
9
Phase1 Job(W1)，Phase2 Job(W2): X=AH T の計算
10
Phase3 Job(W3): Q=HH T
11
Phase4 Job(W4): Y=WQ
12
Phase5 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 >
理時間を示したものである．測定結果から，Phase1, Phase2
の処理 (H1,H2,W1,W2) が全体の 54%(doc user 行列), および
94%(doc word 行列) を占めており，非零要素率の変化による
影響が大きいことが分かった．
2. 2. 2 分散 NMF の課題
NMF で収束解を求めるためには数十から数百回のイテレー
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 は，
ションを繰り返す必要があり，数百万次元の規模の大きな行列
の処理では，結果を得るまでに数時間から数日の処理時間を
必要とする．2. 2. 1 で述べたように Phase1, Phase2 Job では，
それぞれ，X = W T A と X = AH T の計算処理を行うが，計
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
図 4 doc word 行列におけるイテレーション毎のコスト値
テレーションを処理した際の 1 イテレーションあたりの平均処
user
∈
R350,469×2,663,167
非零要素率 0.0013%と，doc word 行列，
+
Adoc word ∈ R350,256×397,676
非零要素率 0.11%の行列データを
+
用いて，従来手法の各フェーズの平均処理時間を測定した．デー
タセットの詳細については，4. 1. 2 で詳述する．図 3 は，50 イ
算結果が密行列 (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 T
wN HH T
となる．同様に，H の更新式は，収束判定を列ごとに適用し，
と表せる．k + 1 イテレーション目の PageRank ベクトルは，
(
(AH T )N
(W HH T )N
N
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 AN
W T W hN
(k)
= hC
となる．本提案手法では，収束判定に基づき，非収束なベクト
ルに対応する AN n ，AN m のみ Phase1 Mapper で出力し，非
T
T
収束ベクトルに該当する AN n H ，W AN m の計算を行い，
3. 2. 1 実
装
まず，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, hT
m 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 計算手法にお
ける更新式を以下に示す．
A(H T +∆H T )
W (k+1) = W (k) . ×
W (H +∆H)(H T +∆H T )
= W (k) .×
W (HH T
T
A(H T + ∆H T )
+H∆H T +∆HH T +∆H∆H T )
T
H∆H + ∆HH + ∆H∆H
T
≈ 0 とし，
AH T に前イテレーションの値を用いると
≈ W (k) . ×
H (k+1) = H (k) . ×
(AH T )(k−1) + A∆H T
W HH T
(W T
実験データセットには，ソーシャルキュレーションサービスで
ある Togetter から得たデータを利用した．Togetter はユーザが
Twitter 上の発言を集約して，まとめページを作成できるサー
ビスである．各記事におけるユーザの発言頻度を bag of words
として表現した doc user 行列，Adoc
user
350,469×2,663,167
∈ R+
非零要素率 0.0013%と，各記事における単語頻度を出現するド
キュメント数で除算し TF-IDF 化したスコアを bag of words と
して表現した doc word 行列，Adoc
(W T +∆W T )A
+∆W T )(W +∆W )H
word
350,256×397,676
∈ R+
非
零要素率 0.11%のデータを用いた．それぞれのデータは，行列
インデックスを 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) .×
4. 1. 2 データセット
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.61
586.8
627.05
616.27
585.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 and
its 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 conference
on 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.

Download Report