MapReduceできる10個のアルゴリズム

HadoopとMahoutにより、ビッグデータでも機械学習を行うことができます。Mahoutで実装されている手法は、全て分散処理できるアルゴリズムということになります。Mahoutで実装されているアルゴリズムは、ここに列挙されています。論文としても、2006年に「Map-Reduce for Machine Learning on Multicore」としていくつかのアルゴリズムが紹介されています。

そこで今回は、（何番煎じか分かりませんが自分の理解のためにも）この論文で紹介されているアルゴリズムと、どうやって分散処理するのかを簡単にメモしておきたいと思います。計算するべき統計量が、summation form（足し算で表現できる形）になっているかどうかが、重要なポイントです。なってない場合は、”うまく”MapReduceの形にバラす必要があります。

※例によって、間違いがあった場合は随時修正致しますのでご指摘下さい。


1. 局所重み付け線形回帰（Locally Weighted Linear Regression, LWLR）

  • mapperでサブデータの重み付き平方和（xxとxy）を計算しreducerで足す。（以前の記事を参考）
  • 重みが1の場合は通常の線形回帰になる。

2. ナイーブベイズ

  • ナイーブベイズには条件付き確率が必要なので、mapperではそれぞれの条件付き”頻度”を計算しreducerで足す。
    • #(x=k|y=1), #(x=k|y=0), #(y=1), #(y=0)（#は頻度）

3. ガウシアン判別分析（Gaussian Discriminative Analysis, GDA）

  • GDAに必要な4つのパラメータを分散計算する。
    • P(y), μ0, μ1, Σ

4. k-means

  • mapperで中心に割り付け＆中心までの距離の合計とサンプル数を計算、reducerで中心の更新を行う。
  • これを繰り返す。

5. ロジスティック回帰

  • ニュートンラフソン法で尤度を最大化する。
  • 更新に必要な部分をmapperで加法できるように計算し、reducerで合計して更新する。

6. ニューラルネットワーク

  • バックプロバゲーションをmapperで行い、部分的な傾きを計算する。
  • reducerでそれぞれの傾きを足し合わせ、重みを更新する。

7. 主成分分析（Principal Components Analysis, PCA）

  • 共分散行列が求まれば良く、共分散行列はsummation formになっている。

8. 独立成分分析（Independent Component Analysis, ICA）


9. EMアルゴリズム（Expectation Maximization, EM）

  • Eステップ、Mステップで推定するそれぞれのパラメータをうまくmapperとreducerにバラす
  • EステップのMapReduce、MステップのMapReduceを繰り返す

10. サポートベクターマシン（Support Vector Machine, SVM）

  • 線形SVMの2次損失関数の場合、ある方程式を解くことで最適化ができる
    • 部分的な傾きをmapperで計算しreducerで足す。これによって重みのwを更新する。

以上です。こうやって見るとsummation formになっていない場合は最尤法を使い、（傾きによる）尤度の更新を1回のMapReduceで行なっているようです。またEMアルゴリズムというとても汎用的な手法がMapReduceできるということで、多くの手法が分散処理できるということが分かります。しかし実際にはそれぞれのEMをMapReduceに分解しなくてはならないので、実装はかなり大変そうです。また毎回のパラメータ更新をMapReduceしなくてはならないので、結構な時間もかかりそうです。

ページTOPへ