Olukotun, NIPS-2006.
id:mamorukさんによる紹介。Multicore上でのMap-Reduceを機械学習でやる話。「SVMを並列でやれるようにしたよ(pSVMとかcascaded SVMとか)」とかそういうものではなく、Statistical Query modelという範疇にあるモデルのクラスでsummation form担っているものに対してMap-Reduceのフレームワークを適用できますよという論文。10個くらいのアルゴリズムに関して書いてある。実験では、コア数に比例するような形で線形にスピードを上げれていることが示されている。
- Multicoreではなく、Multi CPUでもいいんだけど、後者の場合転送速度が問題になることがある
- 近似ではなく、exactに計算する
線形回帰の例が最初に書いてあって、行列AとベクトルBはsummation formをしているからMap-Reduce回せますよね、というのが書いてある。自分としては「そこより逆行列が大変なんじゃないの」と思って質問したところ、Large Dataに対してどうこうというよりコア数に比例するということだけを示したいので問題ないということ。実験で使ってあるデータはNLPのように高次元なデータではなく100次元もないデータだったので、逆行列も計算可能なくらいのところのようだ。その後は、各アルゴリズムのどの部分がsummation formになっているかとかの説明がある。普通のベクトル、行列に対してだけではなく、勾配やヘッセ行列に対してもMap-Reduceなことができるようだ。
実験では、16コアくらいまでやられていて、大体線形になっていることが分かる。しかし、EMやk-meansのようなアルゴリズム(k-meansもEMでできると言えばできるが)は途中でデータのやり取りが必要になってくるので、他の例と比較するとオーバーヘッドになっている部分が結構あるようということが分かる。
計算量のオーダーも書いてあるけど、大規模データで実用に耐えそうなオーダーのものとしてはナイーブベイズ、ニューラルネットワーク、k-meansくらいである。また、紹介が終わってからちょっと話題になったが、オンラインアルゴリズムとMap-Reduceは相性がよろしくない...とあるが、例えばMapper側でデータをK分割、K個のロジステック回帰をオンラインで計算して、Reducer側で、そのパラメータの平均を取るみたいなことが考えられると思うんだけど、どうだろう。ただ、あんまりよいパラメータ出てこなさそうだし、意味がよく分からないですね。。。
