情報系の知識を烏のように啄む

情報系の知識をたまに投稿します

Real-time Personalization using Embeddings for Search Ranking at Airbnb

目次

論文pdf
学会: KDD18

概要

  • 背景:
    • ゲストとホストなどの二つの面を持つマーケット市場に対して検索結果を最適化する問題はいろんなサービスで存在
    • Airbnb(宿泊施設/民泊を貸し出すサービス)に着目
      • ゲスト面の要望: 「地域,旅行期間,人数」を入力し,予約したいと思われる物件を上位に表示
      • ホスト面の要望: 良いゲストに来て欲しい
  • 目的:
    • ゲスト面とホスト面の要望両方とも最適化された検索結果にしたい!
  • アプローチ:
    • ゲストの短期嗜好: Listing Embedding (ユーザのクリックセッションを利用)
    • ゲストの長期嗜好: User type & Listing type Embedding (ユーザやアイテムのメタ情報でハッシュ化し,ユーザの予約セッションを利用)
    • ホストがどのユーザに対してrejectしたかのデータも活用
  • 結果:
    • オフライン,オンライン共に評価し有効性を確認

詳細

Listing Embedding (短期嗜好)

list: 宿泊施設や民泊リスト

Skip gramモデルで有名なword2vecは,入力単語から周辺単語を予測するNNの重みを用いた分散表現 Listing Embeddingでは,入力物件から周辺物件を予測するNNの重みを用いた分散表現
qiita.com

f:id:t_ina17:20200208000401p:plain
定式化すると目的関数は
f:id:t_ina17:20200208000516p:plain
f:id:t_ina17:20200208000530p:plain

  • N : ユーザ数
  • S : ユーザのクリックセッション集合
  • s=(l_1, ..., l_M) : あるユーザがクリックしたセッションで,M個のlist
  • v : 入力ベクタ
  • v' : 出力ベクタ
  • V : ユニークlistの集合

▽Lの計算がVに比例する → 計算コストを抑えるためにネガティブサンプリングを行う
f:id:t_ina17:20200208001004p:plain

  • c : あるl_iに対して,前後m listで参照した別のlのうち同じユーザがクリックしたかどうか
  • D_p : ポジティブペア(l,c)の集合
  • D_n : ネガティブペア(l,c)の集合

上記は|V|からランダム

Booked Listing as Global Context (上記のに該当)

セッションは基本二パターンに別れる

  • booked session : ユーザが予約に至ったセッション
  • exploratory session : 予約に至らなかったセッション

booked sessionって予約予測に使えそう → global contextとして利用(そのためΣがない)
f:id:t_ina17:20200208001707p:plain

  • l_b : 予約に至ったlist

現状のまま行くと,ユーザは行きたい場所を調べるため

  • D_p : ポジティブペアには,同じマーケットのリストが多く含まれ,
  • D_n : ネガティブペアには,それ以外のマーケットのリストが多く含まれる

そのため,地域バイアスがめちゃくちゃかかる...(地域のみ情報だけ使ってレコメンドすることになりそう)
→ 同じマーケットの中のネガティブも考慮しよう! f:id:t_ina17:20200208002250p:plain

  • D_mn : 同じマーケットの中でのネガティブペア

Cold start listing embeddings

Airbnbはめっちゃ人気なので,毎日listが増えている
ただ,新規listって学習データに利用するクリックセッションが存在しない

そこで著者は,listの3つのメタデータ

  • location: 半径10マイル以内
  • price: 同じ価格帯
  • list type: 同じ部屋のタイプ

を利用,上記の条件を満たすlist集合の分散表現の平均を,新規listの分散表現とする
これにより,新規listの98%以上は分散表現を獲得できる

Examining Listing Embeddings

評価するために,8億セッションを用いてAdapting Training for Congregated Searchの式を利用し32次元のEmbeddingを行う

k-means (k=100)で可視化
f:id:t_ina17:20200208003220p:plain
似た地域でクラスタを形成してそう cosine類似度の平均 f:id:t_ina17:20200208003516p:plain
同じlist typeや同じ価格帯が近くなって良さそう

実際どんな感じ?
f:id:t_ina17:20200208003703p:plain
建設的な雰囲気から見ても良さそう

User type & Listing type Embedding (長期嗜好)

クロス-マーケットでのlist分散表現の類似度

  • 一部はクリックで学習したlisting embeddingが可能かも?
  • ユーザが予約したlistで構成されたセッションから学習するのがより良い?

予約セッションデータを使いたいが,,,

  • 予約セッションデータがクリックセッションデータに比べ圧倒的に少ない
  • ほとんどのユーザが今まで1件しか予約していない (セッションの長さ=1)
  • 少なくとも5-10の共起があるといいが,予約が5-10にも満たないlistが多い
  • ユーザの嗜好は適宜変わる

上記の課題を解決するために...

list_id, user_idをlist_type, use_typeにマッピング

f:id:t_ina17:20200208005331p:plain
list_idのメタ情報から以下のルールでlist_typeにマッピング
list_type = US_lt1_pn3_r3_5s4_c2_b1_bd2_bt2_nu3
これにより,同じメタデータを持つlistはまとめることができデータを確保

f:id:t_ina17:20200208005348p:plain
user_idのメタ情報から以下のルールでuser_typeにマッピング
user_type = SF_lg1_fp1_pp1_nb1_ppn2_ppg3_c2_nr3_l5s3_g5s3
(最初の予約を行ったユーザに対して5つのみでuser_typeを計算)

Train Procedure

f:id:t_ina17:20200208005955p:plain

  • Nb : Nユーザから得られた予約セッション数
  • sb = (u_type1, l_type1), ..., (u_typeM, l_typeM) : 予約セッションデータ(user_typeとlist_typeのtuple)

同様に考えるとuser_typeの方は
f:id:t_ina17:20200208010228p:plain
list_typeの方は
f:id:t_ina17:20200208010256p:plain

Explicit Negative for Rejection

ゲストだけでなく,ホストの要望にも応えたい
→ ふぃーどばっくとしてホストがどのユーザをrejectしたかのデータが存在
→ あるuser_typeに対し,rejectされたlist_typeのデータをネガティブサンプルとして扱う
f:id:t_ina17:20200208010838p:plain

それを組み込むと,
f:id:t_ina17:20200208010920p:plain

実験

Offline Evaluation of Listing Embedding

f:id:t_ina17:20200208011149p:plain
縦軸: 予約物件の順位,横軸: 予約物件までの残りクリック数

  • d32 reg: Skip-gram
  • d32 book: Skip-gram + Booked Listing as Global Context
  • d32 book + neg: Skip-gram + Booked Listing as Global Context + Adapting Training for Congregated Search
  • Search Ranking: 後述

紫の提案手法が良さそう

Similar Listing using Embedding

Similar Lisintgモジュールに対してA/Bテストを行った

  • Listing Embeddingで得られた分散表現でコサイン類似度が近いものをK-NNでlist集合を抽出
  • CTR +21%, book +4.9%

Real time personalization in Search Ranking using Embedding

ランキング学習でラベルには,

  • y=1: 予約した
  • y=0.025: ゲストがホストに連絡したけど,予約しなかった
  • y=-0.4: ゲストがホストにrejectされた
  • y=0.01: クリックした
  • y=0: ビューした

GBDT Lambda Rank
f:id:t_ina17:20200208012000p:plain
f:id:t_ina17:20200208012012p:plain
f:id:t_ina17:20200208012027p:plain
f:id:t_ina17:20200208012044p:plain
f:id:t_ina17:20200208012055p:plain
あたりを素性に追加
f:id:t_ina17:20200208012214p:plain
カバレッジも高いし,importanceも上位に来ているものも存在
f:id:t_ina17:20200208012250p:plain
素性を追加したことで精度向上
オンラインでも試して,予約数が増えたので本番反映

Addressing Trust Bias for Unbiased Learning-to-Rank

読んだ論文を整理したいので定期的に記事にします

目次

論文pdf
学会: WWW19

概要

  • 背景&目的:
    • ウェブ検索でランキング学習(Learning-To-Rank)したい!
    • ユーザのフィードバックの意味を持ち,かつ大量のラベル付きデータがあるのはクリックログなので,クリックログを用いたLTRを行う
  • 問題点:
    • ウェブ検索でのクリックされたドキュメントってクエリとrelevanceがあると言い切っていいのか?
    • 例えば, positon biasや誤クリックが存在
  • 本手法:
    • position biasに対して,既存のPosition-Based Model(PBM)で考慮
    • 誤クリックに対して,PBMに対して Trust biasを導入し定式化
    • 定式化することで出現するパラメータはEMアルゴリズムで推定
  • 結果:
    • Gmailでオンラインテストを行い,既存手法よりもCTR, MRRともに改善

詳細

ランキング学習(LTR)

LambdaMARTやRankingSVMのようなランキングアルゴリズムの場合,以下のような損失関数を最小化することが一般的

f:id:t_ina17:20200206223128p:plain

  • L: クエリqとドキュメントdのペアに対して,relevanceがあるかどうかをrでラベル付けしたデータ集合 (q,d,r)
  • Ω: あるクエリqに対して,マッチングするドキュメントd集合
  • f: ランキングに関する関数

ランキングに関する関数は,具体例として

f:id:t_ina17:20200206223455p:plain

既存研究のPosition-Based Model

現実問題として,データセットLを用意することが不可能
ただ,クリックのようなimplicit feedbackだと大量に取得可能

ここでのデータセットLは,

  • L: クエリqに対して,ポジションkに対するドキュメントdをクリックされたかどうかをcでラベル付けしたデータ集合 (q,d,k,c)

を用意

クリックとrelevanceと関係づけるために,以下を仮定する
f:id:t_ina17:20200206225333p:plain
f:id:t_ina17:20200206225344p:plain

ふんわりとした理解だが,ユーザが検索して目にしたかどうかをEで,関連Rがあればクリックされる

  • Eは目にするのでポジションkに依存
  • Rはクエリとドキュメントに本当に関連があるかどうかなのでq,dに依存

Examineされる確率の逆数で重み付けすることで,positon biasを考慮した損失関数となる

f:id:t_ina17:20200206224654p:plain

同時にAPP, DCGを利用する場合

f:id:t_ina17:20200206224810p:plain

本手法

既存手法と違って,本研究ではrelevanceの変数を以下の二つに分ける

  • R : true relevance (真にクエリとドキュメントの関連度)
  • R_hat : judged relevance (ユーザが観測してユーザが思うクエリとドキュメントの関連度) ← 既存手法のRにあたる

R_hat=1 だからといって,必ずしもR=1とは限らない...
二つに分けることで誤クリックを考慮

judged relevanceの観点から見たPBM

judged relevanceを利用すると,既存のPBMは以下に言い換えられる. f:id:t_ina17:20200206224213p:plain

クリックされる確率は, f:id:t_ina17:20200206224256p:plain

Trust Bias

位置に依存した誤クリックに関するbiasを設定
f:id:t_ina17:20200206230020p:plain
クエリと関連したドキュメントなのに,クリックされない確率は 1-εk+
クエリと関連していないドキュメントなのに,クリックされる確率は εk-

Trust PBM

上記のTrust biasを導入したPBMを考える
クリックされる確率は
f:id:t_ina17:20200206230311p:plain

後述するが,θとε+, ε-の三つのパラメータが必要!

対数尤度を最大となるθとε+, ε-をEMアルゴリズムで推定
f:id:t_ina17:20200206230506p:plain
EMアルゴリズムは Postion Bias Estimation for Unbiased Learning to Rank in Personal Searchでのロジックを利用

Bayes-IPS Correction

Trust PBMでは,クリックされたものが必ずしもクエリとドキュメントが関連したものではないと述べた
なので既存のIPSをそのまま利用すると,真の関連度Rではなく,ユーザが思う関連度R_hatに対して最適化されてしまうので補正項を導入
f:id:t_ina17:20200206230825p:plain

実験結果

データセット

f:id:t_ina17:20200206230907p:plain

実験結果1: 対数尤度で評価

f:id:t_ina17:20200206231006p:plain
f:id:t_ina17:20200206231021p:plain

実験結果2: パラメータ推定

f:id:t_ina17:20200206231115p:plain
examination bias:
PBMと比較して,Trust PBMはpostionの値が大きくなってもユーザが目にする確率は高い

trust bias:
関連する文書を正しくクリックする確率ε+ > 関連する文書を誤ってクリックする確率ε-
ε+はpositionに非依存で,ε-はpositionに依存

実験結果3: オンライン検証

f:id:t_ina17:20200206231420p:plain
各手法で求めたIPSを使って LambdaMARTで予測
PBMと比較して,TrustPBMはMRR, CTRともに改善

クラスタリング: k-means法

学生時代,クラスタリングを専門に勉強していたので,Tipsとしてその一部を載せておきます.

クラスタリングとは?

クラスタリング(clustering)とは,教師無し学習の一種である. サンプル集合を,いくつかのクラスタに分け,内的結合(density)と外的結合(sparsity)の性質を持つ.

f:id:t_ina17:20180101164820p:plain

主にデータ解析手法として使われます.

クラスタリングには,ソフトクラスタリングとハードクラスタリングに分かれます.

ソフトクラスタリング

ソフトクラスタリングは,サンプルが複数のクラスタに属することを許すクラスタリング手法である. サンプルは,各クラスタに属する度合いを出力する.

  • 例: ファジィc-means,GMMなど

f:id:t_ina17:20180101170532p:plain

ハードクラスタリング

ハードクラスタリングは,サンプルがある一つのクラスタだけ属するクラスタリング手法である. 一般的に言われているクラスタリングは,こちらの方を意味します.

f:id:t_ina17:20180101171059p:plain

代表例として,今回の記事ではk-means法を取り上げます.

k-means法

k-means法は,クラスタリングの精度を評価関数として定め,その評価関数を最適化する分割を探索する手法である.

k平均法 - Wikipediaの式を最適化する問題として置き換えている.

{ \displaystyle
argmin_{V_1, ..., V_K} \sum_{i}^{N} \min_j || x_i - V_j ||^2
}

ここでのNをサンプル数,Kはクラスタ数である.

上記の関数は,サンプル{ \displaystyle x_i }が各クラスタの重心{ \displaystyle, V_1, ..., V_K }のうち一番近い重心のクラスタに割り当てることを意味している.

アルゴリズム

  1. 各サンプル{ \displaystyle x_1,..., x_N }に対してランダムにクラスタを割り当てる.
  2. 割り当てたデータを元に各クラスタの重心{ \displaystyle, V_1, ..., V_K }を求める.
  3. サンプル{ \displaystyle x_i }クラスタの重心{ \displaystyle, V_j }との距離を求める.
  4. その距離を元にサンプルに対するクラスタを割り当て直す.
  5. 4の処理でクラスタの割り当てに変化がなければ処理を終了する.

メリット

k-means法のメリットとして以下の2点が挙げられる.

  1. 計算が早い
  2. シンプルなので実装しやすい

デメリット

k-means法のデメリットとして以下の4点が挙げられる.

  1. クラスタリングの結果が1の処理で与えられる初期値に依存する
  2. 事前にクラスタ数を与える必要がある
  3. 高次元空間になるとうまく動かない
  4. 外れ値の影響を受ける

それぞれの対処法として...

  • 1つ目に対して,k-means++法など1の処理を工夫したものが存在する.

k-means++法 - Wikipedia

  • 2つ目に対して,x-means法など重心の近くのサンプルはガウス分布していると仮定し自動でクラスタ数を推定したものが存在する.

X-means: Extending K-means with Efficient Estimation of the Number of Clusters | Carnegie Mellon Univ. (2000)

  • 3つ目に対して,主成分分析など用いて高次元空間を低次元に変換する.

  • 4つ目に対して,サンプルからあらかじめ外れ値を推定し除去する.もしくは外れ値に頑健なクラスタリング手法を用いる.DBSCANが一例で挙げられます. (Spectral Clusteringも外れ値に頑健という噂も... [1703.01028] Outlier Cluster Formation in Spectral Clustering )

さいごに

今回はクラスタリング手法の一例としてk-means法をとりあげました. k-means法にはデメリットが存在するので,問題に対し適切なクラスタリング手法を用いましょう〜