分からんこと多すぎ

何故か就職できたので技術磨く。一人前の多重線形代数使いを目指しつつ、機械学習、データマイニングをやる

確率的勾配降下法(SGD)の並列化について

RecSys 2013 (Hong Kong) - RecSysのbest paperが、なんだか面白そうだったので読む。

A Fast Parallel SGD for Matrix Factorization in Shared Memory Systems

論文の提案手法に関してはこっち
RecSys2013のBestPaperを読む_Fast_Parallel_SGD - 分からんこと多すぎ

本論文自体は、Matrix FactorizationのためのSGDの拡張である点が、他の論文とは違うらしい。

で、この論文の途中に、state-of-the-artが丁寧にまとめられていたので、備忘録にする。

SGDというのは、最適化の方法の1つで、

  1. 一回の更新にあたって参照するデータ量が少なく(勾配の計算が簡単)
  2. オンライン化が容易である

ので、大規模データの解析に利用できると言われている。

ただ、SGDはもともと1コア用の処理なので、並列化したい。

そこで、Hog Wildのアルゴリズムと、distributed stochastic gradient descent (DSGD) が、作られた。

今回は、SGDとHog WildとDSGDを、順番に解説(翻訳)していく。

実装は、見たらわかるので割愛する。

1.SGD

これは、単純な勾配法である。

行列Rのu行v列成分を、PuとQvで表現して、誤差を最小化する。

f:id:rishida:20131117090835p:plain

ただし、そのままでは過学習するので、正則化項として、後ろに2つの項を付ける。

SGDでは、(1)の式の勾配を計算するのが困難な場合に、ランダムに(u,v)を選択し、(1)式を以下の式のように簡単化する。

f:id:rishida:20131117090841p:plain

その後、上式を微分し、最急降下法により、(2)式と(3)式で表される更新式を得る。

f:id:rishida:20131117090845p:plain

あとは愚直に(2)と(3)を繰り返せば良い。

2.Hog Wild

この方法では、複数コアで同時に(2)と(3)を繰り返すだけである。

そんなことをすると、更新する時に、あるコアが計算した結果を、別のコアの計算結果が上書きするという事態が発生する。

こういった操作を、Atomic Operation(不可分操作)と言うらしい。

が、そんなことは、疎で巨大な行列なら、滅多に起こらないから気にしない。

特定条件下における収束証明もされていて、実用上問題は発生しないようだ。

3.DSGD

DSGDでは、HogWildとは違い、複数コアで同じ要素を上書きし合うことを避けようとした。

その結果、行列を幾つかに切り分けて、各コア中でそれぞれ独立に更新することにした。

f:id:rishida:20131117094559p:plain

上の図が分かり易いが、行列を分割し、各コアに割り当てると、同じインデックスを選択することが起こりえなくなる。

したがって、コア同士の更新が干渉しなくなる。

ただ、ブロック行列の同じ行や列を選択することができなくなるため、何度も反復してコア間でデータを渡しあわなければならない。

(更新したPやQを参照するために、反復する必要がある)

:以下、個人的疑問

またこの方法では、上手い分割の仕方をしなければ、変なPとQが求まってしまうことが予想される。

例えば、最悪の場合、行列の密部分(いわば1つのクラス)を4つに分割してしまうという事態が発生しうる。

こうなると、その密部分の再構成は、他の密部分が優先された結果、おざなりにされるかもしれない。

(正則化があるので、値の小さな部分は切り捨てられる)