Real-time Personalization using Embeddings for Search Ranking at Airbnb

[hakubishin3]

論文リンク

https://www.kdd.org/kdd2018/accepted-papers/view/real-time-personalization-using-embeddings-for-search-ranking-at-airbnb

公開日

2018/07

概要

Airbubの検索アルゴリズムの話. 部屋を貸すホストと部屋を借りるゲストがいるサービスであり, 相互のマッチングをよくするよう最適化したい. もともとはアイテム特徴やユーザ特徴を使ったlightgbmモデル (lambdamarkで最適化) でランキングを作っていたが, item2vecのようにアイテムやユーザタイプをコンテキストとみなして埋め込み空間を作り, その埋め込みベクトルや類似度を特徴量としてモデルに加えることを検討している.

[hakubishin3]

関連研究

ユーザ履歴などのシーケンス情報を文章としてみなしてembedding

• モバイルアプリの推薦 (Yahoo Labs) https://dl.acm.org/doi/10.1145/2872518.2889411
• 音楽推薦 https://dl.acm.org/doi/10.1145/2911996.2912045
• 求人検索 (Linkdin) https://dl.acm.org/doi/10.1145/3109859.3109921
• Item2vec https://arxiv.org/abs/1603.04259

Cold Start用のembedding

item情報 (e.g. title, description) やユーザのメタ情報を使う

• https://arxiv.org/abs/1706.01084
• https://arxiv.org/abs/1709.03856
• https://arxiv.org/abs/1507.08439
• https://www.kdd.org/kdd2017/papers/view/embedding-based-news-recommendation-for-millions-of-users

グラフにしてランダムウォークでembeddingを得る

• https://arxiv.org/abs/1607.00653
• https://arxiv.org/abs/1403.6652

[hakubishin3]

Listing Embeddings

ユーザのクリック履歴を使い, ユーザの短期間のセッションにおける最適化を行う.

Skip-Gram

• ユーザのクリックセッションのシーケンスを収集して1つのセットとする. ここでユーザが30分以内にクリックしている場合連続したクリックセッションだとみなしている.
• 目的は, item id の埋め込み表現を作ること.
• skip-gramモデルを学習する.
• Negative Samplingを実行. negative pairsは用意したセット中の要素をランダムにサンプリング.

Booked Listing as Global Context

• ユーザの行動は, 探索して目的のものを見つけれず終了するパターンと, 目的のものを見つけて予約を入れて終了するパターンがある.
• ユーザのクリックセッションの最後には予約されたitemのclickが存在する. skip-gramでは周辺のコンテキストのみを予測するが, それに加えて予約されたitem idも予測させる.
• skip-gramの損失に, 予約されたitemに対する予測確率のクロスエントロピー誤差を加える.
• skip-gramではパラメータmというwindow sizeがあって, windowをスライドさせて予測するべきコンテキストを変えていくが, 予約されたアイテムはwindowがslideされても常に予測させる. なのでglobal contextと言っている.

Adapting Training for Congregated Search

• オンライン旅行予約サイトのユーザーは滞在したい場所内でのみ検索するので, negative pairのNegative Samplingの時に異なる場所のアイテムのペアが生成されてしまう. positive pairはほぼ同じ場所のアイテムのペアとなるため, 学習するには不都合なデータとなる.
• pair (l, c) において, アイテムl と同じ場所のアイテムからランダムサンプリングしてペアとなるアイテムcを決めるようなロジックで, 新たなデータセットを作成し追加する.

Cold start listing embeddings

• 新しく追加されたアイテムのembeddingは, 部屋のタイプと価格帯が一致していて, かつ新規アイテムに最も距離の近い3点のアイテムのembedding平均を代用する.

[hakubishin3]

User-type & Listing-type Embeddings

ユーザの短期的な行動履歴に基づいたパーソナライズだけでなく, ユーザーの長期的な行動履歴に基づいて検索をパーソナライズしたい. 例えば, 現在ロサンゼルスを条件に検索しており、ニューヨークとロンドンで過去に予約を行ったユーザーがいる場合、以前に予約したアイテムに類似したものを提示できると便利だろう.

問題点

ナイーブには, ユーザの予約履歴を使って埋め込み空間を作ることになるが, 色々と課題がある.

• 予約はクリックに比べると頻度の低いイベントである
• 多くのユーザは過去に1つのアイテムしか予約していない (長さ1のセッション)
• 多くのアイテムの予約件数は10回未満である
• ユーザの好みが時間変化する. 例えばキャリア変化によって価格帯が変化する.

id -> type

• item idをmappingして新たなカテゴリに集約する.
• item, user別々にマッピングのルールを作る.

embeddings in the same vector space

• ユーザの好みの変化を対処するために, user_typeとitem_typeを同一空間に埋め込みする.
• (user_type, item_type) を1セットとして , ユーザの予約履歴を取得して時間でソートする. 時間が経つにつれて同一user_idでもuser_typeが変化していくので, その変化を考慮できる.

Explicit Negatives for Rejections

• ホスト側 (アイテム側) は, 予約したユーザの評判などに応じて予約を拒否することができる.
• ホスト側の明示的なフィードバックも考慮に入れる. 具体的には, あるuser_typeが拒否されたitem_typeをnegative sampleとして扱うことにして, 拒否された履歴を集めたデータセットを学習に追加する.