Apache Mahoutの分散次元縮約（Parallel ALS）を解説しよう。

ビッグデータ BigData mahout 機械学習 Machine Learning Hadoop MapReduce レコメンデーション 協調フィルタリング

さて、前回のログでは、Mahout 0.7に付属する「factorize-movielens-1M.sh」というサンプルをつかって、Pararell ALSというアルゴリズムを動かしてみた。
少し誉めすぎた感が否めないので、原論文「Large-scale Parallel Collaborative Filtering for the Netflix Prize」を解説しつつ、Mahoutでの実装を追いかけてみたい。

内容的には、理工系学部の専門過程の人あたりをターゲットに書いていく（自分は一サラリーマンであって、大学の先生ではないのだが、前提を書いておくのは重要だと思う）。

先のログにも書いたが、Parallel ALS(Parallel Alternating Leaset Squares)は、疎な行列（Sparse Matrix）を前提とした、次元縮約（dimension reduction）のための手法である。リコメンデーションを実装する場合、ユーザーとアイテムごとのレイティングを行列で表現することが多い。Movie Lensのサンプルでは、アイテムは「映画」であった。ちなみに、レイティングがデータとして与えられている場合を、Explicid Feedbackと呼び、他の指標が与えられている場合をImplicid Feedbackと呼ぶ。Mahoutでの実装は、この両方に対応しているようだが、以下ではExplicid Feedbackの場合を対象とする（上記の原論文がそのように書かれているため）。
一般的に、レイティングを表す行列は、「ユーザーは、一部のアイテムについてのみしか評価できない」という仮定のもとで、疎な行列となる。
（逆に言えば、上記の仮定が満たされない状態では、「リコメンデーション・エンジン」を使う意味がない）

Parallel ALSには以下の特徴がある。

  • ユーザー、もしくはアイテム単位に処理を行うことができるので、並列演算が可能である。
  • 特異値分解（Singular Value Decomposition）を用いない。
  • 疎な行列であれば、レコメンデーション（協調フィルタリング）以外の目的でも使用できる。
  • 大幅に次元を縮約してもリコメンデーション精度が下がらない（原論文、Movie Lensのサンプルからの経験的帰結）。その結果、処理が非常に高速になる。

自分が見る限りにおいて、大規模なリコメンデーションエンジンを実装するための、非常に有力な手法であるが、原論文を読む限りにおいて、（Mahout+Hadoop MapReduceでの実装を想定すると）すこしばかり気にかかる部分がある。以下では、その部分も含めて解説していきたい。

それでは、原論文からポイントを抜き出して見てみよう。

「Large-scale Parallel Collaborative Filtering for the Netflix Prize」の解説

定式化

まず、以下のようにいくつかの記号を定義する。

レーティングの行列（ユーザーが行、アイテムが列を表す）

次に、フィーチャー（features）という概念を導入して、以下の行列を定義する。

そして、このフィーチャーをつかって問題を定式化するが、その時に、以下の仮定をおく。ここで、はベクトルxとyの内積を表す。
これは、そのまま、RをU'Mに分解することを意味している。

上記の仮定をした際の損失関数（Loss Function）を以下とおく。

この損失関数は、MSE の形になっている。データより、以下をもって実際の損失と定義する
。emp はempirical の略である。

そして、求めるべきU,M は損失関数を最小にするものである、と問題を定式化したものは以下となる。

ただし、U,M を求める際に、（Rが疎な行列であるため）オーバーフィットする可能性があるので、Tikhonov の制約をつけた式を満たすU、M を求める。

原論文によると、上の制約部分（右辺第２項）は、経験的に「ユーザー、アイテムそれぞれについての、与えられているレーティングの度数」を「重み」とするのが一番よいと述べられており、上式は、最終的に、以下のように書き直される。

注記：このため、ALS の後にWR（weighted lambda regularization）をつけて、ALS −WR と呼ばれることがある。

Parallel ALSは、この（A）式を最小化する問題として定式化される。

基本ロジック（アルゴリズム）

(A)式には、U、M、λとたくさんの未知のパラメータが存在するが、これらをどのように求めるのだろうか？
結論から言うと、以下に示す典型的なEM アルゴリズムによって、U、M の最適化を行う。

  • step1 : M を初期化する。このとき、第１行目は各アイテムのレートの平均。２行目以降は、小さな乱数をセットする。
  • step2 : M を固定して、 U について損失関数を最小化する。
  • step3 : U を固定して、 M について損失関数を最小化する。
  • step4 : 終了条件を満たすまで、 step2 と step3 を繰り返す。

上記のプロセスでは、λを固定しておき、λはシミュレーションによって最適値を決定する。

計算モデル

具体的に、(A)式をもとにして、基本ロジックを実行するための計算式を導く。
step2 における最適化については、 f(U,M) を u の要素について偏微分し、最終的に以下の式を得る。

step3 における最適化は、 step2 と全く対称となり、最終的に以下の式を得る。

step4 では、( B) 式、( C) 式から求められた U,M を用いて、( A) 式を評価し、一定の基準以下に収束するまで、 step2、 step3 を繰り返す。

注記；原論文では、0 .0001 を基準とおいている。

以上が、原論文で述べられているアルゴリズムである。ここで
step2 ではユーザー、step3 ではアイテム単位で計算を行うことと、(B) 式、(C) 式ともに計算対象となるユー
ザー、アイテムにdepend していることが重要である。この性質から、処理の並列化が可能となる。
ところで、(B) 式、(C) 式には、密な行列の逆行列の演算が含まれている。
以前のログで、対規模な密な行列積についてMapReduce で処理するプログラムと、相関行列を求めるプロ
グラミングをした。
逆行列の演算にも、いろいろなやり方があるが、MapReduce で並列演算を行うのは簡単ではないと思われる。
Mahout ではどのようにおこなわれているのだろうか？
原論文については、これ以上記載しないが、λの値についてはシミュレーションにて、0.065 と決定している
。MovieLens のサンプルでこの数字が用いられているのは、論文から引用したものと推測される。


Mahoutでの実装

原論文のロジックはMATLABで実装されてシミュレーションや評価が行われている。Mahoutに実装されているということは、MapReduceで実装されている、ということを意味する。

まず、「factorize-movielens-1M.sh」を見てみよう。Parallel ALSを実行しているのは以下の部分である。ここで指定している主要なパラメータは、フィーチャー数=20、最大繰り返し数=10、λ=0.065である。上の原論文の基本ロジックでは、繰り返し計算が収束したら計算を終わりにする、という部分があったが、このしきい値を指定していない。

$MAHOUT parallelALS --input ${WORK_DIR}/dataset/trainingSet/ --output ${WORK_DIR
}/als/out \
    --tempDir ${WORK_DIR}/als/tmp --numFeatures 20 --numIterations 10 --lambda 0.065


以下に、ジョブの主要な呼び出し関係を示すが、コントローラーであるorg.apahce.mahout.cf.taste.hadoop.als.ParalleALSFactorizationJob.javaには、「収束を計る」という処理が実装されておらず、指定した最大繰り返し数だけ近似計算を繰り返して処理を終えるようになっている。
最適化計算で、「収束を計らない」というのはしっくりこない。



MahoutのJobのコードは、あっちこっち行って読みにくいのだが、上記の「収束」以外では、(B)、(C)式に出てくる逆行列の演算をガウス消去（１次の連立方程式を解くやり方）で行っているのが興味深い。

ユーザー、アイテム単位に繰り返されるEMアルゴリズムの部分は、スケールアウトできるようにコードされているから、ボトルネックになるとすれば、この部分かもしれない。
(B)式をみると、逆行列の計算は、フィーチャーの次元で行われるので、サンプルプログラムのように20次元程度であれば、ガウス消去（スケールしないアルゴリズム）でも問題ないだろうが、次元数を増やした場合（原論文にあるように、1000のオーダーにした場合など）ではボトルネックになるかもしれない。

いずれにせよ、この方法で大幅な次元縮約が可能であって、RMSEも1以下の数字に収まるのであるから、リコメンデーションのアルゴリズムとして有力な方法であることに変わりはない。


今年の夏はずいぶんと気合いをいれてやってしまった。面白い領域に巡り会ったので、このペースが維持できればいいのだけど。。。。