數據挖掘面試題之梯度提升樹

作者： milter

原文鏈接：https://www.jianshu.com/p/0e5ccc88d2cb

查看更多的專業文章、課程信息、產品信息，請移步至「人工智慧LeadAI」公眾號，或移步至全新打造的官網：www.leadai.org.

正文共2216個字，12張圖，預計閱讀時間14分鐘。

GBDT是機器學習面試中的常客，但是，要準確地說出它的原理卻並不容易，除了掌握DT基本知識外，還要掌握加法模型、前向分步演算法、梯度提升思想，本文是對這些知識點的一個簡單總結，請各路大神指正。

為了提高寫作效率，文中公式都是手寫，美觀不足，但清晰準確是沒問題的。

01

從加法模型說開去

首先，我們需要具備一些基本的機器學習知識，這裡簡單列出，以作為下面討論的基礎：

1、機器學習的大致流程就是確定模型集H、定義經驗損失函數（一般是基於單個樣本點進行定義）、利用給定的數據集{（x_i,y_i）}，從模型集中尋找最佳的模型（一般就是尋找最佳的模型參數）。

2、決策樹是一種模型，它的主要思想是將輸入空間劃分為不同的子區域，然後給每個子區域確定一個值，如果是分類樹，這個值就是類別，如果是回歸樹，這個樹就是一個實值。如下圖所示：

3、GBDT中的DT是回歸樹，不是分類樹，也就是說，只有回歸樹才有所謂的梯度提升。

所謂加法模型，也是一種模型集H，它的一般形式如下：

f_m(x)叫做基函數，基函數可以有各種各樣的形式，自然也會有自己的參數，待會兒我們討論GBDT時，它就是二叉回歸決策樹。β_m是基函數的係數，一般假設大於0。

有了模型，還需定義該模型的經驗損失函數，如下所示：

現在，我們的問題轉變成了通過極小化經驗損失函數來確定各個係數β_m和各個基函數f_m(x)。

問題是：How？

此時，我們既不知道基函數的具體形式，也不知道損失函數的具體形式，只有N個樣本點，很顯然，我們無法往下進行。

02

前向分步演算法橫空出世

這就是前向分步演算法一顯身手的地方，前向分布演算法說：「我可以提供一套框架，不管基函數和損失函數是什麼形式，只要你的模型是加法模型，就可以按照我的框架的指導，去求解。」

也就是說，前向分步演算法提供了一種學習加法模型的普遍性方法，不同形式的基函數、不同形式的損失函數都可以用這種普遍性方法去求出加法模型的最優化參數，它是一種元演算法。

它的思路是：加法模型中一共有M個基函數以及與之相應的M個係數，可以從前往後，每次學習一個基函數及其係數。

其學習步驟如下：

前向分步演算法中最核心的就是第2步中的第1小步，即如何求出f_m和β_m？

03

梯度提升順利接盤

梯度提升思想正是為了解決上面的問題。它的主要思想是先求f_m，再求β_m。觀察式子：

我們要最小化的式子由N部分相加而成，如果能夠最小化每一部分，自然也就最小化了整個式子。考察其中任一部分，並將其進行泰勒一階展開（這是關鍵所在！）：

由於β是大於0的，若：

不難得出：

這說明，我們已經成功地降低了在第i個樣本點上的預測損失。同理，我們可以降低在每一個樣本點上的預測損失。條件就是：

這個條件其實告訴了我們如何去尋找f_m，即能夠使得在每一個樣本點上上式儘可能成立的f_m就是我們要找的。這是一個回歸問題，很容易解決。

我們已經有了f_m，下面優化求解β，很顯然，這是一個一維搜索問題，如下：

在上面的泰勒一階展開時，有一個條件就是βf(x_i)要足夠小，顯然，執行一維搜索後得到的β會滿足這個條件。

04

這時才是學習梯度提升樹的最佳時機

以上是加法模型的一般學習方法，對不同的基函數，不同的損失函數，不同的問題（分類還是回歸），都可以套用上面的方法來求解，只是具體的表現形式會有所變化。

比如當加法模型解決的問題是二類分類問題，基函數是基本分類器，損失函數為指數損失函數時，按照上面的方法求解，其過程就和AdaBoost是完全一樣的。

當用加法模型解決的問題是回歸問題，基函數是二叉決策回歸樹時，加法模型本身會得到簡化，基函數前面的係數可以省去，因為對每一個係數，我們都可以把它內化到二叉決策回歸樹內部去，這時的加法模型變成了這樣：

![Uploading end_421067.PNG . . .]

簡化了加法模型，消除了β，在求解第2步第1小步時，過程也得到了簡化，詳情請參考《統計學習方法》P151-152：

在上面的圖中，有一點值得注意，就是我們用r_mi擬合出一個回歸樹之後，進一步用整體損失函數對這棵回歸樹的值進行了優化。這樣的思想在機器學習中很常見，我管它叫做「先局部、後整體」思想，就是先通過逐步的局部優化得出一個結果，然後再從全局的角度來優化這個結果。

舉個例子，決策樹的生成和剪枝，先通過局部優化（用信息增益等指標選擇特徵）得出一個決策樹，再從降低整體損失的角度，進行剪枝。

Note：注重總結機器學習各種模型中的思想，就可以達到觸類旁通的境界。

更進一步，當損失函數是平方誤差時，求解過程就更加的簡單了，詳情請見《統計學習方法》P148。

05

總結一下

本文首先介紹了機器學習中一類模型——加法模型，然後介紹了求解優化該類模型的前向分步演算法，又進一步介紹了該演算法中最核心步驟求解所用的梯度提升思想。然後，從一般到個別，展示了當加法模型運用到不同問題中（分類和回歸），當基函數採用不同的具體形式（基本分類器和二叉決策回歸樹），當損失函數採用不同的具體形式（指數損失函數和平方損失函數）時，其具體化的求解步驟。

可以看出GBDT作為求解回歸問題的加法模型，具有形式簡單（消除了β），求解便捷（見上面的《統計學習方法》圖）的特點，這也是為什麼它十分流行的原因。

推薦閱讀：