論文選讀 — Real-Time Personalization using Embeddings for Search Ranking at Airbnb

calendar 2018-09-03 · 3 min read · Programming Machine Learning Paper Data

這是我第一次嘗試的系列，因為我工作上也是做推薦系統相關，讀到這篇覺得有很多地方的想法很有趣與實用，因此嘗試寫一篇來介紹。

這篇是 Airbnb 八月底在KDD 2018 發表熱騰騰的 paper，他們試圖建立使用者與房間的 embedding，以此作為搜尋排序的基準。原文請參考 https://dl.acm.org/citation.cfm?id=3219885 。

TL;DR 
Airbnb 用基於 embedding 的推薦方法提升了 21% 的點擊率。

主要組成

使用者 user_type embedding

根據旅遊市場的狀況，一般人一年約旅行 1~2 次，因此針對個別使用者訓練 embedding 是不可行的方案。

他們採用 Many-to-one rule-based mapping 來將使用者分組，這意味著 相同分組的使用者會擁有相同的 user embedding。（後面會提到幫使用者分組的規則）

房間 listings embedding

採用與 user embedding 相同長度的 vector，如此才能算相似度等。主要目標是要包含房間的房型、價位、地點等資訊。

房間類型 listing_type embedding

與 user_type embedding 相似，這個會用許多個規則來幫房間分類，一樣是後面會提到。

訓練資料

使用者點擊序列 click session

單一使用者在單次不中斷的瀏覽中，按照點擊的順序整理成一個序列（sequence），若是兩個點擊間隔超過 30 分鐘則切為不同的 session。其中又分為沒有下訂的 exploratory session，以及最後下訂的 booking session。

資料格式如下，其中每一個 click 都是一個房間物件的編號（listing_id）。

[

    [click 1, click 2, click 3, ..., click m],

    [click 1, click 2, click 3, ..., click n],

    ...

]

方法

Skip-gram model

使用 Skip-gram 的模型，給定當前的點擊後會預測前後 n 個點擊，是一種條件機率的應用。

假如當前是第 i 個點擊，模型要預測從 i-n 到 i+n 的點擊。

Negative sampling

除了對於序列中 positive 的點擊計算以外，會再從所有物件（entire vocabulary）中隨機抽樣一些物件作為 negative 結果，這樣可以避免對於所有物件計算，可以顯著的減少計算複雜度。

Global context

如果序列中點擊的物件最終有被下訂（booking），那麼這個點擊就會作為全域的 context，不論是否在前後 n 個點擊的 sliding window 中，都會跟當前物件計算機率。

使用者通常單次搜尋只會找單一市場內的物件，例如預計要停留的城市。因此 positive 有很高機率是同一個市場，而隨機抽樣的 negative 則為其他市場。

他們發現如此一來會對成果造成負面的影響，因此再額外加入一些來自相同市場的隨機抽樣 negative 結果。

Cold start listing embedding

每天 Airbnb 上都有許多新的物件被新增與啟用，但這些物件還沒被點擊過因此沒有 embedding，於是他們想辦法利用了現有的 embedding。

在增加物件時，會需要輸入一些資訊（如房型、價格、地點等），他們依據 3 個方圓十英哩內最相似的物件，取三者 embedding 的平均來作為新物件的 embedding，如此一來可以涵蓋到98% 以上的新物件。

Examining listings embedding

首先會用 K-Means 將 embedding 集合，看地理位置相關性是否有被編碼（encoded）在 embedding 中。同時他們發現這集合對於他們在重新定義市場時很有幫助。

再來用 cosine similarity 來計算幾種不同的相似度，例如 LA 不同房型的物件還有不同價位的物件。從計算結果來看發現，所有結果都對相同類型或價位的物件有最高的相似度。

從上圖結果來看，確實房型與價位的差異有很好的被編碼在 embedding 中。

同時他們也建立了一個測試用的工具，可以找到相似的物件，提供給線上的測試用。詳細可參考影片

模型總結

整合上面所述的所有方法，在 skip-gram model 加上 global context 後的模型如下圖，click session 中的每次點擊最多會有 2n+1 個點擊做為 positive 的集合。

而最後的 objective function 則包含了四個部分

  1. 當前物件與前後 n 個點擊的 positive 集合Dp
  2. 隨機取樣的 negative 集合Dn
  3. 作為 global context 的點擊 Vlb
  4. 從相同市場隨機取樣的 negative 集合Dmn

User type and listing type embedding

Short-term user interest

前面所述基於 click session 訓練出來的 embedding，可以得到使用者的短期喜好（short-term user interest），讓使用者可以得到與當下物件相似的物件。

Long-term user interest

對於個人化推薦來說，使用者的長期喜好也很重要，因此他們使用訂房紀錄來訓練，只是會遇到幾點問題

  1. booking session 遠少於 click session，且在使用者只訂房過一次的狀況也無法訓練
  2. 物件需要至少 5–10 次的下訂紀錄才足以被訓練，但是平台上有大量物件是少於這次數。
  3. 最後是在較長的時間區間中，使用者的行為也許會有改變，例如因為職涯發展而有不同的價位選擇

基於以上幾種理由，在長期喜好也是使用 listing_type 而不是個別的 listing_id。利用 rule-based mapping 來幫物件分類。

而使用者的分類（user_type）也是使用類似的方法，但如果是新加入的使用者，因沒有過去的下訂紀錄，只會採用分隔線上半部的規則來進行分類。

他們的分類規則都是用數據分析的方法，使分類的涵蓋率更高、並且把每個項目中每個類別的分佈平均，因此例如在房間分類中價位的項目，每個級距的幅度不太一樣。

Training procedure

由於 user_type 與 listing_type 都可能會隨著時間改變，訓練資料保留當下的狀態，每一筆資料為同一個使用者按照時間排序的訂房資料，每一項訂房紀錄都是當時使用者

[u_type1 l_type1, u_type2 l_type2, ..., u_typem l_typem]

使用此資料作為 positive 外，在加上隨機的 user_type 或 listing_type 作為 negative 結果。與 click session 不同，booking session 通常已經包含了不同的市場資料，不需像 Congregated search 中另外抽取相同市場的其他作為 negative。

Explicit negative for rejection

不像 click session 只包含了房客方的偏好，booking session 包含了屋主方的偏好，也就是屋主可以接受或拒絕房客方的下訂請求。通常房東會拒絕的原因包含：房客過低的評價、房客資料填寫不完整、房客沒有大頭照等等，這些也有在分類 user_type 的規則中。

房東的拒絕行為也可以用於將屋主的偏好編碼在 embedding 中，這樣做的目的是因為有些物件對於一些 user_type 比較不敏感，例如沒下訂紀錄、個人資料未完成或評價低於平均的房客。

如此一來讓不敏感的物件與這些房客的 vector 更為靠近，減少這些房客之後被拒絕的機率，以最大化訂房的機會。

實驗 Experiments

上面已經說明完了 listing embedding 及 user_type, listing_type embedding 的做法跟組成，以及線下評估（Offline evaluation）跟線上推薦工具的影片。這兩種 embedding 的應用方法都已經成功地部署在線上環境。

訓練 Listing embeddings

他們使用了 8 億筆 click session。

首先把已登入的使用者紀錄個別整合並按時間排序，然後把這一個個巨大的以排序列表按照「30 分鐘沒動作」的規則切成多個小的列表。

接著將意外或過短的點擊剔除，例如使用者在物件頁面停留低於 30 秒。再將有兩個以上點擊的 session 保留。最後把這列表匿名化，把其中的 user id 去除。

他們發現將 booking session 用五倍於 exploratory session 的過抽樣（oversampled）以後，在線下評估中可以取得最佳結果。

每日訓練 Setting up daily training

他們使用 450 萬個 Airbnb 上的物件，來訓練 listing embedding，並且依靠線下評估來調校。

訓練使用 sliding window 來涵蓋了數個月的資料，藉由每天處理並加入前一天的搜尋紀錄，並且剔除最舊的資料，使訓練資料保持在最新的狀態。

他們每天都會在開始訓練前，對每一個物件重新隨機產生初始的 vector（使用相同的 random seed）。因為他們發現每天從頭開始訓練模型的成效會最好，而不是使用既有的 vector 做 incrementally training。每天不同的 vector 不會影響結果，因為他們使用 cosine similarity 而不是 vector 的實際值。

根據實驗的結果，他們的 embedding size 採用 32 維，這是在線下評估成效與搜尋機器上 memory 使用量之前權衡的結果。

Context window 採用 m = 5（參照前後各 5 個 click），並且針對訓練資料跑 10 個 iteration。

為了達成 Congregated search，他們修改了 word2vec 的程式碼，並使用 MapReduce 來訓練（300 Mapper, single Reducer）。

最後整套流程都是依靠 Airflow 來管理與排程。

線下評估 Offline evaluation of listing embeddings

為了快速決定不同的想法（optimization function, hyperparameters, training data construction），他們需要可以快速評估成效差異的方法，因此採用了線下評估的方式。

使用最新的搜尋、點擊與下訂資料來測試排序（ranking）的結果。排序 booking session 時，會追朔下訂前的 17 個點擊到最後的一個，並平均每個點擊排序的結果（越低代表排序越高），他們測試了三種新模型

  1. d32 reg (positive + negative)
  2. d32 book (positive + negative + booking as global context)
  3. d32 book+neg (positive + negative + booking as global context + negative from same market)

從結果可以發現，他們的既有模型 Search Ranking model 需要越多點擊才能達到較好的成效，而使用 embedding 相似度的模型表現更好（特別是在越初期的時候），其中 d32 booking+neg 的模型比其他兩個都還更好。

同時這方法也可以用來評估不同的 training data construction 或 hyperparameters 之類的。

Similar listings using embeddings

在 Airbnb 每個房間的頁面中（如 https://www.airbnb.com/rooms/433392），都會有個相似物件區塊（Similar Listings carousel），用來顯示相似且在指定日期可下訂的推薦內容。

原先使用的模型是透過 Search Ranking model 這模型取得相似物件列表後，再依據價位、時間、房型等條件過濾出可用的項目。

而基於 embedding 新方式的推薦列表是對 embedding space 找出 k-nearest neighbors，會透過計算「當前物件」與「所有相同市場且可下訂的物件」的 cosine similarity，並按照相似度排序。線上環境中，他們將 embedding 的值儲存在所有搜尋機器（search machine）中，以利於平行運算。

而在最後的 A/B Test 結果中，基於 embedding 的方法使該區塊點擊率（CTR）提升了 21%，甚至在有看到該區塊的使用者中，提升了 4.9% 的下訂比率。因此他們決定部署這個方法到線上環境。

後記

這篇的許多方法讓我覺得很有趣，例如從整體以及相同市場隨機抽樣來作為 negative 的想法、可惜沒辦法套用在我們系統的 global context、使用數據分析方法來產生的分類規則等等，這些都是值得我們去學習的方式。

論文最後其實還有關於整個推薦流程的介紹，但這邊就不多說明，有興趣可以看原文。

其實我沒有看過幾篇 paper，如果這篇對你有幫助或是有什麼建議都歡迎在底下回應，感謝各位的觀看。