Recommender Systems Handbook 3章を読んだメモ (3.3まで)

# Chapter3: Advances in Collaborative Filtering
## 目次
1. イントロ
2. 準備
  1. ベースとなるモデル
  2. Netflixのデータについて
  3. 間接的なフィードバック
3. 行列分解モデル
  1. SVD
  2. SVD++
  3. 時間経過を考慮したモデル
  4. モデルの比較
  5. まとめ
4. 近傍モデル
  1. 類似度
  2. 類似度を利用した補間
  3. jointly derived interpolation weights
  4. まとめ
5. 近傍モデルの改良
  1. 大域的?近傍モデル
  2. 行列分解モデルと組み合わせる
  3. 時間経過を考慮する
  4. まとめ
6. 行列分解モデルと近傍モデル

## イントロ
- いろいろな入力データ
  - 明示的なフィードバック(言い方を変えると予測する値)
     - 5段階評価、好きか嫌いか
     - 常に使えるとは限らない
  - 間接的なフィードバック
     - 購入履歴、閲覧履歴、検索パターン、マウスポインターの動き...
- 主要な手法
  - 近傍モデル
  - 潜在因子モデル (行列分解モデルはその一つ)
- どの手法を使うにせよ、大切なのはデータの中から使える特徴を見つけ出すこと
  - 時間経過の考慮は大事
  - 評価の値だけでなく、評価したかどうかも使える

## 準備
$m$: ユーザ数
$n$: アイテム数
$u,v$: ユーザに関わる添字・変数
$i,j,l$: アイテムに関わる添字・変数
$r_{ui}$: ユーザuのアイテムiの評価値。大きいほど良い
$\\hat{r_{ui}}$: $r_{ui}$の予測値
$t_{ui}$: 評価をした時間
$R(u)$: ユーザuが評価したアイテムの集合
$R(i)$: アイテムiを評価したユーザの集合
$N(u)$: ユーザuが間接的に評価したアイテムの集合 ※購入したアイテムの集合など
$K$: 評価データ内に存在する全ユーザ・アイテムの組の集合

### ベースとなるモデル
ユーザとアイテムの相互作用(ある特定ユーザはある特定アイテムを好む)は無視する。
その代わりに

- あるユーザが他のユーザと比べてどの程度の評価をしやすい(高めor低めにつける傾向がある)か
- あるアイテムが他のアイテムと比べてどの程度評価を受けやすいか

といったユーザ毎、アイテム毎に独立した差分を考える。
$\\mu$を評価の全体平均とする。このとき、あるユーザ$u$のアイテム$i$の評価はこのモデルでは

```math
\hat{r_{ui}} = b_{ui} = \mu + b_u + b_i
```

で表される。ここで$b_u$はユーザ$u$のバイアス、$b_i$はアイテム$i$のバイアスである。
$b_u,b_i$は

```math
\sum_{(u,i)\in K}(r_{ui}-\mu-b_u-b_i)^2+\lambda_1(\sum_ub_u^2+\sum_ib_i^2)
```

を最小にする$b_*$として求めることができ、SGD(確率的勾配降下法)で求められる。

### 間接的なフィードバック
この章では基本的に明示的に与えられた評価を予測することを基本とするが、間接的に与えられるデータも有用である。特に、評価しているアイテムが少ないユーザに対する予測や、アイテム数が膨大であるなどデータがスパースである場合に使える。

Netflixのデータの場合、視聴履歴を使うことをまず思いつくがデータには含まれていない。そこで使えるのがユーザが**どの映画をレビューしたか**である。ユーザは評価するかしないかをランダムに決めているのではなく、何かしらの意図をもって決めているのでこのデータを使うと精度があがる。

## 行列分解モデル

### SVD
行列分解モデルではユーザやアイテムの評価が次元$f$のベクトル

```math
p_u \in R^f \\
q_i \in R^f
```

の内積で表すことができると仮定する。
このとき評価の予測値はベースラインモデルに$q_u$と$q_i$の内積を足した

```math
\hat{r_{ui}} = \mu + b_i + b_u + q_i^Tp_u
```

であらわす。そうすると損失関数は

```math
L = \sum_K \{ (r_{ui}-\mu-b_i-b_u-q_i^Tp_u)^2+\lambda_4(b_i^2+b_u^2+||q_i||^2+||p_u||^2) \}
```

となるのでSGDで解くことができる。p.84の更新式はすべて

パラメータ <- パラメータ - $\\gamma\\frac{\\partial L}{\\partial パラメータ}$

の形になっている。

### SVD++
間接的なフィードバックを考慮したモデルを考えてみる。SVDではユーザが潜在ベクトル$p_u$で表すことができるとしたが、ここにユーザ$u$のアイテム$i$に対する間接的なフィードバック$y_i \in R^f$を組み込むと、ユーザの潜在ベクトルは

```math
p_u+\frac{1}{|R(u)|^{\frac{1}{2}}}\sum_{R(u)}y_i
```

で表すことができる。するとモデルは

```math
\hat{r_{ui}} = \mu + b_i + b_u + q_i^T(p_u+\frac{1}{|R(u)|^{\frac{1}{2}}}\sum_{R(u)}y_i)
```

となる。さらに拡張すると例えばユーザのレンタル履歴$N^1(u)$と閲覧履歴$N^2(u)$を考慮して

```math
p_u+\frac{1}{|N^1(u)|^{\frac{1}{2}}}\sum_{N^1(u)}y^1_i+\frac{1}{|N^2(u)|^{\frac{1}{2}}}\sum_{N^2(u)}y^2_i
```

としていくことができる。

### 時間経過を考慮したモデル
1. ユーザバイアス$b_u$の時間変化
2. アイテムバイアス$b_i$の時間変化
3. ユーザの潜在ベクトル$p_u$の時間変化

を考える。するとベースラインモデルは

```math
b_{ui} = \mu + b_u(t_{ui}) + b_i(t_{ui})
```

と表現できる。まずアイテムバイアス$b_i(t_{ui})$について考える。アイテムの場合は単純に時間を区間(bin)に分けることで時間変化を表現する。例えば第一日目の値は$b_{i,Bin(1)}$で、第三十日目の値は$b_{i,Bin(30)}$でという風に表すことにするとアイテムバイアス$b_i(t_{ui})$は

```math
b_i(t_{ui}) = b_i + b_{i,Bin(t)}
```

となる。次にユーザバイアス$b_u(t_{ui})$について考える。単純な線形のモデルを考えると$t_{ui}$のユーザについての平均値を$t_u$として

```math
b_u(t_{ui}) = b_u + \alpha_u sign(t_{ui} - t_u)|t_{ui} - t_u|^\beta
```

となる。上記のモデルは期間限定的な**スパイク**をとらえることができない。そこでユーザが評価した日毎にパラメータ$b_{ut}$を導入して

```math
b_u(t_{ui}) = b_u + \alpha_u sign(t_{ui} - t_u)|t_{ui} - t_u|^\beta + b_{ut}
```

とするとスパイクをとらえることができる。$p_u$については$b_u$と同様に考えることができる。