機械学習
論文読み

論文読み"Recommending New Movies: Even a Few Ratings Are More Valuable Than Metadata"

概要

  • 論文:[1] Recommending New Movies: Even a Few Ratings Are More Valuable Than Metadata
  • https://dl.acm.org/citation.cfm?id=1639731
  • Model based collaborative filtering でよく使われるmatrix factorization(MF)だとcold start問題に対応できない。
  • MFはユーザ$u$の$p_u$特徴ベクトルとアイテム$i$の特徴ベクトル$q_i$を求め、評価 $r_{ui}$ を $p_u \cdot q_i$ と近似する。
  • 新しいアイテムに対して特徴量ベクトルを計算することができない。
  • この論文では、$q_i$をアイテムのメタデータを使って導出する。

Notation

  • $u, v \in {1, ..., N}$: ユーザのインデックス.
  • $i, j \in {1, ..., M}$: アイテムのインデックス.

Contents based filtering

Notation

  • $x_i \in R^C$: アイテム$i$のメタデータ。
  • $w_l \in R^K$ $(l \in {1, ..., C})$: アイテムの特徴ベクトル。
  • $W:={w_1, ..., w_C}^T \in R^{C \times K}$

モデル

アイテム$i$の特徴ベクトルを $q_i = W^T x_i$ と定義し、評価の近似値は次のようになる。

$$r^a_{ui} = b_u + c_i + p_u \cdot q_i$$

ここで未知のパラメータは$b_u$, $c_i$, $p_u$, $W$ で解くべき最小化問題は

$$\min \sum_{r_{ui} \text{ is known}} (r_{ui} - r^a_{ui})^2
+ \lambda \sum_{u}||b_u||^2
+ \lambda \sum_{i}||c_u||^2
+ \lambda \sum_{u}||p_u||^2
+ \lambda \sum_{l}||w_l||^2$$

Algorithm 1

この最小化をSDGで解く。各パラメータの更新式は、$e_{ui} = r_{ui} - r^a_{ui}$ とおくと、

  • $a \leftarrow q_i$
  • $b \leftarrow p_u$
  • $p_u \leftarrow p_u + \eta (e_{ui} q_i - \lambda p_u)$
  • $q_i \leftarrow q_i + \eta (e_{ui} b - \lambda q_i)$
  • $b_u \leftarrow b_u + \eta (e_{ui} - \lambda b_u)$
  • $c_i \leftarrow c_i + \eta (e_{ui} - \lambda c_i)$

これらは最小化する式を各パラメータで微分し、微分の逆方向(-1を掛けたもの)に学習率 $\eta$ だけ更新することで求められる。

ひとまず $q_i$ をパラメータとして更新したあとで、${w_l}$ を ${q_i}$ に一致するように更新する。

  • $d \leftarrow 1 / (x_i^Tx_i)$
  • $w_l \leftarrow w_l + d x_{il} (q_i - a)$

実際、更新前の $w_l$ を $c_l$ とすると、更新式は
$$\sum_{l} x_{il} c_l + (q_i - a) = \sum_{l} x_{il} w_l$$
となるが、これは一意に解くことができないので、前述のようにしている。

アルゴリズムの全体像は次のようになる([1]から転載)。

algorithm1.png

Algorithm2

前述のAlgorithm1の場合、1のアイテムごとに$q_i$を更新し、$w_l$を$q_i$に一致するように更新している。

次に提案する手法は、全評価の情報を使って$Q$を更新し、その後に$W$を$Q$に一致するようにまとめて更新する。

  • $e \leftarrow q_i - W^T x_i$
  • $d \leftarrow 1 / (x_i^T x_i)$
  • $W \leftarrow W + \eta_2 (d x_i \cdot e^T - \lambda_2 W)$

アルゴリズムの全体像は次のようになる([1]から転載)。

algorithm2.png

この方法の場合、$P$ と $Q$ を求めるときに他の手法(ALSなど)を使用することができる。

その他

他の方法も提案されているが、いったんここまで。