でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

Robust Large-Scale Machine Learning in the Cloud [KDD'16] を読んだ

KDD16で発表されてた論文。著者はかの有名なFactorization Machinesの人。Googleに行ってたのね。いままでとはちょっと違う研究をしてるように感じる。

論文はここから読める。

www.kdd.org

勉強会で紹介したので念のため、その時のスライドはこちら。

一言まとめ

一般化線形モデルの学習を Coordinate Descent で、めっちゃスケールさせるよ。

概要

Coordinate Descent (CD) はシングルマシン上では収束が早いアルゴリズムとして知られてるんだけど、分散には向かない。なぜなら、アルゴリズムの特性上、分散させると1つのワーカーに割り当てられる work load が小さくなってしまって、オーバヘッドを考えると分散効果が小さいから。CDはパラメータの更新を次元ごとに 逐次 繰り返していくことで収束するアルゴリズムなので、分散させるには基本的にはデータパラレルにすることになる。でもパラメータの1つの次元を更新するときの処理はそんなに重くないので、分散させるメリットがあまりないということ。

そこでこの論文では1つの次元ごとじゃなくて、次元の集合(ブロック)ごとに更新するのをくりかえす Scalable Coordinate Descent (SCD) というアルゴリズムを提案する。そうすることで分散させて1つのワーカーに割り当てる work load をある程度大きくすることが出来る。で、ブロックごとに更新しても収束するのか? という話だけど、パラメータの更新時にこれまでの値と更新後の値の間で line search してやると収束するらしい。なぜかは知らん(書いてない)。さらに、特徴次元をうまいことブロックに分割しれやれば、CDと全く同じ解が得られることも示した。

で、この SCD を Google Cloud 上に実装したらしい。論文中では実装時の細かいところの説明がされていた。この辺もさらっと書いてあるけどいろいろ試行錯誤して大変だったんだろなと思った。ポイントは、VM Preemptionがある環境を想定しているところなのかな? AWS の Spot instance とかがそれなんだけど、優先度が低いとみなされた VM(=worker) が勝手に強制終了されて、空いたリソースが別の優先度の高いVMに割り当てられてしまうという環境。

実際にGoogleが持ってる広告のデータを使って実装したらしい。サンプル数は1兆(!)で、特徴数は10億(!)のスケールのデータらしい。Google恐るべし。ちなみにこれはNetflix prizeの1万倍の規模らしい。結果はここでは省略するけどスケールしたとのこと。