け日記

SIerから転職したWebアプリエンジニアが最近のITのキャッチアップに四苦八苦するブログ

「Context-Aware Recommender Systems」まとめ

今回はRecommender Systems Handbook(第1版)の第7章「Context-Aware Recommender Systems」について読んでまとめました。 第1版第7章の内容は以下で公開されています。

NSF CAREER Award Page

現在は第2版がリリースされています。

Recommender Systems Handbook

Recommender Systems Handbook

なぜこれを読んだのか

これまでユーザベースとアイテムベースの協調フィルタリング(9/229/29の投稿)、コンテンツベースフィルタリング(10/13の投稿)について学んできました。
それらはユーザやアイテムの類似や過去の評価に基いて推薦しています。

しかし、いずれも"今のユーザの状況(コンテキスト)"を反映する枠組みが無く、実際の利用にあたってはギャップを感じます。
例えば、このユーザはいつもならAの居酒屋を好むが、「"今回は昼食時に探している"ので、Bの蕎麦屋を推薦する」「"今回は家族との外食先"を探しているので、Bのファミリーレストランを推薦する」といった考慮ができるべきかと思います。

そのため、推薦システムにコンテキストの概念を説明しているこの本を読み、ギャップを埋めることにしました。
サーベイ論文っぽい内容のため、細かいところまで立ち入らず、「最良かどうかはわからないけども、こうすればこんな状況を考慮した推薦が実装できそうだ」とイメージできることを重視しながら読みました。

1 Introduction and Motivation

これまでの推薦システムの多くは、ユーザとアイテムに関する情報のみがインプットとなっていました。

予測精度を上げるために、ユーザとアイテムの情報に加えて、コンテキスト(時間、場所、一緒にいる人など)の情報を導入したContext-aware recommender systems(以降、CARS)について説明します。

2 Context in Recommender Systems

いろいろな分野の"コンテキスト"

  • データマイニングの分野では、顧客のライフステージ(結婚・離婚、出産、退職など)が重要なコンテキストで、ライフステージが変われば嗜好、ステータス、価値観が変わる
  • Eコマースでは、ユーザやアイテム以外に時間や同行者、天気などの情報をコンテキストとして使う研究もある
    • 特にモバイル環境では、各ユーザの現在位置やその周辺の地理情報、気温などをコンテキストとして扱うことができる
  • 情報検索では、検索ワードと潜在的に関連するトピックのこと
    • 例えば"scikit-learn"や"ロジスティック回帰"、"L2正則化"などで検索されていれば、潜在的なトピックは"機械学習"と予想することができます
    • 検索によって解決したい問題(時間軸が短い)と興味・嗜好(時間軸が長い)をどうやって検索結果に反映させるかが焦点

CARSのモデル

評価値を予測するモデル(ここではRとしています)を定義していきます。

協調フィルタリングなどの従来の推薦アルゴリズムは、ユーザとアイテムによって評価値が定まる、いわば2次元のモデルでした。

  • User: ユーザの属性で、ユーザID、名前、年齢、性別、職業など
  • Item: アイテムの属性で、映画を例にすると、映画ID、タイトル、リリース年月日、監督、ジャンルなど


R:User \times Item → Rating

CARSではそれにコンテキストが加わった3次元のモデルになります。


R:User \times Item \times Context → Rating

映画を例にあげると、コンテキストは以下のような情報です。

  • 映画館: 映画館ID、住所、収容人数など
  • 時間: 日付、曜日、時刻など
  • 同行者: 一人、友達と、恋人と、家族となど

User、Item、Contextはそれぞれ異なる次元数で属性値を持ちます。
下図(原文Fig.2の抜粋)の通り、コンテキスト(ここでは奥行方向のTime)が3次元(Weekday, Weekend, Holiday)になっており、時間帯によって評価値が異なるモデルが表現されています。

f:id:ohke:20171014120811p:plain

コンテキスト情報を取得する

こうしたコンテキストはどうやって得られるものでしょうか。 アプローチは3つあります。

  • アンケートなどでユーザから明示的に取得する
  • 暗黙的に取得する
    • 商品の購入履歴から購入時間を得る、デバイスGPSから位置情報を得る、など
  • 推論から得る
    • おむつと幼児用ミルクの購入履歴から子供がいると推定する、など
    • 推論にはナイーブベイズ分類やベイジアンネットワークが使われます

3 Paradigms for Incorporating Context in Recommender Systems

従来のユーザとアイテムのみの2次元の推薦システムによる推薦は、大きく3つのプロセスで行われます。

  1. これまでの購買履歴などの元データから、評価データ(U×I×R)を取得する
  2. 評価データから、関数(U×I→R)を構築する
  3. 特定のユーザの情報(u)を受け取り、関数を使って推薦するアイテムのリスト(i_1, i_2, i_3, ...)を出力する

CARSでは、コンテキスト情報を追加した評価データ(U×I×C×R)を入力として受け取り、出力は同じく推薦するアイテムのリストになります。
コンテキスト情報を適用するタイミングによって、システムの構成は下図(原文Fig.4抜粋)の通りプリフィルタリング(下図a)、ポストフィルタリング(下図b)、コンテキストモデリング(下図c)の3パターンに分類します。

f:id:ohke:20171014124914p:plain

プリフィルタリング

コンテキスト情報を評価データの選択に使い、関数の構築や推薦(上記プロセスの2.以降)はこれまで通り行う方法です。
つまり、土曜日に見る映画を検索しているなら、土曜日の評価のみを入力データとして使うというイメージです。

コンテキストとして時間(Time)を使うと、評価値の計算はUser、Item、Timeの3値で決まります。 Dは(user, item, time, rating)からなるレコードです。


R^{D}_{User \times Item \times Time}:U \times I \times T → Rating

例えば土曜日だけの場合は以下のように、土曜日だけのデータを入力にして評価値を計算します。


R^{D(User, Item, Time=Saturday, Rating)}_{User \times Item}(u, i)

入力データを前段で絞るだけのため、従来の協調フィルタリングなどと容易に組み合わせられます。

しかし、コンテキストの情報が増えすぎる(細かすぎる)と2つの問題を抱えることになります。

  • あまり意味がないかもしれない(映画を見るのに土曜日と日曜日では大差ないかもしれない)
  • 疎になって十分なデータ数が得られないかもしれない

ポストフィルタリング

評価データの取得と関数の構築(上記プロセスの2.以前)はこれまで通り行い、得られた推薦アイテムリストに対して、コンテキスト情報を使って調整(一部を除外したり、順番を入れ替えたり)する方法です。
例えば、土曜日に見る映画を探していて、その人が土曜日にコメディ映画のみを見ることがわかっているなら、推薦リストからコメディ映画以外を除外する、といったイメージです。

一般化すると、このアプローチではコンテキスト情報(映画を見るのは土曜日)から好まれるアイテムのパターン(土曜日はコメディ映画のみを見る)を見つけ、そのパターンに従って調整する(コメディ映画以外を除外する)アプローチで、大きく2つの方法に分類できます。

  • ユーザとコンテキストの情報とアイテムの属性を利用するヒューリスティックな方法
    • 好みの出演俳優が0人の映画は除外する、好みの出演俳優の数が多い映画を上位に移す、など
  • 特定のコンテキストにおける特定のアイテムをユーザが好む確率を計算するモデルベースの方法

プリフィルタリングと同様に、従来の協調フィルタリングなどと容易に組み合わせることができます。

コンテキストモデリング

コンテキスト情報を含めた関数(U×I×C→R)を構築し、ユーザの情報とコンテキスト情報(c)から、推薦するアイテムリストを出力する方法です。

ヒューリスティックなアプローチ

ユーザやアイテムの情報にコンテキスト情報を加えたn次元のベクトルを作り、(類似度の計算に代わって)ベクトル同士の距離から予測する方式です。

User×Item×Timeの推薦システムを例にとると、予測値r_{u,i,t}は下式で計算します。
Wは重みで、(u,i,t)と(u',i',t')の距離の逆数のため、2つの距離が近いほど重みが大きくなります。 つまり、距離が近い評価値ほど、予測値に大きな影響を与えます。 距離の計算には、ごく一般的なマンハッタン距離やユークリッド距離が使われます。

モデルベースのアプローチ

従来の2次元の推薦システムで使ってきたモデルを多次元に拡張し、マルコフ連鎖モンテカルロ法などの確率的モデルや、決定木やSVMなどで予測するアプローチです。

4 Combining Multiple Approaches

複数のフィルタを使って1つの推薦リストを得る方法について考えていきます。

プリフィルタリングであれば、下図(原文Fig.6抜粋)のようになります。
例えば、(Girlfriend, Theater, Saturday)というコンテキストであれば、c{1}=(Friend, AnyPlace, Saturday)やc{2}=(NotAlone, Theater, AnyTime)などの複数のコンテキストと組み合わせて結果を出すこともできます。
Recommender Aggregatorで組み合わせる方法は2つ考えられます。

  • 特定のコンテキストにおいて、最も適したプリフィルタ1つを選択する
  • 複数のプリフィルタの結果を多数決などで統合する

f:id:ohke:20171015111118p:plain

ただし、コンテキストによって適したフィルタが異なる可能性はあります。
時間であればプリフィルタが適しています(お昼ごはんを食べるお店を探しているのに、17時から営業開始するお店が推薦リストに入ってきたらNGですよね)。 一方、天気はポストフィルタの方が望ましいでしょう(近くのレジャー施設を探しているとすると、雨が降っていたとしても、推薦リストの下位に屋外球場が入っていても良いかと思います)。

プリフィルタを組み合わせる

大きく2ステップのアルゴリズムになります。 なお、組み合わせて使う協調フィルタリングなどのアルゴリズムをAとしています。

  1. トレーニングデータ(ユーザの既知の評価値)を使い、アルゴリズムA単体よりも優れたプリフィルタを選ぶ
  2. 特定のコンテキストにおいて最も性能の高いプリフィルタを選択し、そのプリフィルタを使って学習されたアルゴリズムAを適用して予測する
    • 入力するコンテキストに該当するプリフィルタが無い場合は、全てのデータでトレーニングされたアルゴリズムAを使う(コンテキストを全く考慮しない従来方法と同じ)

ステップ1はさらに3ステップからなります。

  1. 考えうる全てのプリフィルタから、閾値N以上の十分なデータ数を持つコンテキストのセグメントを選別する
    • コンテキストが細かすぎてデータ数が不足するという問題への対策
  2. 選別された各プリフィルタに対してアルゴリズムAを使って予測精度を計測し、プリフィルタを使っていない場合の精度よりも、精度が低いプリフィルタは除外します
    • 予測精度には、F値(適合率と再現率の調和平均)などが使われます
  3. 残ったプリフィルタから、より一般的で、かつ、精度の高いプリフィルタのみをさらに選択する
    • 「土曜日」のコンテキストに基づくプリフィルタと、「週末」のコンテキストに基づいたプリフィルタが存在した場合、
    • 「週末」のプリフィルタの方が「土曜日」のプリフィルタよりも精度が高ければ、
    • 「土曜日」は「週末」に包含されるため「土曜日」のプリフィルタは冗長とみなして除外する

論文では、62人の学生を対象に、時間(weekday, weekend, don't remember)・場所(in a movie theater, at home, don't remember)・同行者(alone, with friends, with boyfriend/girlfriend, with family, others)のコンテキストを含む1457の評価値(映画は202種類)を採取し、通常の協調フィルタリングとプリフィルタを使った協調フィルタリングで、予測値の比較を行っていました。
F値で結果を比較すると、トータルで0.063、プリフィルタを適用できたケースのみで0.095の改善が見られました。

5 Additional Issues in Context-Aware Recommender Systems

最後にCARSの課題を挙げます。

  • 3つのモデルのどれを選択すべきか
  • CARSのコンテキストの情報が加わるため単純な協調フィルタリングに比べると複雑になりがち
  • CARSはコンテキスト情報をユーザから取得する必要があるため、高いインタラクティブ性(要するにグッドなUI)を求められる
  • アーキテクチャまでスコープに入れたハイパフォーマンスなCARSの構築

まとめ

自身の所感についてまとめておきます。

プリフィルタリングを重点的に説明されていますが、協調フィルタリングなどと簡単に組み合わせられ、現実的に実装もできそうです。
一方でモデルベースのCARSについては、自身の理解が追いつかず、ちょっとイメージできませんでした。 具体的な実装を行っている文献を読む必要がありそうです。

また、コンテキストにはどういった情報を使うのが有効的なのかを探すのは大変そうです。
闇雲に細かい分類はいくらでもできてしまいますし、次元数を増やせば学習にかかるコストが簡単に高くなってしまいます。 scikit-learnのGridSearchのように、トライアンドエラーが簡単にできる仕組みなどが必要かもしれません。