內容摘要

• 泰勒公式
• 最優(yōu)化方法
  • 梯度下降法
  • 牛頓法
• 從參數(shù)空間到函數(shù)空間
  • 從Gradient descend到Gradient boosting
  • 從Newton's method到Newton Boosting
• Gradient boosting tree算法原理
• Newton Boosting算法原理
• LightGBM

泰勒公式

1. 定義：是一個用函數(shù)在某點的信息价脾，描述其附近取值的公式。

2. 基本形式：
   
   

   其中一階泰勒展開式就是求一階導平夜，二階展開式即求二階導沛申。x0為已知酪耳，公式表示f(x)在x0附近的展開铡恕。

3. GDBT或是xgb都是一個參數(shù)迭代的過程翰萨，因此這里表示一個迭代形式的泰勒函數(shù)：
   

   假設
   
   將f(x^t) 在x^(t-1)處進行展開：

梯度下降法（Gradient Descend Method）

機器學習中需要最小化損失函數(shù)L(θ),這個θ就是要求解的模型參數(shù)脏答。GDM常用于求解無約束最優(yōu)化問題，是一種迭代方法亩鬼。初始話θ為θ^0殖告，不斷迭代來更新θ的值，進行損失函數(shù)的極小化雳锋。

• 迭代公式 θ^t = θ^(t-1)+△θ
  進行一階泰勒展開：

  
  
  
  

  要使得L(θ^t) < L(θ^(t-1)),則可然萍ā：

  
  
• 其中解釋一下為何△θ要取值為上式：首先明確，a的值為正玷过，為了保證△θ恒為負數(shù)爽丹，則需要乘上L’(θ^t-1)先保證其為整數(shù)，再加上負號即可辛蚊。
• 其實a就是我們常用的學習速率
• a如何選仍列？
  對于這個問題其實有很多方法可以使用袋马，如果考慮使用full gradient較為笨但是精確的方法是line search初澎，但是其復雜度過高，因此通常我們選取一個很小的值即可例如0.01-0.1之間虑凛。

牛頓法

假設我們要求的參數(shù)θ是一維谤狡，則記一階導數(shù)為g，二階導數(shù)為h卧檐，那么上式可表示為：

如果參數(shù)θ是向量形式霉囚，那么可以向高維空間推廣捕仔，此時的h為H（海森矩陣）。

以上介紹的梯度下降和牛頓法均為參數(shù)空間的優(yōu)化算法
如何從參數(shù)空間推廣到函數(shù)空間呢盈罐？即從Gradient descend到Gradient boosting榜跌；從Newton's method到Newton Boosting
下面介紹GBDT和xgb中使用的函數(shù)空間的優(yōu)化算法，其基本原理還是梯度下降和牛頓法盅粪。
關系是這樣的：
GBDT泛指一切梯度提升樹钓葫，包括XGB。為了區(qū)分二者票顾，可以利用其梯度下降的原理進行區(qū)分：

• GBDT在函數(shù)空間中利用梯度下降進行優(yōu)化
• XGB在函數(shù)空間利用牛頓法進行優(yōu)化

1. 梯度下降從參數(shù)空間到函數(shù)空間

2. 牛頓法從參數(shù)空間到函數(shù)空間

3. boosting算法小結
無論是梯度下降還是牛頓法，其函數(shù)空間上的boosting優(yōu)化模型都看作是一類加法模型鸭廷，相加的對象可以是一系列弱分類器或是回歸樹枣抱。

4. 牛頓法小結
牛頓法是梯度下降的進一步優(yōu)化，梯度下降利用目標函數(shù)的一階偏導信息辆床，以負梯度方向作為搜索方向佳晶，只考慮目標函數(shù)在迭代點的局部性質；而牛頓法不僅使用目標函數(shù)的一階偏導數(shù)佛吓，還進一步利用了目標函數(shù)的二階偏導，這樣就考慮了梯度變化的趨勢垂攘，因而能更全面地確定合適的搜索方向以加快收斂维雇。

GBDT原理分析

GBDT最早由Friedman提出，其核心是擬合前面迭代所留下來的殘差晒他，使其達到最小吱型。

• 模型F定義為一個加法模型：

  
  

其中x為輸入樣本，h為分類回歸樹陨仅，w是分類回歸樹的參數(shù)津滞，a是每棵樹的權重。

• 通過最小化損失函數(shù)求解最優(yōu)模型：

  
  

• GBDT原是論文的算法偽代碼：

  
  

算法的輸入(xi,yi)分別是樣本和lable灼伤，T為樣本個數(shù)触徐，L為損失函數(shù)

• GBDT的學習過程是使得前面擬合的殘差達到最小，那么首先計算殘差狐赡，即算法中的2.1步撞鹉，也稱為響應。
• 接著學習第t棵樹時就是尋找最新的殘差的最小值颖侄∧癯可以看到lable yi變成了前t-1棵樹的殘差值。
  然后尋找合適的步長（通常情況览祖，不使用line search孝鹊，而是手動給一個很小的值）
  最后將第t棵樹與前t-1棵樹加起來，更新模型即可展蒂。

XGBoost原理

• 模型的函數(shù)形式

  
  

xgb同樣是一個加性模型又活，同樣是在學習多棵樹的結果并將其累加苔咪。f(x)就是每一棵樹。其中q(x)表示將樣本x分到了某個葉子節(jié)點上皇钞，w是葉子節(jié)點的分數(shù)悼泌，所以wq(x)就表示回歸樹對樣本的預測值。

• 回歸樹的預測輸出是一個實數(shù)的分數(shù)夹界，因此可以用于回歸和分類馆里，以及排序等任務。

目標函數(shù)

• 首先回憶一下參數(shù)空間的目標函數(shù)：

  
  
  
  

  實際上就是一個誤差函數(shù)+正則化項

其中誤差函數(shù)可以是平方誤差或是對數(shù)誤差等可柿；正則化項可以是L1或L2

• 正則化項

wepon大神說道鸠踪，正則化項的理解可以從貝葉斯先驗角度去理解。也就是說复斥，如果引入L2营密，那么就是假設模型參數(shù)服從正態(tài)分布（相當于對參數(shù)加上了分布約束），這樣一來就將參數(shù)的取值進行一定的限制目锭，同時可以知道评汰，正態(tài)分布取0附近的概率最大，因此又將參數(shù)空間可能的范圍進一步縮小痢虹，模型最終學習出來的參數(shù)取值都在0附近被去。

• 現(xiàn)在來看函數(shù)空間的目標函數(shù)

  
  

其中正則化項是對每一棵樹的復雜度進行懲罰。
相比于GBDT奖唯，xgb目標函數(shù)就是多了一個正則化項惨缆。這樣的做法使得模型不易過擬合。
既然是對復雜度做懲罰丰捷，那么樹的什么特性可以反映復雜度坯墨？

• 樹的深度、內部節(jié)點個數(shù)病往、葉子節(jié)點個數(shù)捣染，葉節(jié)點分數(shù)
  xgb中選用了葉子節(jié)點個數(shù)(T)，葉節(jié)點分數(shù)(w)來反映樹的復雜度停巷，其復雜度定義如下：
  

看完正則化項后再來關心一下目標函數(shù)中的誤差函數(shù)

• 首先模型第t次迭代后將ft(x)與前t次的迭代結果進行相加液斜，并代入目標函數(shù)，即式2叠穆，然后將誤差項在yt-1處進行二階展開少漆，然后去掉常數(shù)項得到：

  
  
  
  
  上面這個形式跟牛頓法的形式幾乎一樣，由于f在函數(shù)空間中是一個樹的形式硼被，則將f寫為樹的結構：
  
  代入目標函數(shù)中得到：
  
  
  雖然現(xiàn)在loss函數(shù)可以求最小值了示损，但是公式的兩項并不統(tǒng)一，即：
  
  如何將兩項進行統(tǒng)一以方便求導呢嚷硫？因為樣本都會落在每一個節(jié)點上面检访，因此可以定義如下：
  
  對每一個樣本都相應有一個gi和hi始鱼。從最終的公式可以看到，由于是按照葉子節(jié)點進行累加脆贵，所以相當于每一個葉子節(jié)點均有一個誤差函數(shù)医清，都要進行相應的誤差計算。
  根據(jù)轉換后的損失函數(shù)卖氨，就可以求極小值了会烙，前提是樹結構確定：
  相當于每一棵樹的最小損失都可以計算了。

既然前提是需要樹結構確定筒捺，那么如何確定樹的結構柏腻？即如何確定樹節(jié)點的分裂方法？

1. 可以暴力枚舉全部的樹結構然后選擇損失最小的結構即可系吭。明顯是一個NP問題五嫂。不現(xiàn)實！

2. 貪心法：每次嘗試分裂一個葉節(jié)點肯尺，計算前后增益沃缘，選擇增益最大的保留。
   

   那么增益如何計算则吟？

• xgb增益計算方法的演進：

1. 初始版本：
   
   

   這樣的方法相當于去遍歷所有可能分割的分割點槐臀，然后計算增益，最后選取最大的增益的分列方式去分割逾滥，明顯負責度太高７宓怠败匹！

2. 近似算法：
   對于每一個特征寨昙，只考慮分位點，以減少復雜度掀亩，分位點的選取粒度有兩種：全局global和局部local舔哪。全局速度快但是經度降低。
   解釋一下：先將某特征的特征值從小到大排序槽棍，再選取分位點進行計算增益即可捉蚤。
   
   
   3. xgb中采用的樹節(jié)點分裂方法（增益計算）
   
   
   如何看權重分位點的選取呢？上圖中前六個特征值的權重之和為0.6炼七，7-8的權重和為0.6缆巧，最后一個為0.6，就這選取權重之和相同的點來進行分位點的選取豌拙，然后再計算增益陕悬。

內容參考wepon大神天池直播