Practical Lessons from Predicting Clicks on Ads at Facebook

一、摘要

點擊預測系統大多是以在線廣告系統維中心，每天7億的日常活躍用戶和超過1百萬的活躍廣告，因此預測FaceBook上的廣告點擊率是一項具有挑戰的機器學習任務，本片論文中我們介紹了一個模型采用決策樹和邏輯回歸結合的模式，融合模型的表現勝過它們自己單獨建模的效果3%，這個一個重大的影響對于整個系統的表現，

我們然后探索了一些基本引數對我們真個系統的預測表現進行了探索，不足為奇，我們獲得來了一個重要的結論就是：使系統整體表現提高最重要的就是擁有正確的特征（那么捕捉了用戶或者廣告的歷史資訊），這些特征在所有的特征中占據著主導地位，一旦我們擁有了正確的特征和正確的模型（決策樹+邏輯回歸），其它的特征幾乎發揮很小的作用（盡管小的提升在整個業務范圍內也是很重要的），挑選一些最優的資料處理方式，例如資料新鮮度、學習率模式、資料采樣，這些都會輕微的提升模型的性能，但是提升的幅度仍會小于擁有高效的特征組合或者是使用正確的模型，

二、簡介

數字廣告使一個幾十億美元的工業并且每年都在急劇地增加，在眾多互聯網廣告平臺，支配廣告是動態的，居于觀察到的用戶回傳合理為它們調整用戶的興趣，機器學習發揮了重要的作用在計算預測效用和一個用戶對于一個廣告的點擊率，并且這種方式會增加整個市場的效率，

在2007年Varian和Edelman發表了一篇開創性的論文，描述了出家和每次的點擊拍賣，同年，微軟基于相同的拍賣模型構建了一個贊助搜索市場，這個廣告拍賣的有效性依賴于點擊率預測的精度和校準，點擊率預測系統需要健壯性和適應性，并且有能力從海量資料中進行學習，這篇論文的目標就是分享來自實驗的觀點，這些實驗考慮了這些需求并且在真實世界中的資料進行的執行，

在贊助的搜索廣告，用戶搜索被用于去檢索候選的廣告，這些廣告可以隱式或者顯示的進行匹配用戶的搜索，說白了就是可以從用戶每次的搜索匹配對應的廣告，但是FaceBook與微軟不同，它的用戶搜索較少，廣告和搜索幾乎沒什么關聯，它們只和特定的人口特征和興趣目標相關，因此，當一個用戶訪問Facebook時符合條件被展示的廣告要遠大于基于搜索的模型，

為了解決每次請求的候選廣告非常多的問題，當一個用戶訪問Facebook時，這時請求廣告就會被觸發，我們首先建立了一個不斷增加成本的級聯分類器，本篇論文中，主要研究級聯分類器的最后階段的點擊預測模型，即對最終候選廣告集進行預測的模型，

我們發現了一種混合模型（決策樹+邏輯回歸），這種模型比這兩種方法各自的性能都要好3%以上，這種提升在整個系統的表現能力上是有重大意義的，大量的基本引數會影響最終的預測系統的表現，正如預期的那樣，最重要的就是擁有好的特征組合，這些特征會捕捉用戶或者廣告的歷史資訊并且還會占據主導地位在所有的特征中，一旦我們有了這些特征并且使用了我們的混合模型，其它的特征因子將起到很小的作用，挑選一些最優的資料處理方式，例如資料新鮮度、學習率模式、資料采樣，這些都會輕微的提升模型的性能，但是提升的幅度仍會小于擁有高效的特征組合或者是使用正確的模型，

三、實驗設定

為了實作嚴格的控制實驗，我們準備了線下資料通過挑選出任意一周的資料，為了保持相同的訓練和測驗集資料分布在不同的條件下，我們準備的線下資料是與線上觀測到的資料是相似的，我們將線下資料分成了訓練集和測驗集，并且使用它們去模型資料流，對于線上訓練和預測，

3.1 評估指標

因為我們最關心的是特征對整個模型的影響，所以我們使用了預測準確率作為衡量指標而不是以和利益或者收入相關的指標，我們使用Normalized Entropy(NE)和Calibration作為我們主要的評估指標，

NE的評估公式為：
N E = ? 1 N ∑ i = 1 n ( 1 + y i 2 l o g ( p i ) + 1 ? y i 2 l o g ( 1 ? y i ) ) ? ( p ? ( l o g ( p ) ) + ( 1 ? p ) ? l o g ( 1 ? p ) ) NE=\frac{-\frac{1}{N}\sum_{i=1}^n(\frac{1+y_i}{2}log(p_i)+\frac{1-y_i}{2}log(1-y_i))}{-(p*(log(p))+(1-p)*log(1-p))} NE=?(p?(log(p))+(1?p)?log(1?p))?N1?∑i=1n?(21+yi??log(pi?)+21?yi??log(1?yi?))?
Calibration評估指標：Calibration是平均估計CTR和經驗CTR之比，換句話說，它是預測點擊次數與實際觀察到的點擊次數之比，它是個非常重要的指標，準確預測CTR是在線招標和拍賣成功的關鍵，

注意到，AUC也是一個非常好的評估指標對于衡量排序質量如果不考慮Calibration，在真實的環境中，我們期望的是準確的預測而不是僅僅得到最優的排序，

四、預測模型結構

4.1 決策樹特征變換

由于線性模型過于簡單，它只能夠捕捉線性特征，對于非線性是無能為力的，這就會導致如果使用邏輯回歸進行建模會導致丟失很多資料資訊，雖然現在很多模型都可以捕捉非線性關系，但是它們的計算復雜度大，線性回歸演算法簡單，容易實作并行，對于海量資料能大幅提高計算效率，那么我們就希望有沒有一種方法可以轉化特征，變成線性回歸可以擬合的資料，

兩種轉化特征的方法分別是：

• 連續型：將特征進行分箱，然后將每個箱的索引作為類別特征
• 類別型：對所有類別特征做笛卡爾積，產生組合特征

對于類別特征做笛卡爾積產生的新特征，不是所有的特征都是有用的，那么怎樣才能組合出高效的特征呢，

我們發現梯度提升樹是一個強有力而且很方面去實作非線性和成對特征組合，我們將每個獨立的樹作為一個分類特征，然后使用OneHot編碼將其轉化成特征，例如，如果一個梯度提升樹有兩個子樹，第一顆子樹有3個葉子節點，第二顆子樹有兩個節點，假如樣本x分別落在了第一個子樹的第二個葉子節點，落在了第二顆子樹的第1個葉子節點，那么我們就可以為其進行編碼為【0，1，0，1，0】，在每次學習迭代的程序中，一個新的樹會擬合前一棵樹的殘差，我們能夠理解梯度提升樹基于轉化作為一個有監督的特征編碼，會將一個真值向量轉化成一個稠密的二值化向量，從根節點進行遍歷到葉子節點，這時就會呈現一個規則對于某種特征，可以理解為這個樣本可以按照這個路徑的特征來進行區分，梯度提升樹是以一個批次的方式進行訓練，

我們執行了這個實驗去展示將提升樹產生的特征輸入到線性模型的效果，在這個實驗中，我們對比了邏輯回歸模型，一個是帶有融合特征，另外一個是原始特征，我們也使用了一個梯度提升樹模型僅僅用于對比，

提升樹產生的特征幫助我們的模型減少3.4%的損失使用NE熵，這是一個重大的提升，

4.2 資料新鮮度

點擊預測系統通常被部署在一個動態的環境下，這個資料的分布會隨著時間而改變，我們研究了訓練資料新鮮度對于預測表現的影響，為了驗證這個，我們訓練了一個模型根據某一特定天的資料，然后進行驗證測驗使用之后連續幾天的資料，我們進行這個實驗使用的是梯度提升樹和邏輯回歸的模型帶有融合獲得的特征，

在這個實驗中，我們訓練了一天的資料，然后對改天接下來的六天的資料進行了評估并且計算了NE，

結果表明，預測精度隨著每天的推移，訓練集和測驗集的精度都有所下降，很容易看出，如果我們從每周訓練一次到每天訓練一次，我們的模型的表現幾乎可以提高1%，

這些發現表明，我們是很值得每天進行重新訓練模型的，一個選擇就是我們每天將會有一個重復的作業就是重新訓練模型，可能是以批次進行訓練，重新訓練梯度提升樹模型的時間可能依賴不同的因素，例如：訓練集的規模大小、樹的數目、每棵樹葉子節點的個數、CPU、記憶體大小等，如果我們采用單核CPU進行訓練百萬級別的資料，使用幾百棵樹的模型進行訓練，那么我們的訓練時間可能超過24個小時，但實際情況是，如果我們采用多核并行訓練，訓練時間可能縮小到幾個小時內，原因是多核并行可以將整個訓練集加載到記憶體中進行計算，

梯度提升樹需要每天重新訓練或者每兩天訓練一次，但是我們的線性分類器需要通過在線學習進行實時學習，

4.3 在線線性分類器

為了最大化資料的新鮮程度，一個選擇就是在線訓練線性分類器，也就是說，當推薦廣告到達的時候，我們就會為其打標簽，然后進行建模，在接下來的章節，我們會描述一個基礎架構，能夠產生實時的訓練資料，在這個部分我們會評估幾種設定學習率的方式對于邏輯回歸使用SGD進行求解，我們然后對比最好的變體對于在線學習與BOPR模型，

1.Per-coordinate learning rate：
η t , i = α β + ∑ j = 1 t g r a d j , i 2 \eta_{t,i}=\frac{\alpha}{\beta+\sqrt{\sum_{j=1}^tgrad_{j,i}^2}} ηt,i?=β+∑j=1t?gradj,i2? ?α?
2.Per-weight square root learning rate：
η t , i = α n t , i \eta_{t,i}=\frac{\alpha}{\sqrt{n_{t,i}}} ηt,i?=nt,i? ?α?
3.Per-weight learning rate：
η t , i = α n t , i \eta_{t,i}=\frac{\alpha}{n_{t,i}} ηt,i?=nt,i?α?
4.Global learning rate：
η t , i = α t \eta_{t,i}=\frac{\alpha}{\sqrt t} ηt,i?=t ?α?
5.Constant learning rate：
η t , i = α \eta_{t,i}=\alpha ηt,i?=α
前三個設定學習率的模式每個特征之間是獨立的，而后兩個對于所有的特征學習率是相同的，所有可以調節的引數都會使用網格搜索進行優化，

對于持續學習，我們將學習率下界設定為0.00001，我們訓練和測驗是使用相同的資料，然后使用上述的幾種設定學習率的模式然后進行對比，

從上述的結果，我們發現，SGD使用每個可調節的學習率實作了最好的預測精度，大約比使用每個權重的學習模式的NE低了大概5%，使用square root 和constant的學習模式是差不多的，另外兩個學習模式比這幾個的精度都要差，全域學習率模式失敗主要是由于訓練集的樣本資料對于每個特征的分布不均衡，因為每個訓練樣例可能包含不同的特征，一些受歡迎的特征將會得到更多的訓練相對于其它的特征，在全域學習率的模式下，對于較少的示例將會減小的非常快，并且阻止了演算法的收斂，盡管per-weight學習率模式解決了這個問題，但是它仍然失敗了，因為它將會減少所有特征的學習率，訓練停止太早，會導致模型只收斂到區域最優位置，這也就是為什么，這個學習率模式會是所有選擇中表現最差的，

我們執行了一個實驗去對比使用per-coordinate SGD和BOPR在同一資料集上的表現，我們給出了相似的定性模型更新方程，結果BOPR和SGD有著非常接近的預測表現使用NE或者是calibration指標，

LR相對于BOPR的一個優點是模型大小為一半，因為每個稀疏特征值只慣量一個權重，而不是均值和方差，在執行程序中，較小的型號可能導致更好的快取區域性，從而加快快取查找速度，在預測是的計算費用方面，LR模型只需要在特征向量和權重上求一個內積，而BOPR模型則需要兩個內積作為方差向量和帶特征向量的均值向量，

與LR相比，BOPR的一個重要優點是它是一個貝葉斯模型，它提供了一個完全的點擊概率分布，這可用于計算點擊分布的百分位數，可用于探索或者開發新的學習方案，

五、在線資料連接器

之前的部分表明新的資料會導致增加預測精度，它也呈現了一個簡單的模型架構，就是線性分類器是在線學習，

這個部分介紹了一個實驗系統能夠產生實時的訓練資料用于訓練線性分類器通過在線學習，我們將使用這個系統作為在線連接器，去將標簽（用戶點擊或不點擊）與訓練資料（推薦廣告）連接起來作為新的訓練輸入資料，

這和Google Advertising System被用于流計算的例子十分相像，在線資料連接器會輸出一個實時的訓練資料流給一個結構叫做Scribe，我們定義廣告被點擊為正樣本，不點擊為負樣本，但是對于推薦廣告對于用戶來說是沒有不點擊的按鈕的，那么我們就無法判斷用戶是否會點擊該廣告，對于這個原因我們將考慮使用一個時間停留視窗，如果當一個廣告出現后，如果在指定的時間內用戶沒有點擊，我們將視為用戶沒有點擊，關于這個時間視窗的等待時間需要仔細設定，

• 點擊時間長：會導致實時資料的延誤，增加分配給緩沖的記憶體用于等待用戶點擊的信號
• 點擊時間短：會導致資料的丟失，如果時間太短，可能一個用戶會點擊這個廣告，由于時間短，在該時間內還沒有點擊就結束了

所以針對這個現象，就必須時間和點擊覆寫取得權衡，

六、包含記憶體和延遲

6.1 提升樹的數目

如果樹的棵數越多，模型對一個預測所需要的時間就越長，在這個部分，我們將會研究提升樹的數目對于評估精度的影響，

我們改變樹的個數從1-2000，并且訓練這個模型使用一整天的資料然后進行預測評估使用接下來一天的資料，我們強制約束每棵樹的葉子節點個數不超過12個，和之前的實驗一樣，我們使用NE作為評估準則，

通過結果我們發現隨著樹的個數越多，模型的NE越來越小，但是當樹的個數達到500棵左右，NE的下降趨勢越來越小，而且最后增加1000棵樹減少的NE少于0.1%，而且我們還看到使用NE submodel2的模型當樹的棵數達到1000時，模型的效果反而有點倒退，原因就是隨著樹的數目增加，模型產生了過擬合效應，這是因為submodel2的資料集的規模相對于模型0和模型1的資料集規模小了近4倍左右，

6.2 增加特征的重要性

特征數目是模型的另外一個特征能夠影響均衡評估精度和預測時間，為了更好的了解特征數目的影響，我們首先應用一個特征到每個特征中，

為了衡量一個特征的重要性，我們使用了statistic Boosting Feature Importance，這樣的目的是為了捕獲計算每個特征減少的損失，在進行構建每個節點的程序中，挑選最好的特征作為分割節點，然后去最大化平方損失，因為一個特征可能用于多棵樹的構建，所以每個特征的損失需要計算所有樹對于這個特征的損失之和，

結果表明，top10的特征的重要性占據了所有的一半，然而最后300個特征貢獻卻不足1%，基于這個發現，我們進一步研究了top10、20、50、100和200個特征的影響，并且它們是怎樣影響模型的表現的，

6.3 歷史特征

在提升樹模型中使用的特征主要可以分成兩類：背景關系特征、歷史特征，

• 背景關系特征：依賴于當前的背景關系資訊，比如用戶設備的型號、用戶當前所在的頁面
• 歷史特征：依賴于用戶和廣告先前的互動資訊，比如這條廣告上周的點擊率或者用戶的平均點擊率

在這個部分，我們將會研究系統依賴這兩類特征的表現，首先我們會先查兩類特征的的相關的重要性，我們通過重要性將特征進行排序，然后計算每個歷史特征的重要性，

通過結果表明，我們可以發現歷史特征可以提供更多的解釋性比背景關系特征，最重要的10個特征都是基于歷史特征，在前20個特征中，只有兩個特征是背景關系特征，為了更好的了解每種型別特征的對比，我們訓練了兩個提升樹模型分別僅僅使用背景關系特征和歷史特征，然后對比兩個模型和全部特征的比較，

從結果我們可以發現歷史特征是發揮了更大的作用比背景關系特征，

但是背景關系特征也有個重要的作用就是能夠解決冷啟動問題，對于新的用戶和新的廣告，背景關系特征是不依賴于點擊率進行預測的，

接下來，我們評估了訓練模型只使用背景關系特征和歷史特征在連續周的訓練資料針對于資料新鮮度的問題，我們發現有著背景關系的特征是更加依賴于資料新鮮度的相對于歷史特征，這符合我們的直覺，因為歷史功能描述了長期積累的用戶行為，這比背景關系功能更穩定，

七、處理海量資料

Facebook每天的廣告資料多大幾億的資料量，為了減少訓練的消耗，我們通用的做法就是減少訓練資料的列數，在這個部分我們會評估兩種下采樣的方式，分別是：uniform subsampling和negative down sampling，我們會訓練兩個包含600棵樹的模型，然后使用calibration和NE作為評估指標進行評估，

7.1 Uniform subsampling

對訓練行進行均勻子抽樣是一種很有吸引力的減少資料量的方法，因為它既易于實作，而且生成的模型可以在不修改下采樣訓練資料和非下采樣測驗資料的情況下使用，在這一部分，我們評估一組粗略指數增長的子抽樣率，對于每個速率，我們訓練一個增強的樹模型，以該速率從基礎資料集采樣，我們分別設定了采樣率為【0.001，0.01，0.1，0.5，1】

通過結果可以表明，我們僅僅使用總共資料10%的資料，我們的模型表現僅僅下降了1%，可以看到均勻采樣是有一定幫助的，在犧牲小的精度換的更高的時間效率，

7.2 Negative down sampling

類別不平衡已經被許多研究者進行研究，并且表明類別不平衡對模型的表現有著重大的影響，在這個部分，我們使用Negative down sampling去解決這個問題，我們使用不同的比率盡心采樣，然后去測驗模型的精度，我們設定采樣率分別為【0.1，0.01，0.001，0.0001】，

從結果發現，我們能夠看到negative down sampling采樣率有著重大的影響對于模型的表現，最好的表現是我們將這個比率設立在0.025，

八、總結

我們已經呈現了一些來自實驗的經驗關于Facebook廣告資料，這啟發了一個很有前途的混合模型體系結構，用于點擊預測領域，

• Data freshness matters：我們至少每天都要將模型進行重新訓練，本篇論文中我們進一步研究了不同種的在線學習模式，我們也給出了基礎架構允許生成實時的訓練資料，
• 使用梯度提升樹進行轉化特征極大的增加了線性分類器的預測精度，這啟發了一種混合模型體系結構，該體系結構將增強決策樹和稀疏線性分類器連接起來，
• 最優在線學習模式：LR與預協調學習率，最終與BOPR的性能相當，并優于所有正在研究的LR結合SGD的方案

我們已經描述了在大規模機器學習應用程式中保持記憶體和延遲的技巧

• 我們已經提出了改進決策樹的數量和準確性之間的權衡，保持樹的數量小有利于保持計算和記憶體
• 提升樹給予了一個方便的方式去做特征選擇通過特征的重要性，我們可以大幅減少主動特征的數量，同時適度降低預測精度
• 我們分析了歷史特征和背景關系特征的影響對于模型效果，對于廣告和用戶的歷史特征，這些特征會提供更有的預測精度比背景關系特征，

最后，我們討論了對訓練資料進行子采樣的方法，既可以是一致的，更有趣的是，也可以是有偏差的，即只對負樣本進行子采樣，