Machine Learning Advent Calendarです。
普段はGunosyという会社で推薦システムを作ってます
はじめに
推薦システムに関する最近の文献を読むと結構な割合で出てくるMatrix Factorizartion(MF)と呼ばれる手法があります。
ざっくり言うとこの手法は協調フィルタリングにおける次元削減を行うことでよりよい推薦を行おうという手法であり、
Netflix Prize(100万ドルの賞金が賭けられた推薦システムのコンテスト)で最も成果を上げたモデルの一つでもあります。
本記事ではこの手法を紹介していきます。
協調フィルタリング
まず協調フィルタリングについておさらいしましょう。
あるサービスで3人のユーザが５つのアイテムに対して5段階評価をしたとき、その評価値を以下のようにベクトルで表すことができます。
\vec{user_{1}} = (4, 5, 0, 1, 0)^T \\
\vec{user_{2}} = (3, 0, 1, 5, 0)^T \\
\vec{user_{3}} = (4, 0, 0, 3, 5)^T \\
一つ目の要素が$ item_1$の評価であり、同じ次元の要素は同じアイテムにたいする評価を表します。
このとき$user_2$に近いのは$user_1$と$user_3$のどちらでしょうか？
このような多次元空間のベクトル同士がどれだけ似ているかを測る指標は様々にありますが今回はコサイン類似度を用いることにしましょう。
コサイン類似度の定義は以下に示します。
\cos( \vec{p}, \vec{q}) = \frac{\vec{p} \cdot \vec{q}}{|\vec{p}||\vec{q}|} \\
pythonのscipyパッケージを用いてこれを計算しましょう
>>> from scipy.spatial.distance import cosine
>>> import np
>>> user1 = numpy.array([4,5,0,1,0])
>>> user2 = numpy.array([3,0,1,5,0])
>>> user3 = numpy.array([4,0,0,3,5])
>>> cosine(user1, user2)
0.55660554868629408
>>> cosine(user2, user3)
0.35457655095942753
scipy.spatial.distance.cosineは距離を返す関数になっているので, 先ほど定義した値と違い$1- \cos$を返します。
なので値が小さいほど近くなるため, $user_1$より$user_3$のほうが$user_2$に似ていることになります。
なので$user_3$が評価していて$user_2$がまだ評価していない$item_5$を推薦すればいいのではないか、といった形になります。
なぜ次元削減をするのか？
Matrix Factorizationは協調フィルタリングにおいて次元削減を実現する手法です。
ではなぜ次元削減が必要なのでしょうか？
先ほど示したユーザ3人、アイテム5つの例ではうまくいっているように見えます。
しかしこれはアイテムもユーザも少ないからです。実際のサービスを考えればアイテムは何万、何十万とあります。
それだけ次元が増えてしまうと機械学習では問題をうまく扱うのが困難になります。
これは次元の呪いと呼ばれる問題です。
そのためこのような高次元のデータを扱うために、高次元データの特徴をできるだけ保持したままデータを低次元データに変換するという対応がしばしば行われます。これが次元削減です。
Matrix Factorizationとは？
$m$人のユーザと$n$個のアイテムを考えます。
先ほどの例では、ユーザは$n$次元のベクトルで表現されることになりますが、これを$m > k > 0$である$k$次元に次元削減して変換することを目指します。
これは評価値を表す$ m \times n $の行列$R$に対して
これをユーザ要素を表す$k \times m$の行列$P$と$k \times n$の行列$Q$を考え以下のように近似します
R \approx P^TQ
図で表すと以下のような形になります。
ここでユーザ$u$が評価したアイテム$i$の評価値は $\vec{p_{u}}^T\vec{q_{i}}$として表現することができます。
この各ユーザ、各アイテムに対する$\vec{p_u}$、$\vec{q_i}$を既知の評価値から学習するのがMatrix Factorizationです。
以下の式を満たすP, Qを訓練データから導きます
min_{P, Q} \sum_{(u, v) \in R} (r_{u,v} - \vec{p_u}^T\vec{q_i})^2 + \lambda ( ||\vec{p_u}||^{2}_{F} + ||\vec{q_i}||^{2}_{F} )
上の式を最適化するための更新式は以下のように求められることが知られています
e_{u, v} = r_{u, v} - \vec{p_u}^T \vec{q_i} \\
p`_{u,k} = p_{u, k} + 2 * \alpha e_{u, v} q_{k, v} \\
q`_{v,k} = q_{v, k} + 2 * \alpha e_{u, v} q_{u, k} \\
なおこの近似式はNetflix Prize参加者のSimon Funkという人が提案したものなのですが、
普通にブログに投稿されてて、それが論文とかに引用されててなんかすごいです。
当時Netflix Prizeでは彼が公開したアルゴリズムを実装するところがまず入門編だったと言われています。
なぜMatrix Factorizationを用いるか？
次元削減をする方法としてはSVD(Singular Value Decomposition)と呼ばれる手法が広く知られており、情報検索などの分野で活用されています。
しかし推薦システムに適用した場合、通常の協調フィルタリングのモデルに比べて大きな改善はあまり起こらず、むしろ悪くなるケースもあることが報告されています。
これは次元削減の対象となる推薦システムの評価値行列の特性と関係があります。
推薦システムの評価値における0は一般的には「評価値が0」だったわけではなく「評価していない」ことを表す値です。
なのでその0という情報を保存しながら次元削減を行うと推薦の最適化にはあまり有効ではない形で変換されてしまうことになります
そのため、値があるところのみで最適化していくMatrix Factorizationが推薦システムには有効であるとされています。
実際にやってみた
import numpy
def get_rating_error(r, p, q):
return r - numpy.dot(p, q)
def get_error(R, P, Q, beta):
error = 0.0
for i in xrange(len(R)):
for j in xrange(len(R[i])):
if R[i][j] == 0:
continue
error += pow(get_rating_error(R[i][j], P[:,i], Q[:,j]), 2)
error += beta/2.0 * (numpy.linalg.norm(P) + numpy.linalg.norm(Q))
return error
def matrix_factorization(R, K, steps=5000, alpha=0.0002, beta=0.02, threshold=0.001):
P = numpy.random.rand(K, len(R))
Q = numpy.random.rand(K, len(R[0]))
for step in xrange(steps):
for i in xrange(len(R)):
for j in xrange(len(R[i])):
if R[i][j] == 0:
continue
err = get_rating_error(R[i][j], P[:, i], Q[:, j])
for k in xrange(K):
P[k][i] += alpha * (2 * err * Q[k][j])
Q[k][j] += alpha * (2 * err * P[k][i])
error = get_error(R, P, Q, beta)
if error < threshold:
break
return P, Q
R = numpy.array([
[5, 3, 0, 1],
[4, 0, 0, 1],
[1, 1, 0, 5],
[1, 0, 0, 4],
[0, 1, 5, 4],
]
)
nP, nQ = matrix_factorization(R, 2)
nR = numpy.dot(nP.T, nQ)
>>> nR
[[ 5.01206098 2.96974291 3.86684235 0.99604183]
[ 3.9862704 2.37235361 3.27696605 0.99620086]
[ 1.05492795 0.86913835 5.53828733 4.99229311]
[ 0.97312539 0.77030044 4.5002216 3.98906219]
[ 1.63962431 1.16127693 4.93822412 4.04436897]]
すでに値が入っているところは近似された値に、
0だったところには予測値が入っていますね！
蛇足
日本語でMarix Factorizationちゃんと説明したウェブのってあんまりないなーと思って自分で調べるついでに書いてみました。
でもKDD Cup07ぐらいのときはまだRegular-SVDとか呼ばれてていつの間にMatrix Factorizationなんて名前ついたんでしょう。結構謎。
SVDが効かなかったみたいなくだりはなるほどなーという感じでした。
ただSVDだったり、Random-Walkだったり次元削減だったりスパース対策だったりいろいろ手法はあるけど、比較してる文献ってあんまりなさそうな感じでした。知ってたらだれか教えてください
最近はNMF(non-Negative Matrix Factorization)とかが主流なんでその辺もおいおい調べて紹介したいです
参考
-
Y.Koren, R.M. Bell and C.Volinsky, Matrix Faxctrization Techniques for Recommender Systems, Computer, 42(8):30-37, 2009.
-
Badru M. Sarwar, George Karpis, Joseph A. Konstan and John T. Riedl, Application of Dimensionality Redution in Recommender System — A Case Study, IN ACM Web KDD Workshop, 2000
-
A. Paterek, Improving Regularized Singular Value Decomposition for Collaborative Filtering, Proc. KDD Cup and Workshop, 2007