f:id:vasilyjp:20180927112657j:plain

こんにちは、エンジニアの中村(@tn1031)です。弊社のプロダクト「iQON」には「for You」というレコメンド機能が実装され、個々のユーザに毎日おすすめのファッションアイテムを届けています。

今回はこの「for You」に関連して、レコメンドを実現するアルゴリズムのひとつであるBayesian Personalized Ranking (BPR)を紹介したいと思います。

本記事ではひとつの手法に話題を絞りますが、一般的な協調フィルタリングやレコメンド自体について詳しく知りたい方は、こちらのNetflix Prizeで使われた手法のまとめがとても参考になります。

協調フィルタリングとBPR

行動ベースの協調フィルタリングではユーザ x アイテムの行列の行列分解(Matrix Factorization)を考えます。評価の行列を ${X}$ とします。行のインデックス ${u}$ と列のインデックス ${i}$ がそれぞれ1人のユーザ、1個のアイテムと対応しており、行列の ${ui}$ 成分の値 ${x_{ui}}$ はユーザ ${u}$ がアイテム ${i}$ に対して下した評価です。ファクターの個数を与えた時、評価の行列 ${X}$ をユーザ x ファクター行列 ${W}$ とアイテム x ファクター行列 ${H}$ の積に分解します。

f:id:vasilyjp:20160630181055p:plain

f:id:vasilyjp:20160630191000j:plain

これを解く為の手法は様々ありますが、有名なものといえばspark.mllibにも実装されているAlternating Least Squares (ALS)やトピックモデルが一番最初に思い浮かびます。

ALSは観測されたデータと予測した評価値の2乗誤差を最小にするような行列分解を与える手法であり、トピックモデルは観測されたデータの背後に確率分布を仮定し、分布のパラメータを求める事で行列分解を行います。

BPRも行列分解を与える部分は同じですが、上記の手法とは異なるアプローチをとります。そもそもPersonalized Rankingは、ユーザごとの趣味趣向をランキングとして学習します。アイテムリストをユーザの好みでソートしたリストは、結果としてそのユーザに対するレコメンドになっているということです。BPRはPersonalized Rankingを解くための枠組みであり、今回紹介するのはこの手法を行列分解に適用した場合のアルゴリズムです。

BPRの詳細

ユーザ ${U}$ x アイテム ${I}$ の行列の行列分解の問題をBPRで解くことを考えます。はじめに扱うデータを定義します。続いてベイズ的アプローチによって問題を定式化し、パラメータの更新式を導出します。

データ

BPRで扱う学習データは以下のように表現します。

f:id:vasilyjp:20160630180814p:plain

${I}$ はすべてのアイテムの集合、 ${I_u^+}$ はユーザ ${u}$ が好む(評価が正の)アイテムの集合、 ${I \backslash I_u^+}$ は ${I}$ から ${I_u^+}$ を除いたものの集合です。したがって、 ${(u, i, j) \in D_S}$ の意味は、「ユーザ ${u}$ はアイテム ${j}$ よりアイテム ${i}$ を好む」となります。

${D_S}$ のサイズは ${U \times I \times I}$ になります。すべてのデータを学習に用いることは不可能なので、BPRでは学習データを与えられたデータからサンプリングします。

# sample a user
u = np.random.randint(userCount)
itemList = trainMatrix.getrowview(u).rows[0]
if len(itemList) == 0:
    continue

# sample a positive item
i = random.choice(itemList)

# sample a negative item
j = np.random.randint(itemCount)
while trainMatrix[u, j] != 0:
    j = np.random.randint(itemCount)

定式化

分解後の行列を ${W ( U \times k ) ,H ( I \times k )}$ (ただし、 ${k}$ はファクターの数)、ユーザ ${u}$ についての全アイテムの順序を ${\gt_u (\subset I^{2})}$ 、 ${i\gt_u j}$ と表記すれば「ユーザ ${u}$ はアイテム ${j}$ よりアイテム ${i}$ を好む」ことを表すとします。尤度関数は、

f:id:vasilyjp:20160630180711p:plain

と定義します。ここで、

f:id:vasilyjp:20160630180643p:plain

です。 ${U,V}$ の事前分布を ${E}$ を単位行列として

f:id:vasilyjp:20160630180422p:plain

で定義すると、事後確率最大化の式は以下で与えられます。

f:id:vasilyjp:20160630180531p:plain

この式を最大化する ${W,H}$ を求めることがBPRの目的となります。第1項で好きなアイテムに関する予測値とそうでないアイテムに関する予測値の差を大きくするように学習します。第2項、第3項は正則化項として機能します。

更新式

勾配法で ${W,H}$ を求めます。 ${\Theta=(W,H)}$ とおくと、 ${\alpha}$ を学習率として、

f:id:vasilyjp:20160630180905p:plain

となります。 ${\hat{x}_{uij}=W_uH_i^{T} - W_uH_j^{T}}$ として ${L}$ を代入すると、最終的に以下のようになります。

f:id:vasilyjp:20160701103911p:plain

ただし、

f:id:vasilyjp:20160701103954p:plain

です。

ここまでをコードに起こします。

# BPR update rules
y_pos = np.dot(W[u], H[i])  # target value of positive instance
y_neg = np.dot(W[u], H[j])  # target value of negative instance
exp_x = np.exp(-(y_pos-y_neg))
mult = -exp_x / (1.0 + exp_x)
        
for f in xrange(factors):
    grad_u = H[i, f] - H[j, f]
    W[u, f] -= lr * (mult * grad_u + reg * W[u, f])
                
    grad = U[u, f]
    H[i, f] -= lr * (mult * grad + reg * H[i, f])
    H[j, f] -= lr * (-mult * grad + reg * H[j, f])

アルゴリズム

データのサンプリングとパラメータの更新を収束するまで交互に繰り返します。

repeat
 1. (u,i,j)のサンプリング
 2. W,Hの更新
until convergence

コードの全量はGitHubに公開しておきます。なお、上記のコードをそのまま実行するとあまりに遅かったため、一部実装を見直しました。そのときの試行錯誤はQiitaに書いたのでよろしければご覧ください。

BPRの魅力

BPRの魅力は何と言っても計算コストです。 ${ |U|,|I|,|R|,k }$ をそれぞれユーザ数、アイテム数、評価の数、ファクターの数とすると、例えばALSは ${O((|U|+|I|)k^{3} + |R|k^{2})}$ 、速いものだと ${O((|U|+|I|)k^{2} + |R|k)}$ であるのに対し、BPRは ${O(|R|k)}$ で計算できます。