Hadoop MapReduceで行列積を計算する（Introduction to Dense Matrix Multiplication with Hadoop MapReduce)

ビッグデータ BigData クラウド hadoop 統計学 statistics

前回までのログで、観測値（変量：m、サンプルサイズ：n）について、平均、分散、標準偏差を、mとnの両方についてスケーラブルなプログラムに落とし込むことができたように思う。

今回から数回に分けて、Hadoop MapReduceのパラダイムで行列積（Dense Matrix Multiplication）の計算を行うプログラムを作成する。

あれやこれやとテストをしていて、MapReduceには明確に「得意分野」と「不得意分野」があると感じている。
「一冊で分かるビッグデータ　日経BPムック（2012）」にあるNTTデータ猿田氏の言葉（p104）をかりれば

MapReduceに適しているのは、集計、検索や抽出、変換、分類といった処理です。これらすべての処理に共通していえることは、処理で使用する入力データは分割可能であることです、逆に分割して処理できるデータは、並列して処理できることを意味し、したがって、MapReduceによる処理に向いているといえます。
一方、MapReduceに適さないのは、分割できないデータです。分割できないデータというのは「全てのキーが一意である」というデータです。
・・・「一冊で分かるビッグデータ：日経BPムック（2012）」より引用。

ということになり、これがまさにMapReduceの本質であると思う。

MapReduceが、大規模データ分析の「切り札」的な扱いを受けている現実に対して、統計学的な分析・解析の側面からみると、たとえば、「相関分析」はMapReduce（のみ）でできるのか？とか、できるとすれば、どう実装して、どの程度のクラスタで実行すれば（手持ちの）データが（リーズナブルな実行時間で）分析できるのか？ということは、非常に興味がある話題なのであるが、突っ込んだ議論は見かけない。

さらに、歩を進めれば、多変量解析を使う際などを想定して、線形代数における基本演算をどの程度までMapReduceパラダイムに落とし込むべきか（もしくはできるのか）、ということも非常に重要な問題である。

これらの問いに対して、ある程度納得のいく回答をしなければ、MapReduceも一時のブームで終わってしまうかもしれない。

これらの課題に対して、１つの実証を与えたいというのが、MapReduceに関する一連のログの趣旨である。特に、今回から数回にわたって「巨大な行列積」を計算するプログラムを提示する。行列積は、線形代数の基本演算である。
しかしながら、行列の乗算をC=ABと表現したとき、Aは列について分割不可能であり、Bは行について分割不可能であって、MapReduceが本来得意とする演算ではないと思われる。

例えば、共分散（下）を算出する際には、インデックスi,jのすべての組み合わせについて、以下の演算を行わなければならない。

このような表現（Summation Form）に対して、以下のように、観測値をベクトルで記述すると、共分散の計算（正確には、積和の計算）は非常にシンプルに表現できる。

ただし、

とする。上付きのTは転置を表す。

ここで、以下のベクトルを定義する。

すると、X間、XとY間の積和は以下のように、行列積の形式ですっきり表現することができる。なお、データマイニングにおいてよく用いられる相関行列は、この行列を中心に表現される。
相関分析や多変量解析の分野において、統計学者（広く数学者）は、上記のようなMatrixフォームで、分析手法を定式化し、解を得るのが一般的である（ことは、利用局面において非常に重要である）。

簡単な調査

「車輪を２度発明するな」の言葉に従って、インターネット上で探せる範囲で、行列積（Dence Matrix Multiplication）の演算手法について調べてみた。

まず、著名なApache Mahoutに実装されている（OSSなのでソースコードを見る事ができる）ことが確認できる。
ただし、全般的には否定的な見解が多いように感じられた。

注記；Apache Mahoutの協調フィルタリングの実装には、Pearson相関係数によるSimilarity（類似度）計算が含まれている。ユーザープリファレンスの相関を計算するロジックは、行列積を計算するものに近いため、Mahoutを紐解くのもよいかもしれない。
追記；2013/7/19
「Mahout イン アクション」を読んだ限りでは、Mahoutの協調フィルタリングでMapReduceを用いるケースでは、疎な行列の積についてのアルゴリズムを実装しているようだ。ただし、本が少し古いので、新しい実装があるかもしれない。

上に「否定的な見解」と書いたが、以下のスレッドが参考になるかと思う。

最初のBlog記事は比較的新しいもの（2013/3）で、Mahoutで行列積の演算をすると、Mapperが１つしか起動しないので、部分行列に分解して計算させた（ロジックは不明）、と書かれている。２番目のスレッドも、Mapper数が１であることを問題にしている（が、回答は適切ではない=>ソースコードと３番目のブログを参照。MatrixMultiplicationJobが、CompositeOnputFormatを使っているところが問題である）。

他方、これらの否定的な見方に対して、提案もされている。
それらの中で、一番アピアランスが高いのが、HAMAというアプリケーションに関するもので、それに関しては論文が発表されている。
「HAMA: An Efficient Matrix Computation with the MapReduce Framework(2010)」

論文にあるように、HAMAはApache Incubatorに確かに存在する（http://hama.apache.org）のだが、論文の内容とは方向性を変えているような雰囲気がある（BSPという同期演算の方法論に重点が移っているように感じられる）。

また、以下のスレッドではなかり突っ込んだ議論がされていて興味深い。
grokbase: Matrix Multiplication in Hadoop:

この中に、John Norstadという人がかいた文書へのリンクが記載されている。
A MapReduce Algorithm for Matrix Multiplication: Norstad, J. (2009)

論文の形式をとっているが、Introductionに書かれているようにMapReduceを学習するための考察と実装である。（Javaのソースコードが添付されているが残念ながら動作しなかった）

なお、これらの提案に共通しているのは、行列を部分行列に分解してMapReduceで計算する、ということである。


次回以降では、具体的に行列積を求めるプログラムを実装し、Amazon Elastic MapReduceにおいて実行速度などをテストする。