Predicting Clicks- Estimating the Click-Through Rate for New Ads by _Microsoft_2007_WWW【Review】

Author: Junyi

• Introduction
• Brief introduction to the work of this paper
• Necessary background for reader to understand
• Motivation and Contribution

• Method
• Computation
• Algorithmic
• Implementation

• Experiment Result
• Conclusion
• Thoughts from the Reviewer

1. Introduction

這篇論文主要是講對於一些從來沒有出現過的廣告要如何做預測。我們知道有一些廣告是沒有先驗信息的，而這些廣告需要被和已經展示的廣告放在一起進行rank。rank的結果如果特別差的話是會嚴重影響用戶和廣告主的滿意度的，並且會進一步的影響高搜索引擎的收益。

原始的解決方法：用極大似然方式來估計點擊率，即廣告被點擊的次數除以廣告的總展示次數。

缺點：

* 廣告實際被點擊的次數可能很少，計算誤差會比較大

* 對於新廣告，無法解決冷啟動問題

「從來沒有出現過的廣告要如何做預測」。我們可以當作是從來沒有出現，或者說出現的次數不夠多，導致我們沒有足夠的先驗知識來進行判斷。Regelson and Fain的方法：對於冷啟動問題，這兩個人用該廣告bid term中的其他廣告的ctr來對其進行預測。然後本文實驗證明，以上的方式並不能有效的解決冷啟動的問題，所以本文提出了一些新的方法來對解決冷啟動的問題。

之前有過一些工作估計基於ad相似的bid以及topic進行ctr預估。本論文中經過實驗證明即便是相似的ad依然會在表現上會有很大的不同。對於一些表現很好的ad，會十倍於平均值。所以這篇論文使用的特徵要遠遠多於bid以及topic這樣的信息。

本文對於問題的背景以及論文寫作動機都有介紹，之後討論了搜索廣告框架，所用數據以及模型。接下來用四個章節介紹了使用bid term（keyword），廣告本身，order以及外部特徵在這個模型中的效果。章節10中，論文對結果以及模型性能和屬性做了討論。最後也給出了論文貢獻的總結以及對未來工作的期望。

2. Method

搜索廣告框架為：

p(click|ad, pos) = p(click|ad, pos, seen) * p(seen|ad, pos)

其中，ad表示廣告，pos表示展示位置，seen表示廣告被用戶看見。上述表示：用戶在當前位置點擊廣告的概率等於用戶在當前位置看到廣告的概率及看到廣告後點擊廣告的概率。對於上述概率進一步簡化（在直觀上作簡化），得到：

p(click|ad, pos) = p(click|ad, pos, seen) * p(seen|ad, pos) = p(click|ad, seen) * p(seen|pos)

能不能看到廣告和廣告內容其實沒有必然聯繫，而廣告被看到之後，是否會點擊和位置的信息相關度也會下降。為了簡化模型，就直接將公式進行簡化。

對於每個廣告位置，可以估計廣告放在這裡被用戶看到的概率——很多追蹤眼球運動的裝置能夠發現用戶觀看搜索結果的情況（這個圖案論文有給出）——這樣p(seen|pos)的值就可以估計出來。

問題的關鍵轉成計算p(click|ad, seen)的值。

作者把概率估計問題轉成回歸問題（曲線擬合問題），不過用的是邏輯回歸、而不是線性回歸。對此，作者的解釋是，邏輯回歸（不考慮最後的階躍函數來分類）將函數值映射到[0,1]區間，這個區間和概率的區間是一致的，所以就用它了。

訓練方式：

對於某個廣告，根據歷史統計廣告的經驗點擊率，並從廣告和廣告位等信息中抽取特徵，有些是實值特徵，組成<特徵....，經驗點擊率>這樣的訓練樣本，用來進行訓練。

而現在實際常用的系統中，往往採用的是0-1特徵，而輸出值，也是0-1，表示這個廣告在當前是否被點擊。這樣的話，隨著廣告被不斷展示，可以不斷進行增量訓練。而原文作者這種方式，只能是積累了一段時間之後，重新統計，生成新的經驗點擊率，然後再進行重新訓練。而且，原文這種方式，不能夠利用那些稀疏點擊——否則根據MLE來估計的「經驗點擊率」會很不準確（這也是本文要解決的問題），這時候會影響訓練。

2.1 Model

Some concepts you should know for this experiment, and you should know how to use these algorithms below:

• logistic regression
• cross-entropy loss function
• zero-mean Gaussian 0.1 standard-derivation initialize weights
• zero-mean Gaussian 1 standard-derivation initialize features
• KL divergence
• MSE
• L-BFGS

3. Experiment and Result

實驗baseline是平均CTR

3. 1 Term CTR

將廣告直接按照term的ctr來進行估計，term中的廣告ctr是多少，就將此廣告估計為這個值

3. 2 Related-Term CTR

將related-term的ctr利用起來，可以利用更多的信息。來構建新的特徵。構建方式如下：

同時也直接使用了個數作為特徵。對於個數為0的情況，我們做了smooth

3. 3 Estimating ad quality

同一個term下的不同ad都會有很大的不同在ctr上面，所以本文嘗試去挖掘廣告本身的特徵：

• 外觀
• 是否吸引眼球
• 廣告商信譽
• 廣告頁面質量
• 廣告與query的相關性

根據以上五項，找出了81個特徵。同時也添加了10000個unigram的特徵。通過這些單詞在title和body中出現與否來作為特徵（詞頻，bigram和trigram也有嘗試過，但是想過並沒有什麼不同）

效果如下，實驗證明 unigram的作用好像更大一些。

3. 4 Measuring order specificity

廣告覆蓋的類別多少（這裡就使用了nb進行分類）作為一個特徵添加，這個是基於3.3的實驗進行的結果。實驗結果如下：

通過bid term來作為搜索query，進行搜索，在搜索結果中作文本分類（偽相關反饋，不求精度，用NB就可以），用各個類別組成的熵來反映這個廣告是只針對某種特定的類別（熵很小）還是面向很多類別（熵比較大），將這個熵值作為特徵加進去。

3. 5 External sources of data

添加（廣告）外部信息，這裡添加了query後返回的頁面數量作為特徵添加，結果如下：

還是有一定的提高的。

3. 6 Comments to Results

作者在論文的最後對不同特徵的重要性進行了排序，但是這個排序並沒有很明顯的作用，雖然可以用來進行分析模型，不能夠根據特徵的權重大小來決定特徵的好壞，因為各個特徵其實不是獨立的。並且在實際使用中還是特徵越多越好，可以幫助模型具有更強的魯棒性。

某些特徵（如：某些詞）會對點擊率起到很正面的作用，此時有兩個用處：（1）當廣告商購買bid term的時候，給廣告商推薦這些詞；（2）當某些廣告商惡意的購買這些詞的時候，通過該廣告商廣告的ctr的劇烈變化，可以偵測到這個情況，從而進一步處理。

多少次經驗性的觀察之後，對模型的均值預測就可以趕上我們的模型了。從圖上我們可以看出在50-100的時候，差距就不大了。

其次， 對於view次數越多的廣告，這個模型進行的ctr預估效果，比起basline來說就越好。（baseline是所有廣告的均值）

4. Conclusion【something you could bring home】

這篇論文總體而言通過實驗對Regelson and Fain的觀點進行了驗證，表明效果並不是很明顯。針對他們的實驗，又提出了自己的觀點，包括使用廣告本身的信息，廣告覆蓋的類別，外部信息。都得到了更好的效果。

論文寫作時間為2017年，所以當時作者認為實驗結果受限於搜索引擎的獨特性以及研究人員對於搜索引擎的了解有限。同時，實驗數據集也不夠標準，如果有更加標準的實驗數據集應該可以得到更好的效果。

在未來工作上，作者希望可以將user query的更多的信息利用起來（目前主要是利用了query裡面的bid term），而query其實是可以包含更多的信息的。即便是使用同樣的模型，依賴於query的特徵例如說：bid term 和query的相似度，query的words 數目，有多少單詞同時出現在了query和landing page上等等，應該可以對結果進行優化。

同時可以復現Regelson and Fain論文結果作為一維特徵添加到模型中。

5. Thoughts from the Reviewer

這篇論文是比較基礎和經典的關於ctr的論文，裡面主要是在針對性的解決冷啟動的問題。使用的模型並不是很複雜，大多數工作都集中在特徵工程一部分。據大佬說這個是一個比較良好的入門的論文。

Reference：

[1] https://blog.csdn.net/xceman1997/article/details/30772997

推薦閱讀：