でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

LARS: A Location Aware Recommender Systemを読んだ

ICDE2012のBest papersになった"LARS: A Location Aware Recommender System"を読んだのでメモ。
http://www.icde12.org/Site/?page_id=418

内容としては、ざっと言うと、位置情報付きのレーティング(評価したユーザの位置が分かっている)や、位置情報付きのアイテムなどを上手く使って、スケーラブルで精度の高い推薦システムを作るよーっていう内容。

  • モチベーション
    • 位置情報サービス(foursquaretwitter,facebookなど)の普及によって、位置情報を考慮した推薦システムが求められるようになった。
    • 位置情報を加味した評価情報には以下の3つがある。これらを上手く使ってスケーラブルかつ精度の高い推薦システムを作る。
      • spatial user ratings for non-spatial items: 評価したユーザの位置は分かっているが、アイテムの位置は分からない(そもそもない)
        • e.g.) 自宅で、読んだ本の評価
      • non-spatial user ratings for spatial items: 評価したユーザの位置は分からないが、アイテムの位置は分かる
        • e.g.) 以前訪れたレストランの評価
      • spatial user ratings for spatial items: 評価したユーザの位置も、アイテムの位置も分かる
        • e.g.) レストランの評価をその場で
    • 位置情報を加味した評価情報には次の二つの特性がある
      • Preference locality: アイテム(例えば映画)に対する評価は地域ごとに異なる
        • 推薦対象ユーザがいる場所ごとに推薦すれば精度が上がるはず!
      • Travel locality: ほとんどのユーザは近くにある場所にしか訪れない(foursquareのチェックインなど)
        • 推薦対象ユーザから遠いアイテムは推薦対象に入れない(スケーラブル!)
  • 貢献
    • Preference localityとTravel localityを考慮に入れた推薦システムの構築
    • 推薦対象ユーザの位置情報を加味すると、多大な計算コストがかかってしまうため、pyramid structureという構造を取り入れて計算コストを削減
      • pyramid structureの逐次更新方法も示す
    • 推薦対象ユーザと全アイテムとの距離を計算するのにはこれもまた計算コストがかかってしまうため、全てのアイテムと距離計算を行わずにすむアルゴリズムを示す(Early termination)
    • Foursquare、MovieLens(ユーザのZIPコード付き)のデータを用いて実験をし、提案システムが従来のものよりスケーラブルで精度が高いことを示す
  • モデル
    • 基本的に協調フィルタリング(CF)と同じ
    • 入力に推薦対象ユーザの現在位置も必要となるところが違う
      • 推薦対象ユーザの現在位置に近い所で行われた評価情報のみを考慮してモデルを構築する(Pyramid structure)
      • 推薦対象ユーザの現在位置から遠いアイテムは推薦対象に入れない(Early termination)
    • 扱えるクエリとしてはSnap-shot query(一回の入力でひとつの出力)とContinuous queryを想定
  • Pyramid structure
    • 空間をgrid状に区切る多層構造
      • 上位層に行くほど粒度を荒く区切っている(最上位層はひとつのgridで全体を表す)
    • 一つのgridごとに一つのCFモデルを構築する
      • grid内の評価情報のみを用いる
    • 入力された推薦対象ユーザの位置情報を見て、該当するgridのCFモデルを用いてアイテムを推薦
    • 層の数が少なくなれば、管理すべきgridの数が減るため、計算コストが少なくなる。
    • 層の数が多くなれば、管理すべきgridの数が増えるため、よりPreference localityを反映した推薦ができる
    • これらのトレードオフを管理するためにPyramid structureを逐次更新する(余白が少な・・)
  • Early Termination
    • 入力された推薦対象ユーザから遠いアイテムは推薦対象としない
    • これによって、計算コストの削減ができるが、そもそもすべてのアイテムとユーザの距離を計算していてはコストが高い
    • すべてのアイテムと距離計算をしなくてすむアルゴリズムを提案(余白が・・・)
  • 評価実験
    • だいぶ良くなったよ!