TrustWalker: a random walk model for combining trust-based and item-based recommendation(KDD 2009) 読んだ

TrustWalker: a random walk model for combining trust-based and item-based recommendation
タイトルに釣られて読んだ．内容がシンプルなだけでなく，いちいち添字を略す理由だのが書いてあり，非常に読みやすかった．

概要

協調フィルタリングでのコールドスタート問題（評価がほとんどないユーザにアイテムを推薦できない）に対応したい
新規ユーザであっても，他のユーザとの信頼関係のデータ（trust network）があれば対応できる
- しかしそのネットワークは離れるほど信頼性が薄くなるし近すぎると今度は対象アイテムが少ない
- このトレードオフを解決するランダムウォークを提案

notation

ユーザ $U=\{u_1,\cdots,u_N\}$ 及びアイテム $I=\{i_1\,\cdots,i_M\}$ について，ユーザ $u$ がアイテム $i$ について $r_{u,i}$ と評価した（大抵これは[1,5]の整数値である）アイテム集合 $RI=\{i_{u1},\cdots,i_{uk}\}$ がある．また，ユーザ $u$ がユーザ $v$ を信頼している状態を $t_{u,v}$ で表現するtrust networkもあるとする．以下では0/1で信頼している/していないとしているが，これは[0,1]の実数値で表現したとしても容易に拡張可能である．trust networkにおけるユーザ $u$ に対する隣接ユーザ（『信頼ユーザ』）集合を $TU_u=\{v \in U | t{u,v} = 1\}$ とする．
問題定義としては，ユーザ $u_0$ がまだ評価していないアイテム $i$ について評価 $r_{u_0,i}$ を予測する．

TrustWalker概要

アルゴリズムを簡単に書くとこうなる

からランダムウォークを開始し，k-ステップ目でユーザの場所にいるとする
- $u$ が $i$ を評価していたら $r_{u,i}$ を返してランダムウォーク終了
- 評価していなかったら
  - $\phi_{u,i,k}$ の確率で， $u$ が評価している， $i$ に似たアイテム $j$ を確率 $P(Y_{u,i} = j)$ で選び，その評価 $r_{u,j}$ を返してランダムウォーク終了
  - $1 - \phi_{u,i,k}$ の確率で， $u$ が信頼しているユーザ $v \in TU_u$ にランダムウォーク

協調フィルタリングとtrust networkをうまく組み合わせていて，なおかつわかりやすい．

詳細な数式

ランダムウォーク

ユーザ $u$ から $v$ にランダムウォークで移動する確率を
$P(S_u = v) = \frac{t_{u,v}}{\sum_{w \in TU_u}t_{u,w}} = \frac{1}{|TU_u|}$
とする．trust networkのエッジが実数値でもここに代入してやるだけで済む．

類似度

2つのアイテム間の類似度[sim(i,j)]は，アイテム $i,j$ におけるユーザ評価を用いたピアソン相関係数 $corr(i,j)$ を用いて
$sim(i,j) = \frac{1}{1+\exp^{-\frac{|UC_{i,j}|}{2}}} \times corr(i,j)$
とする．
$|UC_{i,j}|$ はアイテム $i,j$ を両方評価しているユーザの人数．なのでこれが大きければ類似度を下げる．

ランダムウォークを続けるかどうかの判定

ランダムウォークを続けるか，それとも現在のユーザの別アイテムの評価を返すかの判定には $\phi_{u,i,k}$ を用いる．
これは，
$\phi_{u,i,k} = \max_{j in RI_{u}} \,sim(i,j) \times \frac{1}{1+\exp^{-\frac{k}{2}}}$
とする．
つまり，評価したアイテムが $i$ と類似していればしているほど，ランダムウォークのステップ数が大きいほど打ち切りやすくなる．

似たアイテムを返す確率

ランダムウォークを打ち切る際，アイテム $j$ を返すわけだがこれも $P(Y_u,i = j) = \frac{sim(i,j)}{\sum_{l \in RI_{u}}sim(i,l)}$ で選ぶ．つまりは似たアイテムほど選ばれやすくなる．

補足

論文では厳密にやるために色々追加してる．

kが深くなりすぎてもだるいので，k=6で打ち切る．

Based on the idea of "six-degrees of separation" [11], we set max-depth = 6.

閉じた形で書くために"dead state"を導入
- どのランダムウォークも最後にはdead stateに行き着く形で書く．概念は変わらず．

TrustWalkerの性質

$\phi=1$ と固定すれば協調フィルタリングの亜種， $\phi=0$ と固定すれば，trust networkのみを用いる既存手法にほぼ近い形になる
推薦の信頼度を得ることできる
- 複数のランダムウォークによる評価値の分散を $\sigma^2$ とすれば，それが低いほど信頼できる（？）
- $confidence = 1 - \frac{\sigma^2}{\max \sigma^2}$
推薦の説明しやすさ