Coda

論文メモ Random Walks in recommender Systems: Exact Computation and Simulations

April 18, 2020

概要

F. FoussらM. Goriらのランダムウォークによる推薦システムの先行研究を、質や計算量について比較した論文である。 比較対象には、著者らの用意したも含まれる。 実験には、MovieLensのデータセットが使われた。 F. Foussらの実験で使われた評価指標や上位kの推薦結果のヒット数で評価したところ、著者らの用意した単純な手法\(P^s\)やその拡張\(P_\alpha^s\)が質と計算量の両方で最も優れた結果を残した。

実験の設定

いずれの手法も、ユーザとアイテムの2部グラフ上でのランダムウォークをもとに、ユーザの好むアイテムを推薦する。 ユーザの集合を\(U\)、アイテムの集合を\(U\)とし、両者の要素間には\((u\in U, m \in I)\)で表記される関係\(R\)がある。 2部グラフ\(G\)は、\(U\)と\(I\)を頂点、\(R\)を辺としてユーザとアイテムの関係をモデル化する。

\(P^s\)

ユーザ\(u\)から\(s\)ステップのランダムウォークで到達するアイテムについての確率分布を\(P^s(u, .)\)とすると、\(P^s\)は\(P^s(u, .)\)の高さをもとにアイテムを推薦する。 \(G\)は2部グラフであるため、\(s\)は3以上の奇数である。 \(s=3,5\)で実験したところ、\(s=3\)のほうが優れていた。 \(P^s\)は、\(G\)の隣接行列\(A\)と頂点の次数の対角行列\(D\)より

$$ P^s = (D^{-1}A)^s $$ で求められる。 \(P_s^\alpha\)は、\(P\)の正の要素を\(\alpha\)乗した値\(P_\alpha\)の\(s\)乗である。 実験では、\(\alpha=1.9\)のときに最もよい結果となった。