確率的勾配降下法(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つで、
- 一回の更新にあたって参照するデータ量が少なく(勾配の計算が簡単)
- オンライン化が容易である
ので、大規模データの解析に利用できると言われている。
ただ、SGDはもともと1コア用の処理なので、並列化したい。
そこで、Hog Wildのアルゴリズムと、distributed stochastic gradient descent (DSGD) が、作られた。
今回は、SGDとHog WildとDSGDを、順番に解説(翻訳)していく。
実装は、見たらわかるので割愛する。
1.SGD
これは、単純な勾配法である。
行列Rのu行v列成分を、PuとQvで表現して、誤差を最小化する。
ただし、そのままでは過学習するので、正則化項として、後ろに2つの項を付ける。
SGDでは、(1)の式の勾配を計算するのが困難な場合に、ランダムに(u,v)を選択し、(1)式を以下の式のように簡単化する。
その後、上式を微分し、最急降下法により、(2)式と(3)式で表される更新式を得る。
あとは愚直に(2)と(3)を繰り返せば良い。
2.Hog Wild
この方法では、複数コアで同時に(2)と(3)を繰り返すだけである。
そんなことをすると、更新する時に、あるコアが計算した結果を、別のコアの計算結果が上書きするという事態が発生する。
こういった操作を、Atomic Operation(不可分操作)と言うらしい。
が、そんなことは、疎で巨大な行列なら、滅多に起こらないから気にしない。
特定条件下における収束証明もされていて、実用上問題は発生しないようだ。
3.DSGD
DSGDでは、HogWildとは違い、複数コアで同じ要素を上書きし合うことを避けようとした。
その結果、行列を幾つかに切り分けて、各コア中でそれぞれ独立に更新することにした。
上の図が分かり易いが、行列を分割し、各コアに割り当てると、同じインデックスを選択することが起こりえなくなる。
したがって、コア同士の更新が干渉しなくなる。
ただ、ブロック行列の同じ行や列を選択することができなくなるため、何度も反復してコア間でデータを渡しあわなければならない。
(更新したPやQを参照するために、反復する必要がある)
:以下、個人的疑問
またこの方法では、上手い分割の仕方をしなければ、変なPとQが求まってしまうことが予想される。
例えば、最悪の場合、行列の密部分(いわば1つのクラス)を4つに分割してしまうという事態が発生しうる。
こうなると、その密部分の再構成は、他の密部分が優先された結果、おざなりにされるかもしれない。
(正則化があるので、値の小さな部分は切り捨てられる)