CTR預估[七]: Algorithm-GBDT: Preliminary

02-09

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

時間：2017年11月

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

在<上一篇>中，我們介紹了非線性模型FM相關的理論（margin的比較、Objective的推導）和實踐（調參等）。

本節我們介紹另一個非線性模型GBDT的前序準備知識：Ensemble和bias/variance。
對bias/variance的分析將貫穿bagging、boosting兩大類演算法的始終。理解bias-variance trade-off對於分析GBDT/Random Forest的適用範圍有很大幫助。

系列目錄傳送門見 -- CTR預估系列一覽表

GBDT系列會按照如下方式組織：

GBDT的前序：

Ensemble方法bagging和boosting的比較：GBDT所屬boosting演算法，說GBDT之前需要對boosting是什麼有個了解
Aside: bias and variance: bias/var tradeoff是機器學習永恆的話題，而bagging和boosting的分析，尤其是後面的RF依然會用到
函數空間和參數空間優化：GBDT本質上是從函數空間優化開始的，所以在講具體的boosting trees之前，從兩者的比較開始更佳 -- 注意，本節雖然全部為推導，但個人認為對於理解GBDT至關重要，否則更像是無根之木 （傳送門：CTR預估[八]: Algorithm-GBDT: Parameter Space Estimation and Function Space Estimation）

Boosting Trees： GBM 和 GBDT; GBDT 的核心推導（傳送門：CTR預估[九]: Algorithm-GBDT: Boosting Trees）
Aside： Random Forest; 作為bagging的優秀代表，後面比較GBDT+LR 而非 RF+LR會用到（傳送門：CTR預估[十]: Algorithm-Random Forest）

1.3 GBDT

GBDT通常情況並不常作為CTR預估問題的主model，但它的一些變形用法經常會出現在CTR預估問題中。

1.3.1 Ensemble: bagging and boosting

Ensemble Learning是對一組individual learner進行組合的模型構造策略。

如果individual learner同質，稱為base learner；
如果individual learner異質，稱為component learner。

Bagging Methods vs. Boosting Methods：

1.3.2 Aside: Bias and Variance

Bias可以認為是: 真值和預估值的差；

Variance可以認為是：預估值之間的方差。

假設 $hat{f}(x)$ 是對 $y=f(x)+epsilon$ 的估計，其中 $epsilonsim mathcal{N}(0, sigma)$

下面 $hat{f}(x)$ 簡寫為 $hat{f}$ ， $f(x)$ 簡寫為 $f$ ，假設有 $n$ 個 $hat{f}$

$egin{aligned}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Error(x) &= E[(y-hat{f})^2] &#MSE\ &= E[(f-hat{f})^2] + sigma_e^2 \ &= f^2 - 2fE[hat{f}] + E[hat{f}^2] + sigma_e^2 \ &= E^2[hat{f}]- 2fE[hat{f}] + f^2 + E[hat{f}^2] - E^2[hat{f}] + sigma_e^2 \ &= left(E[hat{f}]- f ight)^2 + left(E[hat{f}^2] - E^2[hat{f}] ight) + sigma_e^2 \ &= underbrace{ left(E[hat{f}]- f ight)^2}_{Bias^2 } + underbrace{ Eleft[ ( hat{f} - E[hat{f}] )^2 ight] }_{Variance }+ sigma_e^2 \ end{aligned}$

可見，我們可以通過降低bias或降低variance的途徑來降低模型的error。事實上，大部分演算法都可以從這個角度來解釋：要麼理論上降低bias，要麼理論上降低variance，甚至兼備。

1.3.2.1 Bagging: Bias and Variance

Bagging常用的方法有：

對於回歸問題：取各個子模型結果的平均值 avg(o)。
對於分類問題：取各個子模型的結果類別進行投票 vote(o)。

以回歸問題為例：

假設數據 $x$ 經過許多base learner $b_i(x)$ 之後輸出為 $o_i(x)$ ，bagging之後的輸出為

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ar{o}=sum_i w_i o_i(x)$
單個base learner的error為
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~e_i(x) = [f(x)- o_i(x)]^2$
單個base learner的error的加權均值為
$egin{split}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ epsilon(x)&=sum_i w_i e_i(x)\ &= sum_i w_i [f(x)- o_i(x)]^2 end{split}$
bagging後的error為
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~e(x) = [f(x) - ar{o}(x)]^2$
兩者差值
$egin{split}~~~~~~~~~~~~~~~~~~~ epsilon(x) - e(x) &= left(sum_i w_i [f(x)- o_i(x)]^2 ight) - [f(x) - ar{o}(x)]^2\ &= left(sum_i w_i [f(x)- o_i(x)]^2 ight) + [f(x) - ar{o}(x)] [ar{o}(x) - f(x)]\ &= left(sum_i w_i [f(x)- o_i(x)]^2 ight) + [f(x) - ar{o}(x)] [2sum_iw_io_i(x) - f(x) - ar{o}(x))]\ &= left(sum_i w_i [f(x)- o_i(x)]^2 ight) + 2sum_i[(f(x) - ar{o}(x))w_io_i(x)] - f(x)^2 + ar{o}(x)^2 \ &= sum_i w_ileft([f(x)- o_i(x)]^2 + 2[f(x) - ar{o}(x)]o_i(x) - f(x)^2 + ar{o}(x)^2 ight)\ &= sum_i w_i [o_i(x) - ar{o}(x)]^2 geq 0 end{split}$

從上述的分析可以推論：

bagging的error並不能保證一定比單個base learner的低：極端情況下，增加許多AUC < 0.5的base learner會讓bagging後的模型效果變得更差；
如果base learner都是「好」的，那麼 $sum_i w_i [o_i(x) - ar{o}_i(x)]^2$ 一般稱為ambiguity，表示base learner之間的「好而不同」的程度。

那是什麼因素導致了bagging後error的降低呢？

bias:

base learner之間是同分布（identically distributed，i.d.）的，因此對於任意一個base learner的期望和這些base learner均值的期望一致，即bagging後bias保持不變。

variance:

A: $y = f_i(x)$

B: $y = frac1N[f_1(x) + f_2(x) + dots + f_n(x)]$

假設 $f$ 獨立同分布（i.i.d）：

$egin{split}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Var(A) &= Var(f_i(x)) = sigma^2\ Var(B) &= Var[ frac1N[f_1(x) + f_2(x) + dots + f_n(x)]] \ &= frac1{N^2} Var[f_1(x) + f_2(x) + dots + f_n(x)]\ &= frac1{N^2} [Var (f_1(x)) + Var(f_2(x)) + dots + Var(f_n(x))]\ &= frac{sigma^2}N end{split}$

可見，對於獨立同分布的子模型而言，其組合bagging的variance可以降低至原來每個子模型variance的 $frac{1}{N}$ ，其中N為子模型的個數。

假設 $f$ 同分布（i.d）但不獨立：

令 $Corr(f_i(x), f_j(x)) = ho sigma^2$ $egin{split}~~~~~~~~~~ Var(A) &= Var(f_i(x)) = sigma^2\ Var(B) &= sum_i Var(f_i(x)) + sum_{i eq j} Corr(f_i(x), f_j(x)) \ &= frac{Nsigma^2}{N^2} + frac{N(N-1)}{N^2} ho sigma^2\ &= ho sigma^2 + frac{1- ho}N sigma^2 end{split}$

可見，bagging對variance的降低取決於子模型之間的相關性 $ho$ ：

如果特徵完全無關（ $ho = 0$ ）等價於 $i.i.d.$ 情況；
如果特徵完全相關（ $ho = 1$ ）等價於bagging沒有效果。

另一方面，隨著 $N$ 的上升，variance的第二項逐漸趨近於0，說明：

更多的 $N$ 可以降低variance。

從以上分析可以看到：bagging的主要目的是降低variance，因此適合使用高variance、低bias的子模型進行構造再進行bagging。

因此，Trees是理想的bagging子模型候選：

Trees在生成過程中可以捕獲數據中複雜的高階交互信息；
如果Trees模型足夠深，可以得到足夠低bias的子模型，而variance可以交由bagging策略來降低。

與之相比的boosting：
Boosting是通過adaptive way從而降低bias，因此不是identically distributed；
由於boosting是sequential的最小化Loss，其bias會持續降低；但這種adaptive的策略，base learner之間強相關，因此variance並不顯著降低。

本系列目錄，結構和reference請參考：CTR預估系列一覽表