Learning to Rank for Spatiotemporal Search(pdf)
概要
foursquareによる論文.ユーザのGPS情報とPOI(なんらかの場所情報)を紐付ける.
位置情報と地名を結びつけるのは4sqやらinstagramやらPathで行われているけど,実際は結構複雑.
基本的な方針
ユーザのid,緯度,経度,時間を入力(queryと呼ぶ.文字列を入れて検索するアレは今回対象外)とする.まずは venue (チェックインする場所,建物) の候補地を時空間インデックスから持ってくる.その後, query と venue のペアからd次元の特徴ベクトルを作る.その後関数に突っ込む.求めるのは query-venue の組み合わせに対してユーザがチェックインしたか否かの.
人と場所のモデリングでのベタな方法
そもそも venue の候補地をどうやって持ってくるのか
基本的にはクエリ(ユーザがいる場所)に近い venue を150個持ってくる.しかしこれだけでは問題が多い.
- マンハッタンで150の venue を考えると半径75m以内の範囲を考えなければならない(これは範囲が狭すぎるから難しいということ?)
- venue の中心点を時空間インデックスに登録しているので, venue そのものがでかいと別の場所が近くなる
- 空港の滑走路にいたりすると空港そのものより,空港最寄りの鉄道の駅の方が近くなる
この問題に対処するため,次の対策を取る.
- そのユーザがいる場所から半径1000m以内で過去半年の間にチェックインされた venue も持ってくる
- 1200m以内にある venue でユーザの friend がチェックインしたものも持ってくる
- 大きな敷地面積を持つ venue のリストを持っておいて,数km以内ならそれも持ってくる
時空間インデックス自体はS2 Geometry Libraryを使う.
ランキング
前述したように,クエリi及び venue j についてチェックインしたら1,しなかったら0のラベルを使って学習器を作る.
学習器の特徴量には次のものを用いる.
実験
P@1で評価.ランダムだと0.009,距離が一番近い venue だと0.130,混合ガウス分布で0.193,spatial + temporal の線形回帰で0.230,全部入れた線形回帰で0.434,全部入れたLambdaMARTで0.531.
future work
- venue のカテゴリ情報使いたい
- ユーザのデモグラ属性使いたい
- これらを使えば床屋とネイルサロンが隣同士でも区別できるだろう
- venue 間を移動するといった情報を使ってもっとダイナミクスを高める
- venue の形を考慮したい
- 天気の情報を使って venue の人気度を変化させたい
- 動物園は晴れた日に人気だが,雨の日には美術館が人気になる
- 位置情報検索してイベント情報とかお届けしたい
大規模サービスの元締め大勝利という感じの論文だった. first author の Blake Shaw 氏はGraph Embedding周りが専門でNIPSやらICMLやらに通しまくってる人のようなので,こういう人がデータサイエンティストとしてWeb系の企業で活躍してシステム作って論文書いてるの見ると夢がある.