Matrix Factorization:Pythonでのチュートリアルと実装

Matrix Factorization:Pythonでのチュートリアルと実装

こんにちは!エンジョンワークス 機械学習エンジニアのshunです!

今日はレコメンド世界で有名なMatrix Factorizationを見ていきましょう!最後にフルスクラッチでアルゴリズムを実装します。

Webの世界が、情報過多なのは言うまでもないですね。そんな時、私たちは検索エンジンの助けを借ります。さらに便利なのは、頼みもしなく自動的にコンテンツを薦めてくれる、レコメンドシステムの存在です。Amazonのパーソナライズは、もうすっかりおなじみですね。

レコメンド アルゴリズムは、ユーザーベースまたはアイテムベースの協調フィルタリングが非常にシンプルで直感的ですが、今回はMatrix Factorizationを実装していきます。(Matrix Factorizationの日本語訳は行列因子分解)

行列因子分解から分かる通り、マトリックス(行列)を分解して、ユーザーとアイテム間の潜在的な特徴を発見するための手法です。Matrix Factorization自体、レコメンドのアルゴリズムではなく、あくまでデータ構造を再構築数することにより、未知の特徴に対して予測値を出す手法です。

基本的な考え方

行列因子分解はその名前が示唆するように、マトリックスを因数分解することです。これは別名、次元削減とも言います。簡単なイメージとして、分解したマトリックスを再度乗算することにより、元のマトリックスの値を近似するということです。

これにより2種類の特徴間(図の場合だとUserとItem)にある潜在的な特徴を発見します。この特徴を潜在因子(latent factor)と言います。既知の評価値から潜在因子を学習するということです。つまり、データ間の隠れた特徴を予測するということですね。

簡単な例を映画のレコメンドで見ていきましょう。ユーザーとアイテムのデータセットがあり、評価値が1~5の整数であると仮定します。マトリックスは次のようになります。(ハイフン(-)は、ユーザーがまだ映画を評価していないことを意味します)。

つまりこのハイフン(-)を予測するのが、今回のアルゴリズムとなるわけです。

例えば2人のユーザーが、同じ映画の俳優/女優が好きで、ジャンルがアクション映画である場合、ある特定の映画に高い評価を与えるはずです。これらの潜在的な特徴を発見できれば、特定のユーザーと特定のアイテムにある、関係性を予測できるはずです。ユーザーに関連付けられている特徴は、アイテムに関連付けられている特徴と一致するはずです。

レコメンドを考える場合、全てのユーザーが全てのアイテムを評価していることは、ほぼありません。逆に評価していたら、そもそもレコメンドは必要ないですね。

Matrix Factorizationの数学的根拠

では、Matrix Factorizationの数学的な根拠を見ていきましょう。まず、ユーザーのセットUと、アイテムのセットDがあるとします。| U | *  | D |Rがユーザーがアイテムに割り当てた、評価を含むマトリックスとします。U*Dの行列Rを、U*kの行列Pk*Dの行列Qに分解します。kU,Dよりも小さな値が使われます。これらの積から Rの近似を算出します。

このようにして、Pの各行は、ユーザーの特徴を重みとして表します。同様に、Qの各行はアイテムとの特徴を重みとして表します。 次に予測値を得るために、ユーザーの特徴uiとアイテムの特徴djのベクトルの内積を計算します。


ここで、PQを算出する方法を見つける必要があります。最初に、ランダムな値で2つの行列を初期化し、Mとの誤差を繰り返し計算しながら、誤差を最小化することです。この方法を勾配降下法と言います。これは有名な、誤差の極小値を見つけるためのアルゴリズです。機械学習を勉強したことがあれば、聞いたことあると思います。

推定評価と実際の評価の誤差は次の式で計算します。いわゆる損失関数ですね。

推定評価が実際の評価よりマイナイスの場合もあるので、二乗誤差を取ります。

エラーを最小限にするためには、pikqkjの値を、どの方向に増減するか知る必要があります。つまり、偏微分をして増減するための勾配(傾き)を求めます。

ここで、αはその値が最小値に近づく割合を決定する定数です。いわゆる学習率です。一般的に、αには小さな値、たとえば0.0002を選択します。これは、学習率を大きくしすぎると、最小値を飛び越えてしまう可能性があるからです。

ここで疑問が浮かぶかもしれません。2つの行列PQからRを近似する場合、未評価の予測値がすべてゼロになるということはないですか?しかし実際には、Rを完璧に再現できるようなPQを計算しようとしていません。オリジナルのマトリックスとのエラーを最小化しようとします。つまりP,Qが学習データセットです。未知数については、ユーザー(P)、アイテム(Q)、特徴間の関連付けが学習されると、自ずと値を決定できるようになります。

以上のアルゴリズムを使用して、エラー(誤差)が最小に収束するまで処理を繰り返します。次の式を使用して計算されたエラーを確認し、処理をいつ停止するか決めます。

正則化

以上、行列を分解するための基本的なアルゴリズムです。もっと高度なトピックとして、例えば、過学習を避けるために正則化を導入することです。これは、パラメーターβを追加し、次のように2乗誤差を修正します。

言い換えると、新しいパラメーターβを使用して、PQの値が大きくなりすぎることなくRに適切な近似を与えるように、ユーザーベクトルとアイテムベクトルの大きさを制御します。一般的に、βは0.02の範囲の値に設定されます。この二乗誤差のアルゴリズムは次のとおりです。

Pythonでの実装

数学的な根拠が理解できれば、アルゴリズムを実装するのは非常に簡単です。以下は、Pythonでのアルゴリズムの実装です。(numpyが必要)。

import numpy

def matrix_factorization(R, P, Q, K, steps=5000, alpha=0.0002, beta=0.02):
    Q = Q.T
    for step in xrange(steps):
        for i in xrange(len(R)):
            for j in xrange(len(R[i])):
                if R[i][j] > 0:
                    eij = R[i][j] - numpy.dot(P[i,:],Q[:,j])
                    for k in xrange(K):
                        P[i][k] = P[i][k] + alpha * (2 * eij * Q[k][j] - beta * P[i][k])
                        Q[k][j] = Q[k][j] + alpha * (2 * eij * P[i][k] - beta * Q[k][j])
        eR = numpy.dot(P,Q)
        e = 0
        for i in xrange(len(R)):
            for j in xrange(len(R[i])):
                if R[i][j] > 0:
                    e = e + pow(R[i][j] - numpy.dot(P[i,:],Q[:,j]), 2)
                    for k in xrange(K):
                        e = e + (beta/2) * (pow(P[i][k],2) + pow(Q[k][j],2))
        if e < 0.001:
            break
    return P, Q.T

R = [
     [5,3,0,1],
     [4,0,0,1],
     [1,1,0,5],
     [1,0,0,4],
     [0,1,5,4],
    ]

R = numpy.array(R)

N = len(R)
M = len(R[0])
K = 2

P = numpy.random.rand(N,K)
Q = numpy.random.rand(M,K)

nP, nQ = matrix_factorization(R, P, Q, K)
nR = numpy.dot(nP, nQ.T)

上記のアルゴリズムから取得したマトリックスは次のようになります。

元のマトリックスに、非常に近い評価になってますね。ハイフンだった値の予測値も得られたことがわかります。U1U2の趣向が似ており、両方ともD1D2が高く評価しています。残りのユーザーはD3、D4を好んでいますね。特徴量の数(PythonコードではK)が2の場合、アルゴリズムはユーザーとアイテムの、それぞれに2つの特徴を生成し、予測値はKから計算されます。たとえば、U4U5の両方がD4を高く評価したため、D3でのU4の予測評価は4.59であることがわかります。

以上、Matrix Factorizationの直感的な意味と数学的根拠、協調フィルタリングでの使用例について説明でした。

エンジョイワークスではバックエンドエンジニアを募集しております。空き家問題を自分のスキルで解決したいエンジニアは是非ご応募ください!

リクルート情報はこちら!
https://enjoyworks.jp/recruit

一覧へ戻る

最新記事