將 Embedding 應用於搜尋結果排序與商品推薦
論文出處：Real-time Personalization using Embeddings for Search Ranking at Airbnb (這篇文章也是 KDD 2018 Applied Data Science 最佳論文)
近十年來，行動裝置的普及不但讓用戶越來越多的行為轉移到線上，也促成了眾多線上交易平台的誕生，例如 Uber，Lyft，Airbnb，Etsy，或是台灣熟知的蝦皮等等。對於這些平台來說，有效的幫助使用者發現內容，或是做商品的推薦，對搜索的排序做個人化，也越來越重要。
同一時間，在機器學習領域，自然語言處理也進展神速，而其中一個很重要的創新便是 Google 發表的 Word2Vec 技術，可以有效地將字詞嵌入到向量空間後，找到字詞間的相關性。詞嵌入技術可以用來找字詞間的相關性，也可以用來找商品之間，或是人跟人之間的相關性。因此，嵌入 (Embedding) 這個概念，很快地便被應用到其他的領域，例如廣告，電影或音樂的推薦系統等等。這篇論文所介紹的，便是 Airbnb 如何將嵌入技術運用在房源嵌入 (List Embedding) 與用戶類別嵌入 (User-Type Embedding) 中，並實際上線運用在搜尋結果的排序，以及類似房型的推薦，達到非常好的效果。
若對於 Word2Vec 技術不熟悉，可參考之前的文章：
什麼是房源嵌入 (Listing Embedding)？
使用了 450 萬個活躍房型，以及 800 萬個 session 的資料。模型的示意圖如下圖一所示，假設一位使用者，他經過一連串的點擊後，在 30 分鐘內成功訂房，將每一次點擊的房型從 L0, L1, 一直到 Lb 代表最後下訂的房型， 逐一列出。Window size 選擇 5，並採用 Negative sampling 的方式。初始的向量為隨機產生，然後再根據一連串的搜索行為產生的結果逐一更新。中央房型 (central listing) 可看做是 word2vec 中的輸入字詞 (input word)，然後統計前後五個房型中，哪些有被點擊，哪些沒有。有點擊的房型稱為正向房型 (positive context listing)。另外還有負向房型 (negative context listing，為隨機的樣本，有很大的機率他們與中央房型無關)。在每一次的更新中，中央房型會漸漸朝正向房型逼近，並遠離負向房型。當模型訓練完成後，相似的房型會在投影的向量空間中彼此相鄰。
模型可用一個改良過的交叉熵 (cross entropy) 數學式來表示：
- 第一項將所有 positive pair 出現的機率加總
- 第二項則是所有 negative pair 不出現的機率加總
- 第三項是將使用最終下訂的房型作為 Global context：不僅考慮 window size 內的房型，也考慮用戶最終下訂的房型，畢竟那才是最終模型要優化的目標，當中央房型每次在做優化的時候，都會將最終下訂的房型考慮進去，也就是示意圖中的紫色虛線。
- 第四項則是用來增加單一市場 negative sampling 的重要性，目的是解決模型通常對於每個 session，只會學到單一市場的房型的問題：如果我要去巴黎玩，通常我每次的搜尋 session 只會點擊巴黎的房型，雖然合理，但這會讓中央房型只跟在同一地區的房型越來越靠近，而造成局部最佳化 (suboptmal) 的問題。為解決此一問題，在數學模型中加入一項 Dmn 降低地區所造成的影響。
另外，作者也解決了冷起始 (cold-start) 的問題：每天 Airbnb 上都有新增的房型，這些房型沒有任何的訓練資料，因此沒辦法直接做房型嵌入。解決的方法是找到三個相同類型且價格相近的房型，用向量平均值作為新增房型的嵌入向量值。
用房源嵌入訓練出來的模型學的還不錯
用幾種方式來評估最後訓練出來的房型嵌入的結果：第一、用 k-means clustering 集群分析的方式，從地理位置來看是不是相似的房型有被分在一起。理論上，當使用者在搜尋房間時，對於區域應該會有針對性，在同一次搜尋過程中，會點擊的房型應該不會距離太遠。因此，從房型的位置應該可以稍微看出我們分類的結果。圖二為將位於加州的 100 個 clusters 畫在地圖上的結果，可以發現地理位置相近的房型，會被模型分類在同一個 cluster 中。
論文中也透過不同類型的房型，以及不同價位的房型間的平均餘弦相似度，來判定模型訓練的結果。從下表我們可以發現，相同類型或價位類似的物件之間，都有最高的相似度。確實房型與價位的差異有很好的被編碼在我們的結果中。
最後，某些用來描述房型的特徵，例如建築風格，氛圍等等，較難透過數字來描述。因此他們也做了一個工具，輸入物件 ID 後，會將系統認為類似的房型列出，可以發現機器可以成功地將不同風格，類型的物件找出來，非常厲害：
離線測試，找出最好的嵌入模型
一個評估我們訓練出來的房型嵌入結果好壞的方式是：觀察推薦的房型的排名，看用戶是否有點擊，以及最後是否有訂房。具體來說，我們觀察一連串用戶在訂房前點擊過的房型，以及需要被排序的房型，包含最後用戶實際下訂的房型。透過計算有做嵌入的點擊房型與要被排序的候選房型之間的餘弦相似度，我們可以將候選房型做排序，並觀察最後下訂房型出現在排序的位置。
圖四為回朔用戶下訂前 17 個點擊的房型後測試的結果，我們可發現原先搜尋排序的演算法 (綠線)，當用戶的點擊越多時，表現得越好。黃色為第一版的房型嵌入，僅考慮公式的第一第二項；紅色將用戶最終下訂的房型作為 Global context 後訓練的結果，也就是公式中考慮第三項的結果；紫色則為也將單一市場的 negative sampling 考慮進去，加入公式中第四項後，訓練出來的結果。最終的結論是，紫色的線 (d32 book + neg) 所代表的模型表現最好。
類似房源的即時個人化推薦，點擊率增加 21%，訂房率增加 4.9%
如下圖，Airbnb 在每個房型的下方，會用 carousel 的形式推薦類似且可接受預訂的房型。Airbnb 已有自行開發的搜索排名 (Search Ranking) 演算法，找出相同地點，定價接近，相同類型的類似房型。
本論文用 A/B testing 的方式來比較搜索排名演算法和本篇論文的主角：房型嵌入的模型。具體來說，類似房型的找法是給定一個房型，然後用餘弦相似度找到位於相同市場，在給定的時間區間中接受預訂，並依相似度做排序，排名前幾名的房型，推薦給使用者，如下圖五。
A/B 測試的結果，使用房型嵌入的方式找到的相似房型，比起用搜索排名演算法所顯示的房型，點擊率增加了 21%，訂房率提高了 4.9。
應用在即時個人化推薦也證明有效
目前為止，看來房型嵌入模型可以有效找到不同房型間的相似度，我們希望可以更進一步，將這個模型應用在即時個人化推薦，希望可以顯示更多使用者喜歡的房型，並減少推薦使用者不會喜歡的類似房型。
為了達到這個目標，首先定義兩個短期記憶的行為：
- Hc: 一包使用者過去兩週有點擊的房型的 ID
- Hs: 一包使用者過去兩週排名較高，但使用者沒有點擊，選擇忽略的房型 ID
接下來，每次用戶做搜索時，我們對每個推薦的房型都會計算兩個數值：
- EmbClickSim: 推薦的房型的嵌入向量與使用者點擊的房型 (Hc) 的嵌入向量間的相似度
- EmbSkipSim: 推薦的房型的嵌入向量與使用者忽視的房型 (Hs) 的嵌入向量間的相似度
然後再把這兩個計算出來的相似度的值，加入搜索排名的模型中，並做 A/B testing。為了驗證新的模型是否有學到這兩個新的相似度的值，拿搜索排名的結果畫了下圖六：
從左圖可以看到 EmbClickSim 數值愈大 (代表推薦的房型越相似於用戶最近點擊的房型)，模型的分數越高；反之，EmbSkipSim 數值愈大，模型分數越低。
這個觀察也證明了搜索排名的模型確實會受到房型嵌入所做出的相似度影響，因此，產品團隊決定進行線上測試，並在 2017 年夏天上線即時個人化的房型推薦功能。
總結來看，這篇論文主要有五個創新之處：
- 即時個人化推薦：許多的推薦系統產生的是用戶對產品，或產品對產品的一個矩陣，為離線的結果。但這篇論文則實做了當用戶在線上作搜尋時，有辦法對用戶做即時的推薦，是資料科學與產品結合的非常好的範例。
- 將訓練的模型針對要解決的問題的特性做調整：在 Airbnb 的情況，用戶通常會集中搜尋同一城市的房型，會讓模型學錯，造成局部最佳化的結果。本論文透過調整交叉熵的公式來解決這個問題
- 使用用戶實際下訂的房型作為 Global Context：用戶一連串的點擊，最終最重要的還是訂房的行為。最後也證明這可讓模型學的更好
- 用戶類型嵌入 (User-Type Embedding)：一般使用者不會很頻繁的使用 Airbnb，平均一年也就用 1–2 次，因此不適合做單一用戶的嵌入。反之，他們將用戶做歸類，做用戶類型的嵌入。
- 也將屋主是否拒絕接受訂房，考慮進模型中：為了降低推薦的房型最後被屋主拒絕訂房，在訓練模型時也將屋主拒絕接受訂房這個行為，考慮進模型中。
其他將 embedding 技巧運用在產品推薦的案例
Airbnb 其他的與機器學習相關的產品應用：
