本文將帶領(lǐng)大家，一起來(lái)重讀一篇經(jīng)典的 CTR 預(yù)估領(lǐng)域的論文，F(xiàn)acebook 在 2014 發(fā)表的《Practical Lessons from Predicting Clicks on Ads at Facebook》。

在這篇文章中，F(xiàn)acebook 提出了經(jīng)典的?GBDT（Gradient Boosting Decision Trees）+LR(Logistics Regression)?的 CTR 模型結(jié)構(gòu)，可以說(shuō)開(kāi)啟了特征工程模型化、自動(dòng)化的新階段。此外其在五年前就采用的?online learning，online data joiner，negative down sampling?等技術(shù)時(shí)至今日也有極強(qiáng)的工程意義。

下面我們就一起回顧一下這篇當(dāng)時(shí)紅極一時(shí)，現(xiàn)在仍?？闯Ｐ碌恼撐陌?。

用戶場(chǎng)景

文章的用戶場(chǎng)景是一個(gè)標(biāo)準(zhǔn)的點(diǎn)擊率預(yù)估的場(chǎng)景，需要強(qiáng)調(diào)的只有一點(diǎn)，因?yàn)槲覀冃枰?CTR 計(jì)算精準(zhǔn)的出價(jià)、ROI 等重要的后續(xù)預(yù)估值，因此 CTR 模型的預(yù)估值需要是一個(gè)具有物理意義的精準(zhǔn)的 CTR，而不是僅僅輸出廣告排序的高低關(guān)系。所以文中不僅把 CTR calibration 作為重要的評(píng)價(jià)指標(biāo)，更是在最后介紹了模型校正的相關(guān)方法。

模型結(jié)構(gòu)

計(jì)算廣告方向的同學(xué)應(yīng)該都對(duì) GBDT+LR 這個(gè)模型有所了解，這一點(diǎn)也無(wú)益是這篇文章最大的貢獻(xiàn)。雖然文章其他部分的價(jià)值絲毫不遜于該模型，但再次回顧該模型，清楚知道其技術(shù)細(xì)節(jié)還是必要的。

簡(jiǎn)而言之，文章提出了一種利用 GBDT 自動(dòng)進(jìn)行特征篩選和組合，進(jìn)而生成新的 feature vector，再把該 feature vector 當(dāng)作 logistic regression 的模型輸入，預(yù)測(cè) CTR 的模型結(jié)構(gòu)。

GBDT+LR 模型結(jié)構(gòu)

這里需要強(qiáng)調(diào)的是，用 GBDT 構(gòu)建特征工程，和利用 LR 預(yù)測(cè) CTR 兩步是獨(dú)立訓(xùn)練的。所以自然不存在如何將 LR 的梯度回傳到 GBDT 這類復(fù)雜的問(wèn)題，而利用 LR 預(yù)測(cè) CTR 的過(guò)程是顯然的，在此不再贅述，我們著重講一講如何利用 GBDT 構(gòu)建新的特征向量。

大家知道，GBDT 是由多棵回歸樹(shù)組成的樹(shù)林，后一棵樹(shù)利用前面樹(shù)林的結(jié)果與真實(shí)結(jié)果的殘差做為擬合目標(biāo)。每棵樹(shù)生成的過(guò)程是一棵標(biāo)準(zhǔn)的回歸樹(shù)生成過(guò)程，因此每個(gè)節(jié)點(diǎn)的分裂是一個(gè)自然的特征選擇的過(guò)程，而多層節(jié)點(diǎn)的結(jié)構(gòu)自然進(jìn)行了有效的特征組合，也就非常高效的解決了過(guò)去非常棘手的特征選擇和特征組合的問(wèn)題。

我們利用訓(xùn)練集訓(xùn)練好 GBDT 模型，之后就可以利用該模型構(gòu)建特征工程。具體過(guò)程是這樣的，一個(gè)樣本在輸入 GBDT 的某一子樹(shù)后，會(huì)根據(jù)每個(gè)節(jié)點(diǎn)的規(guī)則最終落入某一葉子節(jié)點(diǎn)，那么我們把該葉子節(jié)點(diǎn)置為 1，其他葉子節(jié)點(diǎn)置為 0，所有葉子節(jié)點(diǎn)組成的向量即形成了該棵樹(shù)的特征向量，把 GBDT 所有子樹(shù)的特征向量 concatenate 起來(lái)，即形成了后續(xù) LR 輸入的特征向量。

舉例來(lái)說(shuō)，比如 GBDT 由三顆子樹(shù)構(gòu)成，每個(gè)子樹(shù)有 4 個(gè)葉子節(jié)點(diǎn)，一個(gè)訓(xùn)練樣本進(jìn)來(lái)后，先后落到了「子樹(shù) 1」的第 3 個(gè)葉節(jié)點(diǎn)中，那么特征向量就是 [0,0,1,0]，「子樹(shù) 2」的第 1 個(gè)葉節(jié)點(diǎn)，特征向量為 [1,0,0,0]，「子樹(shù) 3」的第 4 個(gè)葉節(jié)點(diǎn)，特征向量為 [0,0,0,1]，最后 concatenate 所有特征向量，形成的最終的特征向量為 [0,0,1,0,1,0,0,0,0,0,0,1]，我們?cè)侔言撓蛄孔鳛?LR 的輸入，預(yù)測(cè) CTR。

引入了 GBDT+LR 的模型后，相比單純的 LR 和 GBDT，提升效果是非常顯著的。從下表中可以看到，混合模型比單純的 LR 或 Trees 模型在 loss 上減少了 3%。

LR+Trees 模型的 Loss 對(duì)比

為了確定最優(yōu)的 GBDT 子樹(shù)規(guī)模，facebook 繪出了子樹(shù)規(guī)模和 loss 的關(guān)系曲線如下：

GBDT 子樹(shù)數(shù)量與 loss 的關(guān)系

可以看到，在規(guī)模超過(guò) 500 棵子樹(shù)后，增加子樹(shù)規(guī)模對(duì)于 loss 下降的貢獻(xiàn)就微乎其微了。特別是最后 1000 棵子樹(shù)僅貢獻(xiàn)了 0.1% 的 loss 下降，最終 facebook 選擇了 600 作為其子樹(shù)規(guī)模。

該模型的優(yōu)勢(shì)我們上面已經(jīng)提到，即可以自動(dòng)進(jìn)行特征組合和特征篩選，但在實(shí)踐過(guò)程中，模型的缺陷也比較明顯，相比 FTRL，F(xiàn)M，NN 等能夠通過(guò)梯度下降訓(xùn)練的模型來(lái)說(shuō)，GBDT 缺乏 online learning 的能力，因此我們往往只能相隔一天甚至幾天才能夠 update GBDT 模型，勢(shì)必影響模型的實(shí)效性，那么 Facebook 是如何解決模型更新的問(wèn)題的呢？

模型的實(shí)效性問(wèn)題和更新策略

雖然我們的直覺(jué)是模型的訓(xùn)練時(shí)間和 serving 時(shí)間之間的間隔越短，模型的效果越好，但為了證明這一點(diǎn)，facebook 的工程師還是做了一組實(shí)效性的實(shí)驗(yàn)，在結(jié)束模型的訓(xùn)練之后，觀察了其后 6 天的模型 loss（這里采用 normalized entropy 作為 loss）。

模型更新延遲與 loss 的關(guān)系

可以看出，模型的 loss 在第 0 天之后有所上升，特別是第 2 天過(guò)后顯著上升。因此 daily update 的模型相比 weekly update 的模型效果肯定是有大幅提升的。

但囿于 facebook 巨大的數(shù)據(jù)量以及?GBDT 較難實(shí)施并行化的原因，GBDT 的更新時(shí)間往往超過(guò) 24 小時(shí)，所以為了兼顧 data freshness 和客觀的工程要求，facebook 采取了下面的模型更新方法：

The boosted decision trees can be trained daily or every couple of days, but the linear classifier can be trained in near real-time by using some flavor of online learning.

就是說(shuō) GBDT 的部分幾天更新一次，而 LR 的部分進(jìn)行準(zhǔn)實(shí)時(shí)的更新，這無(wú)疑是很好的工程實(shí)踐經(jīng)驗(yàn)。時(shí)至今日，我們已經(jīng)開(kāi)始使用大量不同的 embedding 方法進(jìn)行特征編碼，facebook 當(dāng)時(shí)的做法也對(duì)我們現(xiàn)在的工程實(shí)踐有重要的參考價(jià)值。因?yàn)榇罅可疃葘W(xué)習(xí) embedding 方法的更新計(jì)算開(kāi)銷也非常大，但對(duì)實(shí)效性要求并不高，我們也完全可以低頻更新 embedding，高頻或?qū)崟r(shí)更新基于 embedding 特征的 LR，NN 等預(yù)測(cè)模型。

facebook 的實(shí)時(shí)數(shù)據(jù)流架構(gòu)

為了實(shí)現(xiàn)模型的準(zhǔn)實(shí)時(shí)訓(xùn)練，facebook 專門介紹了其基于 Scribe 的數(shù)據(jù)流架構(gòu)，文中稱其為?online data joiner。

該模塊最重要的作用是準(zhǔn)實(shí)時(shí)的把來(lái)自不同數(shù)據(jù)流的數(shù)據(jù)整合起來(lái)形成 sample features，并最終與 click 數(shù)據(jù)進(jìn)行 join，形成完整的 labeled sample。在整個(gè)過(guò)程中，我認(rèn)為最應(yīng)該注意的有三點(diǎn)：

1. waiting window 的設(shè)定：waiting window 指的是在 impression 發(fā)生后，我們要等待多久才能夠判定一個(gè) impression 是否有 click。如果 waiting window 過(guò)大，數(shù)據(jù)實(shí)時(shí)性受影響，如果 waiting window 過(guò)小，會(huì)有一部分 click 來(lái)不及 join 到 impression，導(dǎo)致樣本 CTR 與真實(shí)值不符。這是一個(gè)工程調(diào)優(yōu)的問(wèn)題，需要有針對(duì)性的找到跟實(shí)際業(yè)務(wù)匹配的合適的 waiting window。除此之外，無(wú)論怎樣我們都會(huì)漏掉一部分 click，這就要求我們階段性的全量 retrain 我們的模型，避免 online learning 誤差的積累。
2. 分布式的架構(gòu)與全局統(tǒng)一的 action id：為了實(shí)現(xiàn)分布式架構(gòu)下 impression 記錄和 click 記錄的 join，facebook 除了為每個(gè) action 建立全局統(tǒng)一的 request id 外，還建立了 HashQueue 緩存 impressions。hashQueue 緩存的 impression，如果在窗口過(guò)期時(shí)還沒(méi)有匹配到 click 就會(huì)當(dāng)作 negative sample，這里說(shuō)的窗口與上面提到的 waiting window 相匹配。facebook 使用 scribe 實(shí)現(xiàn)了這一過(guò)程，更多公司使用 Kafka 完成大數(shù)據(jù)緩存和流處理。
3. 數(shù)據(jù)流保護(hù)機(jī)制：facebook 專門提到了 online data joiner 的保護(hù)機(jī)制，因?yàn)橐坏?data joiner 失效，比如 click stream 無(wú)法 join impression stream，那么所有的樣本都會(huì)成為負(fù)樣本，由于模型實(shí)時(shí)進(jìn)行 online learning 和 serving，模型準(zhǔn)確度將立刻受到錯(cuò)誤樣本數(shù)據(jù)的影響，進(jìn)而直接影響廣告投放和公司利潤(rùn)，后果是非常嚴(yán)重的。為此，facebook 專門設(shè)立了異常檢測(cè)機(jī)制，一旦發(fā)現(xiàn)實(shí)時(shí)樣本數(shù)據(jù)流的分布發(fā)生變化，將立即切斷 online learning 的過(guò)程，防止預(yù)測(cè)模型受到影響。

降采樣和模型校正

對(duì)于巨型互聯(lián)網(wǎng)公司來(lái)說(shuō)，為了控制數(shù)據(jù)規(guī)模，降低訓(xùn)練開(kāi)銷，降采樣幾乎是通用的手段，facebook 實(shí)踐了兩種降采樣的方法，uniform subsampling 和 negative down sampling。

uniform subsampling?是對(duì)所有樣本進(jìn)行無(wú)差別的隨機(jī)抽樣，為選取最優(yōu)的采樣頻率，facebook 試驗(yàn)了 0.001，0.01，0.1，0.5 和 1 五個(gè)采樣頻率，loss 的比較如下：

可以看到當(dāng)采樣率是 10% 時(shí)，相比全量數(shù)據(jù)訓(xùn)練的模型，僅損失了不到 1% 的效果。

另一種方法?negative down sampling?保留全量正樣本，對(duì)負(fù)樣本進(jìn)行降采樣。除了提高訓(xùn)練效率外，負(fù)采樣還直接解決了正負(fù)樣本不均衡的問(wèn)題，facebook 經(jīng)驗(yàn)性的選擇了從 0.0001 到 0.1 的一組負(fù)采樣頻率，試驗(yàn)效果如下：

大家可以看到，當(dāng)負(fù)采樣頻率在 0.025 時(shí)，loss 不僅優(yōu)于更低的采樣頻率訓(xùn)練出來(lái)的模型，居然也優(yōu)于負(fù)采樣頻率在 0.1 時(shí)訓(xùn)練出的模型，雖然原文沒(méi)有作出進(jìn)一步的解釋，但推測(cè)最可能的原因是解決了數(shù)據(jù)不均衡問(wèn)題帶來(lái)的效果提升。

負(fù)采樣帶來(lái)的問(wèn)題是 CTR 預(yù)估值的漂移，比如真實(shí) CTR 是 0.1%，進(jìn)行 0.01 的負(fù)采樣之后，CTR 將會(huì)攀升到 10% 左右。而為了進(jìn)行準(zhǔn)確的競(jìng)價(jià)以及 ROI 預(yù)估等，CTR 預(yù)估模型是要提供準(zhǔn)確的有物理意義的 CTR 值的，因此在進(jìn)行負(fù)采樣后需要進(jìn)行 CTR 的校正，使 CTR 模型的預(yù)估值的期望回到 0.1%。校正的公式如下：

其中 q 是校正后的 CTR，p 是模型的預(yù)估 CTR，w 是負(fù)采樣頻率。大家可以利用簡(jiǎn)單的轉(zhuǎn)換關(guān)系就可以得出上述公式，有興趣的同學(xué)可以手動(dòng)推導(dǎo)一下。

至此，我們介紹完了 facebook 這篇經(jīng)典的 CTR 預(yù)估論文，可以看到雖然五年過(guò)去了，我們?nèi)阅軓闹屑橙〔簧倌Ｐ透脑旌凸こ虒?shí)現(xiàn)的經(jīng)驗(yàn)，就我個(gè)人來(lái)言，最值得學(xué)習(xí)的有下面三點(diǎn)：

1. 特征工程模型化。五年前在很多從業(yè)者還在通過(guò)調(diào)參經(jīng)驗(yàn)嘗試各種特征組合的時(shí)候，利用模型進(jìn)行特征自動(dòng)組合和篩選是相當(dāng)創(chuàng)新的思路，也幾乎是從那時(shí)起，各種深度學(xué)習(xí)和 embedding 的思想開(kāi)始爆發(fā)，一脈相承的發(fā)揚(yáng)著特征工程模型化的思路。
2. 模型復(fù)雜性和實(shí)效性的權(quán)衡。對(duì) GBDT 和 LR 采用不同的更新頻率是非常工程化和有價(jià)值的實(shí)踐經(jīng)驗(yàn)，也是對(duì)組合模型各部分優(yōu)點(diǎn)最大化的解決方案。
3. 有想法要用數(shù)據(jù)去驗(yàn)證。這其實(shí)是我讀完這批文章最大的感觸，在做算法工程師的過(guò)程中，我們其實(shí)是有很多直覺(jué)上的結(jié)論，比如 data freshness 的影響有多大，GBDT 應(yīng)該設(shè)置多少顆子樹(shù)，到底是應(yīng)該用負(fù)采樣還是 uniform 采樣，針對(duì)這些問(wèn)題，facebook 告訴你的是，用數(shù)據(jù)說(shuō)話，無(wú)論是多么小的一個(gè)選擇，都應(yīng)該用數(shù)據(jù)去支撐，這才是一位工程師嚴(yán)謹(jǐn)?shù)墓ぷ鲬B(tài)度。

最后慣例提出兩個(gè)問(wèn)題供大家討論：

• 如果采用 random forest 替代 GBDT，有哪些優(yōu)點(diǎn)和缺點(diǎn)？
• GBDT+LR 這個(gè)模型結(jié)構(gòu)，是否能夠有效處理大量 ID 類特征，為什么？如果希望處理大量 ID 類特征，我們應(yīng)該如何改進(jìn)這個(gè)模型？

參考資料：

Practical Lessons from Predicting Clicks on Ads at Facebook

Computational Advertising Paper List

作者：王喆，硅谷高級(jí)工程師，原文發(fā)表在“知乎專欄 王喆的機(jī)器學(xué)習(xí)筆記”上，雷鋒網(wǎng)（公眾號(hào)：雷鋒網(wǎng)）獲授權(quán)轉(zhuǎn)載。

原文鏈接：https://www.leiphone.com/news/201903/5Z2Hn1mKQ42zSaRr.html

本文來(lái)源于人人都是產(chǎn)品經(jīng)理合作媒體 @雷鋒網(wǎng)，作者@王喆

題圖來(lái)自Unsplash，基于CC0協(xié)議。