Factorizing Personalized Markov Chains for Next-Basket Recommendation (WWW 2010) 読んだ

Factorizing Personalized Markov Chains for Next-Basket Recommendation(pdf)

概要

「各ユーザが次に何を買うか」というタスクに対してマルコフ連鎖ベースの予測モデルを作る．
ユーザごとの遷移確率を計算するにはスパースなので行列分解と組み合わせてその問題を解消する．

問題

ユーザ $u$ の $t-1$ 回分の購買履歴 $B^u$ があるとして， $t$ 回目で何を買うかをあてる．また，一度の購買では複数の商品を購入している(これをバスケットと表現する)．

手法

まず1購買に複数商品があるので，真面目にやるとそれぞれのアイテムのあるなしを1/0で表すと $2^{|I|}*2^{|I|}$ 次元のマルコフ連鎖を考えなければならない．
なので，「商品が前回のバスケットに入っている時，次のバスケットに入っている確率」を考える．
遷移確率は数え上げで計算ができるし，ユーザごとの履歴に絞ればpersonalizeも可能(パラメータはテンソル $\mathcal{A}=|U|*|I|*|I|$ )．
でもこれはスパースすぎてうまくいかない．なのでこのテンソルを低次元分解した形を考えてその低次元行列を推定することを考える．
推定にはBPR(bayesian personalized ranking)というものを考える．つまり，買ったアイテム全てが買ってないアイテム全てよりも確率が高くなるように学習する(eq 23)．
学習は Figure 5 に擬似コード載ってるからこれ実装すればどうにかなる．