スライドメモ:KDD2014 Tutorial "the Recommender Problem Revisited"

Netflixの中の人によるKDD2014 Tutorialの”The Recommender Problem Revisited”のスライド1を読んだので，簡単にまとめてみた．レコメンドのこれまでと現状をひと通り網羅したチュートリアルという感じ．このスライドはKDD2014 Tutorial向けだけれど，今度のRecSys 2014のTutorialでも同様の発表があるようだ(link)．

  • レコメンドの大まかな流れを知りたい人
    • このチュートリアルもいいけど，日本語で書かれたしましま先生の資料の方が丁寧でわかりやすいかも
  • レコメンドの具体的な手法や流行を知りたい人
    • このチュートリアルで興味ある分野の箇所を見て個別にReferenceを当たる

どっちにしろ素人のまとめなので，以下のメモは参考程度にお願いします．

Kdd 2014 Tutorial - the recommender problem revisited

Kdd 2014 Tutorial - the recommender problem revisited from Xavier Amatriain

(追記:2014.10.8) RECSYSのスライドも公開された．

Recsys 2014 Tutorial - The Recommender Problem Revisited

TL;DR

レコメンドのこれまでと現状をひと通り網羅した資料．情報過多の時代においてレコメンドは必要不可欠な技術であり，いまでは従来のレコメンドに加えてパーソナライズやインターフェイスなどの複合要素を考慮したレコメンドが必要になってきた．それにともなって，レコメンド手法としても古典的な協調フィルタリングから，Netflix Prizeにより出現した次元削除の手法，ランキングアルゴリズムやディープラーニングを用いたコンテンツベースのレコメンドなどへと広がりをみせている．

1. The Recommender Problem

  • レコメンデーションは必須
  • レコメンドの定義
    • 今までの定義：ユーザが好きなアイテムを自動的に予測する効用関数を作る
    • これからのレコメンド：今までのレコメンド＋α
      • セレンディピティ（偶然の発見＆ユーザが既に知っているアイテムを推薦しない）
      • ユーザインターフェイス，パーソナライズなど
  • レコメンドの進化
    • 単純なレート付け→ランキング→ページ最適化→コンテキストを含めたレコメンドへ

2. Traditional Approaches

2.1 Collaborative Filtering (CF)

協調フィルタリングの基本

  • 協調フィルタリングの構成要素
    • ユーザがアイテムに付けたレートが基本
    • レートが無くても購買履歴などから補完することもできる
  • アクティブユーザの情報がメイン
  • ユーザ間の類似度を使う
    • 一種のパーソナライズと取れる
    • ピアソンの相関係数/コサイン類似度
  • あるユーザに類似したユーザを探しだしてレート付けされてない作品を推測する
  • ユーザベースの協調フィルタリング / アイテムベースの協調フィルタリング
  • 協調フィルタリングの特徴
    • 長所：最小限の情報で計算できて，だいたいにおいて性能が良い
    • 短所：アイテム数が増えるとスパースになる＆スケールが難しい
      • ユーザ数xアイテム数のうち，値が入っているのはごく僅か(1%以下)

モデルベースの協調フィルタリング Model-based CF

  • Netflix Prize

    • アルゴリズム的にRMSE基準でトップ2つのアルゴリズム
      • SVD
      • RBM
    • 今でもNetflixのレート推定の一部に使われている
      • SVD++とRBMの組み合わせ

  • Simon Funk’s SVD

    • Netflix Prizeで出てきた面白いアルゴリズム（Blogが初出）
    • SVD++

  • Restricted Boltzmann Machines

クラスタリング Clustering

クラスタリング：ユーザを特定の好みごとにクラスタリングして推薦する

  • Locality-sensitive Hashing(LSH)
    • 高次元空間で類似したアイテムをクラスタリングする手法
    • 似たアイテムが近くにくるようなハッシュ関数を探す
    • 最近傍探索(NN)によく使われる
  • 他のクラスタリングアルゴリズム
    • k-means
    • Affinity Propagation
    • Spectral Clustering
    • HDPs

相関ルール Association Rule

  • アプリオリ・アルゴリズムなど

分類器 Classifiers

  • いわゆる普通の分類器
    • 使い勝手が良くて組み合わせも可能だが，トレーニングセットが必要で正則化などが必要
    • ロジスティック回帰，ベイジアンネット，SVM，決定木など

協調フィルタリングの限界 Limitations of Collaborative Filtering

  • コールドスタート問題
    • 他のユーザの評価が十分に無いと機能しない
    • 新しいアイテムなどで推薦が難しい
  • 人気バイアス
    • 既に人気のあるアイテムを推薦しがち

2.2 Content-based Recommenders

コンテンツベースの特徴

  • 長所
    • 他のユーザ情報が不要なためコールドスタートやスパース性を考慮しなくて良い
    • ユーザ独自の好みに合わせることができる
    • 新しいアイテムを推薦することができる
    • レコメンドの理由を説明しやすい
  • 短所
    • アイテムの内容から意味のある特徴量を抽出する必要がある
    • セレンディピティのある推薦が難しい
    • ユーザに最適化されすぎる

2.3 Hybrid Approach

  • Content-based recommendation with Bayesian classifier
  • Hybridization Method
    • (see P.68)

3. Beyond traditional Approarches to Recommendation

3.1 Ranking

  • ほとんどのレコメンドアルゴリズムは推薦するアイテムをソート済みのリストで返すから，レコメンドはランキングの問題とも捉えることができる
  • レートでランキングの順位を付ける
  • RMSEはランキングに使えない(?)
    • Linear modelで考えた時に，RMSEを最小にした結果ランキングに違いが生じる（Predicted RankingとFinal Rankingが違う）
    • (詳しくは図を参照)
  • ランキングを測る指標
    • Normalized Discounted Cumulative Gain
    • Mean Reciprocal Rank (MRR)
    • Fraction of Concordant Pairs (FCP)
  • 最近はランキング指標自体を最適化する研究も

3.2 Similarity

  • SimRank
    • グラフベースの類似度を考える
  • 幾つかの類似度を組み合わせる
    • データごとに様々な類似度がある（e.g. タグ，ユーザの行動，ユーザのレート付け）
    • 組み合わせの時の重みは回帰で学習する

3.3 Deep Learning for Recommendation

3.4 Social Recommendations

  • (詳細は省略)

3.5 Page Optimization

  • どうやって推薦したアイテムを表示させるかというページ構成の話
    • デバイスによって表示できるアイテム数などが違う
  • ユーザの注目度をモデリング，ヒートマップで可視化
  • 限られた状態で何を重視するか
  • 共存させるためのモデル
    • Navigational/Attention Model
    • Personalized Relevance Model
    • Diversity Model

3.6 Tensor Factorization & Factirization Machines

3.7 MAB Explore/Exploit