多層梯度提升決策樹(個人理解)

08-10

多層梯度提升決策樹(個人理解)

來自專欄機器學習筆記1 人贊了文章

原文:馮霽,俞揚，周志華 Multi-Layered Gradient Boosting Decision Trees

1.簡介

深度神經網路成功的關鍵主要是通過構建多層結構從原始數據取得特徵。目前大多數神經網路都是利用反向傳播進行參數更新的。而目標傳播被提出作為一個可選的方法，但是目前還是處於實驗階段。反向傳播仍然是神經網路在可微學習系統中最有效的訓練方法。

另一方面，非可微模塊構建的深度神經網路的訓練有探索的需求性。在離散數據方面，隨機森林或梯度提升樹有顯著的優勢，所以探索基於樹的多層結構模型是重要。

2.演算法

一個有 $M-1$ 個中間層和一個輸出層的多層結構。 $o_i$ 表示第 $i$ 的輸出，對於輸入數據 $x$ ,每一層對應的輸出為 $R^{d_i}$ 。學習任務可認為是找尋一個映射函數: $F_i:R^{d_{i-1}} ightarrow R^{d_i}$ ,以至於最終的輸出的損失函數 $L$ 最小。對於可微的模塊，可利用反向傳播訓練，而對於不可微的情況下，反向傳播不在可用，這時可假設 $F_i$ 表示一梯度提升樹處理。

在第 $t$ 輪， $F_i^{t-1}$ 表示前一輪取得的梯度提升樹。定義偽逆映射 $G_i^t$ : $G_i^t(F_i^{t-1}(o_{i-1})) approx o_{i-1}$ 。為了取得 $G_i^t$ ,可利用最小化輸出值 $o_{i-1}$ 和重構值之間的損失函數 $L^{inverse}$ 取得。即:

$widetilde G_i^t=argmin_{G^t}E_x[L^{inverse}(o_i,G_i^t(F_i^{t-1}(o_{i-1})))]$

$L^{inverse}=left|| G_i(F_i(o_{i-1}+varepsilon)) - (o_{i-1}+varepsilon) ight||$

$varepsilon sim N(0,diag(sigma^2))$

其中, $varepsilon$ 是添加的隨機雜訊，增加構建函數的魯棒性。

定義偽標籤 $z_{i-1}^t=G_i(z_i^t)$ ,則對於 $F_i^{t-1}$ ,可基於偽殘差 $-frac{partial L(F_i(o_{i-1}),z_i^t)}{partial F_i(o_{i-1})}$ 構建經典的梯度提升樹。

對於 $Z_M^t$ 有 $Z_M^t=o_M-alpha frac{partial L(o_M,y)}{partial o_M}$ ，對應的偽殘差為 $-frac{partial L(F_M^{t-1}(o_{M-1}),z_M^t)}{partial F_i^{t-1}(o_{M-1})}$ ，構建出梯度提升樹得到 $F_M^t$ ,進而得到 $G_M^t$ 。訓練圖如下:

神經網路的參數初始化可以通過隨機高斯雜訊取得，對於樹結構，可以通過在中間層基於隨機高斯雜訊產生輸出，構建初始的梯度提升樹。

演算法流程如下:

1.初始化 $F_1^0,F_2^0,...,F_M^0$

2.迭代循環，在第t輪,得到為標籤 $Z_M^t=o_M-alpha frac{partial L(o_M,Y)}{partial o_M}$

4.從頂層向底層開始構建得到 $G^t$

利用前一輪得到的 $G_j^{t-1}$ 應用在當前輪，即 $G_j^t=G_j^{t-1}$

對輸出加入高斯雜訊，加強魯棒性，即 $o_{j-1}^{noise}=o_{j-1}+varepsilon$

利用誤差函數 $L_j^{inv}=left|| G_j^t(F_j^{t-1}(o_{j-1}^{noise}))-o_{j-1}^{noise} ight||$ 構建出梯度提升樹

更新下一底層的偽標籤 $z_{j-1}^t=G_j^t(z_j^t)$

5.從底層向頂層開始構建得到 $F^t$

利用前一輪得到的 $F_j^{t-1}$ 應用在當前輪，即 $F_j^t=F_j^{t-1}$

利用誤差函數 $L_j=left||F_j^{t}(o_{j-1})-z_j^t ight||$ 構建出梯度提升樹

6.回到步驟2，直到迭代終止

3.演算法理解

$F_i^t$ 相當於編碼器, $G_i^t$ 相當於解碼器,模塊在訓練過程構成一自編碼器，模型的訓練過程相當於結構變為自編碼器n-自編碼器n-1-...-自編碼器1。在訓練階段，從自編碼器n開始，中間表示通過梯度下降法得到理想的表示，編碼器進一步擬合理想表示得到更加完善的編碼器，另一方面，藉助於解碼器得到理想的目標輸入，即為自編碼器n-1的理想表示，此時自編碼n-1藉助這一理想表示進一步完善自身，以此迭代下去。

吉布斯採樣通過遍歷每個變數 $x_i$ ，固定其他變數，對變數 $x_i$ 進行採樣,最終會平穩分布的樣本。類比於該思想，演算法從訓練開始階段，目標就是基於梯度下降不斷擬合出目標輸出，然後在每一階段，都是固定其他階段，"採樣"得到優化後的編碼器，最後整體會達到穩態收斂。

參考文獻

馮霽,俞揚，周志華 Multi-Layered Gradient Boosting Decision Trees