先日Gunosy新オフィスにて「RecSys2013論文読み会」というものに参加してきました。全体の様子はこちらで紹介していただいているので、ここでは私担当分の論文だけ簡単に解説したいと思います。
一応説明しておくと、RecSysというのは、レコメンデーションシステム（自動推薦システム）に関する国際会議で、毎年行われています。「RecSys2013論文読み会」というのは、その国際会議で今年発表された論文を各自選んで解説するものです。
紹介した論文はこちら：
Zuang et al., A Fast Parallel SGD for Matrix Factorization in Shared Memory Systems
ユーザによるレイティング（点数）の予想については、matrix factrization（行列積分解）という手法がよく知られていて、その開放としては確率的最急降下法（Stochastic Gradient Descent, SGD）というアルゴリズムが使わている。SGDによる解法では、ランダムにi,jの組を選んで、行列のi,j成分に注目してパラメータ（積分解したときの行列の要素）を動かすのだが、これを共有メモリを使って並列に計算するのを効率的にやるのがこの論文。
クラスタなどの分散環境については、既存のDSGDというアルゴリズムが知られている。これだと分散ということで通信量が少なくなるようにうまく工夫されているが、CPUの負荷のアンバランスが発生して、待ち状態が発生してしまう。そこでFPSGD（提案手法）ではDSGDを修正してロックフリーに動くようにしている。
DSGD：行列をs×s（sはノード数）のブロックに分割して、各スレッドに更新場所が重ならないようにブロックを割り当てる。更新箇所が重ならないという条件は、ちょうど将棋の飛車（チェスのrook）がお互いに取り合えないという配置。
FPSGD：行列をs×sより細かいブロック（つまりM×M, M>s, sはスレッド数）に分割して、開いているブロックの中から更新回数が少ないものをスレッドに割り当てる。
キャッシュヒット率を上げるため、ブロック内のアクセスはランダムにせずにシーケンシャルにし、しかしブロック選択をランダムにすることでランダム性を確保。
アルゴリズムの詳細は図解のほうがわかりやすいと思うので、上記スライド参照。
参加者の人たと色々とディスカッションしましたが、このような計算スピードを追求するような論文はRecSysでは珍しいようです。なのに（だからなのか？）この論文はベストペーパー賞受賞だそうです。