Boosting

Boosting是一類將弱學習器提升為強學習器的算法。這類算法的工作機制類似：先從初始訓練集中訓練出一個基學習器，再根據基學習器的表現對訓練樣本分布進行調整，使得先前基學習器做錯的訓練樣本在后續受到更多關注。 然后基于調整后的樣本分布來訓練下一個基學習器；如此重復進行，直至基學習器的數目達到事先指定的值T，最終將這T個基學習器進行加權結合。

Boost算法是在算法開始時，為每一個樣本賦上一個相等的權重值，也就是說，最開始的時候，大家都是一樣重要的。 在每一次訓練中得到的模型，會使得數據點的估計有所差異，所以在每一步結束后，我們需要對權重值進行處理，而處理的方式就是通過增加錯分點的權重，這樣使得某些點如果老是被分錯，那么就會被“嚴重關注”，也就被賦上一個很高的權重。 然后等進行了N次迭代，將會得到N個簡單的基分類器（basic learner），最后將它們組合起來，可以對它們進行加權（錯誤率越大的基分類器權重值越小，錯誤率越小的基分類器權重值越大）、或者讓它們進行投票等得到一個最終的模型。

梯度提升（gradient boosting）屬于Boost算法的一種，也可以說是Boost算法的一種改進，它與傳統的Boost有著很大的區別，它的每一次計算都是為了減少上一次的殘差(residual)，而為了減少這些殘差，可以在殘差減少的梯度(Gradient)方向上建立一個新模型。所以說，在Gradient Boost中，每個新模型的建立是為了使得先前模型殘差往梯度方向減少， 與傳統的Boost算法對正確、錯誤的樣本進行加權有著極大的區別。

梯度提升算法的核心在于，每棵樹是從先前所有樹的殘差中來學習。利用的是當前模型中損失函數的負梯度值作為提升樹算法中的殘差的近似值，進而擬合一棵回歸（分類）樹。

梯度提升

根據參考文獻【1】的介紹，梯度提升算法的算法流程如下所示：

第一個對數損失用于分類，后兩個平方誤差和絕對誤差用于回歸。

隨機梯度提升

有文獻證明，注入隨機性到上述的過程中可以提高函數估計的性能。受到Breiman的影響，將隨機性作為一個考慮的因素。在每次迭代中，隨機的在訓練集中抽取一個子樣本集，然后在后續的操作中用這個子樣本集代替全體樣本。 這就形成了隨機梯度提升算法。它的流程如下所示：

實例

（提示：代碼塊部分可以左右滑動屏幕完整查看哦）

下面的代碼是分類的例子：

下面的代碼是回歸的例子：

源碼分析

5.1 訓練分析

梯度提升樹的訓練從run方法開始。

在MLlib中，梯度提升樹只能用于二分類和回歸。所以，在上面的代碼中，將標簽映射為-1,+1，那么二分類也可以被當做回歸。整個訓練過程在GradientBoostedTrees.boost中實現。 GradientBoostedTrees.boost的過程分為三步，第一步，初始化參數；第二步，訓練第一棵樹；第三步，迭代訓練后續的樹。下面分別介紹這三步。

• 初始化參數

這里比較關鍵的是通過GradientBoostedTreesModel.computeInitialPredictionAndError計算初始的預測和誤差。

根據選擇的損失函數的不同，computeError的實現不同。

上面代碼最重要的部分是更新預測和誤差的實現。通過GradientBoostedTreesModel.updatePredictionError實現。

5.2 測試

利用梯度提升樹進行預測時，調用的predict方法擴展自TreeEnsembleModel，它是樹結構組合模型的表示，其核心代碼如下所示：