search

hakubishin3 / papers

3 stars 0 forks source link

Managing Diversity in Airbnb Search #8

Closed hakubishin3 closed 3 years ago

hakubishin3 commented 4 years ago

論文リンク

https://arxiv.org/abs/2004.02621

公開日

2020/03/31

概要

Airbubの検索アルゴリズムの話. 検索結果を多様にしてユーザにより良い検索体験を提供するために取り組んできたことを紹介している.

hakubishin3 commented 4 years ago

モチベーション

オフラインでNNモデルを作ったら, top-kのリスティングには多様性がなかった. 下図は, 検索で上位に入っているリスティングのペアをサンプリングして価格とロケーションのdiffをプロットしたものであるが, 似ているリスティング (diffが小さいこと) に集中していることが分かる.

スクリーンショット 2020-04-09 1 44 34
hakubishin3 commented 4 years ago

関連研究

ランキングの多様性を管理する方法の1つとして, MMRのような方法を使う. https://dl.acm.org/doi/10.1145/290941.291025 ただこれは検索結果がユーザにどう表示されるかという位置的なバイアスを考慮できない.

スクリーンショット 2020-04-09 1 51 19

(右辺第一項はクエリに関連するものを抽出する項, 第二項は相違点検出と冗長性の削除をする項)

α-NDCGはランキング中の冗長なものにペナルティを与える指標になっている. https://dl.acm.org/doi/10.1145/1390334.1390446 だがこれはAirbnbというドメインで使うのが難しい. (アイテムの入れ替えが激しいのと, リスティングを離散的なサブトピックにマッピングすることが難しい)

あとはモデルに文脈情報を追加して多様性を理解することに焦点を当てる方法. https://arxiv.org/abs/1804.05936 https://arxiv.org/abs/1811.04415 試してみたが直接適用は無理だったのと, groupwise scoringの方はレイテンシが著しく増加してしまった.

hakubishin3 commented 4 years ago

diversity metric

多様性を定量化するためのメトリックを定義する. MNRからヒントをもらい, クエリの関連性と, 既に選択したものと類似したアイテムに対するペナルティの線形和を評価に使う.

スクリーンショット 2020-04-09 2 27 38

Airbnbでは上位のリスティングはその順位にあるという理由だけで予約される傾向があるので, 位置的なバイアスを導入する. 経験的に決められた以下のような割引関数を位置的なバイアスとして使っていて, これを元にスコアを調整する.

スクリーンショット 2020-04-09 2 31 21

またNMRでは第二項にmaxを使っているがこの評価指標では平均を使っている. NMRは「ユーザが1つのカテゴリにつき1つのアイテムにしか興味を持っていない」という暗黙的な仮定が貼られていたがAirbnbではそうではないので, その仮定を緩和するために平均を採用.

hakubishin3 commented 4 years ago

Listing Distance Metric

次にアイテム間の距離を定義する. 各アイテムを[価格, 緯度, 経度, 収容人数, バスルームの数, 部屋タイプ]などの要素から成るベクトルとして表現する. 離散値に関しては正規化するためにone-hot-encodingで対応する. これによって解釈しやすい距離尺度を扱えるようになっている.

スクリーンショット 2020-04-09 2 46 41
hakubishin3 commented 4 years ago

Distribution Distance as a Diversity Measure

Top-Kのアイテムの位置や価格の分布をdiversity metricとして使う. 例えば「フロリダ州オーランド」を条件に入れたとして, 人によってはより細かな希望の場所が異なったりする. 家族連れのユーザならディズニーワールドエリアの近くがいいし, 出張しているユーザなら市街地中心部がいい. 理想的には, 各エリアのアイテムの割合がユーザの好みと一致していることが望ましいので, top-kの経験分布と理想的な分布との差をhellinger距離で定義する.

Location Diversity

理想的な分布はユーザの行動履歴から構築する.

スクリーンショット 2020-04-09 3 00 50

Price Diversity

ユーザは様々な価格帯のアイテムを比較して探す. この時ランキング上位にはユーザの期待する価格に比較的近いアイテムが並んでいて欲しいので, 理想的な分布は正規分布を採用する.

スクリーンショット 2020-04-09 3 01 29
hakubishin3 commented 4 years ago

試した手法

Greedy Ranker

MLRの最大化を目的とする. 直接最適化するのは難しいので貪欲的なアルゴリズムを使って計算可能にしている (ようわからん)

Location Diversity Ranker

Airbnbにとって場所の多様性は非常に重要であるため, 以下の損失関数を最適化する.

スクリーンショット 2020-04-09 3 15 10

Combined Loss Function

以下のような設定で最適化を実施する

最初は直接Hellinger距離を損失として使おうとしたが, 各リスティングからバケットへのマッピングは固定で分布中の値として一定であるため, DNNの重みに直接依存せず学習できない. そのため, サロゲートCE Lossを採用する. 各バケットについて, そのバケットの値が目標値を上回っているかもしくは下回っているかどうかをバイナリラベルとして定義して, 各バケットのCElossの重み付け和を損失として使う. 例えばあるバケットのリスティングの総量が目的値を超えている場合, その量を減少させるように (ロジットを減少させるように) ネットワークパラメータを調整する.

これを適用したparwise loss, location distribution loss, price distribution lossを線形和した損失関数を使ってモデルを訓練する.

hakubishin3 commented 4 years ago

試した手法(2)

with Contextual Features

リスティングの属性 (価格, 位置, 部屋タイプ, 定員など) のaggregation (meanやvariance) を特徴量として加える. 気持ちとしては, 近い属性を持つリスティング集合と比較してpriceや位置などがどのぐらい差異があるかを特徴として加える? あるリスティングが他の利用可能なリスティングと比べて多様である場合にそれに応じてランクを上げるかどうかモデルが判断していることを期待して投入していた.

Query Context Embedding

クエリやユーザ特徴と, リスティングのリストを使って埋め込みを行う. 学習は https://arxiv.org/abs/2002.05515 と同じことを行なっている.

スクリーンショット 2020-04-09 17 51 14 スクリーンショット 2020-04-09 17 59 57