分からんこと多すぎ

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

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つの基準にしたがって、新たなブロックを割り当てる。

  1. 割り当てるblockがfree blockであること
  2. すべてのfree blockの中で最も更新回数が少ないこと

両方の条件を満たしたものが複数ある場合は、ランダムに1つ選択する。

s個のスレッドが与えられた時、少なくとも行列Rを(s+1)×(s+1)個に分割する。

f:id:rishida:20131117150804p:plain

上の図では、R00をスレッドT1で処理し、R22をスレッドT2で処理している。

今、T2における処理が完了したとすると、そのスレッドを用いて、R11、R12、R21のうちの1つを新たに割り振り、処理を行う。

このようにすることによって、Locking Problemを回避することができる。

ただし、あるブロックに多くの要素が固まっている場合、そのブロックの更新回数は必然的に少なくなってしまう。

簡単な救済策としては、前述したrandom shufflingがある。

(筆者たちの体感だが、random shuffle後は、最も密なブロックの要素数は、最も疎なブロックの要素数の二倍に、届かない程度になるらしい)

ブロックの更新回数の差に関する指標を求めて計算したところ、ほぼ差がなくなっていることが、図に示されている。

ただ、Random

Partial Random Method

Memory Discontinuityを解決するために、Random Methodに対抗して、ordered methodというものを導入する。

これは、userあるいはitem方向に関して連続的に選択していく方法である。

f:id:rishida:20131117154612p:plain

例えば上図のようにアクセスすると、Pに連続的にアクセスできる。

アクセスの順番が固定されていれば、元の行列Rを同じ順序でメモリに格納することで、同じ順序で連続的なアクセスが可能となる。

ただ、ordered methodは確かに連続的にアクセスできるようになるが、経験的には安定的なものではないと言える。

learning rate(最急降下法の係数γ)を変化させると、RandomMethodの方が高速になる場合があるのである。(図9)

つまり、収束性という観点においては、RandomMethodの方が良いと言えるのかもしれない。

例えばcoordinate descent methodにおいては、ランダムな更新の方がはるかに収束速度が早い。

そこで、筆者たちはPartial random methodを導入する。

f:id:rishida:20131117160127p:plain

上図で示したように、ブロック内の更新は順番に(ordered methodで)行うが、ブロックの選択においては乱択にする。

他文献[4]に示されている関連手法に関する調査では、ordered methodの方がrandom methodよりも収束が悪いと言っている。

これは筆者たちが実験的に示した結果とは逆の結果となる。

それに関して考えうる理由としては、筆者たちがRMSE(最小二乗誤差)を指標としているのに対して、訓練誤差を見ていることが上げられる。

おわりに

あとはFPSGD早いという実験結果が載っているだけなので、省略する。

大体既存の十倍くらい早い。

FPSGDのMethod間の比較では、Partial Random Method最強らしい。

Rでパッケージを書くべきか悩む。

超訳してたらごめんなさい。している気はする。