まえがき
レコメンドの勉強をしていると、いろんな情報が多すぎて結局どうすればいいかわかりにくいと思ったので、まとめようと思います。
なるべく式や図を載せつつ説明し、使うためのソースコード例も載せてます。
この記事だけ見れば各手法を理解できるように心がけて書いてます。
なお、各手法の西暦はGoogle Scholarのbibtexから取ってきているので、登場時期とズレがあるかもしれません。
対象読者
- 機械学習はやったことあるが、レコメンドは初めてな人
- レコメンドの基礎を学びたい人
- レコメンドコンペでベースラインを作りたい人
基本知識
よく入門書に書いてありそうな知識。ここだけ読んでも実装はできない。
データの種類
-
明示的フィードバック（Explicit Feedback）
- 商品へのレーティングやレビューなどユーザー自らの意思で明示的に評価をつけないと発生しない情報
- 確実な情報が集まる一方で、ユーザーの協力が必要なため、データが集まりにくい
-
暗黙的フィードバック（Implicit Feedback）
- クリック履歴、閲覧履歴、購入履歴など行動によって自然に発生する情報
- たくさんのデータが集まる一方で、誤クリックなど意図しないデータが混入しやすく、解釈が難しい
レコメンドモデルを作るときはこれらの情報を組み合わせて開発しますが、得られていない情報には不確定要素が残る点には注意が必要です。
たとえば、クリックされなかった商品は、「見かけたけど興味がなくてクリックしなかった」のか「そもそも存在を知らなくてたどり着いていない」のかは不明です。
別のログデータと組み合わせればわかる場合もあるので、ログ設計も重要です。
協調フィルタリング
ユーザーの行動データ（購入、閲覧、評価など）を使って、ユーザー同士 or アイテム同士の類似度を計算して推薦します。
ユーザー x アイテム行列
| item1 | item2 | item3 | item4 | item5 | item6 | |
|---|---|---|---|---|---|---|
| userA | 1 | 1 | - | 1 | 0 | 0 |
| userB | - | 1 | 0 | 1 | - | 1 |
| userC | 1 | - | 1 | 1 | 0 | 1 |
| userD | 1 | - | 1 | - | - | - |
-
1: 購入 -
0: 閲覧(したが購入してない) -
-: 未観測
ユーザーベース型
- ユーザー同士の類似度を計算
- 「あなたと購入履歴の似たユーザーはこんな商品を買っています」
- 行を各ユーザーのベクトルとみなして、似たユーザーを見つける（上位N人）
- 似たユーザーが購入しているアイテムを推薦する（N人の平均値などで購入しそうな順に提示）
アイテムベース型
- アイテム同士の類似度を計算
- 「この商品を買ったユーザーはこんな商品も買ってます」
- 列を各アイテムのベクトルとみなして、類似度の高いアイテムを推薦する（上位M件）
類似度計算には、コサイン類似度やJaccard類似度が使われる。
類似度を計算する際に、未観測「-」は適当な値（0, 0.5など）で埋めるか、無視をする。
ログデータを使うため、情報の少ない新規アイテム/新規ユーザーに弱いコールドスタート問題がある。
コンテンツベースフィルタリング
アイテム固有の情報を使って推薦する手法をいいます。
たとえば、アイテムの画像や説明文などから作った特徴ベクトルを使って推薦をする事が考えられます。
- 直近見たM個のアイテムの平均ベクトルと類似度の高いアイテムを提示する
- M=1なら「このアイテムに似たアイテムはこちら」みたいなものができる
アイテムのベクトルを作る方法さえあれば、アイテムが追加されたタイミングでベクトルを登録しておいて、近似最近傍探索（後述）をするだけでよいため導入しやすいです。新規ユーザーに対するコールドスタート問題も起きにくいといえるでしょう。
一方、ログデータを全く活用していないため、使えるかは実現したいサービス次第で、極端に同じようなアイテムばかり提示されて困るケースだとイマイチです。
協調フィルタリングとの比較は以下の記事にまとめられていました。
レコメンドを支える技術
レコメンドモデルを考えるうえで重要な技術の紹介です。
ここを読むと実装イメージが湧きます。
行列分解
協調フィルタリングのユーザー x アイテム行列は、ユーザーとアイテムが増えると次元が大きくなりすぎるため、扱いづらくなります。
行列分解では、ランクを落とした2つの行列の積で近似することを考えます。
こうすることで、各ユーザーと各アイテムのベクトル表現が得られると共に、まだ得られていない評価値を推定することができます。
特異値分解（SVD）
固有値分解を一般化した方法で、非正方行列にも使える行列分解です。
ユーザーxアイテム行列は非常に大きいサイズのスパースな行列になることが多いですが、スパース行列の特異値分解はscipyでサポートされています。
上位$k$個だけを計算するので計算量を抑えられます。
import numpy as np
from scipy.sparse.linalg import svds
R = np.random.rand(500, 400)
U, sigma, Vt = svds(R, k=2)
ユーザーxアイテム行列で未評価の値は、ゼロで埋める（スパース行列として扱う）かユーザーごとの平均値で埋めるなどで対応します。
参考文献
Matrix Factorization（MF）（2009年）
Netflix Prizeで登場した行列分解アルゴリズムです。
ユーザー$u$のアイテム$i$への評価値$r_{ui}$を$p_u^\top q_i$で表現するために、以下の最小化問題を解きます。
$$
\min_{p_*, q_*}\sum_{(u, i) \in \mathcal D} (r_{u,i} - p_u^\top q_i)^2 + \lambda ( \|p_u\|^2 +\|q_i\|^2)
$$
- $p_u\in\mathbb{R}^k$: ユーザーベクトル（学習するもの）
- $q_i\in\mathbb{R}^k$: アイテムベクトル（学習するもの）
- $k$: 次元数（ハイパーパラメータ）
- $\mathcal D$: 評価済みのユーザーアイテムペア（学習データ）
- $\lambda$: 正則化係数（ハイパーパラメータ）
最適化はSGD（1サンプルずつの勾配法）で行えばよく、誤差を$e_{ui}:=r_{ui}-p_u^\top q_i$、学習率を$\gamma$とすると、更新式は
- $p_u\leftarrow p_u + \gamma (e_{ui}q_i-\lambda p_u)$
- $q_i\leftarrow q_i + \gamma (e_{ui}p_u-\lambda q_i)$
で表現できます。（実装簡単！）
MFでは評価済みデータのみを使うため、SVDと異なり未評価（欠損値）の扱いを考えなくてよいです。
論文内ではさらなる工夫としてバイアス項も考慮した式が登場します。
$$
\min_{p_*, q_*, b_*} \sum_{(u, i) \in \mathcal D} [r_{u,i} - (p_u^\top q_i + \mu + b_u + b_i)]^2 + \lambda ( \|p_u\|^2 +\|q_i\|^2 + b_u^2 + b_i^2 )
$$
- $\mu$: 全体の平均値（定数）
- $b_u$: ユーザー$u$のバイアス項（学習するもの）
- $b_i$: アイテム$i$のバイアス項（学習するもの）
明示的フィードバックデータに対するレコメンド系ライブラリSurpriseでは、ソースコードのコメントを見る限りSVDという名前でこのMFをサポートしているようです。
# pip install scikit-surprise
from surprise import Dataset, Reader, SVD, accuracy
from surprise.model_selection import train_test_split
import pandas as pd
# ダミーデータ
data = {
"user_id": ["User1", "User2", "User3", "User4", "User1", "User2", "User3", "User4"],
"item_id": ["Item1", "Item1", "Item1", "Item1", "Item2", "Item2", "Item2", "Item2"],
"rating": [5, 4, 3, 2, 4, 3, 2, 1]
}
df = pd.DataFrame(data)
reader = Reader(rating_scale=(1, 5))
dataset = Dataset.load_from_df(df, reader)
trainset, testset = train_test_split(dataset, test_size=0.2)
algo = SVD()
algo.fit(trainset)
predictions = algo.test(testset)
accuracy.rmse(predictions)
参考文献
Factorization Machine (FM) （2010年）
ここまでの行列分解は、ユーザーとアイテム間の評価値のみで、特徴量をいれることはできませんでした。
Factorization Machine (FM)では、特徴量を扱える上に、2つの特徴間の相互作用も扱えて、スパースな特徴量に対しても機能するモデルです。
次の図のように、ユーザー(User)とアイテム(Movie)のonehot特徴に加えて、任意の特徴を扱えます。
（図: 論文より引用）
FMのモデルは次の通りです。
\hat {y}(\boldsymbol{x})
= w_0 + \left\langle \boldsymbol{w},\boldsymbol{x}\right\rangle
+\sum_{i=1}^{n}\sum_{j=i+1}^{n}\left\langle \boldsymbol{v}_i,\boldsymbol{v}_j\right\rangle x_j x_j
- $\boldsymbol{x} \in \mathbb{R}^n$: $n$次元特徴ベクトル
- 学習するもの
- $w_0\in \mathbb{R}$: バイアス項
- $\boldsymbol{w}\in\mathbb{R}^n$: 特徴量の係数
- $\boldsymbol{V}\in\mathbb{R}^{n\times k}$: 相互作用項の係数
- $i$行目を$\boldsymbol{v}_i$で表す
- 次元数$k$はハイパーパラメーター
- $\langle\cdot,\cdot\rangle$: 内積
2次の項は計算量が多く見えますが、式変形によってオーダー$O(kn)$で済みます。（式変形気になる方は論文を参照）
\sum_{i=1}^{n}\sum_{j=i+1}^{n}\left\langle \boldsymbol{v}_i,\boldsymbol{v}_j\right\rangle x_j x_j
=\frac{1}{2}\sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n}v_{i,f}x_{i}\right)^{2}-\sum_{i=1}^{n}v_{i,f}^{2}x_{i}^{2}\right)
特徴ベクトル$x$がスパースで、非ゼロ特徴がデータセット全体で平均$m$次元の場合、$O(km)$で済みます。
損失関数
FMはさまざまなタスクに使えます。
- 回帰: $\hat{y}(\boldsymbol x)$が予測値で、二乗損失などを使う
- 2値分類: $\hat{y}(\boldsymbol x)$の符号が予測値で、ヒンジ損失やloglossなどを使う
- ランキング: $\hat{y}(\boldsymbol x)$の値の順序が重要で、pair-wiseのクラス分類損失などを使う
この論文が発表された頃、後述するBPRはまだ発表されていないので述べられてませんでしたが、与えるペアを同じユーザーにすることでBPRも適用できます。（公開されているライブラリではBPRが実装されていました）
最適化にはSGDが紹介されてました。
\frac{\partial}{\partial \theta} \hat {y}(\boldsymbol x)=\begin{cases}
1, &\theta \text{ is } w_0\\
x_i, &\theta \text{ is } w_i\\
x_i\sum_{j=1}^nv_{j,f}x_j-v_{i,f}x_i^2&\theta \text{ is } v_{i,f}
\end{cases}
$\sum_{j=1}^nv_{j,f}x_j$は事前に計算しておくと、各勾配を$O(1)$で計算できます。
特徴ベクトルがユーザーとアイテムのonehotだけの場合、前述のMFと一致するため、FMのほうが表現力があることがわかります。
$$
\hat {y}(\boldsymbol x)=w_0+w_u+w_i+\langle \boldsymbol v_u, \boldsymbol v_i\rangle
$$
参考文献
- Factorization Machines
- Factorization Machine (FM) についての私的まとめ
-
fastFM
- pythonで使えるライブラリ、ランキング学習はBPR損失
ランキング学習（ランク学習）
検索エンジンの検索結果のランキングや、商品の推薦リストなど、順序を学習する技術です。
損失関数の考え方として主に以下の3つのアプローチがあります。
- ポイントワイズアプローチ（Pointwise Approach）
- 各サンプルについて独立に損失を考える
- モデルの予測値とターゲット（教師データ）との比較による損失
- 例：回帰/分類モデルを用いて、スコアを予測し、そのスコアに基づいてソートする
- ペアワイズアプローチ（Pairwise Approach）
- 2つのペアに対して損失を考える
- 順序が間違っていると大きな損失が発生する
- 例: RankNet, LambdaRank, BPR
- 2つのペアに対して損失を考える
- リストワイズアプローチ（Listwise Approach）
- リスト全体の順序に対して損失を考える
- 例: ListNet, XENDCG
参考文献
BPR (Bayesian Personalized Ranking)（2012年）
ランクキング学習するフレームワーク。
他の論文ではよく損失関数として登場します。
目的関数
$$
\mathrm{BPR}(\Theta)=\sum_{(u,i,j)\in D_S}\log \sigma\bigl(x_{uij}(\Theta)\bigr)-\frac{\lambda}{2} \|\Theta\|^2
$$
を最大化する。（最小化問題の損失関数として使うときは全体にマイナスをかけてください）
- $D_S:=\{(u,i,j)\mid ユーザーuはアイテムjよりアイテムiを好む\}$
- $\sigma(\cdot)$: シグモイド関数
- $x_{uij}(\Theta)$: 任意のモデル（$\Theta$はモデルのパラメーター）
（論文内では1/2が無いですが、事前分布が標準正規分布でlogを取ると1/2残るし、目的関数と勾配の整合性が合わなくなるので1/2をつけてます。）
BPRのお気持ち
事後確率（の対数）の最大化問題を解いています。
シグモイド関数の部分が尤度関数を表現しており、正則化項は事前分布から現れる部分です。
事後確率（の定数倍）
\underbrace{p(\Theta)}_{事前分布}\times\underbrace{\prod_{(u,i,j)\in D_S} p(i>_uj|\Theta)}_{尤度}
のlogになっているわけです。
- $i>_u j$: ユーザー$u$がアイテム$j$よりアイテム$i$を好む
最適化方法はSGD（確率的勾配降下法）が紹介されてました。
$$
\Theta \leftarrow \Theta + \alpha\left(\frac{\exp(-x_{uij}(\Theta))}{1+\exp(-x_{uij}(\Theta))}\frac{\partial}{\partial \Theta}x_{uij}(\Theta)+\lambda \Theta\right)
$$
なので、ユーザー$u$の好むアイテム$i$の集合を持っておいて、（無数にある）好んでいないアイテム$j$はランダムサンプリングすればよいことになります。
任意のモデル$x_{uij}(\Theta)$は何でもいいので、論文内ではMatrix Factorizationとk近傍法が紹介されてました。
Matrix Factorizationを例に説明します。
行列分解なので、行列$X\in\mathbb{R}^{|U|\times |I|}$を$X=WH^\top$と表現し、2つの行列$W\in\mathbb{R}^{|U|\times k},H\in\mathbb{R}^{|I|\times k}$を学習することになります。（$\Theta=\{W,H\}$）
任意のモデル$x_{uij}(\Theta)$を、2つのアイテムの差$x_{uij}:=W_u H_i^\top - W_u H_j^\top$で定義したら完了です。
SGDの更新式では、偏微分の値があればよいので、
$$
\frac{\partial}{\partial W_u}x_{uij}=H_i - H_j,~
\frac{\partial}{\partial H_i}x_{uij}=W_u,~
\frac{\partial}{\partial H_j}x_{uij}=-W_u
$$
を使えばアルゴリズム完成です。
このように、BPRは任意のモデルに対してSGDで事後確率を最大化するフレームワークといえます。
暗黙的フィードバックデータに対するレコメンドライブラリimplicitでMFのBPRをサポートしています。
# pip install implicit
import numpy as np
import implicit
import scipy.sparse as sparse
# ユーザー数
num_users = 600
# アイテム数
num_items = 500
# ダミーのユーザーxアイテムデータ
data = sparse.random(num_users, num_items, density=0.01, format="csr")
# BPRモデルの学習
model = implicit.bpr.BayesianPersonalizedRanking()
model.fit(data)
# ユーザーに推薦する上位N件
user_id = 123
ids, scores = model.recommend(user_id, data[user_id], N=5)
print("User", user_id, "ids", ids, "scores", scores)
# 類似アイテム上位N件
item_id = 456
ids, scores = model.similar_items(item_id, N=5)
print("Item", item_id, "ids", ids, "scores", scores)
参考文献
- BPR: Bayesian Personalized Ranking from Implicit Feedback
- Factorization MachinesによるBayesian Personalized Ranking
- レコメンドアルゴリズム(BPR)の導出から実装まで
LambdaRank（2006年）
LambdaRankは、ペアワイズで損失を考えながらも、リスト全体に対してのランキング指標（NDCGなど）も考慮しつつ最適化する手法です。
みなさんがよく使っているLightGBMの目的関数にもlambdarankがあります。
これがどういうものか理解しておきましょう。
LambdaRankは、RankNetを参考にしており、ペアに対するloglossから始まりました。
C_{ij}=-y_{ij}\log\hat{y}_{ij}-(1-y_{ij})\log(1-\hat{y}_{ij})
- $y_{ij}$: アイテム$i$がアイテム$j$よりも優先度が高いなら1
- $\hat{y}_{ij}=\mathrm{sigmoid}(s_i-s_j)$
- $s_i$: モデルのアイテム$i$に対するスコア
ペア集合$\mathcal{D}=\{(i,j) \mid jよりiのほうが優先度高い\}$について学習することを考えると、$y_{ij}=1$だけを考えればよいため、
C_{ij}=-\log\hat{y}_{ij}=-\log\mathrm{sigmoid}(s_i-s_j)=\log(1+e^{-\alpha(s_i-s_j)})
となります。（BPRの特殊ケースですね）
pairwise logistic lossやRankNet lossと言われるようです。
最適化をするには勾配があればよいので、
\frac{\partial C_{ij}}{\partial s_i}
=\frac{-\alpha}{1+e^{\alpha(s_i-s_j)}}
となります。
式からわかるようにpairwise logistic lossでは、2ペアに関しての関係を見ているものの、全体でどのくらいの位置であるかは考慮できていません。
たとえば、1位と3位が入れ替わっているのと、1000位と1003位が入れ替わっているのだと、前者のほうを重要視したくなりますが、考慮できていないわけです。
そこで、LambdaRankではこの勾配を次のように修正しています。
\lambda_{ij}:=\frac{-\alpha}{1+e^{\alpha(s_i-s_j)}}|\Delta\mathrm{NDCG}_{ij}|
- $|\Delta\mathrm{NDCG}_{ij}|$: $i$と$j$の位置を交換したときのNDCGの変化量
NDCGの変化量を係数に入れることで評価指標をそのまま考慮しにいっているわけです。（NDCG以外も使えるようです）
このようにLambdaRankでは勾配を直接修正した手法になっているので、論文内でも明示的な目的関数の式は見つかりませんでした。
まとめると、LambdaRankはペアに関するloglossの勾配をNDCG変化量で重み付けしたものと考えればよいでしょう。
LightGBMではobjectiveにlambdarankを指定することで使用できます。
ランク学習のデータの与え方は、回帰や分類と異なり、groupでまとまりを表現してあげる必要があります。
import lightgbm as lgb
import numpy as np
# ダミーデータ
X = np.random.rand(1000, 10)
y = np.random.randint(0, 5, 1000) # 0-5の教師ラベル
group = [10]*100 # 考えたいまとまりのサイズ（この例では各クエリに対して、10個ずつデータが連続して並んでいることを意味する）
# LightGBMデータセットの作成
dataset = lgb.Dataset(X, label=y, group=group)
# ハイパーパラメータの設定
params = {
"objective": "lambdarank",
"metric": "ndcg",
"ndcg_eval_at": [3], # NDCG@3
}
# モデルの訓練
model = lgb.train(
params,
dataset,
num_boost_round=100,
)
参考文献
- From RankNet to LambdaRank to LambdaMART: An Overview
- ランキング学習： RankNetからLambdaRank、そしてLambdaMARTへ
- LambdaRankのLightGBMの実装
- The inner workings of the lambdarank objective in LightGBM
埋め込み（Embedding）
各ユーザーや各アイテムの埋め込み表現（ベクトル）を得ることで、候補生成（実践編参照）や任意のモデルの入力に使うことができます。
Item2Vec（2016年）
アイテム系列の集合からアイテムの埋め込み表現を得るのに使えます。
自然言語処理の分野で、文章から単語のベクトル表現を獲得するための手法としてWord2Vecがあります。
これをレコメンドに応用したものがItem2Vecです。
アイテムを単語、アイテム系列を文章とみなし、Word2Vecを適用することでアイテムのベクトル表現を得ることができます。
from gensim.models import Word2Vec
sessions = [
["item5", "item1", "item2", "item8"], # sessionA
["item5", "item2", "item4"], # sessionB
["item8", "item4", "item8"], # sessionC
]
model = Word2Vec(sentences=sessions, vector_size=64, window=5, min_count=1, sg=1)
item_vector = model.wv["item1"] # item1のベクトルが得られる
候補生成の際には、これにより得られたベクトルのコサイン類似度が近いものを候補に入れることが考えられます。
参考文献
- Item2Vec: Neural Item Embedding for Collaborative Filtering
- word2vecでitem2vecを実装して映画を推薦する
- Item2vecを用いた商品レコメンド精度改善の試み
node2vec（2016年）
グラフからグラフ頂点の埋め込み表現を得る方法です。
ユーザー同士のつながりや、ユーザーとアイテムのつながりグラフなどから頂点（ユーザー, アイテム）の埋め込み表現を獲得したいときに使えます。
手法としては、各頂点からランダムウォークを数回実施した系列をWord2Vecに突っ込むだけです。
ランダムウォークの工夫
いまノードtからノードvに遷移したとする。
... → t → v → x
（図: 論文より引用）
ノードvから次のノードxに遷移するとき、次の重みを使ってランダムに遷移します。
\alpha_{pq}(t,x) = \begin{cases}
1/p, &t=x\\
1, & x \in \mathcal{N}(t) \\
1/q, & \mathrm{otherwise}
\end{cases}
- $\mathcal{N}(t)$: $t$の隣接頂点集合
- $p,q$: ハイパーパラメータ
- $p$: 前のノードに戻る確率を調整するパラメータ（小さいほど前のノードに戻りやすい）
- $q$: グラフを幅広く探索するためのパラメータ（小さいとDFSのような、大きいとBFSのような動き方をする）
この重み$\alpha_{pq}(t,x)$を正規化（合計1）にしたものを、次のノードへの遷移確率としてグラフ上をwalkしていき、その訪問頂点系列（path）を保存してWord2Vecに入力するためのデータセットを作ります。
各頂点について、何回ランダムウォークするか、ランダムウォークの長さをどうするかもハイパーパラメータです。
参考文献
- node2vec: Scalable Feature Learning for Networks
- 【論文要約】node2vec: Scalable Feature Learning for Networks
-
オンボーディング改善に機械学習を活用する〜Graph Embedding（node2vec）による推薦アイテム計算〜
- 実装例が載っている
NN (Neural Network)を使った協調フィルタリング
NeuMF (Neural Matrix Factorization)（2017年）
ニューラルネットワークによる協調フィルタリングモデルです。
一般系である NCF (Neural Collaborative Filtering) が提案され、NCFの下で表現される GMF (Generalized Matrix Factorization) が提案されました。（GMFの特殊ケースがMF）
また、Deep NNで協調フィルタリングを作るために、NCFの MLP (Multi-Layer Perceptron) バージョンを提案しています。
GMFとMLP版NCFを組み合わせたNeuMFは以下のような構成になってます。
（図: 論文より引用）
左側がGMF、右側がMLP部分です。
NCF (Neural Collaborative Filtering)
NNを使った協調フィルタリングの一般系を示したものです。
\hat{y}_{ui}=\phi_{\rm out}(\phi_X(\ldots\phi_1(p_u,q_i)\ldots))
- $p_u:=P^\top v_u^U$
- $v_u^U$: ユーザー$u$の特徴ベクトル
- $P\in\mathbb{R}^{M\times K}$: 潜在因子行列（学習する重み）
- $q_i:=Q^\top v_i^I$
- $v_i^I$: アイテム$i$の特徴ベクトル
- $Q\in\mathbb{R}^{N\times K}$: 潜在因子行列（学習する重み）
- $\phi_x$: NN協調フィルタリング層
- $\phi_{\rm out}$: 出力層
特徴ベクトルは、図ではonehotベクトルで表現されてますが、実装上はEmbedding層にIDを与えればよいです。
また、ユーザーやアイテム固有の特徴から作った連続値でもよいです。
GMF (Generalized Matrix Factorization)
NCFの特殊ケースで、MFの一般化にあたるモデルです。
1層目を要素積にして出力層につなぎます。
\begin{align*}
z_1^{\rm GMF}&=\phi_1(p_u^{\rm GMF},q_i^{\rm GMF})=p_u^{\rm GMF} \odot q_i^{\rm GMF}\\
\hat{y}_{ui}^{\rm GMF}&=a_{\rm out}(h_{\rm GMF}^\top z_1^{\rm GMF})
\end{align*}
- $h_{\rm GMF}$: 学習される重み
- $a_{\rm out}$: 活性化関数
特に、特徴ベクトルがIDのonehotで、$h_{\rm GMF}=1,a_{\rm out}(x)=x$のケースは、単なる要素積の和となり、MFと一致します。
論文では、implicitデータに対して、$a_{\rm out}$をシグモイド関数にしてloglossで学習すると書かれてました。
目的にあった活性化関数と損失を使えばよいです。
MLP版NCF
NCFの特殊ケースで、MLPを使ったものです。
\begin{align*}
z_1^{\rm MLP}&=\phi_1(p_u^{\rm MLP}, q_i^{\rm MLP})
=\left[\begin{array}{c}
p_u^{\rm MLP} \\
q_i^{\rm MLP}
\end{array}\right]\\
z_{2}^{\rm MLP}&=\phi_2(z_1^{\rm MLP})=a_2(W_2^\top z_1^{\rm MLP}+b_2)\\
&\vdots\\
z_{L}^{\rm MLP}&=\phi_L(z_{L-1}^{\rm MLP})=a_L(W_L^\top z_{L-1}^{\rm MLP}+b_L)\\
\hat{y}_{ui}^{\rm MLP}&=\sigma(h_{\rm MLP}^\top z_L^{\rm MLP})
\end{align*}
- $W_x, b_x, h_{\rm MLP}$: 学習する重み
- $a_x$: 活性化関数。sigmoid/tanh/ReLUなど
- $\sigma$: シグモイド関数
NeuMF (Neural Matrix Factorization)
GMFとMLPを組み合わせたものになってます。
\hat{y}_{ui}=\sigma(h^\top
\left[\begin{array}{c}
z_1^{\rm GMF} \\
z_{L}^{\rm MLP}
\end{array}\right]
)
学習方法としては、いきなりNeuMFを全体学習させるのではなく、GMP、MLPをそれぞれ学習させて（事前学習）から全体を学習させるとよいそうです。
それぞれを学習させた重みは全体学習の際の対応する重みの初期値として使いますが、GMFとMLPをつなぐ部分である出力層の重み$h$は以下のような調整が必要です。
h\leftarrow
\left[\begin{array}{c}
\alpha h_{\rm GMF} \\
(1-\alpha )h_{\rm MLP}
\end{array}\right]
- $\alpha$: ハイパーパラメーター
import numpy as np
from keras.models import Model
from keras.layers import Input, Embedding, Flatten, Multiply, Concatenate, Dense
num_users = 600
num_items = 500
latent_dim = 64
# ダミーデータ
num_samples = 10000
user_train_data = np.random.randint(num_users, size=num_samples)
item_train_data = np.random.randint(num_items, size=num_samples)
labels = np.random.randint(2, size=num_samples)
# 入力層
user_input = Input(shape=(1,), name="user_input")
item_input = Input(shape=(1,), name="item_input")
# GMF
user_embedding_gmf = Embedding(input_dim=num_users, output_dim=latent_dim, name="gmf_user_embedding")(user_input)
item_embedding_gmf = Embedding(input_dim=num_items, output_dim=latent_dim, name="gmf_item_embedding")(item_input)
user_latent_gmf = Flatten()(user_embedding_gmf)
item_latent_gmf = Flatten()(item_embedding_gmf)
gmf_vector = Multiply()([user_latent_gmf, item_latent_gmf])
# MLP
user_embedding_mlp = Embedding(input_dim=num_users, output_dim=latent_dim, name="mlp_user_embedding")(user_input)
item_embedding_mlp = Embedding(input_dim=num_items, output_dim=latent_dim, name="mlp_item_embedding")(item_input)
user_latent_mlp = Flatten()(user_embedding_mlp)
item_latent_mlp = Flatten()(item_embedding_mlp)
mlp_vector = Concatenate()([user_latent_mlp, item_latent_mlp])
mlp_vector = Dense(128, activation="relu")(mlp_vector)
mlp_vector = Dense(64, activation="relu")(mlp_vector)
mlp_vector = Dense(32, activation="relu")(mlp_vector)
# NeuMF
predict_vector = Concatenate()([gmf_vector, mlp_vector])
prediction = Dense(1, activation="sigmoid")(predict_vector)
neumf_model = Model(inputs=[user_input, item_input], outputs=prediction)
neumf_model.compile(optimizer="adam", loss="binary_crossentropy", metrics=["accuracy"])
neumf_model.summary()
neumf_model.fit([user_train_data, item_train_data], labels, epochs=5, batch_size=256)
参考文献
NGCF (Neural Graph Collaborative Filtering)（2019年）
ユーザーとアイテムの2部グラフ（左図）の接続情報を使って、埋め込み表現（Embedding）を伝播させることでユーザー・アイテム間の相互作用を考慮するNGCFが提案されました。
各頂点から$l$ステップ先の接続情報まで考慮（右図）します。
（図: 論文より引用）
論文内の式を図にまとめると、次のようになります。（クリックして拡大してご覧ください）
- $\odot$: 要素ごとの積
- $\mathcal{N}_u$: $u$の隣接頂点の集合
- LeakyReLU: 活性化関数
\mathrm{LeakyReLU}_\alpha(x)=\begin{cases}
x, &x\ge 0\\
\alpha x, &x<0
\end{cases}
これでモデルがわかったと思います。
損失関数にはBPRを用いていました。
論文内では、実装をしやすくするために各層をまとめて行列表記した式も載っていました。
実装する際は著者の実装コードと共に参照するとよいです。
参考文献
- Neural Graph Collaborative Filtering
- 論文著者による実装（tensorflow実装）
- pytorch実装
- 論文の再現実験: Neural Graph Collaborative Filteringを実装してみた
- 【論文要約】Neural Graph Collaborative Filtering
LightGCN（Light Graph Convolutional Network）（2020年）
NGCFから複雑な要素を取り払ったモデルとなってます。
各層の処理が隣接頂点（ユーザーorアイテム）の和を取るだけになりました。
そして、各層の結果を結合する際に重み付き和を取るようになりました。
重み$\alpha_k$は学習させてもいいし、ハイパーパラメータでもよいそうですが、論文では単純平均となるように$\alpha_k=1/(l+1)$としています。
- LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation
- 論文著者による実装
- 【論文要約】LightGCN: 推薦システムのためのシンプル化したGCN
近似最近傍探索（ベクトル検索）
登録したベクトル集合に対して、任意のベクトルを与えたときに近いベクトルを上位N件返してくれるのが最近傍探索です。
高速化のために近似計算したものを近似最近傍探索といいます。
pythonではいくつかのライブラリがあります。
小さなデータセットではsklearnのNearestNeighborsを使えばよいですが、大規模なデータではfaissなどの高速なライブラリの使用が求められます。
# pip install scikit-learn
import numpy as np
from sklearn.neighbors import NearestNeighbors
# ダミーデータ
data = np.random.rand(1000, 5)
# 上位10件を取得するモデル
nbrs = NearestNeighbors(n_neighbors=10, algorithm="ball_tree", metric="euclidean")
nbrs = nbrs.fit(data)
# クエリベクトル
query = np.random.rand(1, 5)
# 近傍探索の実行
distances, indices = nbrs.kneighbors(query)
# pip install faiss-cpu
import numpy as np
import faiss
# ダミーデータ
dim = 128
data = np.random.rand(1000, dim)
# インデックス作成
index = faiss.IndexFlatL2(dim)
# より効率なindex
# index = faiss.IndexIVFFlat(faiss.IndexFlatL2(dim), dim, 100, faiss.METRIC_L2)
# index.train(data)
# インデックスに追加
index.add(data)
# クエリベクトル
query = np.random.rand(1, dim)
# 近傍探索の実行
distances, indices = index.search(query, k=5)
GCPではVector Search (Vertex AI Matching Engine)があり、いくつか使用例が見つかりました。
- Vertex AI Matching Engine を利用したニュース記事のレコメンデーション
- Vertex AI Matching Engine: フルマネージドで利用する Google のベクトル検索
- Vertex AI Matching Engineをつかった類似商品検索APIの開発
AWSではAmazon OpenSearch Serviceでサポートしているようです。
評価指標
ランキング学習、レコメンドの評価指標によく使われる評価指標を書きます。
モデルの出力値の上位k件について見る場合、NDCG@kやAP@kなど@kを付けて表現されます。
NDCG (Normalized Discounted Cumulative Gain)
2つ定義がありますが、新しい方の定義を理解しやすい形で載せます。
$$
\mathrm{DCG_k}(m)=\sum_{i=1}^{k}\frac{2^{y_{m_i}} - 1}{\log_2 (i+1)}
$$
- $y$: 教師ラベル
- 実際のユーザーの評価値や0/1ベクトル
- $m$: モデルが出力したアイテムindex列
- モデルの出力値が$\hat{y}$のとき、$m=\textrm{argsort_by_descending}(\hat{y})$
（評価値の高い順に推薦するため降順argsortでアイテムのindexが得られる）
- モデルの出力値が$\hat{y}$のとき、$m=\textrm{argsort_by_descending}(\hat{y})$
- 大きいほどよい
NDCGはDCGの最大値が1になるように正規化した指標です。
$$
\mathrm{NDCG_k}(m)=\frac{\mathrm{DCG_k}(m)}{\mathrm{DCG_k}(m^*)}
$$
- $m^*$: 最適なアイテムindex列
- $m^*=\textrm{argsort_by_descending}(y)$
参考文献
AP (Average Precision)
$y$を0/1の教師ベクトルとする。（1: 上位に出したい、0: 上位に出したくない）
$m$をモデルが出力したアイテムindex列とする。
Precision@k: 上位$k$個についての精度（適合率）
\mathrm{P}_k(m) = \frac{1}{k}\sum_{i=1}^k y_{m_i}
- 推薦した上位k件のうちラベル1を含む割合です
Average Precision@k: ラベル1のデータに対してのみ、上位$k$件について順に、Precision@iの平均を考えた指標
\mathrm{AP}_k(m) =
\frac{1}{\min(k, y^\top1)} \sum_{i=1}^{k} \mathrm{P}_i(m) \cdot y_{m_i}
- $y^\top1$: 全体の1の数
- 大きいほどよい
複数のクエリに対して評価する場合で、APの平均を取ったものをMAP（Mean AP）といいます。
（APが特別というわけではなく、複数クエリの場合NDCGでも平均をとって評価することになります）
参考文献
実践編
ここまでで基礎技術を学んだので、次は実践編です。
ここまで紹介した技術は、レコメンドに使える技術や、それ単体がレコメンドモデルなものもありましたが、実際に単体のモデルで十分かどうかは試してみないとわかりません。
ここでは、以下のコンペからモデルの作り方の例を学びます。
また、最後に実務で注意することを述べて締めます。
モデル作成
ここでは機械学習モデルをどのように学習させるかを説明します。
問題設定として、「ユーザーの閲覧系列から、次に閲覧し購入する可能性が高い商品のリストを提示したい」とします。
簡単のため購入が起きたらセッションは切れるものとしてます。
レコメンドアルゴリズムを作る手順は、以下の流れを行う事が多いです。
- 候補生成: データセット作成
- リランキング: 学習
候補生成
よくある機械学習の問題では、入力と出力のペアを用意して、それをモデルに学習させます。
レコメンドでも同様に入出力のペアを作るわけですが、「購入したデータに比べて、購入しなかったデータが無数にあり膨大すぎる」という難しさがあります。
イメージしやすくするために、たとえば、「直近の商品の閲覧系列 と 任意の商品$i$を入力すると、その商品$i$の購入確率を出力するモデル」 を作って、購入確率の高い順に商品のリストを提示することを考えるとします。
仮にこのモデルを作れたとして、推論時の処理を考えると、1つの閲覧系列に対して、すべての商品をモデルに入力する必要があり、商品数が膨大な場合かなり大変です。
学習時には、すべての系列に対して、購入しなかった商品まですべて用意してからバッチ学習する場合、膨大すぎて扱いきれないという問題もあります（オンライン学習やミニバッチ学習の手法なら、ミニバッチ作成時にサンプリングすればよいのだが）。
以上の理由から、レコメンドモデルを学習する際は、まず必要そうな商品の候補に絞る処理（候補生成）がよく行われます。
候補生成では、以下のようなアイデアが使われます。
- 人気アイテム
- 共起
- 遷移確率
- embedding類似度
人気アイテム
全体で人気なアイテムは、みんなに購入されやすいので候補に追加します。
もし商品カテゴリのような付加情報が使える場合、商品カテゴリごとの人気アイテムを候補にするというのも有効です。
共起
行動系列で毎回一緒に登場する（共起）アイテムは関連性が高く、購入される可能性が高いといえます。
共起するアイテムの計算方法は、次のように行えます。
この図の説明では、候補生成の際に、すべての閲覧アイテムに対して共起行列を結合しましたが、末尾N件に絞るのも有効です。
遷移確率
最後に見たアイテムから、次に遷移しやすいアイテムを候補とするために、ログデータから遷移確率を計算します。
遷移確率の計算は次のように行えます。
この図の説明では、1ステップ先の遷移確率のみを扱いましたが、2ステップ先も考慮することも有効です。
2ステップ先の遷移確率の計算方法を2つ紹介します。
- ログデータから直接2ステップ先の遷移先のカウントをして正規化する
- 1ステップ先の遷移確率行列を2乗する（マルコフ連鎖: N乗すればNステップ先の遷移確率が得られる）
embedding類似度
アイテムの画像や説明文などからアイテムのembeddingが得られる場合や、item2vecを使ってアイテムのembedding表現を獲得して、アイテム同士のコサイン類似度が高いものを取ってくることも有効な可能性があります。
リランキング
候補生成したあとは、それらのアイテム候補を順位付けするために学習します。
初手LightGBMを使って学習すると決めたとすると、以下を考えることになります。
- ターゲット（教師ラベル）
- 特徴量
- 学習方法
ターゲット（教師ラベル）
0/1のバイナリラベルを使うのが一番簡単です。
セッションと候補のアイテムペアに対して、実際にアクションが起きていれば1、そうでなければ0を付与します。
バイナリ以外だと、各セッションに対して、候補アイテムの順位を何かしらの計算方法で作る必要があります。たとえば、候補生成で使ったスコアを基準に使う、セッション内のviewの回数を使うなどがありそうですが、何を信じればいいかわからないため難しそうです。
特徴量
モデルに入力する特徴量について考えます。
以下の3つの軸それぞれで特徴量を考えられます。
- 候補アイテムの特徴量
- 全体の人気度
- Embedding
- セッションの特徴量（閲覧系列から作成可能な特徴量）
- 系列に含まれるアイテムの特徴ベクトルを集約したもの
- 発生した行動の個数や回数
- セッション x 候補アイテムの特徴量
- 最後のアイテムと候補アイテムのペアに対する特徴（遷移確率や類似度など）
- シンプルなモデルの予測値（協調フィルタリング系の手法など）
どれにも言えることですが、候補生成で作ったスコアを特徴量に再利用できます。
学習方法
ターゲットが2値の場合、たとえば次のアプローチがあります。
- 分類タスク
- ランク学習
2クラス分類タスクとして解いた場合、購入するかどうかを分類するモデルができるため、購入確率を出力するモデルができます。
購入確率の高い順に提示することで、レコメンドを実現できます。
LightGBMを使う場合、binaryを指定します。
ランク学習として解く場合、順位付けを学習してくれて、モデルは順位のスコア（実数値）を出力します。
モデルの出力値の高い順に提示することで、レコメンドを実現できます。
バイナリラベルなのにランク学習？って思う気持ちが湧くと思いますが、分類モデルとは目的が異なり、並び順に対しての損失を考えているため、本来の目的に合っており有効です。
（2値ラベルの分類タスクを解きたいときに、回帰ではなく分類で解く気持ちに近い）
LightGBMを使う場合、lambdarankとrank_xendcgがランク学習の目的関数として指定できます。
参考文献
サービスにレコメンドを入れる前に
あなたはある会社でAI技術者として働いています。
あるサービスの担当者から「ユーザーにおすすめを表示したい」と言われました。
さて、どうしますか？
目的の明確化
いきなりレコメンドモデルを作ってしまってませんか？
レコメンドモデルは一度作ってリリースすると、ずっとシステムの面倒を見なければならず、モデルによってはかなり負担です。
次の項目を確認するといいでしょう。
- 何を最大化したいの？
- クリック率？購入確率？Retention Rate？
- 多様性や被覆率の考慮も必要？
- その目的を達成するのに本当にレコメンドが必要？
- 単純な人気順、新着順でも十分？
- 注力したい対象は？
- 新規ユーザー向け？既存ユーザー向け？
- 新規アイテム向け？既存アイテム向け？
モデルの選定
モデルを作る際にいきなり完璧なものを作る必要はなく、有用性の検証のために簡単なモデルから試す（MVP）という動き方も重要です。
- いきなり重たいモデルを開発する必要はない
- 軽いモデルを導入して効果があるとわかってから改善すればよい
- いきなり凝ったモデルをリリースしてしまうと、シンプルなモデルにするのに心理的な抵抗がある
- 開発コスト、メンテナンス性、定期更新の必要性は？
- 一度開発してしまうとずっと面倒を見ないといけなくなる
凝った複雑なモデルになると理解できる人が自分しかおらずSPOFに繋がりますし、毎日バッチ更新を行うようなモデルであれば、エラーで学習が落ちたときに原因を探るのも大変になります。
あとがき
レコメンドは学ぶことが多すぎて大変でした。
入門としてまとめましたが網羅性はありません。
たとえば、非負値行列因子分解（NMF）も基礎だと思いますが省略しました。
その他、ここに書ききれないこととして、ロングテール、多様性を考慮した推薦や、マッチングサービスに使う相互推薦などがあります。
ニュース等で耳にした話でいうと、Twitterのレコメンドアルゴリズムが公開された件や、Two-Towerモデルなどレコメンドの世界は幅広いです。
また、系列のレコメンドではBERT4RecやTransformers4Recも気になりますね。
全体の参考文献