CTR點擊率預估
4 人贊了文章
1.指標
點擊率預估主要有兩個層次的指標： 1.排序指標。排序指標是最基本的指標，它決定了我們有沒有能力把最合適的廣告找出來去呈現給最合適的用戶。這個是變現的基礎，從技術上，我們用AUC來度量。2.數值指標。數值指標是進一步的指標，是競價環節進一步優化的基礎，一般DSP比較看中這個指標。如果我們對CTR普遍低估，我們出價會相對保守，從而使得預算花不出去或是花得太慢；如果我們對CTR普遍高估，我們的出價會相對激進，從而導致CPC太高。
3.數據探索(data exploration)
主要是基礎特徵(raw feature/fundamental feature)的粗篩和規整。展示廣告的場景可以表述為」在某場景下，通過某媒體向某用戶展示某廣告」，因此基礎特徵就在這四個範圍內尋找：場景 – 當時場景，如何時何地，使用何種設備，使用什麼瀏覽器等廣告 – 包括廣告主特徵，廣告自身的特徵如campaign、創意、類型，是否重定向等媒體 – 包括媒體(網頁、app等)的特徵、廣告位的特徵等
用戶 – 包括用戶畫像，用戶瀏覽歷史等單特徵選擇的方法有下面幾種：
1.簡單統計方法，統計特徵取值的覆蓋面和平衡度,對dominant取值現象很顯著的特徵，要選擇性地捨棄該特徵或者是歸併某些取值集到一個新的值，從而達到平衡的目的。2.特徵選擇指標，特徵選擇主要有兩個目的，一是去除冗餘的特徵，也就是特徵之間可能是互相冗餘的；二是去無用，有些特徵對CTR預估這個任務貢獻度很小或沒有，對於這類特徵選擇，要小小地做，寧不足而不過分，因為單特徵對任務貢獻度小，很有可能後面再組合特徵生成時與其他特徵組合生成很有效的組合特徵，所以做得不能太過。a) 去冗餘。主要是特徵間的相關性，如Pearson相關性，或者指數回歸(從泰勒定理的角度它可以模擬高階的多項式特徵)。b) 去無用。主要是信息增益比。4.特徵組合
兩派方法：FM系列 – 對於categorical feature，把他們encode成one hot的形式，特徵組合適合用FM。Tree系列 – 對於numerical feature和ordinal feature, 特徵組合可以使用決策樹類的，一般用random forest或GBDT。其中GBDT的效果應該更好，因為boosting方法會不斷增強對錯判樣本的區分能力。
對於廣告點擊率預估，同時擁有這三類特徵。所以一個簡單的方法就是級聯地使用這兩個方法，更好地進行特徵組合。
5.LR
a. OWL-QN這個是batch訓練的方法，主要用於處理L1正則下的LR最優化。b. Online learning(FTRL and Facebook enhancement)在線學習，及時反饋點擊信息，不斷演化LR模型，從而為新廣告更快收斂。CTR預估中用的最多的模型是LR（Logistic Regression），LR是廣義線性模型，與傳統線性模型相比，LR使用了Logit變換將函數值映射到0~1區間，映射後的函數值就是CTR的預估值。LR這種線性模型很容易並行化，處理上億條訓練樣本不是問題，但線性模型學習能力有限，需要大量特徵工程預先分析出有效的特徵、特徵組合，從而去間接增強LR的非線性學習能力。
LR模型中的特徵組合很關鍵， 但又無法直接通過特徵笛卡爾積解決，只能依靠人工經驗，耗時耗力同時並不一定會帶來效果提升。如何自動發現有效的特徵、特徵組合，彌補人工經驗不足，縮短LR特徵實驗周期，是亟需解決的問題。Facebook 2014年的文章介紹了通過GBDT（Gradient Boost Decision Tree）解決LR的特徵組合問題，隨後Kaggle競賽也有實踐此思路，GBDT與LR融合開始引起了業界關注。
GBDT（Gradient Boost Decision Tree）是一種常用的非線性模型，它基於集成學習中的boosting思想，每次迭代都在減少殘差的梯度方向新建立一顆決策樹，迭代多少次就會生成多少顆決策樹。GBDT的思想使其具有天然優勢可以發現多種有區分性的特徵以及特徵組合，決策樹的路徑可以直接作為LR輸入特徵使用，省去了人工尋找特徵、特徵組合的步驟。這種通過GBDT生成LR特徵的方式（GBDT+LR），業界已有實踐（Facebook，Kaggle-2014），且效果不錯，是非常值得嘗試的思路。下圖1為使用GBDT+LR前後的特徵實驗示意圖，融合前人工尋找有區分性特徵（raw feature）、特徵組合（cross feature），融合後直接通過黑盒子（Tree模型GBDT）進行特徵、特種組合的自動發現。
6 GBDT與LR融合現狀
GBDT與LR的融合方式，Facebook的paper有個例子如下圖2所示，圖中Tree1、Tree2為通過GBDT模型學出來的兩顆樹，x為一條輸入樣本，遍歷兩棵樹後，x樣本分別落到兩顆樹的葉子節點上，每個葉子節點對應LR一維特徵，那麼通過遍歷樹，就得到了該樣本對應的所有LR特徵。由於樹的每條路徑，是通過最小化均方差等方法最終分割出來的有區分性路徑，根據該路徑得到的特徵、特徵組合都相對有區分性，效果理論上不會亞於人工經驗的處理方式。
GBDT模型的特點，非常適合用來挖掘有效的特徵、特徵組合。業界不僅GBDT+LR融合有實踐，GBDT+FM也有實踐，2014 Kaggle CTR競賽冠軍就是使用GBDT+FM，可見，使用GBDT融合其它模型是非常值得嘗試的思路。
筆者調研了Facebook、Kaggle競賽關於GBDT建樹的細節，發現兩個關鍵點：採用ensemble決策樹而非單顆樹；建樹採用GBDT而非RF（Random Forests）。解讀如下：
1） 為什麼建樹採用ensemble決策樹？
一棵樹的表達能力很弱，不足以表達多個有區分性的特徵組合，多棵樹的表達能力更強一些。GBDT每棵樹都在學習前面棵樹尚存的不足，迭代多少次就會生成多少顆樹。按paper以及Kaggle競賽中的GBDT+LR融合方式，多棵樹正好滿足LR每條訓練樣本可以通過GBDT映射成多個特徵的需求。
2） 為什麼建樹採用GBDT而非RF？
RF也是多棵樹，但從效果上有實踐證明不如GBDT。且GBDT前面的樹，特徵分裂主要體現對多數樣本有區分度的特徵；後面的樹，主要體現的是經過前N顆樹，殘差仍然較大的少數樣本。優先選用在整體上有區分度的特徵，再選用針對少數樣本有區分度的特徵，思路更加合理，這應該也是用GBDT的原因
7 GBDT與LR融合方案
AD ID類特徵在CTR預估中是非常重要的特徵，直接將AD ID作為feature進行建樹不可行，顧考慮為每個AD ID建GBDT樹。但互聯網時代長尾數據現象非常顯著，廣告也存在長尾現象，為了提升廣告整體投放效果，不得不考慮長尾廣告。在GBDT建樹方案中，對於曝光充分訓練樣本充足的廣告，可以單獨建樹，發掘對單個廣告有區分度的特徵，但對於曝光不充分樣本不充足的長尾廣告，無法單獨建樹，需要一種方案來解決長尾廣告的問題。
綜合考慮方案如下，使用GBDT建兩類樹，非ID建一類樹，ID建一類樹。1）非ID類樹：不以細粒度的ID建樹，此類樹作為base，即便曝光少的廣告、廣告主，仍可以通過此類樹得到有區分性的特徵、特徵組合。2）ID類樹：以細粒度的ID建一類樹，用於發現曝光充分的ID對應有區分性的特徵、特徵組合。
如何根據GBDT建的兩類樹，對原始特徵進行映射？當一條樣本x進來之後，遍歷兩類樹到葉子節點，得到的特徵作為LR的輸入。當AD曝光不充分不足以訓練樹時，其它樹恰好作為補充。
通過GBDT 映射得到的特徵空間維度如何？GBDT樹有多少個葉子節點，通過GBDT得到的特徵空間就有多大。如下圖4一顆樹，一個葉子節點對應一種有區分性的特徵、特徵組合，對應LR的一維特徵。這顆樹有8個葉子節點，即對應LR 的8維特徵。估算一下，通過GBDT轉換得到的特徵空間較低，Base樹、ID樹各N顆，特徵空間維度最高為（N+N*廣告數+N*廣告主數+ N*廣告類目數）*葉子節點個數。其中廣告數、廣告主數、廣告類目數都是有限的，同時參考Kaggle競賽中樹的數目N最多為30，葉子節點個數小於10，則估算通過GBDT 映射得到的特徵空間維度並不高，且並不是每個ID訓練樣本都足以訓練多顆樹，實際上通過GBDT 映射得到的特徵空間維度更低。
如何使用GBDT 映射得到的特徵？
通過GBDT生成的特徵，可直接作為LR的特徵使用，省去人工處理分析特徵的環節，LR的輸入特徵完全依賴於通過GBDT得到的特徵。此思路已嘗試，通過實驗發現GBDT+LR在曝光充分的廣告上確實有效果，但整體效果需要權衡優化各類樹的使用。同時，也可考慮將GBDT生成特徵與LR原有特徵結合起來使用，待嘗試。
8 總結與展望
點擊率預估模型涉及的訓練樣本一般是上億級別，樣本量大，模型常採用速度較快的LR。但LR是線性模型，學習能力有限，此時特徵工程尤其重要。現有的特徵工程實驗，主要集中在尋找到有區分度的特徵、特徵組合，折騰一圈未必會帶來效果提升。GBDT演算法的特點正好可以用來發掘有區分度的特徵、特徵組合，減少特徵工程中人力成本，且業界現在已有實踐，GBDT+LR、GBDT+FM等都是值得嘗試的思路。不同場景，GBDT融合LR/FM的思路可能會略有不同，可以多種角度嘗試。
CTR預測就是對用戶是否點擊廣告進行預測，其實可以看成二分類問題，即點和不點。因此，自然會想到用logistics回歸來完成這個任務。
logistics回歸(LR)：
優點：
1、logistics輸出的是概率，可以較為直觀的解釋用戶點擊廣告的幾率
2、計算目標函數的複雜度O(N)，計算速度快，所以比較適合處理大數據
缺點：
1、沒有考慮特徵之間的相關性，沒有特徵進行組合
2、為了提高模型性能，在模型訓練之前，需要做很多的特徵工程
GDBT+LR:
使用GDBT的輸出作為LR的輸入
優點：
1、使用GDBT可以組合特徵，增強特徵的表達能力
2、通過控制GDBT中樹的個數和每顆樹的樹葉個數來對數據進行降維
FM：
FM通過對每個特徵都學習一個隱變數，從而考慮到特徵之間的關係。
優點：
1、考慮特徵之間的關係，增強了模型的泛化能力
2、通過對目標函數巧妙的分解合併，可以O(N)時間複雜度下完成
3、適合處理稀疏數據。相對來說SVM就不能用來處理稀疏的數據。
補充：FM一般結合GDBT來提高模型性能，即用GDBT的輸出作為FM的輸入
FFM：
FFM是在FM基礎上進行了改進，提出了filed概念。每個特徵在不同的filed中有不同的隱變數。
優點：
1、在FM模型的基礎，模型的性能得到進一步的提高
2、同樣適合處理稀疏數據
缺點：
1、FFM不像FM那樣可以對目標函數分解合併，在線性時間內完成函數的計算。在時間複雜度上要比FM要複雜。
以二次項為例時間複雜要O(N^2)
也可以用常用的機器學習方法來完成CTR預測，如xgboost、SVM、RF等
推薦閱讀：