CTR預估[十一]: Algorithm-GBDT Encoder

作者：@三瘋蘭尼斯特 && @Ainika Peng

時間：2017年12月

出處：https://zhuanlan.zhihu.com/p/31734283

聲明：版權所有，轉載請聯繫作者並註明出處。

1.4 GBDT Encoder + LR/FM

GBDT編碼之後利用其稀疏特徵加入到傳統的LR/FM 框架中進行優化是Facebook 2014年的思路，在進入具體的encoder方法和實踐之前，我們先看一下GBDT和FM的對比

• FM: 更好的刻畫長尾
• 長尾就是稀疏的沒有出現過的特徵，FM可以算出沒有出現過的特徵組合
• GBDT: 更好的刻畫頭部
• GBDT主要是記憶樣本，所以對頭部更優

而FM+GBDT 融合方式目前看可能有三種

• GBDT leaf信息作為feature加入FM訓練(FB.2014)
• GBDT branch信息作為離散化方案離散化後加入FM訓練
• GBDT + FM分別訓練之後做bagging

下面主要說GBDT Encoder + LR/FM

1.4.1 Method of GBDT Leaf + LR/FM

DT based 特徵轉換(相當於做了N棵樹*m條路徑種的特徵組合)

這個過程可以看做有監督的feature encoding

從GBDT的角度看，encode過程做了什麼呢？

• 特徵離散化 -- Leaf Split對連續值特徵做了離散化
• 特徵組合 -- Multi Layers之間可以視作特徵組合
• 特徵選擇 -- 不是所有的feature, 所有的split都加入Tree

從LR的角度看，encode給了LR什麼？

• 組合特徵 -- LR由於線性假設，組合特徵需要手工添加，GBDT提供了基於Objective的特徵組合

為什麼用ensemble Trees而不是單獨一顆Decision Tree?

• 單獨一棵樹表達的是樣本的一種特徵組合，Ensemble可以表示特徵的多種組合 -- 可以生成N維向量而非只有1維
• 單棵樹通常深度很深，實際不需要如此高維度的特徵組合 -- 組合維度越高，從屬於這個特徵的樣本就越少

同樣是Ensemble Tree, 為什麼用GBDT而不是RF?

• RF生成的node都是同一個粒度的，而adaptive的boosting會生成從最大到很小的粒度的聚合信息 -- GBDT 前面的樹側重對多數樣本有區分度的特徵；後面的樹針對經過前面的樹仍然殘差大的少數樣本
• 從bias and variance角度，RF只降低variance而不改變bias, 而LR線性模型的variance足夠低，需要更多的組合特徵降低bias

1.4.2 In Practice: Parameter Tuning

Facebook源paper中用NE評估效果，給出的效果LR+Tree > LR > Tree

1.4.2.1 Boosting Tree Number

Facebook的paper中給出了GBDT+LR 的數據效果

重要的結論是： Tree Number增長的收益逐漸降低，甚至在過高之後有負向收益 -- 這一點在GBDT+FM中體現尤為明顯

1.4.2.2 GBDT+FM：GBDT 的testAUC 和FM的testAUC是否是正相關的？

GBDT+LR相對效果是比較平穩的 -- 因為LR本身是一個相對平穩的線性模型，不是那麼容易過擬合；

但FM這種非線性模型則不同，本身即容易過擬合，引出的第一個問題是，如何調節參數，使得GBDT+FM兩個非線性模型結果起來不過擬合

即：是否GBDT的testAUC越高，放到FM裡面testAUC越高？

這裡沒有理論推導，做了多次測試發現：兩者的 test AUC 確實是正相關的

調優的時候，選擇可以使test AUC最高的Tree Num即可使GBDT+FM之後的AUC最高

注意：這裡並沒有嚴謹的理論推導，只是我們所使用的數據上的表現；各位MLer如果需要使用請先驗證結論

驗證結論中我們使用了構造數據實驗和線上數據實驗，下面是我們所使用的構造數據和部分實驗結果：

• 特徵構造方法：相關feature(完全線性正相關，上凸相關，分段相關等) + random feature(用來表示雜訊，加大過擬合的負效果)
• 測試效果圖例：
• GBDT表示XgBoost本身的test AUC; FM 表示GBDT Encoder作為特徵使用FM的test AUC；
• 左表中均為test AUC; 右圖中，橫軸為使用GBDT的Tree Number，縱軸為不同Tree Number所對應的GBDT 的test AUC和GBDT Encoder做特徵加入FM的(下簡稱FM)test AUC

Exp 1: GBDT dep=6,fea=線性正相關+5random

Exp 2: GBDT dep=3,fea=混合各類相關特徵+5random

兩個實驗結論類似，FM的峰值test AUC高於單GBDT的，但更容易overfitting（多tree num時）

1.4.3 Feature Selection and 」GBDT Forest「

GBDT Encode系列效果和餵給GBDT的特徵關係甚大，面對GBDT這種high variance模型，尤其要注意過擬合問題

首先考慮特徵類型：

• Numerical Features: GBDT是擅長處理連續值特徵的，所以不需要額外處理
• Categorical features: GBDT處理one-hot特徵是把每個feature當做一個0(no)~1(yes)連續值來處理的，直接打散大量ID類的特徵不僅使GBDT計算緩慢，而且由於過擬合而大幅降低效果

合適於GBDT Encode的特徵是： 有效的Numerical Features和高頻的Categorical features

舉例而言

Kaggle2014 中競賽冠軍使用了這種特徵篩選方法

- All numerical data are included. (13 features)

- Categorical features (after one-hot encoding) appear more than 4 million times are also included. (26 features)

其次考慮特徵強度

舉個例子，蓋樓需要鋼筋混凝土，也需要磚頭和牆灰，「重要性」依次遞減；牆灰在鋼筋混凝土面前表現的微乎其微，可能鋼筋混凝土的某種錯誤(雜訊)粗看起來比牆灰級別的最重要的有用特性還要顯著

GBDT擬合heading部分，也就是擬合鋼筋混凝土，牆灰在鋼筋混凝土面前完全表現不出重要性。那麼一種辦法就是，鋼筋和鋼筋建一類GBDT，磚頭和磚頭建，牆灰和牆灰建 -- 我們把這個方法叫做GBDT Forest -- 不同群的Tree組成了Forest

實際CTR系統中，重要ID特徵(ad_id之類)的反饋特徵就屬於鋼筋級特徵，而低維圖像特徵則屬於牆灰級特徵(圖片平均亮度飽和度等,和CTR可能有非常微弱的關係)，直接把兩類特徵混起來建GBDT，有可能還沒有開始學圖像特徵，就發現反饋特徵的雜訊太大，整體已經過擬合而使得效果降低了

一種建立GBDT Forest的方法是區分Categorical Feature和Numerical Features建GBDT

• Numerical Features特徵建的樹，更多是把握長尾廣告的規律
• 泛化能力好，曝光少的廣告，廣告主也可以獲得權重
• Categorical Feature，尤其是高頻ID
• 細粒度ID建樹，發現曝光充分的ID的有區分度的特徵組合 -- 主要是發現曝光充分的廣告的Crossing
• 本身高維ID組合建樹，可以發現人工沒有發現的組合，以提升效果

再次考慮通過控制樣本來控制特徵

控制過擬合問題的另一個思路是，控制/刪除/減小小類樣本影響 -- GBDT本身模型特性決定其非常high variance的/非常擬合heading的，小類樣本本身帶入的收益可能大於雜訊，因此可以嘗試控制小類

也就是，一個Tuning思路是對小樣本做限制：

• 去除小樣本數據
• 小樣本單獨建樹，並限制小樣本GBDT個數(樣本量少的樹個數也少，防止過擬合)

舉例而言，可以控制廣告訂單 -- 樣本充足的場景才能保證效果；樣本不足情況，GBDT學出的pattern不具有泛化性/過擬合

1.4.4 GBDT Encode Feature vs. Manmade Features

有了GBDT做feature crossing，是否可以完全替換人工feature crossing

不然

從兩個角度進行對比

• 1. 支持特徵維度方面
• GBDT Encode樹個數相對有限時，GBDT相對不適合高維ID特徵；所以人工用ID特徵和其他特徵Crossing(包括興趣特徵和年齡、性別等)
• 2. 特徵交叉階Encode Leaf/Node
• GBDT leaf vs. 人工Crossing相比，少了低階feature
• GBDT leaf vs. Kaggle相比，少了原始feature

1.4.5 In Practice: 增大GBDT Encode表達能力

實踐方面，有一些細節可以增強encode出的特徵的表達能力

• 1. 自適應方式優化特徵抽樣，加大分支特徵區分度
• 自適應: 原來是按照同一個採樣率採樣特徵進行節點的分裂，現在如果特徵已經被前面的樹採到，被後續樹採到的概率設置小一點，不再用同一個採樣率。
• 2. 去除重複分支，去除重複分支有幾個層面:
• GBDT的路徑要做簡化
• 比方路徑為 [a>1, a>2, a<3, a<4]要簡化為[a>2,a<3]
• GBDT路徑間去重
• 前面的樹和後面的樹得到的組合特徵如果相同要去重
• 人工cross的和GBDT生成做去重

總體來說，GBDT Encoder+LR/FM是一個有效的方法，但同時也是一個非常吃優化的方法，尤其是GBDT+FM的組合，筆者team在早期嘗試時候經常出現加入GBDT特徵效果變的更糟的情況，而且和各種場景強相關：

• 一些場景中，數據相對充足且集中，人工的特徵組合已經達到非常充分的水平，那加入GBDT生成的高階組合特徵效果有，但不明顯，因為ID類特徵已經基本可以cover需求；
• 一些場景中，數據非常分散，幾乎所有的特徵都不能達到置信的程度，這種情況下GBDT 加入會增大overfitting
• 一般來說，有足夠的field，且這些field有表達能力（或許很微弱），人工不足以找出所有的高階組合，數據混雜著曝光充分和曝光不充分的情況（尤其是兩者相差懸殊）的時候，可以嘗試GBDT Encoder，有時會有很驚艷的效果提升

換句話說，在field量足夠，instance足夠，數據不是完全散開也不是完全集中的場景中，GBDT Encoder效果相對較好 -- 這一點，其實和DNN的使用場景也是類似的