推薦モデル

推薦モデル、所謂リコメンデーションモデルの最近の同行をまとめました。

• 様々な記述があり、書き手により単語が指す範囲が異なる場合がある

• $\langle w, x\rangle$とはw,xの内積を表す

分類

• 推薦システムは大きく分けて3種類
  • ルールベース：推論時に他のユーザーの情報を利用しない
  • メモリベース：学習・推論時共に他のユーザーの情報を利用する
  • モデルベース：学習時に他のユーザーの情報を利用するが、推論時には他のユーザーの情報を利用しない

	ルールベース	メモリベース	モデルベース
個人化の度合い	低い	高い	モデルによる
方法	ルールに従って推薦する	推薦の度に、全体的なアイテム・ユーザーの情報から計算する	推薦の度に、モデルに対象者の情報をいれ計算する
手法		協調フィルタリング	クラスタモデル、関数系、ベイズ

• その他の分類
  • 個人化なし：全てのユーザーに対し同じ推薦を行う
  • 一時的個人化：そのセッションのデータ（一時的なデータ）のみ用いて推薦を行う
  • 永続的個人化：長期的なデータ（履歴など）を用いて推薦を行う
  • 更新しない個人化：ユーザーが登録した基本的には更新されない情報や、そのセッションでのみ有効なデータなどを用いて推論する

-	個人化なし	一時的個人化	永続的個人化	更新しない個人化
アイテム	スペックランキング（価格順）	カゴ内の類似商品・代替材補完残	履歴からの類似傾向商品	相互的でないチャットボット・販売員のおすすめ？
人	人気ランキング	よく一緒に買われるもの	協調フィルタリング（評価・行動からの類似傾向商品）	アンケートなど
知識	店・時期ごとのおすすめ	会計時のおすすめ	あまりなし・個人に対する専門家のおすすめ	チャットボット・販売員のおすすめ

協調フィルタリング

• ユーザーの評価（行動）情報を使い、対象ユーザーに類似した他のユーザーの情報を用いて推薦を行う手法

利点

• ドメイン知識が不要
• 異なるジャンル間で推薦可能（セレンディピティ）

欠点

• コールドスタート問題

  • サービス初期、購入（行動）回数が少ない利用者やアイテムは推薦できない

• カバレッジ（被覆率）が低くなる

  • 推薦されるアイテムが多く買われているものになりやすい
  • 買われていないアイテムは推薦できない

• 類似アイテムは推薦できない

  • アイテムの類似度はわからない

手順

1. ユーザーの評価（行動）情報を蓄積する
   • 蓄積できていない場合は、ルールベースやコンテンツベースのシステムを用いる
2. 評価（行動）情報から、嗜好が似ているユーザーを探す
   • どのように嗜好が似ているかを算出するかは、類似性指標のサーベイを参照
   • ユーザーが多い場合、あらかじめユーザーを行動履歴などによりクラスタリングすることで、計算資源を節約できる
3. 嗜好が似ているユーザーが好んでおり、そのユーザーにとって評価が高いと思われるものを推薦する
   • ここでは、k-NNなどを用いる

問題

データのスパース性

• アイテムが非常に多い場合、ユーザーは大半の商品を買わない
  • そのため、実際は類似しているユーザーであっても、全く同じアイテムをともに評価しないと類似であると判別できない（同類推移問題）
• 解決するためには以下の手法が存在
  • 特異値分解（SVD）による次元削減
  • 行列分解による次元削減（モデル.関数系.回帰の欄参照）
  • ハイブリッド協調フィルタリングによる補完
    • ユーザーの履歴を用いない、アイテムベース・ユーザーベースで類似度を計算
  • 予測モデル構築によるデータの補完
    • 未評価のアイテムの評価値を予測して埋める

スケーラビリティ

• アイテム数やユーザー数が非常に速いスピードで増大した場合、計算量が大きくなる
• 解決するためには以下の手法が存在
  • CFを使う前に、アイテムベース・ユーザーベースで類似するアイテム・ユーザーをクラスタリングし、計算対象を絞り込む（ハイブリッド協調フィルタリングのようなもの）

灰色の羊

• 複数パターンの趣向と一致する、あるいはどれとも一致しないために、フィルタリングの恩恵にあずかれないユーザー群のこと
• 解決するためには以下の手法が存在
  • ハイブリッド協調フィルタリングによる行動パターン以外での差別化

シリングアタック

• 評価システムに対する攻撃を指す（サクラレビューなど）
• 解決するためには以下の手法が存在
  • アイテムベースの協調フィルタリングを用いる
    • ユーザーベースより影響を受けにくい
  • アイテムベース＋CFのハイブリッド協調フィルタリングを用いる

分類

• メモリベースか、モデルベースか、ハイブリッドかに分類できる

メモリベースのCF

• ユーザーとアイテムの相関関係により、類似したユーザー同士の評価をもとに推薦を行う

代表的な手法

• ユーザーベース
  • ユーザーの行動履歴を元に、ユーザー間の類似性を解析し、評価が高いアイテムを推薦する
• アイテムベース
  • ユーザーの行動履歴を元に、アイテム間の類似性を解析し、関連性の高いアイテムを推薦する

長所

• 実装が容易
• データの追加が容易
• コンテンツの内容について考慮が不要
• ともに評価されたアイテムのスケーリングが不要

短所

• 人の評価への依存

  • 評価を標準化することで精度が上がる

• 疎なデータでの性能悪化

• コールドスタート

• スケーラビリティ

  • ユーザーやアイテムを事前にクラスタリングしていれば、ある程度は改善可能

  • ただし、ある程度の頻度で更新する必要がある

モデルベースのCF

• 統計的なアルゴリズムによりユーザーの購買行動をモデル化し、モデルをもとに推薦を行う

代表的な手法

• ベイジアンネットワークCF
• クラスタリングCF
• 潜在意味CF
• 素因子分析
• 次元削減を用いたCF

長所

• 疎なデータでの性能
• 予測性能向上
• 直感的な説明

短所

• モデルの構築が複雑
• スケーラビリティ（メモリベースよりは速い）
  • 夜間や、月・週ごとに更新すれば良い
• 適応性
  • ユーザーやアイテムの変化に弱い
    • モデルを更新しないと対応できない
• 次元削減による有益な情報の損失

ハイブリッドなCF

• （CFではない）コンテンツベースと、CFの双方を用いて推薦を行う

代表的な手法

• コンテンツベースCF
• メモリベース＋モデルベースのCF

長所

• 単体での問題を克服可能
• 予測性能向上
• スパース性、灰色の羊に対応

短所

• 構築が複雑
• 場合により外部データ（ユーザーの行動情報以外の情報）が必要

使うデータ

明示的なデータ

• ユーザーに明示的に評価させる
• Good/Bad, n段階評価
• データ量は少ないが、正確で、未評価と不支持の区別は明確

暗黙的データ

• 閲覧データ、購買データなどの自動的に取得できる情報
• データ量は多いが、不正確で、未評価と不支持の区別は明確でない

テクニック

SVD

定義など

• 任意のm x nの実数行列A（rank=k）があるとき、次元m x mの直行行列U, 次元n x nの直行行列V, 非対角成分が0で、対角成分が0より大きい（もし列がk以下なら）か0と等しい（もし列がkより大きいなら）行列Sが存在し、以下のように分解できる

  • 下の行列との差（行列Uだと、r行〜m行の部分）の部分の成分は全て0

• このとき、Aの特異値分解は以下のように表される

$$\begin{aligned} A &= U \Gamma V^T \\ A &: m \times n, ~U: m \times r,~ \Gamma: r \times r,~ V^T: r \times n \end{aligned}$$

• U, Vは直行行列、\Gammaは対角行列で、\Gammaの対角成分の行列がAの特異値（＞0）
• 対角成分の大きさが一定値以下の\Gammaを切り捨てることで、次元を削減する

性質

• 以下の行列Aj*は、Aのランクjの最小二乗近似

$$A_{j*} = \sum^j_{i=1}\lambda_ju_iv_i$$

• Aに対して\Gammaは一位に定まるが、U,Vは一意に定まるとは限らない

SVD ++

• 次元削減手法としてのMFを正則があるSVDとみなし、それの進化系という位置付け
• →メモリベース.Factorization Machines.SVD++参照

他の次元削減手法との比較

• NMF
  • 係数が0以上であるという制約がある手法
  • 分解後の係数が疎になってしまうので適していない
• PCA
  • 0以下をとる場合がある
  • しかし、実際には閲覧や評価、行動などは非負であり、0以下にになることはない
• LDA
  • データが多変量正規分布でないので前提条件が満たされない
• ICA
  • 評価・行動履歴は相互に統計的に独立でないので仮定が満たされない

メモリベース

協調フィルタリング→推薦の流れ

1. ユーザー・アイテム同士の類似性スコアを算出する
   1. 何を持って類似しているとするか定義
   2. 定義に合わせ、データを用意
   3. 定義に合わせ、算出手法を算出し実装
   4. 実際に類似性スコアを算出
2. 類似性スコアで重みをつけて推薦
   1. 類似性スコアで重み付け（似ているユーザー・アイテムの影響度を大きくする）
   2. 正規化する
   3. 適切にソートして、スコアが高い順に結果を表示

例

ユーザーベース

---	アイテム1	アイテム2	アイテム3	アイテム4	アイテム5	アイテム6	アイテム7	アイテム8	類似度
ユーザーA	1	0	x	1	0	x	1	0	1.0
ユーザーB	0	0	1	1	1	0	0	1	0.5
ユーザーC	0	0	1	0	1	0	0	x	0.25
ユーザーD	0	1	0	x	1	0	1	0	0.0
推薦される人	1	0	x	1	0	x	x	x	-
評価(n=1)	-	-	x	-	-	x	1	0	ref A
n=2	-	-	1	-	-	0	0.5	0.5	ref A&B

• 簡略化のために類似度は一致率（同じ値の割合）を使った

• 簡略化のために評価は1（購買したか否か、好きか否か）

• K-NN(n=1)ならば、一番似ているユーザーAの評価が高いアイテム7を推薦する

• K-NN(n=2)ならば、似ているユーザーAとBの評価の平均が高いアイテム3を推薦する

共通の改善点

• ユーザー間の類似度の計算、似ているユーザーからの推薦するアイテムの計算に改善点が多い
  • 類似度に閲覧したか否かなどを含める
  • 推薦するアイテムの計算時に類似度による重み付けを行う
  • 評価者の多さにより重み付けを行う　など
• また、疎なデータを扱う場合、次元圧縮を行う
  • PCAを使う場合は、欠損値をデフォルト投票値（下参照）やEMアルゴリズムで保管する
• 評価値への依存を低めたい場合は、ランキング化した後、ランキングに対する類似指標などを用いる

ユーザーベース独自の改善点

• 一人当たりの共通の評価者が少ない場合、あるユーザーの未評価アイテムの評価値を、全利用のそのアイテムの評価値で埋める（デフォルト投票値）
• 最低、最高などの両端に近い評価値をより重視する

アイテムベース

	アイテム1	アイテム2	アイテム3	アイテム4	アイテム5	アイテム6	アイテム7	アイテム8
ユーザーA	1	0	x	1	0	x	1	0
ユーザーB	0	0	1	1	1	0	0	1
ユーザーC	0	0	1	0	1	0	0	x
ユーザーD	0	1	0	x	1	0	1	0
推薦される人	1	0	x	1	0	x	x	x
アイテム1の類似度	-	-	0.33	-	-	1.00	0.75	0.33
アイテム4の類似度	-	-	0.5	-	-	0.5	0.67	0.5
高評価アイテムの類似度	-	-	0.42	-	-	0.75	0.71	0.42

• 簡略化のため、ユーザーベースと同じ計算方法を用いた

• 改善手法もユーザーベスと同様

• 推薦したいユーザーが高評価をしたアイテム4を使い、未評価のアイテムの類似度を計算

• 類似度が高いアイテム6を推薦する

アイテムベース独自の改善点

• 共起性や、閲覧・買い物・直近の利用履歴と類似しているアイテムを推薦することで、一時的個人化の推薦を行える

• プライバシー保護においてユーザーベースより優位

問題

• 映画・コンサートのように、推薦対象のアイテムが頻繁に入れ替わる状況では、頻繁な近傍の更新が必要になる
• 実験的に特定のアイテムに偏る傾向が強い（理論的根拠はないが）

ユーザーベースとアイテムベースの差別化

• ユーザーベース
  • メモリに収まるサイズで変更が頻繁に行われる
  • ユーザーごとの趣向が独自の値を持っている
    • 〜を推薦するサイト
  • セレンディピティ（予想外のものを見つけること）が高い
• アイテムベース
  • 巨大なデータが対象
  • アイテムが多いと、ユーザー同士の類似度を出しにくい
    • 同じアイテムを買う人が少なかったり、行列が疎になったりする
  • アイテム同士の類似度は事前に計算可能なので、運用環境での推薦が楽
  • アイテム同士の類似度は変化しづらいので再計算が少なくて済む
  • 説明しやすい

Factorization Machines

• 2010年にICDMで出された汎用的なモデル

• 特徴量の交互作用をうまく計算する

  • 年齢を表す特徴量と、性別を表す特徴量があった場合、年齢＋性別のAND条件の特徴量を、年齢と性別の交互作用で表現する
  • 交互作用の重みを各特徴に対応するベクトルの内積で表現することで学習する
  • より高次なFMも提案されているが、2018年時点では、3次くらいまでしか精度が上がっていかない

• CFとは考え方がやや異なる

user A	user B	user C	-	Item a	Item b
1	0	0		1	0
1	0	0		0	1
0	1	0		1	0
0	1	0		0	1
0	0	1		0	1

• このように、1評価を1行で示し、取り出すのはユーザーとアイテムの相互作用の特徴ベクトル
• 相互作用を時間やコンテキストなど自由に入れられる
  • 例えばAgeを入れれば、UserxItemxAgeの交互作用をモデルで扱える

予測式

• 2次のFM

$$\begin{aligned} \hat y(x) &:= w_0 + \sum^n_{i=1}w_ix_i+\sum^n_{i=1}\sum^n_{j=i+1}\langle v_i,v_j\rangle x_ix_j \\ \text{where} \ \ w_0 &\in \mathbb{R},\ \ w \in \mathbb{R}^n,\ \ V \in \mathbb{R}^{n\times k} \\ \langle v_i,v_j\rangle &:= \sum^k_{f=1}v_{i,f} v_{j,f} \end{aligned}$$

V内の行v_iは、k個の因子を持つi番目の変数

k in N+0は因子分解の次元性を定義するハイパーパラメータ

• 参照：通常の交互作用がある2次までの線形モデル
  • そのまま推薦のデータに持っていくと、**$x_ix_j$*が疎であるため$w_{i,j}$*部分が学習しにくい
  • よって、そこの部分をベクトルの内積として学習する
    • ついでに、学習パラメータが減らせる

$$\hat y(x) := w_0 + \sum^n_{i=1}w_ix_i+\sum^n_{i}\sum^n_{j=i+1}w_{i,j}x_ix_j$$

• 2way FMは、変数間の変数単一＋ペアワイズ相互作用を捉える
• w0はグローバルバイアス
• wiは、i番目の変数の強さをモデル化する
• $w^i,j := <v_i,v_j>$はi番目とj番目の変数間の相互作用をモデル化する
• 相互作用ごとにパラメータw_i,jを使用する代わりに、FMモデルは因数分解（Factorize）することで相互作用をモデル化する
  • 疎なベクトルでは、これが重要

予測

• 回帰
  • y^(x)を直接予測対象として使用し、MSEなどで学習させる
• 2値分類
  • y^(x)をラベルとして、ロジット回帰やヒンジロスで学習させる
• ランキング
  • ベクトルxを**$y^{(x)}$で順位付けし、$x(a), x(b) \in D$**のペアに対してペアワイズ分類損失を用いて学習する

最適化手法

• SGD, ALS, MCMCなど
• MSE, ロジット損失、ヒンジロスなど様々な損失を学習できる
• L2正則化で過学習を防ぐ
  • Early stoppingの方が精度が良い？
• 勾配は以下の式で表される（１次の場合？）

\begin{equation} \frac{d}{d\theta}\hat y(x)= \Biggl\{ \begin{array}{1} 1, ~if~\theta~is~w_0 \\ x_i, ~if~\theta~is~w_i \\ x_i\sum^n_{i=1}v_{i,f}x_j- v_{i,f}x^2_i,~if~\theta~is~v_{i,f} \end{array} \end{equation}

数式にエラーが出るため、パーシャルdをただのdとして書いています。

SVD++

元のMF（SVD）

$$\begin{aligned} \hat r_{ui} &= \mu + b_{user}(u)+b_{item}(i)+U_uI_i \\ \text{where} \ \ \hat r_{ui}&: \text{評価の予測} \\ b_{user}&: \text{個人の影響（バイアス）} \\ I&: \text{商品の属性}(I \in R^{k\times m}) \\ \mu&: \text{全体平均} \\ b_{item}&: \text{商品の影響（バイアス）} \\ U&: \text{商品の属性}(U \in R^{u \times k}) \end{aligned}$$ $$loss = \min_{b,U,I}\sum_{u,i\in R}(r_{ui}-\hat r_{ui})^2 + \lambda(|b_{user}|^2+|b_{item}|^2+|U^T_u|^2+|I_i|^2)$$

SVD++

$\hat{r}_{ui} = \mu + b_{user}(u)+b_{item}(i)+(U_u+|R(u)|^{-0.5}\sum_{j \in R(u)}y_j)I_i$

where $R(u)$ is the set of items rated by user $u$ and $y_j$ is the effect of a user action on item $j$.

The loss function is:

$\text{loss} = \text{argmin}\left[\sum(r_{ui}-\hat{r}_{ui})^2+\lambda_1(||b||^2+||U||^2)+\lambda_2(||I||^2+||y||^2)\right]$

Field-aware FM; FFM

• 元論文：https://www.csie.ntu.edu.tw/~cjlin/papers/ffm.pdf
• このモデルで優勝したコンペ（論文の筆者が使用）
  • Logarithmic Loss https://www.kaggle.com/c/criteo-display-ad-challenge
  • CTR https://www.kaggle.com/c/avazu-ctr-prediction

予測式

• FMの発展型
  • FMでは各特徴量につき一つの埋め込みベクトルを学習した
  • FFMでは、Field（元のカテゴリ分類）の単位に分け、各特徴量につきField分の埋め込みベクトルを学習するように改善した
• FMはカテゴリ変数をone-hot encodingして特徴量とするのが前提だったため、異なる属性情報が一律で1の値にされてしまった
  • 各特徴量は、元がどのようなカテゴリ変数に属するかという情報が抜け落ちてしまっている
  • FFMにより、フィールドごとに特有の要因である相互作用を表現できる

$$\hat{y}(x) := w_0 + \sum_{i=1}^n w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n \langle v_{if_j}, v_{jf_i} \rangle x_i x_j$$

where $f_i$ and $f_j$ denote the fields that $i$ and $j$ belong to respectively.

学習方法

• FMと同じ
• ただしパラメータが増大した分、過学習しやすいので、Early stoppingを用いる

DeepなFM

• Factorization Machines https://data.gunosy.io/entry/deep-factorization-machines-2018#f-95055ec5
• ベクトルごとの交互作用を用いると良い
• 高次の特徴を学習するためには、明示的なアーキテクチャが必要
  • 通常のDNNとは違う性質を持つ
  • （通常のDNNとは別の性質を持ったネットワークが必要）

Factorization-machine supported Neural Network (FNN)

• ECIR2016

• 普通のMLP

  • カテゴリカルな入力データを、各変数ごとにOne-Hot→EmbeddingしてDenseなNetworkに入れる
  • レイヤーの重みの初期化にFMの重みやベクトルを使う

Deep Crossing Network (DCN)

• KDD2016
• FNNのMLP部分をResNetのようなskip-connectionにして、残差を予測
• 内部データに対する実験なので、あまり引用されていないが、後発の研究だとFNNより精度が高い

Wide & Deep (arXiv:1606.07792)

• 2016
• カテゴリカルな値をEmbedして使うのは、FNNやDCNと同じ
• 線形モデルを出力層でくっつける
• FNNやDCNより精度が良い上、TensorflowにAPIがある

Product-based Neural Network (PNN)

• ICDM2017

• CategoricalEmbeddingしてしまうと、カテゴリ変数同士の明示的な相互作用が扱いにくい

• モデルのアーキテクチャに、カテゴリ変数の交互作用項を組み込む

• カテゴリ変数同士の交互作用項の層を作る

• Embeddingを積み上げたFNNより、PNNの方が精度が良い

  • （Wide&Deepよりは弱い？）

DeepFM

• IJCAI2017

• Wide&Deepの発展系？

• スパースな特徴量をEmbedding層に入れる

  • 分岐１：Factorization Machineに入れる
  • 分岐２：DenseなNetworkに入れる

• 分岐１、分岐２を結合して出力

• FM&Deep（FMへの入力をEmbedしない版）より精度が良い

Deep & Cross Network (CrossNet)

• ADKDD2017

1. 連続値はそのまま、カテゴリ変数はEmbedして特徴にする
2. 以下の分岐を行う
   1. 分岐１：交互作用項を考慮したようなCross Networkに入れる
   2. 分岐２：DenseなNetworkに入れる
3. 分岐１、２を結合し、FC後、Sigmoidで出力

xDeepFM

• KDD2018
• Compressed Interaction Network(CIN)というアーキテクチャでベクトル単位で明示的に高次の特徴を学習する

1. 分岐する
   1. Linear層
   2. Embedding
2. 1-2のEmbeddingから分岐する
   1. CIN
   2. Plain DNN
3. 1-1, 2-1, 2-2を結合し出力

FFMの発展系

• https://qiita.com/guglilac/items/6c8971d27c143e2567a4
• FMの発展系より、FFMを元に発展しているため比較的新しい
• 少し理解が浅め

Field-aware Probabilistic Embedding Neural Network(FPENN)

• RecSys2018
• 過学習を防ぐ＋NNの導入
• Field分のEmbeddingを学習するのは同様
  • ただし、Embeddingが従う確率密度のパラメータを推定する
  • こうすることで、学習時に含まれるノイズに頑健に学習できる
• Deepとの組み合わせ型などはDeepFMを参考にしている（？）

Field-weighted Factorization Machine(FwFM)

• WWW2018
• Fieldの組み毎に、予測に対する重要度は変わってくる
  • なので、Fieldの組毎の重要度も定式化する

Interaction-aware Factorization Machines (IFM)

• AAAI 2019
• Attention + FM
• feature levelとfield levelのattentionを考慮する
• attentionについてよくわかっていないので、このモデルと下のモデルはあまり理解できていない

Field Attention Deep Field-aware Factorization Machine (FAT-DeepFFM)

• ICDM 2019

• Attention + FFM

• Embedding入れる段階でAttentionを考慮する

モデルベース

クラスタモデル

手法

1. 嗜好パターンが類似している利用者のクラスタを作成
   • アイテムの評価値などを用いる
2. 利用者に対し、最も似ているクラスタを探す
3. クラスタ内で最も平均評価値が高いアイテムを順に推薦する

性質

• クラスタ数によって、推薦の性質が大きく異なる
  • 目的に合わせてクラスタ数を調整する必要がある
• 推薦の種類はクラスタ数に制限される
  • クラスタ数が小さいと、大まかであまり個人化されていない推薦が行われる
    • 一方、コールドスタート問題には強くなる
  • クラスタ数が多いと、安定したクラスタを求めるのが難しい
    • 一方、推薦の個人化の度合いは高まる
  • 灰色の羊問題に対応できない
    • 利用者を特定のクラスタに分けてしまうため、複数クラスタに跨がるような推薦はできない
• 実装が容易で、実行速度も速い

関数系

• 利用者が好きなほど大きな値を取る効用関数や、評価値を予測する関数を用いるモデル全般
• 回帰、分類、ランク回帰などに帰着する

回帰

モデルについて

• 評価値行列R（欠損なし）を、以下のように分解する

• Uは$k x n$, Vは$k x m$次元である$(k<<m, n)$

$$R^* \approx U^T V$$

• Uのx列は利用者xの特徴を、Vのy列はアイテムyの特徴を表す
• よって、利用者xのアイテムyへの評価値は以下のようになる

$$r^*_{xy} \approx u^T_x v_y$$

• これはユーザーベース協調フィルタリングで、u_x=1/|v|, v_y=アイテムの評価とみなした場合、類似したモデルとみなせる

学習方法

• RとR*との期待的な損失を最小化するように、UとVを分解して学習する
• 行列分解の手法を用いる
  • R-R*の残差が正規分布に従うと仮定し、観測された評価値の生成確率が高くなるようにUとVを計算する（因子分析）
• 目的関数を最小化する
  • λは過学習防止用のパラメータ
  • SGDやALS（他の値を固定し、逐次的にパラメータを更新する）で学習する

$\text{loss} = \text{min}\bigl(p^*, q^*\bigr) \sum\bigl(r_{ui}-q^T_ip_u\bigr)^2+\lambda \left(\bigl|\bigl|q_i\bigr|\bigr|^2+\bigl|\bigl|p_u\bigr|\bigr|^2\right)$

• 欠損値については以下の対応が考えられる
  • 潜在変数とみなしてEMアルゴリズムを用いて解く
  • 欠損値がないデータのみで計算する
  • 平均値などで補完する
  • 欠損値は無視して損失を計算する

その他

• 単純なので、プライバシー保護フィルタリングや、非線形回帰を導入した予測精度向上などの拡張が可能

• 全体を1つの線形モデルで表すと、大まかすぎて予測精度が低くなる場合がある

  • 嗜好が類似している利用者間で、局所的に線形モデルを構築するHorting法などで対応可能

クラス分類

• 評価値の大小関係を無視し、クラスと見なす
  • 大小関係を考慮する工夫も為せる
• 特徴量には、対象アイテムの他の利用者による評価値や、対象者の他のアイテムへの評価値が利用できる

逐次型二項関係学習法

• 各クラスごとに、対象の分類されやすさを表す関数を獲得
• 関数の値が最大となるクラスに対象を分類

$\hat{r}_{xy} = \operatorname{argmax}_{r \in R}\left( \sum_{i} u_{xi}+\sum_{j} w_{yj} \right)$

where:

• $u_{xi}$ is the user-similarity weight for user $i$ evaluating item $y$ with rating $r$

• $w_{yj}$ is the item-similarity weight for item $j$ evaluated by user $x$ with rating $r$

• u, wはオンライン学習の枠組みで求める

  • 学習率を収束させないSGD（Momentum）など

  1. 最初にu, wを初期化する
  2. rが観測されるたびに、利用者x以外でアイテムyを評価済みの全てのユーザーiについて、
     • 評価が同じならvを増やし、そうでないなら減らす
  3. また、利用者xが評価しているy以外のアイテム全てについて、
     • 評価が同じなら重みwを増やし、そうでないなら減らす

その他

• オンライン学習なので、モデルベースだがアイテムや利用者の追加に対応できる

• アイテムや利用者の削除に対応できない

ランキング

• RankBoostで推薦する研究がある

k-NN

• モデルを使うが、モデルベースではない？

• CFの文脈で使われている

• K個の近いアイテム・ユーザーの評価から、推薦を行う

  • 近いユーザーほど重み付けして和を取る場合もある

ルールベース

• モデルといえばモデルだが、エキスパートモデルを指す？

ベイズ分類器（確率モデル）

履歴条件型

• 対象者の過去の嗜好データが与えられたときの、対象者のアイテムyへの評価値の条件付き期待値
  • 確率分布は未知なので、推定した関数を利用する
  • 式中では他の標本利用者の嗜好データは参照されていないが、確率分布の推定過程で利用するため、協調フィルタリングによる推薦と言える

$\hat{r}_{ay} = E[r_{ay} | j \in Y_a] = \sum_{r \in R} P(r_{ay}=r | r_{aj}, j \in Y_a)$

where:

• $r_{ay}$ is the rating given by user $a$ to item $y$

• $Y_a$ is the set of items rated by user $a$

• R = 1の嗜好データの場合は、条件つき確率分布になる

  • 訓練するためのデータが必要だが、暗黙的評価ではr_ay=0となるノイズが多くなり、不利になる
  • また、この形では個々の利用者についてモデルが必要になり、現実的でない

$$\hat r_{ay} = Pr \bigl[ r_{ay}=1 | s_{aj} ~s.t.~ j \in Y_a \bigr]$$

• 実際には、利用者に依存しない全アイテムへの評価の同時分布を求める

$P(r_{.y} | y \in Y)$

where $r_{.y}$ is the rating distribution of all users for item $y$

• 最初の式の条件付き分布はベイズ則と不要な変数の周辺かで消去することで計算する
  • ただし、|Y| = mで、R^(r) = R1xR2xR3x...xRmとパラメータ数はmに対して指数関数的に増加する
  • そこで、変数r.yの間に部分的な条件付き独立性を仮定し学習すべきパラメータを減らす
  • 条件付き独立性を導入した確立モデルは、依存関係をグラフで示すため、グラフィカルモデルという
    • ベイジアンネットワークはその一つ

ベイジアンネットワーク

• 過去のユーザーの行動データから、予めベイジアンネットワークを作成する

• 実環境で、事象発生した際に推薦するアイテムを決定する

  • 閲覧したページをベイジアンネットワークに与え推論、閲覧確率を算出

• ユーザーのセグメントを作成するために使用している研究あり

  • この場合、各セグメントに所属する確率が得られる
  • クラスタリングなどでも、各クラスタの中心からの距離などが得られるはず
  • ベイジアンネットワークは、全てのノードに対してデータを与える必要がない

• Maximum Weighted Spanning Tree (MWST) Algorithm

  • 大規模データに適し、予測効果が良いとされる計算量がノード数に対しO(n^2)
  • 条件付き確立が一番大きくなるSpanning Treeを構築する
  • 別項（下）で扱う

• Pearl's Passage Passing Algorithm

  • 高速にネットワーク上の全ノードの周辺自己確率を求める手法

• ユーザーアイテムベイジアン

  • ユーザーが評価したアイテムのメタデータと、他アイテムのメタデータを比較する
  • 他アイテムを選ぶ確率を算出する

• ユーザーユーザーベイジアン

  • ユーザーが好むアイテム同士のメタデータを比較
  • ユーザー同士の好みの近さを算出

• アイテムアイテムベイジアン

  • アイテムメタデータを比較
  • アイテム同士の近さを算出

ナイーブベイズ

共起型

• ある利用者があるアイテムを評価したことを、その利用者がxであるという事象と、そのアイテムがyであるという事象が共起していると捉える
• この共起確率をモデル化する
• 確率的潜在意味解析（pLSA）を利用する
  • 非常に柔軟で、評価の揺らぎ、アイテムの情報、コンテキスト情報、個人属性情報などの要因を導入するといった拡張が可能
• 新規の利用者に対応するために、ベイズの枠組みに拡張すると潜在的ディリクレ配分法（Latent Dirichelt allocation; LDA）となる
• 詳細はhttp://www.kamishima.net/archive/recsysdoc.pdf　P70

MWST algorithm

• 各変数間の相互情報量を基準として木を構築する手法
• 以下のようなステップからなる

1. 与えられたデータより、Nx(N-1)/2個の枝について、全ての枝の相互情報量I(xi; xj)を求める
2. 最も大きな相互情報量を示す枝を取り出し、木を構築する枝とする
3. 次に大きな相互情報量を示す枝を木に加える
   • ただし、ループができるならその枝を捨てる
4. ステップ3を、N-1個の枝が木に加わるまで繰り返す
5. 最後に根ノードを決定し、根から葉に向かうように枝に方向をつける
   • Webページ（ページ数10万以上）を推薦する論文では、根ノードを最も多くのユーザーが閲覧したページとしていた
   • サイト全Webページに対するベイジアンネットワークの構築は計算量が膨大になり実行できず、構築するネットワークのページ数は5000程度が限界としていた
   • サイト内の各ページを数十個のカテゴリに分け、各カテゴリ変数としてベイジアンネットワークを構築し、ユーザーに対してカテゴリを推論を行なっていた

利点

• 二次統計量までしか用いないため、データからの演算が容易で信頼できる
• 計算量がノード数nに対して高々O(n^2)
• 統計的には一致性が全くないが、予測効率が良い

Pearl's Message Passing Algorithm

• 高速に確率推論を行うための手法
• 一般的に、ベイジアンネットワークではネットワークを構築した後や、ノードにデータを与えた場合、あるノードの事後確立を求めるのに周辺化を行う必要がある
• この周辺化を一般的にネットワーク構造を利用して効率的に計算するアルゴリズム

1. データを与えられたノードから、その周辺ノードへ向けてメッセージの送信を行う
2. メッセージを受信したノードは、受信したメッセージを用いて自分の周辺事後確率を更新する
3. 周辺自己確率を更新したノードは、メッセージの送信元以外に自分の周辺ノードにメッセージを送信する
4. 2,3を繰り返し、全てのノードの周辺事後確率を更新する

推論時

• ユーザーが閲覧したページをデータとしてベイジアンネットワークに入れ推論を行い、そのユーザーにおけるアイテムの嗜好確率を求める
  • 推論アルゴリズムにはPearl’sMessage Passingアルゴリズムを用い高速化する
  • 計算された嗜好確率が大きい順に並べていく

時系列モデル

最大エントロピーモデル

$P(y^{(t+1)} | Y^{(t)}) = \frac{1}{Z}\exp\left[\sum_{k=1}^K \lambda_k f_k(y^{t+1}, Y^{(t)})\right]$

where:

• $Z$ is the normalization constant

• $\lambda_k$ are weight parameters

• $f_k$ are feature functions

• 素性関数とは、購入履歴$<Y^(t)>$をにある特徴があるとき、次回に購入するアイテムが特定のものになるなら1を取り、それ以外では0となるような関数

• 購入履歴中にアイテムyがあるとき、次にアイテムy`を購入する確率

$P(y^{(t+1)}=y' | y \in Y^{(t)}) - P(y^{(t+1)}=y')$

We select items where this difference is largest.

• こうして素性関数を選択すれば、モデルのパラメータlamda_kは最大エントロピー原理に基づいて推定できる
• この素性関数には様々なものが利用できる

マルコフ過程モデル

• 直近K個のアイテム系列を用いて予測する
• 強化学習を使うなどする

定期購入

• 生存時間解析などの手法を用いる
• Cox比率ハザードモデル

コンテンツベースフィルタリング

データの形式

• 嗜好データと検索質問がある
• 嗜好データの場合は、ユーザーの属性、コンテキストの属性を特徴に、アイテムを機械学習アルゴリズムで予測する

参考文献

• 推薦システム全般のこと：https://www.kamishima.net/archive/recsysdoc.pdf

• 協調フィルタリングの分類など：https://eulerdijkstra.hatenadiary.org/entry/20130407/1365349866

• CFを用いた推薦システム構築：https://www.slideshare.net/masayuki1986/recommendation-ml

• Webページの推薦にベイジアンネットワークを使った日本語研究：https://www.ai-gakkai.or.jp/jsai2007/data/pdf/100205.pdf

• FM, FFM、FM+NNについて：https://qiita.com/s_katagiri/items/d630685dd2fe2627ecd3

• FMの元論文：https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf

• DeepFMの動向(2018)：https://data.gunosy.io/entry/deep-factorization-machines-2018#f-95055ec5