カエルでもわかる!Spark / MLlib でやってみる協調フィルタリング(前編)

はじめに

当ブログでは Apache Spark プロジェクトの機械学習ライブラリ MLlib について何度か取り上げました。

今回のエントリでは MLlib の協調フィルタリングについて書きます。 アルゴリズムの簡単な解説と Java からの利用方法、性能評価実験などの話をします。 Spark 1.1.0 が9月にリリースされてからしばらくたってしまいましたが、1.1.0 から実装された機能も紹介します。

少し長くなるので前・後編に分かれます。

以下では Spark 1.1.0 を想定しますが、このあたりは今も発展中であり、以降のバージョンではまた違う話になっている可能性が高いのでご注意ください。

MLlib における協調フィルタリング

協調フィルタリング

協調フィルタリングは(例えば EC サイト等の)推薦システムにおける推薦手法の1つです。 あるユーザに適切な商品を推薦するということは、各商品について、そのユーザが明示的に与える評価や閲覧・購買してくれそうな確度を予測する問題であるという見方ができます。

下の図の行列  R は各ユーザによる各商品の評価値を表します。 評価値はユーザによる☆×5の評価で1~5の数字が入っていると考えてください。 要は各ユーザの各商品への嗜好の度合いを表す情報です。 したがってユーザ数を  n_u 、商品数を  n_v としたとき  R  n_u \times n_v の行列となります。

現実的にユーザによって商品が評価されたり閲覧されたりするのはこの行列中でほんの一部です。 その一部の情報を元にすべてのユーザ/商品の組み合わせの評価値を予測し、あるユーザについて予測評価値の高い商品をユーザに推薦する、というのが協調フィルタリングです。1

rating

行例因子分解

協調フィルタリングの中にもいくつか手法がありますが、MLlib においては交互最小二乗法による行列因子分解による協調フィルタリングが実装されています。 行列因子分解(Matrix Factorization)とはなんでしょうか? Jannach et al., / 田中克己・角谷和俊監訳『情報推薦システム入門』(共立出版、2012)27頁によると、

大まかにいうと, 行列因子分解手法は推薦システムの潜在(隠れた)因子を評価値のパターンやユーザとアイテムの双方を因子のベクトルによって特徴付けるものである. (中略)アイテム i の推薦は対象ユーザとアイテム i が, これらの因子に関して類似しているということに基づいて行われる (Koren et al. 2009).

とのことです。 イメージしやすいように図示して考えてみましょう。

matrix_factorization

前述の  n_u \times n_v 評価値行列  R は行列因子分解の結果、  n_u \times n_f のユーザ特徴量行列  U  n_v \times n_f の商品特徴量行列  V に分解されます。 この特徴量が前述の潜在因子であり、通常は特徴量の数  n_f  n_f \ll n_u かつ  n_f \ll n_v となるように取ります。 したがって次元削減(dimension reduction)を行っていると言えます。

あるユーザに対するある商品の予測評価値は、この特徴量を介して求めることができます。 つまり  U からターゲットのユーザ  i に対応した1行を取り出した特徴量ベクトル  u_i と、  V から商品  j に対応した1行を取り出した特徴量ベクトル  v_j 、この2つのベクトルの類似度の高さで評価値を予測することができるわけです。

次元削減により  U および  V は疎性が小さくなっており(=行列中の値のない要素が少なくなっている)、それにより元の  R よりもユーザと商品を関連付けやすくなっています。

交互最小二乗法

ではその因子分解された行列  U および  V をどうやって得るのでしょうか。 この方法もいくつかあるようですが、MLlib で採用しているのが交互最小二乗法(ALS: Alternative Least Squares)です。2

 R は疎な行列ですが、実際にユーザ  i が商品  j を評価値  r_{ij} で評価していた場合、  U  V から予測されるユーザ  i の商品  j に対する予測評価値と実際の評価値  r_{ij} の誤差は小さい方が良いでしょう。 であれば適切な  U  V を求めるという問題は、すべての  i, j に対しての上記の誤差の二乗和を最小化する問題と考えることができます。

しかし、 U  V のすべてのパラメータを一度に見て誤差を最小化するのは問題が複雑すぎます。 そこで最適化するパラメータを、例えば  V の中のある商品  j についての行だけに限定して考えます。 そうすることにより問題は単純化され、この場合は線形の問題として扱えてしまいます。

当然これだけでは全体の最適化にはなりえませんが、この1回の試行により誤差は必ず小さくなります。 これをすべての商品、およびユーザについて繰り返し実行することにより、全体の誤差を極小化していくことが可能です。 これが交互最小二乗法です。 EM アルゴリズムとよく似ていますね。

MLlib におけるこのあたりの実装の元となっている Zhou et al.,(2008) では次のようなステップを提案しています。

  1.  V の最初の行をその商品の平均評価値で初期化。他の行は小さなランダム値で初期化します。
  2.  V は固定し、  U についてパラメータを動かして目的関数(誤差)を最小化します。
  3.  U は固定し、  V についてパラメータを動かして目的関数(誤差)を最小化します。
  4. 目的関数の値の変化が閾値以下になるまで 2, 3 を繰り返します。

分散処理の形をとりやすいのが他の行列因子分解手法に対する ALS のメリットだそうです。 正に Spark 向きですね。

ALS-WR

さて、元論文 Zhou et al.,(2008) の話を挙げましたが、この論文で提案され、かつ Spark 1.1.0 以降の MLlib で実装されているのは、実は純粋な ALS ではなく拡張された ALS-WR(ALS with Weighted λ Regularization)という手法です。 ALS とは何が違うのでしょうか?

学習データにあたる  R は疎な行列であることを思い出してください。 他方、  U  V はそれなりの量の行列要素を持つことになります。 何も考えずに  U  V を学習した場合、学習データ量に対してモデルパラメータの数が大きくなりすぎてしまい overfitting(過学習)が起こってしまうでしょう。

これを防ぐために Tikhonov の正則化法を誤差最小化の目的関数に取り入れたのが ALS-WR です。 (2014-11-05 追記: Tikhonov の正則化法はリッジ回帰等でも使われる考え方です。 誤差最適化関数に正則化項を追加し、モデルの複雑度を制限することにより overfitting を防ぐことができます。)

この正則化法を加味して提案された  U ,  V についての目的関数は以下のようなものです。

 f(U, V) = \sum_{(i,j) \in I} (r_{ij} - u_i^T v_j)^2 + \lambda \left( \sum_i n_{u_i} ||u_i||^2 + \sum_j n_{v_j} ||v_j||^2 \right)

ここで  I は既知の評価値を持つユーザ  i  j のすべての組み合わせであり、  n_{u_i}  n_{v_j} はそれぞれ特徴量ベクトル  u_i ,  v_j の中で 0 でない値を持つ要素の数です。

 U ,  V についてこの関数の値が小さくなる程良いわけです。 右辺の第1項は誤差の二乗和を表しています。

第2項が正則化のための項であり、第2項が正則化のための項であり、  \lambda の値が大きくなるほどにユーザまたは商品の特徴量ベクトルにおいて値を持つ要素の数を少なくするような働きがあります。2014-11-05 修正: 値を持つ要素の数は少なくなりません。 \lambda の値が大きくなるほどにユーザまたは商品の特徴量行列においてモデルの複雑度を下げ、したがって overfitting が妨げられ、頑健性を上げる働きがあります。) 一方で  \lambda を大きくしすぎるとモデルの表現力が落ちて予測精度が下がってしまいます。  \lambda はハイパーパラメータであり、実験的に適切な値を決めてやる必要があります。

その他、アルゴリズムについて

NMF

評価値が負の値をとらない場合、負にならないという制約を課して非負値行列因子分解(NMF: Nonnegative Matrix Factorization)を使用することが MLlib の協調フィルタリングでは可能です。 この制約により  U ,  V の特徴量にメリハリがつきやすくなるそうですが… 負にならない評価値を扱うのであれば指定した方が良さそうな雰囲気です。2014-11-05 修正: 評価実験の結果からすると必ずしもそうではない模様…というか NMF 指定してもあまり変化がないように見えます。)

暗黙的な嗜好データ

ここまでの説明ではユーザが意識して明示的にアイテムを評価して値を付与するという、明示的な嗜好データを例にして説明しました。 一方で商品ページの閲覧や購買など、ユーザが意識的に評価しているわけではなく、ユーザ行動の結果として嗜好を示すような暗黙的な嗜好データを推薦に使うこともあります。

Hu et al., (2008) によれば、暗黙的嗜好データを使う場合は最小化の目的関数において評価値(閲覧回数など)そのものではなく、それを変形することによって得られる嗜好の度合いとその信頼度を導入すると予測精度が改善する場合があるとのことです。 MLlib では Hu et al., (2008) の手法も実装されており、暗黙的な嗜好データであることを指定するとそちらの目的関数に切り替えることが可能となっています。

まとめ

  • MLlib に協調フィルタリングの実装がある
  • 協調フィルタリングの中でも行列因子分解という潜在因子を扱う手法を採用している
  • 行列因子分解を ALS-WR で実現している
  • 非負値行列因子分解や暗黙的嗜好データの扱いもある

長くなったのでここでいったん切ります。 アルゴリズムの話に終始してしまいましたが、後編では Java からの利用と性能評価実験について掲載したいと思います。

参考資料

  • Jannach et al., / 田中克己・角谷和俊監訳『情報推薦システム入門』(共立出版、2012)
  • Y. Zhou et al., “Large-Scale Parallel Collaborative Filtering for the Netflix Prize,” Proc. 4th Int’l Conf. Algorithmic Aspects in Information and Management, LNCS 5034, Springer, 2008, pp. 337-348
  • Y.F. Hu, Y. Koren, and C. Volinsky, “Collaborative Filtering for Implicit Feedback Datasets,” Proc. IEEE Int’l Conf. Data Mining (ICDM 08), IEEE CS Press, 2008, pp. 263-272.

  1. 「協調フィルタリング」という言葉には広義と狭義の意味があったりして人によって定義が違っていたりしますが、MLlib における協調フィルタリングはこのような理解で問題ありません。 

  2. ALS は協調フィルタリングを実施するクラスの名前 org.apache.spark.mllib.recommendation.ALS にもなっています。