機械学習 × MapReduce

研究

個人的な興味というより，雑用絡みで眺めた論文の紹介．機械学習アルゴリズムを並列分散化するという話が最近流行っているようだ．全然網羅的ではないけど，誰かの役に立つかも知れないので，幾つかメモしておく．まず古典的にはこれ，

古典的な機械学習アルゴリズム（バッチ学習）の多くは，Statistical Query Model で記述できて，それらは summation form で記述できる (から，MapReduce で並列化できる)．実装は Mahout．ただ最近は，バッチアルゴリズムで解ける問題には多くの場合対応するオンラインアルゴリズムが提案されていて，バッチアルゴリズムを並列化することのメリットはあまり無い．オンラインアルゴリズムだとパラメタが連続的に更新されるので，MapReduce との相性が非常に悪かった．この辺りの議論をもう少し知りたい人は，

の p152 (manuscript) 辺りを読むと良い．
そこで最近，(maxent で) データを分割して独立して学習して得たパラメタを重み付き線形和などでまとめてもいいし，(perceptron なら) 各繰り返しごとに averaging すれば良いよという話が (parameter mixing; 収束証明付き) で出てきた．

これならオンライン学習も MapReduce と組合せられる（というか二つ目はオンライン学習）．
さらに，機械学習のような，同一データを入力として繰り返し計算するようなアルゴリズムのための MapReduce の拡張モデルも提案されている．最初の二本はデータはメモリに置く．最後の一本は Mapper/Reducer でデータの一部が再利用される場合や，ハードウェア故障等も想定してもうちょっとカッチリしたモデルを提案している（以上，1分斜め読み）．

機械学習的に面白いのは，MapReduce で本質的に扱えない問題 (局所的なデータに対する計算に分割できない問題) に挑戦している以下の論文．二章辺りを読むと，機械学習的な視点からの high-level な並列化モデルの流れが分かる．

また，Hadoop にもう一段 layer を加えて 機械学習アルゴリズム用の API を充実させるという話（注: 発表のみなので概要読んだだけ）もある．

同じ Workshop で Vowpal Wabbit の Langford が SGD の並列化について発表している．これはやや low-level の議論だが，データを分割する代わりに素性集合を分割するアプローチ (Feature Sharding; ある種の bagging 的な気分か)．Langford のブログも合せて読むと良い．彼が言うように，遅い学習アルゴリズム（多くのバッチ学習）を今さら並列化するというのはあまり意味がないと思う．

あと並列化できていないのは何が残っているのか．Michael Jordan が講義で言っていた内容？をまとめた人がいたのでリンクを張っておく．

あまりみんなちゃんと議論してないけど，実際に機械学習を使って実問題を解くときは，素性抽出の方が結局重かったりするので，どうせやるならそこも並列化してやらないと本末転倒だと思う．
[追記] 斜め読み以下なので取扱注意．しかし，これだけ色々な学会で発表されるほど流行るとフォローするのも大変だろうな．個人的には，人がわんさか集まってるトピックだと，自分がちょっと考えて思いつくようなことは既に他のグループも並列してやっていることが多いので，われ先に，とやらないと新規性がすぐ無くなってしまうのであんまりやる気がしない．
今後の展開を予測して最初の一手をつけるか（大抵，その最初の一手で問題の最も面白く重要な部分は解けてしまう），人が寄り付かなくなった砂漠で（出るか分からない水を求めて）井戸を掘るような仕事の方が好みだ．