淺談Airbnb基於嵌入的搜索排序和推薦系統

10-15

原文是2018年KDD ADS track的最佳論文主要介紹了目前Airbnb最新的個性化搜索排序系統的實現，系統通過引入房源嵌入表示和用戶嵌入表示實現了更好的實時個性化搜索排序以及相似推薦效果。

引入

愛彼迎是一個短期租賃平台，也是一個two-sided平台，除了要為租客生成個性化搜索結果，以及推薦相似房源，還要考慮租客是否滿足房東的要求，比如有寵物的租客可能會被房東拒絕，那麼對應的房源就會有較低的概率被推薦和展示給租客。而且由於 1）租客不太可能租賃同一間房子 2）一間房子只能同時被一個租客租下這兩個特點，愛彼迎面臨的搜索排序和相似推薦任務更艱巨。

當租客在搜索框中輸入一串條件並點擊「搜索」，然後開始瀏覽結果列表時，這是一個實時排序和推薦場景，租客在整個搜索的幾十分鐘內瀏覽/駐足的頁面明確的表示了他在這一次搜索過程中的偏好。針對這一場景提出了房源嵌入。

對於老用戶，他們的歷史訂單在很大程度上代表了他們的租房/出租偏好。在租客還未開始搜索前，如果可以根據歷史信息為其生成嵌入表示，那麼在搜索時就可以有針對性的為他生成推薦列表。對於房東/房源來說，可以根據房源的出租情況和房東的拒單行為為其生成嵌入表示，同樣的在生成推薦列表時，可以減小房源排在列表靠前位置/被推薦給房東更可能拒絕的租客的概率。針對這一場景提出了用戶類型嵌入和房源類型嵌入。

房源嵌入

房源嵌入（Listing Embeddings）適合於短期實時個性化排序和推薦場景。

數據集 $S$ 由N個用戶的點擊會話（click session）構成，每個會話 $s=(l_1,...,l_M)in S$ 定義為一個用戶點擊的不間斷的房源號序列，如果兩次點擊之間的間隔超過30分鐘，就會開始一個新的會話。我們的目標就是為每個房源學習一個32維的嵌入表示 $v_{l_i}$ ，使得相似房源在嵌入空間中處於臨近位置。

為了降低更新嵌入表示的計算複雜度，我們採用了帶負採樣的Skip-Gram模型進行嵌入學習。首先，將嵌入向量初始化為隨機向量，然後通過滑動窗口（窗口大小m=5）的方式讀取上下文即正樣本，通過隨機抽樣的方式得到負樣本，用SGD更新嵌入向量，每次更新的目標是使得中心房源與正相關房源更接近，與負相關房源更疏遠。

為了更好的學習嵌入表示，對上述模型提出了兩個補充：

1. 使用最終預訂的房源作為全局上下文 將點擊會話 $S$ 劃分為搜索會話和最終預訂會話，如果用戶的一次點擊會話是以預訂為結束的，那麼這次會話就是最終預訂會話，否則是搜索會話。顯然，用戶下單的房源應該是最符合用戶當前偏好的，因此在每次優化時，除了預測相鄰點擊房源，還要預測最終點擊房源。也就是說，隨著滑動窗口的移動，一些房源會離開或進入窗口，但最終預訂房源作為全局上下文始終被保留在窗口中（圖中虛線所指部分）。

2. 對聚集搜索額外採樣負樣本 用戶通常只在自己的目的地內進行搜索，也就是說用戶點擊會集中在一個城市（marketplace）內，因此，對於給定的中心房源，正樣本主要包括來自相同目的地的房源，而負樣本由於是全局隨機採樣，會包括來自不同目的地的房源。這種情況會導致學到的同一目的地內的房源相似性不是最優的。為了解決這種不平衡，增加一部分負樣本，這些負樣本是從中心房源所在城市的所有房源中隨機採樣的。

綜上所述，最終的目標函數定義為：

冷啟動問題 愛彼迎平台上每天都會新增許多新房源，這些房源只有房東提供的基本信息，沒有嵌入表示。那麼如何為新房源生成初始嵌入呢？我們根據房源的基本信息，從已有的房源中找到3個與它地理位置最接近、房屋類型相同、價格區間相同的房源，計算它們的平均嵌入向量即為新房源的初始嵌入向量。

用戶類型嵌入 & 房源類型嵌入

用戶類型嵌入（User-type Embedding）和房源類型嵌入(Listing-type Embedding)適合於長期個性化場景。

用戶的歷史行為對於學習嵌入有很強大的作用。考慮這樣一個場景：用戶曾經在紐約和倫敦租過房子，現在他需要在洛杉磯預訂一間房子。對於個性化搜索來說，很顯然他以前租過的房子是一個很好的參考，為用戶推薦類似於它們的房源很可能會被點擊和預訂。

數據集 $S_b$ 由N個用戶的預訂會話構成，每個預定會話 $s_b=(l_{b_1},...,l_{b_M})in S_b$ 是一個用戶的所有已預訂房源號序列。但是這樣得到的數據集存在一些問題：

預訂會話 $S_b$ 相比於點擊會話 $S$ 要小得多，這與用戶行為相符合，用戶在下單之前總是會瀏覽很多相關房源。
存在很多隻下單過一次的用戶，一個樣本是無法進行嵌入學習的。
為了學到一個有意義的嵌入表示，用戶/房源至少要在上下文窗口中出現5~10次，但是現實是大部分用戶沒有預定超過5~10次，大部分房源沒有被預定超過5~10次。
用戶的偏好常常會隨著時間而變化，所以針對用戶個體的嵌入表示很可能不能被學習的很好。

為了解決上面的問題，我們提出了按類型學習嵌入——用戶類型嵌入和房源類型嵌入。為了便於計算用戶和房源相似度，學習時使用同一個嵌入空間。通過分析用戶數據和房源數據，我們將類型劃分為如下表所示， $user_{type}$ 和 $listing_{type}$ 就由對應項的橫縱標籤連接得到，比如 $user_{type}=SF\_lg_1\_dt_1\_fp_1\_pp_1\_nb_1\_ppn_2\_ppg_3\_c_2\_nr_3\_l5s_3\_g5s_3$ 。

預訂會話的新定義為 $s_b=(u_{type_1}l_{type_1},...,u_{type_M}l_{type_M})$ ，依然還是一個會話對應一個用戶，其中每一項代表用戶的一次預訂事件，但用戶可以有多個用戶類型，對房源也是一樣。下圖為以 $user_{type}$ 為中心的負採樣Skip-Gram模型，可以看到滑動窗口中是成對的預訂事件，並且可能出現不同的 $user_{type}$ 。

由此得到以 $user_{type}$ 為中心的目標函數：

以 $listing_{type}$ 為中心的目標函數類似：

被拒訂單作為顯式負樣本 與點擊行為只能描述租客偏好不同，訂單狀態還可以描述房東偏好。比如，房東可能因為租戶有寵物或者沒有詳細填寫個人信息而拒絕他的訂單，雖然這個訂單沒有成功，但為系統提供了學習房東偏好的負樣本。經過學習後，系統將不會把很可能被房東拒絕的房源展示給租客，這樣可以有效的減少訂單失敗率，提升成交率。下圖是以 $user_{type}$ 為中心並加入了拒絕樣本的模型：

目標函數更新為：

實驗

房源嵌入

===訓練===

使用了800,000,000點擊會話來為4,500,000房源訓練嵌入，這些會話中已經去掉了一些沒有價值的部分，比如頁面停留時間少於30秒的點擊視作無效數據，會話中包含的點擊行為少於一個的視作無效數據。在訓練模型的幾個月里，訓練集每天都會更新——新增當天的搜索數據，刪除當前最早一天的數據。

有趣的是，每天隨機初始化嵌入表示再學習的效果要比在前一天訓練得到的嵌入表示的基礎上繼續學習的效果要好。這是因為我們使用了餘弦相似度而不是嵌入向量本身來衡量模型效果，即使向量在不斷更新，兩個向量之間的相似度也不會發生太大的改變。

使用MapReduce來實現訓練，其中300個mapper用來讀數據，1個reducer多線程地訓練模型。使用Airbnb的開源調度平台Airflow實施日常數據生成和管道訓練。

===線下===

為了驗證訓練得到的嵌入表示的效果，根據房源嵌入以及近期的點擊行為為用戶推薦可能預訂的房源，這個可能性是由已點擊嵌入與候選嵌入的餘弦相似度表示的。候選項中包含了實際預訂項。按計算得到的餘弦相似度對候選項排序，我們關注的是實際預訂項在序列中的位置。

對上面提到的三種模型——帶負採樣的Skip-Gram（d32）、增加已預訂項（d32 book）、考慮聚集搜索（d32 book+neg）以及現有的搜索排序模型進行該實驗，實驗結果下圖：

橫坐標是在用戶最終預訂之前的點擊次數，縱坐標是實際預訂房源的平均排名。可以看到對於嵌入方法，在點擊次數達到17次之前，平均排名並沒有隨著點擊次數的變化有明顯改變，因此採用嵌入方法的搜索排序可以在一定程度上減少租客最終預訂前的點擊次數。總的來說，考慮了已預訂項和聚集搜索的負採樣Skip-Gram模型的效果是最好的。

===線上===

為了驗證嵌入方法用於線上場景的效果，對嵌入方法和現有的搜索排序方法進行了A/B測試，測試內容是尋找K近鄰。測試結果表明，嵌入方法提升了21%基於相似推薦的CTR，提升了4.9%基於相似推薦的預訂率。

2. 類型嵌入

首先需要定義搜索 $D_s=(vec{x_i},y_i), i=1,...,K$ ，其中K是本次搜索返回的房源個數， $vec{x_i}$ 是房源i的特徵向量， $y_iin {-0.4, 0, 0.01, 0.25, 1}$ 是房源i的在本次搜索後的狀態，分別表示預訂後被拒、未點擊、僅點擊、租戶與房東有交流但未預定、成功預訂。

下面詳細介紹特徵向量 $vec{x_i}$ 的組成：

房源特徵：包括單價、風格、卧室數量、拒單率等
租客特徵：平均預訂價格、個人評分等
查詢特徵：容納人數、預訂天數、預訂首日日期等
混合特徵：這一部分的特徵是由上面三類特徵中的兩類及以上的細節特徵共同構成的。比如，價格差=|房源單價-用戶平均預訂價格|。

以上是基本的特徵，下面介紹基於嵌入的幾類特徵：

房源嵌入特徵：根據租客在過去兩周的歷史行為為每個租客構造以下短期歷史集，集合是實時更新的：

$H_c$ ：在過去兩周點擊過的房源集合
$H_{lc}$ ：點擊且在詳情頁面停留超過1分鐘的房源集合
$H_s$ ：跳過的房源集合
$H_w$ ：加入收藏的房源集合
$H_i$ ：與房東有交流但最終沒有預定的房源集合
$H_b$ ：最終預訂的房源集合

對上面每個集合還要根據城市劃分子集，比如 $H_c$ 中位於紐約的房源構成子集 $H_c(NY)$ 。

基於已經計算好的4,500,000房源嵌入和上面定義好的集合，為候選房源計算得分（如下表前6行），另外，表中第7行 $EmbLastLongClickSim$ 表示的是候選項與該租客最近一次預訂的房源的餘弦相似度。

以 $EmbClickSim(l_i,H_c)$ 為例，首先計算出 $H_c$ 在每個城市的centroid embedding，然後計算 $l_i$ 的房源嵌入和城市級centroid embedding的餘弦相似度，取其中最大的作為結果：

用戶類型和房源類型嵌入特徵：首先根據50,000,000預訂會話為500,000用戶類型和500,000房源類型生成各自的32維嵌入表示，直接使用兩者的嵌入計算上表中的最後一行：

===訓練===

根據上述所有特徵（共104個）訓練GBDT模型用於搜索排序，訓練數據來自近30天。部分重要的嵌入類特徵在訓練集中的覆蓋情況和權重排序如下表：

其中點擊和跳過特徵覆蓋的數據是最多的，這很符合直覺。另外，由於考慮了長期行為特徵，類型嵌入特徵 $UserTypeListingTypeSim$ 比只考慮短期預訂的 $EmbBookSim$ 重要度更高。

===線下===

比較了使用和不使用嵌入特徵在相同數據上訓練的兩個搜索排名模型。我們測試了每種狀態下的房源的DCU(Discounted Cumulative Utility)和整體NDCU(Normalized Discounted Cumulative Utility)的結果。從下表可以觀察到，增加嵌入功能導致NDCU上升2.27％，預訂DCU增加了2.58％，這意味著最終被預訂的房源在推薦列表中排名靠前（更可能、更早被租客看到）；拒單DCU效果持平，這意味著被拒絕的房源排名沒有比沒有嵌入特徵時更高。

===線上===

在線上實驗中，預訂收益有所增長。嵌入式方法運行幾個月後，我們進行了一次後退測試（刪除嵌入功能），這導致了負面預訂，也表明實時嵌入功能有效。