CTR預估[八]: Algorithm-GBDT: Parameter Space Estimation and Function Space Estimation

01-28

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

時間：2017年11月

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

在<上一篇>中，我們介紹了GBDT的前序準備：Ensemble和bias/variance分析。
本節我們來比較「參數空間優化問題」和「函數空間優化問題」，進而引出GBM的思想。

1.3.3 Function Estimation: Parameter Space and Function Space

在一個Function Estimation問題中，求對 $F(x):Xto y$ 的最優解 $F^*$ 的估計 $hat F(x)$ ，使得針對所有樣本 $(y,x)$ 上的某種Loss期望最小。

Variables: $X = {x_1, x_2, cdots, x_n}$ Training Data: ${y_i,X_i}_1^n$ Goal: 求對 $F(x):Xto y$ 的最優解 $F^*$ 的估計 $hat F(x)$ $begin{split}~~~~~~~~~~~~~~~~~~~~ F^* &= argmin_F E_{y,X} left[L(y,F(X))right] &= argmin_F E_Xleft[E_y left(L(y,F(X)) right) | Xright] end{split}$

-- $E_{y,X} left[L(y,F(X))right]$ 為對所有Training Data上Loss的均值；
-- $F^*$ 可以理解為對所有instance期望Loss最小的 $F$ 。

一般情況下，會限制 $F(x)$ 是一個包含finite參數 $P={P_1,P_2,cdots,}$ 的函數 $F(x;P)$ ，然後在參數 $P$ 空間下求解。

如果不考慮參數，直接對 $F(x)$ 就是函數空間 $F$ 下求解，函數空間下可擴展為Additive Model。

Additive Model $~~~~~~~~~~~~~~~~~~~~F(X;{beta_m, alpha_m}_1^M) = sumlimits_{m=1}^M beta_m h(X;alpha_m)$
-- $h()$ 是一個base learner, $alpha$ 是 $h()$ 的參數

-- 如果是GBDT， $h(x;alpha)$ 是一個regression tree, $alpha$ 是split參數位置或者葉節點

但直接求解function space下優化依然有如下問題：

Flaw 1: Finite data vs. Infinite function
統計量無法逼近總體，總體最優 $F^*$ 是在Training Data上而不是X空間上，且 $E_y[· | X]$ 也無法準確估計。

Solution 1: Additive Model
使用加法模型做參數優化逼近data，最小化expected loss $~~~~~~~~~~~~~~~~~~~~{beta_m, alpha_m}_1^M= argmin_{{beta_m, alpha_m}_1^m} sumlimits_{i=1}^N Lleft(y_i, sumlimits_{m=1}^M beta_mh(x_i; alpha_m)right)$

Flaw 2: 直接優化複雜
Solution 2: 使用Forward Stage-wise Algorithm進行逼近：
For m = 1,2,...M:

$begin{split}~~~~~~~~~~~~~~~~~~~~ (beta_m, alpha_m) &= argmin_{beta, alpha} sumlimits_{i=1}^N Lleft(y_i, F_{m-1}(x_i) + beta_m h(x_i; alpha_m)right) F_{m}(x) &= F_{m-1}(x) + beta_m h(x; alpha_m) end{split}$

對下面這個問題，GBM和XgBoost在優化手段上有一些不同。

Friedman優化了下面這個點，作為GBM的整體框架：

Flaw 3: $argmin_{beta, alpha}$ 不容易求解，且梯度只是樣本 ${x_i}_1^N$ 上的最優方向，不能泛化到整體 $X$ 空間
Solution 3: Gradient 逼近（GBM）
-- 從 $h(x;alpha_m)$ 中選擇和 $-g_m$ 最平行的
-- $alpha_m = argmin_{alpha, beta} sumlimits_{i=1}^N [-g_m(x_i) - beta h(x_i,alpha)]^2$
-- 用 $h(x; alpha_m)$ 逼近 $-g_m$ ，保證了Solution 2中第1式難解的部分直接用 least square求解

陳天奇這裡沒有這樣估計，而是將Objective擴展到了二階梯度泰勒展開：

Flaw 3: $argmin_{beta, alpha}$ 不容易求解，且梯度只是樣本 ${x_i}_1^N$ 上的最優方向，不能泛化到整體 $X$ 空間
Solution 4: 2nd-order Taylor Expansion（XgBoost）
-- For m = 1 to M do:
$begin{split}~~~~~~~~~~~~~~~~~~~~ alpha_m &= argmin_{alpha} sumlimits_{i=1}^N L(y_i, F_{m-1}(x_i) + h(x_i; alpha_m)) &approx argmin_{alpha} sumlimits_{i=1}^N left[ L(y_i, F_{m-1}(x_i))^2 + frac{partial L(y_i, F_{m-1}(x_i))}{partial F_{m-1}(x_i)} h(x_i; alpha_m) + frac{1}{2} frac{partial ^2 L(y_i, F_{m-1}(x_i))}{partial F_{m-1}(x_i)} h^2(x_i; alpha_m) right] &= argmin_{alpha} sumlimits_{i=1}^N left[ frac{partial L(y_i, F_{m-1}(x_i))}{partial F_{m-1}(x_i)} h(x_i; alpha_m) + frac{1}{2} frac{partial ^2 L(y_i, F_{m-1}(x_i))}{partial F_{m-1}(x_i)} h^2(x_i; alpha_m) right] + constant F_{m}(x) &= F_{m-1}(x) + h(x; alpha_m) end{split}$
-- 這裡步長=1，在實際應用中會在 $h()$ 前乘以0.01左右的小量作為regularization。

GBDT的優勢：

-- 一階梯度和二階梯度是只和loss function類型有關的量；

-- 工程實現中這裡根據loss function不同即為可插拔的模式。

GBDT組織方式和傳送門：

GBDT的前序兩篇：

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

Ensemble方法bagging和boosting的比較：GBDT所屬boosting演算法，說GBDT之前需要對boosting是什麼有個了解
Aside: bias and variance: bias/var tradeoff是機器學習永恆的話題，而bagging和boosting的分析，尤其是後面的RF依然會用到

CTR預估[八]: Algorithm-GBDT: Parameter Space Estimation and Function Space Estimation

函數空間和參數空間優化：GBDT本質上是從函數空間優化開始的，所以在講具體的boosting trees之前，從兩者的比較開始更佳 -- 注意，本節雖然全部為推導，但個人認為對於理解GBDT至關重要，否則更像是無根之木 （傳送門：）

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