推薦システム
takumiこのスクラップの目的
推薦システムの基本を理解し，まとめる．
参考書籍（随時追加）
- Deepak K.Agarwal, Bee‐Chung Chen著/島田直希, 大浦健志訳, "推薦システム : 統計的機械学習の理論と実践",共立出版(2018/4).
takumi推薦と検索：プッシュとプル
推薦システムは以下の2モデルに分類されるか，2モデルの組み合わせである．
プルモデル
Web検索クエリのようにユーザーの意図が明確である場合に，意図に会ったアイテムを見つけたり「推薦する」モデル．検索の「もしかして」など．
プッシュモデル
ユーザーの意図が明確でない場合に，システムがユーザに情報を「プッシュ」するシステム．（トップページにおける）おすすめ記事の推薦など．
組み合わせ
ニュースポータルのトップでユーザに記事を「推薦」する場合，ユーザの意図は明確でないのでプッシュモデルを採用する．一方で，ユーザが記事を読んでいるときに，（エンゲージメントを高めるために）関連する記事を「推薦」する場合は，ユーザの読みたい記事の意図はある程度明確なので，プルモデルを採用できる．
まとめ
解決したタスクに応じて，適切なモデル，あるいは組み合わせを選択するべきである．
takumi探索と活用のトレードオフ
推薦システムには「探索と活用のトレードオフ」が存在する．
どういう問題なのか
推薦システムでは，CTRのような応答率をスコアリングに利用する．例えばCTRは「表示されたうち，クリックされた割合」である．問題は，推薦する各アイテムの分散が異なるということである．
つまり，1000回表示され，200回クリックされた(CTR=0.2)と，新たに推薦対象に追加され(*1)，100回表示され，40回クリックされたもの(CTR=0.4)を比較した際に，後者のがCTRが高いのであるから，後者をより推薦すべきであるか？という問題である．一般的に，これはそうではない．また，逆に，CTRが高いものを推薦するような戦略の場合，新たに追加されたアイテムが十分なCTRを計算できるほど表示されず，永遠に推薦されないという飢餓問題も発生しうる．
そこで，推薦するアイテムの内一定割合を探索(exploration)，すなわち，表示回数が少ない（分散が大きい）アイテムなどの応答率を計測する目的で表示し，また一定割合で活用(exploitation)，すなわち，純粋な推薦を行う必要があるのだ．
探索と活用のトレードオフは平均と分散のトレードオフともいえる．
*1 新しく推薦対象に追加されたアイテムは，ユーザにとって新しく，目につきやすいなどの理由から応答率が高くなることがある．これを新奇性という．デプロイ後評価フェーズでは，新奇性に注意する必要もある．
単純な探索-活用戦略
もっとも単純な探索-活用戦略にはランダムバケットとサービングバケットを用いる手法がある．
ランダムパケットは探索に利用され，少数の訪問に対して1/全アイテム数の確率で，あるアイテムをランダムに推薦する．ランダムパケットは応答率の計算に利用する．ランダムパケットの中身の更新は，一定時間(5分など)が経験則的に良いとされている．
一方で，サービングパケットは応答率の高いアイテムを推薦する(*2)．
このような推薦システムをε-greedy法という．εはランダムパケットのサイズである．経験則では1~5%と言われている．
*2 推薦システムでは，同じアイテムをユーザに何度も推薦することを避ける必要性が生じる．ユーザとアイテムの組み合わせに対して，割引係数を導入し，スコアリングに影響させる必要がある．
探索-活用戦略の理論
多腕バンディット問題(MABP)が知られている．これは古典的な強化学習の問題である．
まとめ
推薦システムは教師あり学習のみならず，強化学習の問題をはらんだシステムである．デプロイ前のモデル設計においても，分散の異なる応答率を持つ推薦アイテムをどう扱うかをよく検討する必要がある．
takumi素性ベクトルと協調フィルタリング
推薦システムは素性ベクトルを用いる手法と，協調フィルタリングを用いる手法，そしてその組み合わせ(ハイブリッド法)に分類できる．
素性ベクトル
素性ベクトルベースの手法では，推薦対象のアイテムと，推薦先のユーザそれぞれを素性ベクトル（特徴量）として表現し，アイテム素性ベクトルとユーザ素性ベクトル間の関係を学習し，推論を行う．
素性ベクトルの算出には，one-hot encodingや，bag of wordsなど，よくある手法を用いる．一般にこれらの素性ベクトルは疎（スパース）であり，特異値分解(SVD)や主成分分析(PCA)などの次元削減が有効な場合がある．
協調フィルタリング
アイテムへの評価が似ているユーザは嗜好が似ており，推薦に活用できる．嗜好の似ているユーザーが与えた評価を，推薦におけるスコアリングに活用する手法である．アイテム間やユーザ間の類似度関数を利用できる．
ハイブリッド法
訓練データに十分なユーザ・アイテムの関係データがあれば，協調フィルタリングは素性ベクトルベースの手法よりもうまくいくことが知られている．そのようなウォームスタートの状況で，協調フィルタリングは有効な手法である．
一方で，そのようなデータが十分でないコールドスタート時は，素性ベクトルベースの手法が有効である．
ウォームスタートとコールドスタート，推薦タスクのシナリオ等によって，推薦システムを素性ベクトルと協調フィルタリングの組み合わせによって実装することが有効な場合がある．以下のような手法がある．
- アンサンブル
- 協調フィルタリングを素性ベクトルとして扱う
- 協調フィルタリングの類似度の算出にスコアリングではなく，素性ベクトルを用いる，あるいは，素性ベクトルベースの類似度とスコアリングによる類似度（協調フィルタリング）を組み合わせる．
- 協調フィルタリングを人工的なデータ入力によってコールドスタート時に補完する．
まとめ
実装・運用する推薦システムのシナリオに応じて，素性ベクトルと協調フィルタリングを使い分ける必要がある．
takumi推薦システムのオフライン評価
基本的には機械学習システムの評価と同じ．推薦システムに特異（だと僕が考えた）ものだけを挙げる．
データ分割
いわいる無作為分割によって，訓練・テストに分けることの他に，以下を考えることができる．
- 時間ベース分割・・・過去に基づいて未来を予想するという意味で，推薦システムにとっては都合の良い分割手法である．
- ユーザーベース分割・・・まだアイテムを評価していない新規ユーザに対するモデルの精度測定を目的とする場合，ユーザベース分割は有効である．
- アイテムベース分割・・・上のアイテム版．
metrics
精度指標は推薦システムに向いているか？
RMSEや対数尤度，クロスエントロピー誤差といった，精度指標は推薦システムに向いているとは言えない．推薦システムはアイテムをランキングし，上位のアイテムを推薦する問題（ランキング問題）であるからだ．また，精度指標は推薦システムのパフォーマンス評価に使いづらい（RMSEが0.1ポイント上がったからと言って，どうよくなったのだろうか？）
ランキング指標の導入
そこで，情報検索の分野などで利用されてきたランキング手法を検討する．
大局的ランキング指標
評価の高いユーザ・アイテム対が評価の低いユーザ・アイテム対よりも，上位に順位付けされている度合いを示す．おなじみのPR曲線や，ROC曲線，AUCが利用できる．
また，順位相関を利用する方法もある．これは2つのリストの類似度を表すもので，予測と実際のランキング結果に対して算出できる．順位相関には，2つの順位リスト間のピアソン相関であるスピアマンのρや，2つのユーザ・アイテム対が同じように順位付けされているかを表す，ケンドールのτなどがある．
局所的ランキング指標
各ユーザについてアイテムを個別に順位付けし，高評価アイテムが低評価アイテムよりも上位に順位付けされているかの2値を測定する．その後，ユーザ間で平均を取る．正負の2値を測定しており，バイナリレイティングを対象としている．普通はバイナリレイティングではないので，閾値を用いて正負を決定するか，平均順位相関を計算するなどする．
- 順位
K K K - 平均適合率の平均(mean avarage precision, MAP)・・・アイテムが正のレイティングを持つ順位
K K - 正規化割引累積利得(nDCG)・・・順位
k i p_i(k)=1 n DCG_i=p_i(1)+\sum_{k=2}^{n} \frac{p_i(k)}{\log_2 k} i
まとめ（感想）
推薦システムの評価には大局的ランキング指標や局所的ランキング指標が用いられる．機械学習の文脈ではAUCなどが利用しやすそうだ．しかしながら，推薦システムの本質は強化学習であり，オフライン評価よりは，デプロイ後のオンライン評価が重要そうである．
takumi推薦システムのオンライン評価
MLOpsみたいな話
オンラインバケットテスト
ユーザやリクエストによって異なるモデルを提示する手法．いわいるA/Bテスト．あるいは，2つのモデルの統計的特性が同じかどうかを測定するA/Aテストなどを実施することができる．
オンラインパフォーマンス指標
オンラインバケットテストにおける指標
- CTR
- ユーザ当たりの平均クリック数・・・ユーザの訪問頻度が多い場合，CTRは低下するが，訪問頻度が多いことは良いことなはずである，そこでこの指標を用いることがある．
- クリックするユーザの割合・・・クリックしないユーザにも訴求する推薦の評価
- クリック以外のアクション
- 消費時間
バケットテストの検証
試験結果の健全性をチェックしたり，セグメントごとの指標を確認する．
オフラインシミュレーションとリプレイ
A/Bテストにはコストやリスクがかかるため，シミュレーション代替することがある．その場合は過去の訪問履歴を利用したリプレイ推定量を用いることがある．
まとめ（感想）
MLOpsの話に繋がってくる内容だと思った．実運用を知らないので小学生並みの感想しか浮かばなかった．