《Scalable Semantic Matching of Queries to Ads in Sponsored Search Advertising》精讀

01-27

自從word embedding流行之後，很多研究都在此基礎上，將研究問題轉化為向量的形式，再通過向量間距離計算相關性，用於搜索、排序、推薦等場景。而本文帶來的這篇來自YahoonLabs的論文，就是將query和ad(廣告)進行向量化，通過餘弦相似度，計算query和ad的match情況。因此，核心問題就是，如何在搜索廣告這個場景下，獲取query和ad在同一語義空間的向量表示。由於是通過query去找最match的ads，因此我們在下文中將這個問題簡稱query2ads。

nn如果看過deepwalk[1]的同學，可能第一直覺就是，可以通過query和clicked ad，建立一個bi-graph，通過Random Walk的方式生成query ad query ad…..這樣的序列，將其作為sentences輸入skip-gram模型中，也可以得到一組query和ad的向量表示。具體實現細節可以看論文，而本文主要針對搜索廣告領域，提出了另一種轉換問題的思路。

0. 簡述

本文解決的是query和相關ad匹配問題，通過將query和ad都映射到同一語義空間中，利用 cosine相似度獲取相關ad。而在訓練向量的過程中，將用戶的廣告停留時間和用戶略過的廣告作為特徵，融入優化目標中，利用大規模訓練演算法一起訓練。而針對未登錄的query和ad，作者也提出了相應的解決方案。最後在離線和在線測試中，都取得了很好的效果。

1. 背景

付費搜索是搜索引擎公司的主要收入來源，但是如何識別所有與query相關的ads，一直是需要解決的問題。

最初的方法，就是用query去匹配ad的bid terms，是一種精準匹配。然而，廣告商不可能給出所有相關的bidnterms。因此，隨後又提出了Advancednmatching。它主要包括兩個方面， 1、Variant match：針對bid terms進行較小的形態變化，如typo、詞形變化等。2、Broad match：可以沒有相同的詞，但是要有語義相同或相近的詞，如query擴展，query改寫等。不過，問題仍然存在，對於變化後的terms如果和query仍然沒有交集，那麼也會matching失效。

本文提出的方法，直接在語義層面進行matching，可以很好的解決Broad match帶來的問題。

2. 論文亮點

Implicitnnegatives*：將用戶略過的，沒有點擊的廣告作為負例，比隨機選擇負例有更好的效果。
Dwellntime weights*：將用戶在廣告頁面的停留時間作為權重，整合到訓練過程中。
Large-scalentraining：利用parameter server進行大規模詞向量訓練。
Cold-startnad embeddings*：解決未登錄ad的matching問題。
Cold-startnquery embeddings*：利用head query的向量生成未登錄的tail query的embedding。
Experimentsnon real search traffic：在真實的搜索環境中測試。
Open-sourcenvectors：將訓練好的embedding開源。

3. 方法

因此，我認為本文的核心問題可以歸結為下面這幾個方面：

如何學習query和ad的向量形式？
如何融入Implicit negatives和Dwell time weights一起訓練？
未登錄Ad和query的冷啟動是如何實現的？

我們帶著這三個問題，看看作者是如何解決的。

問題一：如何學習query和ad的向量形式？

這個問題本質是，如何將query和ad，序列化為類似於句子的形式。作者將一個用戶在一段時間的query，clicked ad，link click作為一個session，即 $s=(a_1,a_2,...,a_M)$ ，其中 $a_i$ 是一個action，可能為query、ad clicks, 或者link clicks。這裡，作者將link click也作為訓練對象，因為其可以提供更多上下文信息，畢竟link click和query的co-click會影響query和ad的向量生成。

為了提高訓練效率，作者採用negative sampling，這是先假設使用隨機sampling，因此，優化目標為下面的形式：

$mathcal{D}_p$ 代表正例集合， $mathcal{D}_n$ 代表負例集合，其中， $a$ 為一個action，正例的 $c$ 為 $a$ 的真實上下文，負例的 $c$ 為隨機選擇的上下文。詳見下圖：

問題二：如何融入Implicit negatives和Dwell time weights一起訓練？

(1). 先看Implicit negatives：

假設用戶點擊了第 $n$ 個ad，則第 $1$ 到 $n-1$ 個廣告，就可以認為是該query的負例。這裡，作者為了減少雜訊帶來的干擾，只針對Top3的ad，並且在該session中只有1次ad click，並且停留時間超過10分鐘的。這樣，我們就可以將公式(3.3)變為：

$mathcal{D}_{in}$ 代表query和負例ad的集合。

(2). 再看Dwell time weights：

Dwell time主要指用戶點擊ad後，在落地頁的停留時間，用 $t$ 表示停留的分鐘數。作者通過 $eta =log(1+t)$ 來表示該廣告的權重。並且，該權重僅用於更新ad的向量，在更新query向量時， $eta =1$ 。那麼，可將(3.3)變為如下形式：

問題三：未登錄ad和query的冷啟動是如何實現的？

(1). 未登錄ad解決：

對於一個新的ad，我們只能依賴它的文本信息，包括bid term, ad title和description。因為我們已經有了大量詞和短語的embedding，因此，作者將上面提到的這些文本信息，取n-gram(n=1,…,10)，將出現在這些n-gram中已知的詞或短語向量相加，得到未登錄ad的向量，這種方法，作者稱為「anchor phrases model」。具體演算法見Algorithm 1：

(2). 未登錄query解決：

長尾query數量龐大，具有巨大的商業價值。然而，訓練數據永遠無法涵蓋所有的query，因此作者提出用top query建立一個索引，將新query匹配到這個索引中的某個query中，再用該query的ad來作為新query相關的ad。當然，在用索引匹配的時候，並不是傳統的按字(詞)精確匹配，而是利用訓練好的query的embedding在語義空間進行匹配，因為有共同的詞，並不意味著有類似的content(link和ad clicks)。

4. 結論

nnnn 其實，雅虎也在其他場景下嘗試向量化，比如這篇《E-commerce in Your Inbox: ProductnRecommendations at Scale 》中，作者對product和 user進行向量化，用於推薦，也取得了很好的效果，方法與本文類似。因此我們會想，是否可以將everything2vec？如何將兩(多)者建立聯繫，來表示成上下文的形式？是否可以把對象表示成圖的形式？這就又是一類問題，各種graph2vec的論文也可以借鑒。以及，如何對未登錄的對象進行處理？比如論文中，拿到一個新的query，我們是否可以通過ad click或者ad的文本信息，將已知的query和新query建立聯繫？這些問題，都值得我們思考。

參考：

[1]DeepWalk:nOnline Learning of Social Representations