Nです．
今回は商品などのレコメンデーションの予測などに使用されるImplicitモデルについて，論文を参考に説明していきたいと思います．今回参考にした論文は”Hu, Yifan, Yehuda Koren, and Chris Volinsky. “Collaborative filtering for implicit feedback datasets.” 2008 Eighth IEEE international conference on data mining. Ieee, 2008.”です．
Implicitモデルの概要（explicitモデルと違う点）
ユーザーの好みを予測する手法は大きく2つにわけることができます．explicitモデルというのはアンケート等でユーザの好みを収集する場合に使用できるモデルです．一方，implictモデルはアンケートのような直接的な方法が使用できないときにでも，ユーザーの購入履歴や閲覧履歴，検索履歴，マウスの動きなどから集めた受動的な情報をもとにユーザーの好みを予測できます．
Implicitなデータの特徴
- ネガティブなフィードバックがない．まだユーザーが見ていないあるテレビ番組があったときに嫌いだから見ていないのか，たまたま見なかったのか（まだデータが取得できていないだけなのか）はわかりません．
- ノイズが多い．たとえば購入履歴にある商品はプレゼントでユーザーが好きな商品ではなく，別の人が好きな商品かもしれません．
- explicitフィードバックの値は好みを表すが，implicitフィードバックの値は自信を表す．explicitの方は例えば５段階評価のような形で好みの強さを表せるが，implicitなデータはその行動を起こした頻度を表します．頻度が高いからと言ってそれが好きとは限りません．ただ繰り返し起こることは重要な情報であることを意味しています（自信）．
- レコメンデーションの評価には適切な指標が必要となる．explicitなデータと異なり，正解が存在しないため答え合わせのためには適切な指標を用意する必要があります．
以下で使用する表記の準備
ユーザー：\(u,v\)
商品：\(i,j\)
ユーザー\(u\)と商品\(i\)に関する入力データ(観測データ)：\(r_{ui}\)
implicitなデータの場合はユーザーがその商品を購入した回数や，そのページを見ている時間などが\(r_{ui}\)に当たる．
先行研究
Neighborhood models 近傍モデル
商品指向型のアプローチでは商品間の類似性が重要です．商品\(i\)と\(j\)の間の類似性は\(s_{ij}\)で表します．\(s_{ij}\)にはピアソンの相関係数（普通の相関）がよく使用されます．レコメンデーションのためにはまだ観測していないユーザー\(u\)の商品\(i\)に対する評価\(r_{ui}\)を予測する必要があります．商品間の類似性の指標を使ってまだ観測できていない商品\(i\)に最も類似している\(k\)個の商品を特定します．この\(k\)個の近傍の商品の集合を\(S^k(i;u)\)と表記します．\(r_{ui}\)の予測値は近傍の商品のレーティング((r_{uk}))の類似性による重みづけ平均として以下のように表記されます．
\[\hat{r}_{ui} = \frac{\sum_{j \in S^k(i;u)} s_{ij}r_{ui}}{\sum_{j \in S^k(i;u)} s_{ij}}\]
Latent factor models 潜在因子モデル
潜在因子モデルは\(r_{ui}\)だけでなく，観測したレーティングを説明する潜在因子を明らかにすることを目的としています．ユーザー因子ベクトル\(x_u \in R^f\)と商品因子ベクトル\(y_i \in R^f\)の内積によって\(\hat{r}_{ui}\)を予測します．
\[\hat{r}_{ui} = x_u^T y_i\]
ユーザー因子ベクトルと商品因子ベクトルを共通の因子で表しているところがポイントです．服のレコメンデーションをする際に服の色が暖色か寒色かが因子の一つだったとします．つまり暖色なら1，寒色なら-1みたいになったりしているとします．この時あるユーザ因子ベクトル内のこの因子が-1になっていればこのユーザーは寒色がすきだということを表しています．また商品因子ベクトルのその因子が1になっていればその商品は暖色系だということです．内積は同じ因子同士を掛け算して足し合わせたものです．寒色が好きなユーザー(-1)と寒色な商品(-1)の掛け算は1となり正になりますが，暖色な商品(+1)との掛け算はは-1となり負となります．様々な因子について同じように掛け算を行い，足し合わせるとそれらの因子を考慮したうえでユーザーがその商品を好きか（大きな正の値になるか）どうかがわかるということです．
ユーザー因子ベクトルや商品因子ベクトルは以下の正則化項つきの二乗誤差を評価関数としそれを最小化する因子ベクトルとして推定します．
\[ \min_{x_\star y_\star} \sum_{r_{ui}が既知のu,i}(r_{ui} – x_u^T y_i)^2 + \lambda (||x_u||^2 + ||y_i||^2)\]
右辺の第一項が小さいほど予想がうまくできていることを意味します．また，右辺の第二項は正則化項で過学習を防ぐことを目的としています．
\(\lambda\)は正則化項をどれくらい重視するかを決めるパラメータです．潜在因子はよく確率的勾配降下法で学習します．
このモデルをimplicitで計算できるようにしたのがモデルになります．
今回紹介するモデル
このモデルではユーザー\(u\)の商品\(i\)に対する好みを表すバイナリ変数\(p_{ui}\)を使用します．
\[p_{ui} = \begin{cases} 1 & r_{ui}>0\\ 0 &r_{ui}=0 \end{cases}\]
さらにもう一つ自信を表す指標\(c_{ui}\)を導入します．
\[c_{ui} = 1 + \alpha r_{ui}\]
例えばある商品を購入した回数が高いほど\(c_{ui}\)は高くなります．
今回の目的はすべてのユーザーに対するユーザー因子ベクトル\(x_u \in R^f\)と，すべての商品に対する商品因子ベクトル\(y_i \in R^f\)を見つけることです．それらの内積をとることでユーザー\(u\)の商品\(i\)に対する評価\(r_{ui}\)を予測することができます．この因子の数\(f\)はこちらで決める必要があります．
すべてのユーザー因子ベクトルを並べた行列\(x_\star\)と商品因子ベクトルを並べた行列\(y_\star\)は潜在因子モデルと似たような評価関数を最小化する\(x_\star, y_\star\)として推定します．
\[ \min_{x_\star y_\star} \sum_{u,i}c_{ui}(p_{ui} – x_u^T y_i)^2 + \lambda (\sum_u||x_u||^2 + \sum_i||y_i||^2)\]
上記の式の第一項は\(p_{ui}\)を\(x_u,y_i\)からどれだけうまく推定できたかを評価しています．第二項は過学習を防ぐための正則化項で因子ベクトルの大きさが小さいことを良いと評価することでより少ない重要な因子で\(p_{ui}\)を予測する方向に学習させる効果があります．この時の\(\lambda\)はどれだけこの正則化項を重視するかを決めるパラメータで交差検証などから決定されることが多いようです．
この評価関数の最小化に使われる手法がAlternating Least Squares(交互最小二乗法)です．
一度に最小化するのではなく，\(x_u, y_i\)を交互に更新して評価関数が最小となるベクトルを求めるような手法になっています．交互最小二乗法によって計算量が入力の数に対して線形に抑えられるのがこの最適化手法のメリットです（詳細を知りたい方はYifan et al. 2008を見てください）．
ステップ1: 商品因子を定数とみなしてユーザー因子を計算
まず商品因子を\(n \times f\)行列\(Y\)として仮定します．この時\(n\)は商品の数，\(f\)は因子の数です．
次にそれぞれのユーザーについて対角行列\(C^u\)を考えます．この行列\(C^u\)の対角成分\(C^u_{ii} = c_{ui}\)です．また\(p(u) \in R^n\)はユーザー\(u\)のすべての商品に対する好みを並べたベクトルです．これらを使って評価関数を\(x_u\)について微分した式を書き直すと以下のようになります．
\[ \frac{\partial}{\partial x_u} \left(\sum_{u}\sum_{i}c_{ui}(p_{ui} – x_u^T y_i)^2 + \lambda (\sum_u||x_u||^2 + \sum_i||y_i||^2) \right)\\
= \sum_{i}c_{ui}(p_{ui} – x_u^T y_i)\times -(2y_i) + 2\lambda x_u \\
= -2\sum_{i}c_{ui}p_{ui}y_i + 2\sum_{i} y_i x_u^T y_i + 2\lambda x_u \\
= -2\sum_{i}c_{ui}p_{ui}y_i + 2\sum_{i} y_i y_i^T x_u + 2\lambda x_u \\
= -2Y^TC^up(u) + 2Y^TC^uYx_u +2\lambda x_u\]
\(y_i\)を定数として考えると評価関数は２次関数で下に凸であるので微分が0の時最小となります．この時\(x_u\)は以下のように計算できます．
\[0 = -2Y^TC^up(u) + 2Y^TC^uYx_u +2\lambda x_u\\
(Y^TC^uY +\lambda I) x_u = Y^TC^up(u)\\
x_u = (Y^TC^uY +\lambda I)^{-1}Y^TC^up(u)\]
ステップ2: ユーザー因子を定数とみなして商品因子を計算
評価関数は\(x_u\)と\(y_i\)について対称なため\(y_i\)について微分して上記と同様の変形を行うと\(y_i\)は以下の式のように計算できる．
\[y_i = (X^TC^iX +\lambda I)^{-1}X^TC^ip(i)\]
ここで\(X\)はユーザー因子ベクトルを並べた\(m \times f\)の行列．\(C^i\)は対角成分\(C_{uu}^i = c_{ui}\)である対角行列．\(p(i) \in R^m\)は商品\(i\)に対する\(m\)人のユーザーの評価を並べたベクトルです．
安定するまでステップ1と2を繰り返し計算
上記の計算を\(x_u\)と\(y_i\)が収束するまで繰り返し行います．
そのようにして求めたユーザー因子ベクトルと商品因子ベクトルの内積からユーザーの好み\(\hat{p}_{ui}\)を推定します\(\hat{p}_{ui} = x_u^T y_i\)．
コメント