本文介紹 Airbnb 發表在 KDD 2018 的論文《Real-time Personalization using Embeddings for Search Ranking at Airbnb》。該文獲得了 KDD 2018 Applied Data Science Track 的 Best Paper，主要介紹了 Embedding 技術在 Airbnb 房源搜索排序中的應用。

Airbnb是目前全世界最大的民宿短租平臺，房主發布房源（listing）信息，而旅客可以搜索房源並預訂，房主可以選擇接受或拒絕預訂。整篇文章與Airbnb自身業務特點緊密結合，非常具有工程實踐價值，該文被評為ADS best paper也引起了不少討論和爭議，強烈推薦知乎上的2篇乾貨解讀：

  1. @石塔西：石塔西：如何評價Airbnb的Real-time Personalization獲得2018 kdd最佳論文？
  2. @吳海波：不一樣的論文解讀2018 KDD best paper: Embeddings at Airbnb

這2篇進行了很精彩的「宏觀」解讀，本文則從更「微觀」的視角出發，詳細介紹並探討論文中涉及的諸多工程細節，並進行了一些有趣的思考。

1. Listing Embedding

用戶在Airbnb搜索房源時，相隔時間較短的、連續點擊的房源往往是比較相似的，因此作者希望利用這些點擊信息學習房源的embedding。

從這點出發，定義用戶的點擊會話（click session）：用戶連續點擊的房源序列，且一個點擊會話中用戶連續兩次點擊行為間隔不超過30分鐘，否則就會生成一個新的點擊會話。作者將點擊會話中的點擊房源序列類比看作 NLP 中的sentence，直接使用 word2vec 的 skip-gram 模型從點擊會話中學習Listing Embedding。

這裡不再單獨介紹 skip-gram，具體地，目標函數為

max~ sum_{sin S} sum_{l_iin s} ~[ sum_{-mle j le m, ~i e0} log~P(l_{i+j}|l_i)~], ~~~~~where~P(l_{i+j} | l_i) = frac{ exp( m{v}_{l_i}^T m{v}_{l_{i+j}}^{} ) } {sum_{ l in mathcal{L}} exp( m{v}_{l_i}^T m{v}_{l}^{} ) }

其中S是從N個用戶點擊行為中得到的click session集合，s=(l_1,l_2,...,l_{|s|})， l_i 表示點擊會話中第 i 個點擊的房源， m 表示希望考慮的context窗口大小，m{v},m{v}inmathbb{R}^d 分別表示 input 層和 output 層的Embedding，mathcal{L} 表示所有Listing的集合。

使用Negative Sampling後，目標函數轉化為：

max~ sum_{sin S} sum_{lin s} ~[ sum_{(l,t)inmathcal{D}_p} log frac{1}{1+e^{-m{v}_l^Tm{v}_{t}}} + sum_{(l,f)inmathcal{D}_n} log frac{1}{1+e^{m{v}_l^T m{v}_f}} ]

其中 (l,t)in mathcal{D}_p 表示房源 l 和它的context房源組成的正例對，(l,f)in mathcal{D}_n表示房源 l和從所有房源集合mathcal{L} 中隨機抽樣得到的負例對。

到目前為止，討論的幾乎全是skip-gram的內容，接下來亮點來了，作者結合了兩個Airbnb業務強相關的點對目標函數進行了修改：

    • Book Listing as Global Context Airbnb上的這些點擊會話可以細分為兩種，1）用戶最終預定了一個房源，2）單純的點擊，沒有產生預定行為。作者把預定房源（booked listing ）視為強信息，當作全局的context，即無論context窗口滑到哪裡，預定房源始終出現在context中。
    • Market-Sensitive Negative Sampling 用戶在搜索房源時，通常只限定在某一個具體的market，例如夏威夷，而單純的負採樣是從全局的房源中抽樣。這導致 mathcal{D}_p 中正例對大多來自相同market，而 mathcal{D}_n 中負例對往往來自不同market。為了修正這個偏差，針對每個房源 l ，作者額外再從和 l 相同market的房源中抽取負例。

此時，目標函數轉化為：

max ~ sum_s sum_l [ sum_{(l,c)inmathcal{D}_{pos}} log frac{1}{1+e^{-m{v}_l^Tm{v}_{c}}} + sum_{(l,c)inmathcal{D}_{neg}} log frac{1}{1+e^{m{v}_l^T m{v}_c}} + log frac{1}{1+e^{-m{v}_l^Tm{v}_{b}}} + sum_{(l,c)inmathcal{D}_{m}} log frac{1}{1+e^{m{v}_l^T m{v}_c}} ]

其中 m{v}_b 對應點擊會話中的預定房源，只有產生了預定行為的點擊會話中會有這一項，(l,c)in mathcal{D}_m表示房源 l 以及 從房源 l 相同market的房源集合中抽樣得到的負例對。

??context窗口的概念在word2vec是很重要的，將Book Listing作為Global Context，而無視上下文窗口限制，其合理性體現在哪裡？

思考：一個合理的解釋是，與NLP中單純的句子不同，這裡可以認為整個點擊會話最終「造成」了最後用戶預訂的這個決策，因此會話中的每個click listing都與book listing相關。??Book Listing as Global Context的目的是什麼 ？思考：Airbnb最關注的業務指標是預訂率，而word2vec是非監督的，這個策略的主要動機應該是加入人為的「監督信息」，使學到的embedding更有助於提升預訂率，上面提到的解讀中 @石塔西 也做了相關分析。

  • Listing Embedding 效果

這裡展示學習到的Listing Embedding 的一些特性，具體的訓練參數設置會在第3部分介紹。Listing Embedding 之間的度量使用 Cosine相似度。

位置 對 California 的房源進行k-means聚類，聚類個數為100，從下圖可見，距離相近的房源大都被聚在一起，作者說這對Airbnb重新規劃market區域很有幫助。

價格和房源類型 計算Los Angeles 不同房源類型 / 不同價格區間的Listing 兩兩間的cosine相似性，然後取平均值。從下表可見，學到的embedding也encode了價格 / 房源類型信息。

房源風格 有些抽象的房源特徵是很難用特徵描述的，例如建築風格、style、給人的feel。作者使用KNN，給出某房源，如下最左圖房源，找到3個相似度最大的房源，結果顯示embedding也學到了這些抽象的風格信息。

2. User-type & Listing-type Embedding

另一自然的想法是利用用戶的長期偏好。房源預訂是比點擊更強的行為，能更精確反映用戶偏好，同時用戶歷史預訂行為間的時間跨度往往較大，可以更好地捕捉「長期」，因此文中從用戶的預訂會話（book session）中挖掘用戶長期偏好。與點擊會話不同，使用word2vec從中直接學習Embedding存在諸多挑戰：

  1. 預訂是比點擊頻次更低的行為，相應的預定會話數據遠低於點擊會話數據；
  2. 很多用戶在過去只預訂過一次，這種預訂會話沒有context信息，無法使用word2vec學習；
  3. 很多房源被預約的次數少於5-10次，很難學到meaningful的embedding；
  4. 用戶兩次預訂行為的時間間隔可能很長（年、月），這期間用戶偏好可能發生了變化，比如因職業改變而對價格敏感度改變；

Type Embedding 為了處理這些問題，文中先對用戶和房源的屬性（type）進行分桶，然後把用戶和房源的原始id映射為type_id，將type_id作為實體，學習embedding。這其實有點像在embedding前做了一個特殊的「聚類預處理」。

Table3、4給出了Airbnb的type分桶表，分桶原則是最大化每個桶的覆蓋率。舉個例子，給定一個listing_id，根據它的位置、類型、價格等type進行分桶，將對應type和其所屬桶號拼接，作為listing_type_id，例如country1__listingType3__perNight2__...__newGuestAcc3。Type Embedding 的引入有如下好處：

  1. 數據稀疏性的相關問題大大緩解；
  2. 有效處理冷啟動 / type缺失。對於type缺失、以及新用戶/房源註冊時，一些type例如好評率為空的情況，還是可以生成對應的type_id，對應某一「聚類」；
  3. 對用戶興趣隨時間的變化更魯棒。例如當用戶的一些type可能發生了改變，雖然他的user_id不變，但他對應的user_type_id會得到及時更新；

在同一向量空間學習user & list type的embedding。具體地，每次預訂行為都會將用戶和房源的type_id加入預訂序列。某個用戶的預訂會話s _ { b } = left( u _ { t y p e _ { 1 } } l _ { t y p e _ { 1 } } , ldots , u _ { t y p e _ { M } } l _ { t y p e _ { M } } ight) in mathcal { S } _ { b } ，注意，雖然 s_b 對應的用戶user_id不會改變，但其中的user_type_id是可以隨著用戶屬性變化而改變的。下圖 a) 顯示了當中心項為 u_{typei} ，context窗口大小為 m 的情形。

Explicit Negatives for Rejections 在Airbnb，房主可以拒絕用戶的預訂，為了提升用戶的預訂成功率，作者將這個信號作為顯示的負反饋加入目標函數，希望使user_type和容易拒絕其的listing_type盡量遠離。下圖 b) 展示了這個策略。

最終目標函數為：

max sum_{s_b in S_b} sum_{t in s_b} ~ [ sum_{(t,c)inmathcal{D}_{book}} log frac{1}{1+e^{-m{v}_t^Tm{v}_{c}}} + sum_{(t,c)inmathcal{D}_{neg}} log frac{1}{1+e^{m{v}_t^T m{v}_c}} + sum_{(t,c)inmathcal{D}_{reject}} log frac{1}{1+e^{m{v}_t^T m{v}_c}} ]

這個式子令不少讀者困惑，如前文所述，作者想在同一個向量空間中統一學習user_type和list_type的embedding，因此在預訂序列中，user_type和list_type一視同仁，即D_{book},D_{neg} 包含 (u_{type},l_{type}), (l_{type},u_{type}),(u_{type},u_{type}), (l_{type},l_{type}) 。 而引入D_{reject} 的目的，是使user_type和被拒絕的listing_type遠離，故 D_{reject} 只包含 (u_{type},l_{type}), (l_{type},u_{type}) 。

??點擊會話中只需要學習房源嵌入，而從預訂會話中，需要學慣用戶&房源嵌入，為什麼不和點擊會話一樣只學房源嵌入？

思考：從點擊會話中學習得到的房源Embedding，可以很好刻畫相同market下的房源相似性，因此很適合 short-term、in-session 的個性化推薦，文中的一個應用是在搜索會話中，根據用戶實時點擊行為來推薦相似房源。注意，這裡「點擊房源」是用戶短期/實時興趣的一個顯示反饋，可以根據「點擊房源」和候選房源計算相似度。但是，這裡並沒有用戶長期興趣的反饋，所以需要學慣用戶&房源嵌入，計算用戶與候選房源的embedding相似度。
  • Type Embedding 效果

學習得到用戶和房源的type embedding後，根據某用戶當前的type embedding，可以計算其與候選房源的cosine相似度。例如，某用戶通常會預訂high-quality、spacious、lots of good reviews的房源，下表根據type embedding，計算了該用戶與一些位於US的房源的相似度。從表可見，相似度排名可以較好地反映用戶對房源type的偏好。

3. Training Detail

Training Listing Embedding

  • 實驗設置
  1. 數據集
    1. 約 800 million 點擊會話作為訓練集，時間跨度達幾個月，約 4.5 million 房源；
    2. 過濾停留時長低於30s的無效點擊，過濾點擊個數少於2的點擊會話
    3. 訓練集按天更新，每天加入latest day的點擊會話，同時丟棄oldest day的點擊會話；
    4. 對含Book Listing的點擊會話進行「過採樣」，使數量擴至5x，實驗表明這有效提升了性能；
  2. 訓練設置
    1. 每天訓練時，所有房源embedding都隨機初始化（random seed不變），作者發現，這比使用昨天訓練完的embedding作為初始值效果更好；
    2. embedding維度d=32，選這個值是memory和performance的trade-off；
    3. context窗口的大小m=5；
    4. 在訓練集上的迭代次數設為 10；
  3. 冷啟動 Airbnb上經常會有新的房源上線，作者根據新房源的屬性（文中使用「價格區間」、「房源類型」），在方圓10英里內，找到3個距離最近、屬性相同的房源（如「20-35美元/晚」，「單人間」），取它們embedding的平均值作為新房源的embedding。這個方法可以解決超過98%新房源的冷啟動問題。
  • 線下評估

我們需要一個離線指標衡量 Listing Embedding 學習效果的好壞，以便快速優化。論文提出了一種評估方法：給出用戶最近點擊的房源 list_{click} 以及候選房源集，其中候選房源集中包含了該用戶這次search中最終預訂的房源 list_{book} ，計算所有候選房源與list_{click}的cosine相似度，以此排序，觀察list_{book}在排序中的位置，排名越前說明效果越優。

相關評測數據可以從用戶在Airbnb的歷史搜索日誌中整理，下圖顯示了一次評估結果，其中：

  1. 橫軸表示追溯到預定行為前的17 次點擊（Last到-16），作為點擊房源；
  2. d32表示嵌入維度d=32；reg——skip-gram原始目標函數，book——考慮「Book Listing as Global Context」，neg——考慮「Market-Sensitive Negative Sampling」；
  3. Search Ranking表示Airbnb現有搜索排序模型給出的原始排序結果。

可以看到，d32 book+neg是最優的，說明在目標函數中加入「book「和「neg」項是有效的。

Training Type Embedding

相比Listing Embedding，文中Type Embedding的訓練細節介紹沒那麼詳細，實驗設置如下：訓練集包含 50 million user booking session，約500K user_type和500K listing_type。嵌入維度d=32，context窗口的大小m=5。

??Type Embedding的效果好壞使用什麼指標衡量？

思考：文中沒有像Listing Embedding一樣給出說明和相關實驗結果，一個合理的猜測是給定用戶和某次搜索對應的候選房源集，其中包括預訂房源，可以計算用戶與候選房源的type embedding的cosine相似度，觀察預訂房源的排序位置。不知道大家有什麼其他想法？

4. Embedding在Airbnb的應用

應用1：相似推薦

點擊房源進入該房源的詳情頁，會有「相似房源」推薦模塊，該模塊原先的排序方法是：

At the time of our test, the existing algorithm for Similar Listings carousel was calling the main Search Ranking model for the same location as the given listing followed by filtering on availability, price range and listing type of the given listing.

一個新的思路是，在與詳情頁房源處於相同market的房源中，基於Listing Embedding計算它們的cosine相似度，找到k近鄰作為相似房源推薦。實驗中設置 k=12，A/B實驗結果顯示，「相似房源」模塊的點擊率提升了21%，轉化率（預訂）提升了4%。

應用2：實時搜索

Embedding的另一個應用是基於Embedding構造特徵，作為Airbnb的搜索排序模型的輸入，這裡先介紹一下Airbnb現有的搜索排序方案。

  • 基本背景

數據 訓練集 mathcal{D}=cup_{s=1}^{N} D_s ，D_s 表示一次具體search相關的樣本集，D_s 包含多個樣本(x_i,y_i)in D_s ，Aibrbnb每天更新線上搜索模型時，會使用最近30天的D_s 作為訓練集。另外，一些數據處理的trick如下：

  1. 不同於常見的二值值域， y_i 有5個不同取值：1——預訂成功、0.25——點擊後聯繫房主但未預訂、0.01——單純點擊、0——單純瀏覽、-0.4——預訂被房主拒絕；
  2. 每個search發生後，會等待1周的時間，再決定這個search中每個樣本最終的 y 值；
  3. 每個search只保存到用戶最後一次點擊的listing，過濾後面全部只是瀏覽的listing；
  4. 只保留至少包含一次booking行為的D_s ；

特徵 樣本包含四類特徵：房源特徵、用戶特徵、上下文特徵，以及三者的組合特徵，共約100個特徵。組合特徵的例子如：房源價格與用戶歷史預訂房源平均價格的差值、房源與用戶位置的距離、房源的實時點擊率等。

模型 搜索排序模型使用pairwise regression 的方式，修改GBDT的實現以支持Lambda Rank

  • Embedding特徵

對於Type Embedding，直接計算user和listing當前的type_id的相似度特徵。

對於Listing Embedding，作者從多個不同維度計算房源間的相似性特徵，具體地，統計每個用戶不同歷史行為的房源集合：

  1. H_c ：過去2周click的Listing id集合
  2. H_{lc} ：過去2周click停留超過60s的Listing id集合
  3. H_s ：過去2周skip的Listing id集合，注意統計的click操作前的skip房源
  4. H_w ：過去2周加入心願單的Listing id集合
  5. H_i ：過去2周連續房主但未book的Listing id集合
  6. H_b ：過去2周book的Listing id集合
  7. l_{lastclick} ：最近一次點擊的Listing id

在工程實踐中，大家通常都會想到利用點擊、轉化等顯示的正向反饋，而這裡很有意思的一點，利用skip這種隱式的負反饋信息，下面的實驗結果顯示了這個特徵非常有效，我們也在自己的推薦業務中進行類似的嘗試。

這些集合會實時更新，並且基於markets生成子集 H_m ，例如某用戶過去2周點擊過New York和Los Angeles的房源，那麼 H_c 細分為 H_{c}^{NY} 和 H_{c}^{LA} 。以 H_c 為例，計算具體特徵時，會分別對每個market子集中的房源embedding取平均，再計算與候選房源 l 的相似度，最後取相似度最大值作為特徵值，公式如下：

EmbClickSim(l,H_c)= max_limits{H_{c}^{m} in H_c} ~ cos(m{v}_l, sum_{l_i in H_{c}^{m}} m{v}_{l_i}) .

??在計算相似度特徵時，作者為什麼要基於market區分子集，更具體地，為什麼對不同market得到的相似度做max，而非不區分market對所有相似度直接取平均？

思考：1）Listing Embedding是從點擊會話中學習，點擊序列往往來自相同market，前面也說過（見Figure 2），學到的嵌入確實encode了很強的地理位置信息。2）以EmbClickSim特徵為例，最佳方案其實是使用用戶近期在候選房源 l 相同market下的行為數據，但考慮到Airbnb的業務特點，用戶去過一個地方旅遊後短時間內幾乎不會再去，因此用戶的搜索大概率都是尋找近期沒去過的某個market下的房源。3）一個折中的方法是，從用戶近期有過行為的markets中，找和本次搜索的market最相似的market，某種程度上，取max操作體現了這點。
  • 實驗結果

作者同時進行了離線實驗和線上A/B測試，離線實驗中，樹模型給出的特徵重要度如下，排名越小表示越重要，可看到embedding特徵的重要度都較高，尤其是ClickSim和SkipSim。

選取ClickSim、SkipSim和TypeSim特徵做 partial dependency 圖，下圖的結果符合我們的直觀認知，當ClickSim、TypeSim得分變高，即候選房源與用戶點擊過的房源、用戶當前type的相似度更高時，模型輸出分數更高；SkipSim的情況則相反。

以沒有加入embedding特徵的排序模型為baseline，離線實驗的指標選擇 DCG，下表給出DCG for each Utility（DCU）的相對提升結果。

線上A/B實驗也顯示，加入embedding特徵後，房源預訂指標有了提升，目前這些特徵已經在線上實際投入使用。比較奇怪的是，作者在這裡沒有像「相似房源推薦」模塊一樣，給出具體的指標提升數據，只是說「statistically significant booking gain 」，這難免不讓人遐想，其實線上提升效果並沒有那麼明顯？

5. Discussion

文首推薦的 @石塔西 和 @吳海波 的解讀中已經做了很精彩的conclusion和comment，本文不再贅述，建議讀者看看這兩篇解讀。另外，稍感困惑的一個點是，Airbnb成立於2008年，近10年多發展，已經成為全球民宿短租平臺的領頭羊，應該擁有了足夠龐大的數據量和計算能力，但文中顯示XGB目前仍是其線上主模型——不少公司在業務發展初期的選擇，相信Airbnb應該也有在主模型更迭上有過不少嘗試，以後準備抽時間讀讀Airbnb技術博客上發表的一些技術路線復盤一探究竟。

歡迎讀者對本文提出的、未提及的問題進行交流和探討。

推薦閱讀：

相關文章