線形単回帰をmap reduce風に分散処理して計算する
巷では何かと分散処理が流行っています。
特にHadoop＋Mahoutで大規模データに対して機械学習や統計モデルを高速分散処理することで、データマイニングがより盛んになるのではないかと期待がされています。
分散処理するためには、最後に足し合わせることができればいいわけで、考えてみるとそんなに難しいことじゃないんですよね。
試しにRを使って、線形単回帰を分散処理っぽく計算します。
大規模データで試しているじゃないですし、パフォーマンスを比較しているわけではありませんのであしからず、、
結局、分散処理は
- データを分割
- それぞれのデータでパラメータ計算
- 計算結果を足す
の3つをやっているだけだと、私は理解しています。
ですので、その3つの手順をRで100サンプル発生させて書いてみます。
まずは全体データで回帰係数を計算。
set.seed(1) x <- rnorm(100) set.seed(2) y <- 2*x + rnorm(100) #------全体での計算 lm(y ~ x - 1) sum(y * x) / sum(x^2) > [1] 1.800222
次にHadoop＋Mahoutっぽく分散処理します。
#---------分散処理 #------1.データ分割＆2.パラメータ計算 #---data1 x_sub1 <- x[1:50] y_sub1 <- y[1:50] ss_xy_sub1 <- sum(y_sub1 * x_sub1) ss_xx_sub1 <- sum(x_sub1 * x_sub1) #---data2 x_sub2 <- x[51:100] y_sub2 <- y[51:100] ss_xy_sub2 <- sum(y_sub2 * x_sub2) ss_xx_sub2 <- sum(x_sub2 * x_sub2) #---3.併合 (ss_xy_sub1 + ss_xy_sub2) / (ss_xx_sub1 + ss_xx_sub2) > [1] 1.800222
全体のデータで計算したときと、分散処理したときの回帰係数が一致していることが分かります。
ここで肝となるのは、サブデータでは回帰係数まで計算せず平方和の計算で止めていることです。
今回参考にしたのはこの論文です（@doryokujin君の紹介）。
他の手法も、「足すことのできる」とこまで計算して最後にパラメータ推定するってのが基本ですね。
（Rで書いたら簡単ですが、これをJavaで書こうと思ったら面倒なのかな？）
ちなみに、サブデータで回帰係数まで計算して併合すると次のようになり、全体で計算したときと値がずれてしまうことが分かります。
coef1 <- lm(y_sub1 ~ x_sub1 - 1)$coefficients coef2 <- lm(y_sub2 ~ x_sub2 - 1)$coefficients (coef1 + coef2)/2 > x_sub1 > 1.841857
重回帰はベクトルが行列になるだけだし、一般化線形モデルもヘシアン行列を足せるみたい。
EMアルゴリズムも分散処理できるみたいだから、基本的に何でも計算できるようですね。
MCMCみたいにチェーンさせないといけない手法は厳しいかな？
