カテゴリー: 情報推薦

Recommender Systems: The Textbookの要点まとめ(随時更新)

はじめに

レコメンド関連の書籍を探していた際に、
Recommender Systems: The Textbook (English Edition)の無料公開されているPDFを見つけたので、それについて読んでは追記するスタイルでメモを残していこうと思います。（すごく長くなる予感）

これまで読んできたレコメンド関連の本の中では、説明が丁寧だったり事例が豊富に思います。数式はあまり出てこないですが、言葉でちゃんと説明しようとしているのが感じられます。『AIアルゴリズムマーケティング 自動化のための機械学習/経済モデル、ベストプラクティス、アーキテクチャ (impress top gear)』のレコメンドの章もわかりやすく幅広いトピックが扱われていますが、それに匹敵する本にも思います。

第1章(An Introduction to Recommender Systems)

Goals of Recommender Systems

  • 1.ユーザーとアイテムの組み合わせの評価値の予測問題
    過去のユーザーのプリファレンスデータを使って学習する。未知のアイテムに関しては行列補完問題とも見なせる。
  • 2.上位k個の推薦問題
    あるアイテムに対して、あるユーザーの上位k個のアイテムを推薦する。

推薦システムの第一の目的はプロダクトの売上向上。

  • 推薦システムの運営上ないし技術的な目的
    1.関連性(Relevance)
    2.新規性(Novelty)
    3.意外性(Serendipity)
    4.推薦の多様性(Diversity)
  • 推薦システムの例
    1.GroupLensの推薦
    2.Amazon.comの推薦
    3.Netflixの映画推薦
    4.Googleニュース推薦
    5.Facebookの友達推薦

Basic Models of Recommender Systems

  • 協調フィルタリング(Collaborative Filtering)
    1.メモリーベース
    ・ユーザーベース協調フィルタリング
    ・アイテムベース協調フィルタリング
    2.モデルベース
  • コンテンツベース(Content-Based)
  • ナレッジベース(Knowledge-Based)
    滅多に買われないようなアイテム（自動車、不動産）の際に考える。評価は使わない。その代わり、ユーザーの要望とアイテムの近さや、ユーザーの制約などを用いる。
    1.制約ベースの推薦システム
    2.条件ベースの推薦システム
  • デモグラフィック(Demographic)
  • ハイブリッド、アンサンブルベース(Hybrid and Ensemble-Based)
  • 評価の種類
  • 明示的な評価と暗黙的な評価
  • 欠損値分析との関係性

Domain-Specific Challenges in Recommender System

  • コンテキストベース(Context-Based)
    時間や場所、ソーシャルデータを使う。季節性を考慮したりする。
  • 時間依存(Time-Sensitive)
    1.時間と共に評価は変わる。流行りすたりがある。
    2.特定の時期だけ、特定のアイテムの評価があがることはある。（レインコート、ダウン）
  • 位置情報(Location-Based)
  • ソーシャル(Social Recommender System)
    ネットワーク構造やソーシャルでの繋がり、タグ、組み合わせに基づいている。

Advanced Topics and Applications

  • コールドスタート問題(Cold-Start Problem)
  • 攻撃耐性(Attack-Resistant)
    アルゴリズムをハックされると情報推薦の効率性が阻害される。本来、上がってくるべきものが上がらないので。
  • 集団への影響(Group)
    推薦アルゴリズムは個々人よりも集団のプリファレンスに影響を与える。
  • 複数の基準(Multi-Criteria)
    ユーザーは単一の基準でアイテムを評価はしない。
  • アクティブラーニング(Active Learning)
    ユーザーが評価をしやすいようにするための取り組み、たくさん過去に評価したユーザーがいた場合は、新しい映画に関して評価をしやすいように予測するとか色々。
  • プライバシー(Privacy)
  • 様々な適用領域
    小売、音楽、コンテンツ、web検索、クエリ、デジタル広告

第2章

TBD

第3章

TBD

第4章

TBD

第5章(Knowledge-Based Recommender Systems)

  • コンテンツベースは新しいアイテムの推薦には良いが、新しいユーザーには推薦できない。協調フィルタリングやコンテンツベースは過去の履歴といったデータをベースに扱うが、ナレッジベースはユーザーが何を求めているのかに基づいている。
  • 不動産や自動車、旅行商品などは滅多に購入しないため、評価のデータは十分に得ることができない。
  • 映画はレコメンドされた際に、その理由が明示されなくとも受け入れるが、不動産や自動車は詳細な情報抜きには、そのレコメンドを受け入れることは難しい。
  • ナレッジベースのレコメンドが有効なケース
    1.ユーザーの要望が明確なケース。協調フィルタリングやコンテンツベースでは満たせない。
    2.選択肢が幅広く商品の複雑さが大きい商品のケース。詳細な評価を得にくい。
    3.商品の評価が時間と共に大きく変わるケース。パソコンとか車はすぐ新しいものが出てきたりして評価が変わってしまう。
  • ナレッジベースのレコメンドにおけるユーザーとのコミュニケーション
    1.対話システム
    対話でのフィードバックループのコンテキストからユーザーのプリファレンスを把握する。
    2.検索ベースシステム
    質問に答えることでプリファレンスを把握していく。
    3.ナビゲーションベース
    ユーザーがアイテムに対して反応をしてしていき、その結果に応じて望んでいるアイテムに到達できる。

Constraint-Based Recommender Systems

  • アイテムの属性に関する強い要望や制約を識別する。
  • 制約ベースのレコメンドシステムにおける3つのインプット
    1.ユーザー固有の情報（デモグラ、リスク嗜好）、必須要件（バストイレ別とか）
    2.ナレッジベースの属性情報。アイテムに応じた属性を顧客の属性にマッピングする。
    直接：都心か郊外か→郊外→近隣のものを推薦
    間接：家族の人数→5人以上→寝室が2つ以上のものを推薦
    3.アイテムに関するデータを全部使う
  • 関連した結果を返す際の3つのアプローチ
    1.ユーザーの回答をもとに条件を類推し、ユーザーの要望に加える。（例えば、家族の人数が5以上と回答された場合に、寝室の数は3以上必要だろうとして要望に加える。）
    2.要望をもとにデータベースのクエリを生成
    3.ユーザーの要望に関連したカタログを抽出する
  • 対話のアプローチ
    1.インターフェースを通してユーザーのプリファレンスの初期値を得る。
    2.マッチさせたアイテムを並べてユーザーに示す。なぜそれを表示したのかの理由も付ける。
    3.条件緩和や追加の要望を受け付ける。レコメンドの件数が多すぎたら要件を増やして、少なすぎたら要件を減らす。
  • マッチしたアイテムの並べ方
    効用関数を使ったりする。
    $$ U( \overline V ) = \sum_{j=1}^{d}w_j \cdot f_j(v_j) $$
    \( w_j \)は評価のウェイト、\( v_j \)はマッチした属性の値。
  • 受け入れられない結果や空集合への対応
  • 制約の追加

Case-Based Recommenders

  • 制約ベースのレコメンドとは違い、強い制約がない。良いレコメンド結果になるまでユーザーの要望を繰り返し修正していくアプローチとなる。
  • ケースベースのレコメンドの場合の重要な要素
    1.類似度の指標

    $$f(\overline{T}, \overline{X}) = \frac{\sum_{i \in S}w_i \cdot Sim(t_i, x_i)}{\sum_{i \in S} w_i} $$

    Sは属性の集合で、属性ごとに重みが違う。tはターゲット。xはあるアイテム。

    ・対称
    $$ Sim(t_i, x_i) = 1 – \frac{|t_i – x_i|}{max_i – min_i} $$
    ・非対称

    $$ Sim(t_i, x_i) = 1 – \frac{|t_i – x_i|}{max_i – min_i} + \alpha_i \cdot I( x_i > t_i ) \cdot \frac{|t_i – x_i|}{max_i – min_i} $$

    ・多様性
    1から類似度を差し引いたものが多様性の尺度となる。
    $$D(\overline{X}, \overline{Y}) = 1 – f(\overline{X}, \overline{Y})$$
    2.批評
    ・推薦結果がユーザーに示されてから、批評を通じてフィードバックを受ける。
    ・単純な批評：特徴の一つを変更してもらう
    ・複合的な批評：複数の特徴量を変更してもらう
    ・動的な批評：データマイニングからフィードバックを掴み取る（アソシエーション分析とか）

Persistent Personalization in Knowledge-Based Systems

  • ナレッジベースのレコメンドでの過去ログの蓄積があれば、効用関数や類似度関数、制約の提案、動的な批評に関してパーソナライズすることが可能。

第6章

TBD

第7章

評価の目標に正確度がよく使われるが、ユーザー体験において重要な指標は目新しさや信頼度やカバー範囲やセレンディピティなど、それ以外の指標によるところが多い。正確度は大事な指標ではあるが、それだけでは良いレコメンドシステムを作ることは難しい。

Evaluation Paradigms

レコメンドシステムの評価方法にはユーザースタディ、オンライン評価、オフライン評価の3つがある。

  • ユーザースタディ
    特定のタスクを行い、レコメンドシステムを触ってもらい質問をするなどして、ユーザーからのフィードバックをもらう。ただし大規模に行うとコストもかかるし、参加する時点でユーザーの性質が違う可能性もあり、バイアスが含まれる可能性がある。
  • オンライン評価
    レコメンドシステムを実装したサイトなどで、ユーザーのグループをAとBに分け、アルゴリズムAとアルゴリズムBをそれぞれ用いて、その結果としてコンバージョンレートなどを比較する。バンディットアルゴリズムを使うのも良い。ただ、オンライン評価は実装含めコストがかかる。
  • オフライン評価
    レコメンドアルゴリズムにおいて最もポピュラーな評価方法で、過去のデータにおける評価を行う。当然、オンライン評価のほうが望ましいが、統計的にロバストであろうと観点で非常によく使われる。ただし、セレンディピティや目新しさを評価することは難しい。

General Goals of Evaluation Design

  • Accuracy
    モデルの訓練にも、評価にも使われる。レコメンドシステムにおいても、機械学習の分類や回帰タスクと同様に、ホールドアウトや交差検証などを行って評価する。
    あるユーザーのあるアイテムに対する評価の誤差を以下の式で表す。
    \(e_{uj} = \hat r_{uj} – r_{}uj \)
    なお、Eは評価対象の集合とする。その際、正確度の評価は以下のようになる。

    $$ MSE = \frac{\sum_{(u, j) \in E} e_{uj}^2 }{|E|} $$

    $$ RMSE = \sqrt{ \frac{\sum_{(u, j) \in E} e_{uj}^2 }{|E|} }$$

    なお、他にもランキングベースの評価方法もある。
    ただ、精度が高くても、ユーザーが絶対に買うであろうアイテムしかレコメンドできない場合は、レコメンドシステムの意味合いとしては薄れる。

  • Coverage
    レコメンドシステムが精度が高すぎる場合、一部のアイテムは一部のユーザーに全く推薦されなくなる。
    k点以上の評価を付けるであろうと予測したユーザーの割合は、ユーザー空間でのカバレッジと呼ばれる。
    一般的に、近傍ベースの手法を考えた際に、近傍を広げた場合、精度は落ちてしまうが、カバレッジは高くなる。ようは、精度とカバレッジはトレードオフの関係にある。
  • Confidence and Trust
    予測した評価の範囲として信頼区間が与えられる。予測した値の誤差が信頼区間にマッチしているかどうかで測る。同じアルゴリズムにおいて、信頼区間が狭いものほど良いと判断する。ただし、予測が正確だとしても、評価をユーザーに信じてもらえないと役に立たない。推薦理由がロジカルかどうかが重要となる。
  • Novelty
    ユーザーがこれまで気づかなかったような推薦ができているかどうかを表す指標。オンライン評価として画面上でユーザーに回答してもらうという方法で測るケースが多いが、いつでもその評価を実行することはできない。
    一方、オフラインであれば、それが可能となる。現時点よりも将来に選びそうなアイテムを推薦できるようになれば、それがノベルティに繋がる。
    過去に評価されているアイテムを、正しく推薦されてしまうとノベルティに関するペナルティが与えられるとする。将来時点で評価されるアイテムを正しく推薦できたらノベルティに関してリワードが与えられると考える。ようは将来と過去の予測の正確度の差分でもってノベルティを測ることとなる。
  • Serendipity
    セレンディピティは幸運な発見を意味する。レコメンドの成功における驚きのレベルを測る。セレンディピティはノベルティよりも強い条件で、セレンディピティがある場合、そのアイテムは目新しいが、逆は真ではない。
    オンライン評価の場合、ユーザーからのフィードバックで意外性があったかどうかを測ればいい。
    オフライン評価の場合、コンテンツベースで選んだものではないアイテムがユーザーに選ばれた場合に、セレンディピティがあると見なすことができる。コンテンツベースのレコメンドとそうでないレコメンドの結果の二つを用意する必要がある。
  • Diversity
    推薦リストの中でのアイテムの多様性を測る。多様性が高まれば、ユーザーのニーズを捉える可能性が高まると考えられる。
    多様性はコンテンツを元にしたアイテム間の類似度で測る。全てのアイテムのペアに対しての平均的な類似度が多様性を表す。
  • Robustness and Stability
    偽の評価や時間とともに急激にデータが変化した際に、レコメンドシステムが影響をあまり受けない場合、そのレコメンドシステムはロバストで安定していると見なすことができる。レコメンドシステムの利用者の中には、ランキングを不正に高めることが自身の利益に繋がることがある。
  • Scalability
    近年、暗黙フィードバックも考慮すれば、レコメンドシステムを構築するためのデータは比較的簡単に入手できるようになった。そこで、データの大きさがもたらす問題に関して注意を払う必要がある。
    1.機械学習モデルの訓練時間
    2.予測（推論）時間
    3.計算の際に要求するメモリの量

Design Issues in Offline Recommender Evaluation

  • レコメンドシステムを開発するに際して、データは3つのパーツに分割される。
    1.訓練データ（モデルの構築）
    2.検証データ（モデル選択・パラメータチューニング）
    3.テストデータ（二度漬け禁止）
  • ※豆知識：Netflix Prizeのデータは学習データとテストデータがかなり違っていたらしい。学習データに古いレーティングが入っていて、テストデータに新しいレーティングがあるという状態だったとのこと。
  • Segmenting the Rating for Training and Testing
    ・Hold-Out
    ・Cross-Validation
  • Comparison with Classification Design
    回帰や分類タスクと同様にサンプルセレクションバイアスの問題がはらんでいる。

Accuracy Metrics in Offline Evaluation

  • レコメンドシステムの評価方法としてはランキング系のものが良いが、わかりやすさを重視するならばRMSEが良い。
  • Measuring the Accuracy of Ratings Prediction
    ・MSE
    ・RMSE
    ・MAE
    ・NRMSE
    ・NMAE
  • RMSE versus MAE
    RMSEは異常の影響を受けやすい。一方でMAEは影響を受けにくい。
  • Impacr of the Long Tail
    主要なアイテムによって評価は影響を受けるが、売り上げの大半はロングテールなアイテムであり、主要なアイテムがロングテールなアイテムに悪影響を与えることがありうる。
  • Evaluating Ranking via Correlation
    レコメンドシステムはユーザーに対しアイテムのランキングを提供し、上位k個のアイテムが推薦されることとなる。
    ランキングのための評価指標について。
    1.スピアマン順位相関係数
    2.ケンドール順位相関係数
  • Evaluating Ranking via Utility
    効用関数ベースのランキング評価指標。
    $$ F(u, j) = \frac{max\{ r_{uj} – C_{u} , 0 \}}{2^{\frac{v_j – 1}{\alpha}}} $$
    ここで、\( C_{u} \)はユーザーの平均的な評価とされる。

    $$ R-score(u) = \sum_{j \in I_{u} F(u, j) } $$

    ・DCG(discounted cumulatiove gain)
    $$ DCG = \frac{1}{m} \sum_{u=1}^{m} \sum_{j \in I_u, v_j \leq L } \frac{g_{uj}}{log_2 (v_j + 1)} $$
    \( v_j \)はアイテムjの順位を表す。
    $$ g_{uj} = 2^{rel_{uj} – 1 } $$
    ここで\( rel_{uj} \)は実際の評価が使われることが多いとのこと。

    ・NDCG(normalized discounted cumulatiove gain)
    $$ NDCG = \frac{DCG}{IDCG} $$

Limitations of Evaluation Measures

第8章

TBD

第9章

TBD

第10章

TBD

第11章

TBD

第12章

TBD

第13章

TBD