RecSys2013のBestPaperを読む_Fast_Parallel_SGD
RecSys 2013 (Hong Kong) - RecSysのbest paperが、なんだか面白そうだったので読む。
A Fast Parallel SGD for Matrix Factorization in Shared Memory Systems
著：Yong Zhuang, Wei-Sheng Chin, Yu-Chin Juan, and Chih-Jen Lin
本論文自体は、Matrix FactorizationのためのSGDの拡張である点が、他の論文とは違うらしい。
序論は確率的勾配降下法（SGD）の並列化について - 分からんこと多すぎに書いたので、本文の3章（SGDの並列化に関する諸問題）からになる。
また結論から言うと、計算速度は従来手法の十倍程度になる。
ただし、プログラミング上のテクニック的な話なので、理論とかあんまりない。
勉強になるし実用的で、企業的にはすごく身になる話なのだろうけれど、数学的な面白さはない。
Problem in Parallel SGD Methods For Matrix Factorization
SGDの並列化には、Locking Problemという問題と、Memory Discontinuityという問題がある。
Locking Problem
並列化において、すべてのスレッドを常にbusy状態にすることは、重要である。
Locking Problemというのは、他のコアの処理が終了するのを待つために、アイドリング状態になることを指す。
また、この問題は、分割したあとの行列Rの各ブロック行列がアンバランス（疎密の差が激しい状態）だと、より深刻になる。
密部分の更新には時間がかかるが、疎部分の更新には時間がかからないため、多くの疎部分の更新に割かれているスレッドが、待ちの状態にならざるを得ない。
分割したブロック行列の密疎の差をなくすための、簡単な方法として、random sufflingというものがある。
これは、行列の行のインデックスや列のインデックスを、ランダムに並べ替える方法である。
しかしこの方法でも、各ブロック行列に入っている要素の数は同じではないし、よしんば同じだったとしても、必要な更新時間は異なっている。
（訳注：おそらく大規模行列だと、この辺りの僅かな無駄の影響が、無視できないほど大きいのだろう）
ちなみにDSGDではメモリが共有されていないので、スレッド間の対話（更新値の渡し合い）の方が、スレッドのアイドルの問題よりも重要視されているようである。
Memory Discontinuity
プログラムが不連続的にキャッシュにアクセスするとき、キャッシュミス（参照すべきデータがキャッシュ上になく、メインメモリにアクセスしに行くこと）を頻繁に起こし、パフォーマンスが低下する。
HogWildやDSGDでの実装では、更新時にランダムに行列Rの一部を取り出すため、この問題に苦しめられる。
（筆者たちはこれをRandomMethodと呼称している）
The reason is that not only are rating instances randomly accessed, but also user/item identities become discontinuous.
（これはデータのインスタンスにランダムにアクセスするためだけでなく、ユーザ/アイテムのインデックスが処理ごとに切り替わるためである、の意？）
HogWildとDSGDではこの問題の深刻さは若干異なっている。
HogWildではそれぞれのスレッドでランダムにアクセスするため、行列R,P,Qの全てにおいて、Memory Discontinuityが起きる。
対してDSGDでは、ブロックの中でランダムにアクセスされるだけなので、本論文ではここでの問題を軽減するように、手法を改善する。
Fast Parallel SGD
本論文内では、lock-free scheduling とpartial random methodを提案する。
これは、Locking ProblemとMemory Discontinuityを解決するためである。
Lock-Free Scheduling
DSGDに習って、行列Rをブロックに分割する。
そしてs個のスレッドをbusy状態にし続けられるように、スケジューラを設計する。
ブロックBijが他の処理中のすべてのブロックから独立なとき、これをfree blockと呼ぶ。
一方そうでない時を、non-free blockと呼ぶ。
スレッドが処理を終えた時、スケジューラは、以下の2つの基準にしたがって、新たなブロックを割り当てる。
- 割り当てるblockがfree blockであること
- すべてのfree blockの中で最も更新回数が少ないこと
両方の条件を満たしたものが複数ある場合は、ランダムに1つ選択する。
s個のスレッドが与えられた時、少なくとも行列Rを（s+1）×（s+1）個に分割する。
上の図では、R00をスレッドT1で処理し、R22をスレッドT2で処理している。
今、T2における処理が完了したとすると、そのスレッドを用いて、R11、R12、R21のうちの１つを新たに割り振り、処理を行う。
このようにすることによって、Locking Problemを回避することができる。
ただし、あるブロックに多くの要素が固まっている場合、そのブロックの更新回数は必然的に少なくなってしまう。
簡単な救済策としては、前述したrandom shufflingがある。
（筆者たちの体感だが、random shuffle後は、最も密なブロックの要素数は、最も疎なブロックの要素数の二倍に、届かない程度になるらしい）
ブロックの更新回数の差に関する指標を求めて計算したところ、ほぼ差がなくなっていることが、図に示されている。
ただ、Random
Partial Random Method
Memory Discontinuityを解決するために、Random Methodに対抗して、ordered methodというものを導入する。
これは、userあるいはitem方向に関して連続的に選択していく方法である。
例えば上図のようにアクセスすると、Pに連続的にアクセスできる。
アクセスの順番が固定されていれば、元の行列Rを同じ順序でメモリに格納することで、同じ順序で連続的なアクセスが可能となる。
ただ、ordered methodは確かに連続的にアクセスできるようになるが、経験的には安定的なものではないと言える。
learning rate（最急降下法の係数γ）を変化させると、RandomMethodの方が高速になる場合があるのである。（図9）
つまり、収束性という観点においては、RandomMethodの方が良いと言えるのかもしれない。
例えばcoordinate descent methodにおいては、ランダムな更新の方がはるかに収束速度が早い。
そこで、筆者たちはPartial random methodを導入する。
上図で示したように、ブロック内の更新は順番に（ordered methodで）行うが、ブロックの選択においては乱択にする。
他文献[4]に示されている関連手法に関する調査では、ordered methodの方がrandom methodよりも収束が悪いと言っている。
これは筆者たちが実験的に示した結果とは逆の結果となる。
それに関して考えうる理由としては、筆者たちがRMSE（最小二乗誤差）を指標としているのに対して、訓練誤差を見ていることが上げられる。
おわりに
あとはFPSGD早いという実験結果が載っているだけなので、省略する。
大体既存の十倍くらい早い。
FPSGDのMethod間の比較では、Partial Random Method最強らしい。
Rでパッケージを書くべきか悩む。
超訳してたらごめんなさい。している気はする。