轉(zhuǎn)載自 http://www.52caml.com/head_first_ml/ml-chapter6-boosting-family/
內(nèi)容列表
寫在前面
Boosting
Boosting介紹
前向分步加法模型
Boosting四大家族
AdaBoost
算法學習過程
算法實例
訓練誤差分析
前向分步加法模型與AdaBoost
Boosted Decision Tree
Gradient Boosting
寫在前面
提升（boosting）方法是一類應用廣泛且非常有效的統(tǒng)計學習方法。
在2006年，Caruana和Niculescu-Mizil等人完成了一項實驗，比較當今世界上現(xiàn)成的分類器（off-the-shelf classifiers）中哪個最好？實現(xiàn)結(jié)果表明Boosted Decision Tree（提升決策樹）不管是在misclassification error還是produce well-calibrated probabilities方面都是最好的分離器，以ROC曲線作為衡量指標。（效果第二好的方法是隨機森林）
參見paper：《An Empirical Comparison of Supervised Learning Algorithms》ICML2006.
下圖給出的是Adaboost算法（Decision Stump as Weak Learner）在處理二類分類問題時，隨著弱分類器的個數(shù)增加，訓練誤差與測試誤差的曲線圖。
損失函數(shù)示意圖
損失函數(shù)示意圖
從圖中可以看出，Adaboost算法隨著模型復雜度的增加，測試誤差（紅色點線）基本保持穩(wěn)定，并沒有出現(xiàn)過擬合的現(xiàn)象。
其實不僅是Adaboost算法有這種表現(xiàn)，Boosting方法的學習思想和模型結(jié)構(gòu)上可以保證其不容易產(chǎn)生過擬合（除非Weak Learner本身出現(xiàn)過擬合）。
下面我們主要是從損失函數(shù)的差異，來介紹Boosting的家族成員；然后我們針對每個具體的家族成員，詳細介紹其學習過程和核心公式；最后從算法應用場景和工具方法給出簡單的介紹。
Boosting
Boosting介紹
基本思想
Boosting方法基于這樣一種思想：
對于一個復雜任務來說，將多個專家的判定進行適當?shù)木C合得出的判斷，要比其中任何一個專家單獨的判斷好。很容易理解，就是”三個臭皮匠頂個諸葛亮”的意思…??????。
歷史由來
歷史上，Kearns和Valiant首先提出了”強可學習（strongly learnable）”和“弱可學習（weakly learnable）”的概念。他們指出：
在概率近似正確（probably approximately correct，PAC）學習框架中：
①. 一個概念（一個類，label），如果存在一個多項式的學習算法能夠?qū)W習它，并且正確率很高，那么就稱這個概念是強可學習的；
②. 一個概念（一個類，label），如果存在一個多項式的學習算法能夠?qū)W習它，學習的正確率僅比隨機猜測略好，那么就稱這個概念是弱可學習的。
Schapire后來證明了:?強可學習和弱可學習是等價的。?也就是說，在PAC學習的框架下，一個概念是強可學習的 充分必要條件 是這個概念是弱可學習的。?表示如下：
強可學習?弱可學習強可學習?弱可學習
如此一來，問題便成為：在學習中，如果已經(jīng)發(fā)現(xiàn)了”弱學習算法”，那么能否將它提升為”強學習算法”？ 通常的，發(fā)現(xiàn)弱學習算法通常要比發(fā)現(xiàn)強學習算法容易得多。那么如何具體實施提升，便成為開發(fā)提升方法時所要解決的問題。關于提升方法的研究很多，最具代表性的當數(shù)AdaBoost算法（是1995年由Freund和Schapire提出的）。
Boosting學習思路
對于一個學習問題來說（以分類問題為例），給定訓練數(shù)據(jù)集，求一個弱學習算法要比求一個強學習算法要容易的多。Boosting方法就是從弱學習算法出發(fā)，反復學習，得到一系列弱分類器，然后組合弱分類器，得到一個強分類器。Boosting方法在學習過程中通過改變訓練數(shù)據(jù)的權(quán)值分布，針對不同的數(shù)據(jù)分布調(diào)用弱學習算法得到一系列弱分類器。
這里面有兩個問題需要回答：
在每一輪學習之前，如何改變訓練數(shù)據(jù)的權(quán)值分布？
如何將一組弱分類器組合成一個強分類器？
具體不同的boosting實現(xiàn)，主要區(qū)別在弱學習算法本身和上面兩個問題的回答上。
針對第一個問題，Adaboost算法的做法是：
提高那些被前一輪弱分類器錯誤分類樣本的權(quán)值，而降低那些被正確分類樣本的權(quán)值。
如此，那些沒有得到正確分類的樣本，由于其權(quán)值加大而受到后一輪的弱分類器的更大關注。
第二個問題，弱分類器的組合，AdaBoost采取加權(quán)多數(shù)表決的方法。具體地：
加大 分類誤差率小 的弱分類器的權(quán)值，使其在表決中起較大的作用；減小分類誤差率大的弱分類器的權(quán)值，使其在表決中起較小的作用。
AdaBoost算法的巧妙之處就在于它將這些學習思路自然并且有效地在一個算法里面實現(xiàn)。
前向分步加法模型
英文名稱：Forward Stagewise Additive Modeling
加法模型（addtive model）
f(x)=∑k=1Kβk?b(x;γk)(ml.1.6.1)f(x)=∑k=1Kβk?b(x;γk)(ml.1.6.1)
其中，b(x;γk)b(x;γk)?為基函數(shù)，γkγk為基函數(shù)的參數(shù)，βkβk為基函數(shù)的系數(shù)。
前向分步算法
在給定訓練數(shù)據(jù)及損失函數(shù)L(y,f(x))L(y,f(x))的條件下，學習加法模型f(x)f(x)成為經(jīng)驗風險極小化即損失函數(shù)極小化的問題：
minβk,γk∑i=1ML[y(i),∑k=1Kβkb(x(i);γk)](ml.1.6.2)minβk,γk∑i=1ML[y(i),∑k=1Kβkb(x(i);γk)](ml.1.6.2)
通常這是一個復雜的優(yōu)化問題。前向分布算法（forward stagwise algorithm）求解這一優(yōu)化問題的思路是：因為學習的是加法模型，如果能夠從前向后，每一步只學習一個基函數(shù)及其系數(shù)，逐步逼近優(yōu)化目標函數(shù)式(ml.1.6.1)(ml.1.6.1)，那么就可以簡化優(yōu)化的復雜度。具體地，每步只需優(yōu)化如下?lián)p失函數(shù)：
minβ,γ∑i=1ML(y(i),βb(x(i);γ))(n.ml.1.6.1)minβ,γ∑i=1ML(y(i),βb(x(i);γ))(n.ml.1.6.1)
給定訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))},x(i)∈X?Rn,y(i)∈Y=D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))},x(i)∈X?Rn,y(i)∈Y={?1,+1}{?1,+1}。損失函數(shù)L(y,f(x))L(y,f(x))和基函數(shù)的集合{b(x;γ)}{b(x;γ)}，學習加法模型f(x)f(x)的前向分步算法如下：
{輸入：訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))};損失函數(shù)L(y,f(x));基函數(shù)集{b(x,γ)}；輸出：加法模型f(x)。計算過程：(1).初始化f0(x)=0(2).對于k=1,2,?,K(a).極小化損失函數(shù)(βk,γk)=argminβ,γ∑Mi=1L(y(i),fk?1(x(i))+βb(x;γ))(n.ml.1.6.2)得到參數(shù)βk,γk.(b).更新fk(x)=fk?1(x)+βkb(x;γk)(n.ml.1.6.3)(3).得到加法模型f(x)=fK(x)=∑Kk=1βkb(x;γk)(n.ml.1.6.4)}{輸入：訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))};損失函數(shù)L(y,f(x));基函數(shù)集{b(x,γ)}；輸出：加法模型f(x)。計算過程：(1).初始化f0(x)=0(2).對于k=1,2,?,K(a).極小化損失函數(shù)(βk,γk)=arg?minβ,γ∑i=1ML(y(i),fk?1(x(i))+βb(x;γ))(n.ml.1.6.2)得到參數(shù)βk,γk.(b).更新fk(x)=fk?1(x)+βkb(x;γk)(n.ml.1.6.3)(3).得到加法模型f(x)=fK(x)=∑k=1Kβkb(x;γk)(n.ml.1.6.4)}
這樣前向分步算法將同時求解從k=1k=1到KK的所有參數(shù)βk,γkβk,γk的優(yōu)化問題簡化為逐次求解各個βk,γkβk,γk的優(yōu)化問題。
Boosting四大家族
Boosting并非是一個方法，而是一類方法。這里按照損失函數(shù)的不同，將其細分為若干類算法，下表給出了4種不同損失函數(shù)對應的Boosting方法：
名稱(Name)損失函數(shù)(Loss)導數(shù)(Derivative)目標函數(shù)f?f?算法
平方損失
(Squared Error)
12(y(i)?f(x(i)))212(y(i)?f(x(i)))2y(i)?f(x(i))y(i)?f(x(i))E[y|x(i)]E[y|x(i)]L2Boosting
絕對損失
(Absolute Error)
|y(i)?f(x(i))||y(i)?f(x(i))|sign(y(i)?f(x(i))sign(y(i)?f(x(i))median(y|x(i))median(y|x(i))Gradient Boosting
指數(shù)損失
(Exponentail Loss)
exp(?y(i)~f(x(i)))exp?(?y(i)~f(x(i)))?y(i)~exp(?y(i)~f(x(i)))?y(i)~exp(?y(i)~f(x(i)))12logπi1?πi12log?πi1?πiAdaBoost
對數(shù)損失
(LogLoss)
log(1+e?y(i)~fi)log?(1+e?y(i)~fi)y(i)?πiy(i)?πi12logπi1?πi12log?πi1?πiLogitBoost
說明：
該表來自于Machine Learning: A Probabilistic PerspectiveP587頁
L2Boosting全稱：Least Squares Boosting；該算法由Buhlmann和Yu在2003年提出。
二分類問題時損失函數(shù)示意圖：
損失函數(shù)示意圖
下面主要以AdaBoost算法作為示例，給出以下3個問題的解釋：
AdaBoost為什么能夠提升學習精度？
如何解釋AdaBoost算法？
Boosting方法更具體的實例－Boosting Tree。
下面首先介紹Adaboost算法。
Adaboost
算法學習過程
Adaboost算法在分類問題中的主要特點：通過改變訓練樣本的權(quán)重，學習多個分類器，并將這些分類器進行線性組合，提高分類性能。?AdaBoost－算法描述（偽代碼）如下：
{輸入：訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))}，x(i)∈X?RN，y(i)∈Y={?1,+1},弱分類器;輸出：最終分類器G(x).過程：(1).初始化訓練數(shù)據(jù)的權(quán)值分布D1=(w11,w12,?,w1M),w1i=1M,i=1,2,?,M(2).訓練K個弱分類器k=1,2,?,K(a).使用具有權(quán)值分布Dk的訓練數(shù)據(jù)集學習，得到基本分類器Gk(x):X→{?1,+1}(ml.1.6.3)(b).計算Gk(x)在訓練數(shù)據(jù)集上的分類誤差率ek=P(Gk(x(i))≠y(i))=∑i=1MwkiI(Gk(x(i))≠y(i))(ml.1.6.4)(c).計算Gk(x)的系數(shù)αk=12log1?ekek(e是自然對數(shù))(ml.1.6.5)(d).更新訓練數(shù)據(jù)集的權(quán)值分布Dk+1=(wk+1,1,wk+1,2,?,wk+1,M)wk+1,i=wk,iZkexp(?αky(i)Gk(x(i))),i=1,2,?,M(ml.1.6.6)Zk是規(guī)范化因子Zk=∑i=1Mwk,i?exp(?αky(i)Gk(x(i)))(ml.1.6.7)使Dk+1成為一個概率分布。(3).構(gòu)建基本分類器的線性組合f(x)=∑k=1KαkGk(x)(ml.1.6.8)得到最終的分類器G(x)=sign(f(x))=sign(∑k=1KαkGk(x))(ml.1.6.9)}{輸入：訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))}，x(i)∈X?RN，y(i)∈Y={?1,+1},弱分類器;輸出：最終分類器G(x).過程：(1).初始化訓練數(shù)據(jù)的權(quán)值分布D1=(w11,w12,?,w1M),w1i=1M,i=1,2,?,M(2).訓練K個弱分類器k=1,2,?,K(a).使用具有權(quán)值分布Dk的訓練數(shù)據(jù)集學習，得到基本分類器Gk(x):X→{?1,+1}(ml.1.6.3)(b).計算Gk(x)在訓練數(shù)據(jù)集上的分類誤差率ek=P(Gk(x(i))≠y(i))=∑i=1MwkiI(Gk(x(i))≠y(i))(ml.1.6.4)(c).計算Gk(x)的系數(shù)αk=12log?1?ekek(e是自然對數(shù))(ml.1.6.5)(d).更新訓練數(shù)據(jù)集的權(quán)值分布Dk+1=(wk+1,1,wk+1,2,?,wk+1,M)wk+1,i=wk,iZkexp?(?αky(i)Gk(x(i))),i=1,2,?,M(ml.1.6.6)Zk是規(guī)范化因子Zk=∑i=1Mwk,i?exp?(?αky(i)Gk(x(i)))(ml.1.6.7)使Dk+1成為一個概率分布。(3).構(gòu)建基本分類器的線性組合f(x)=∑k=1KαkGk(x)(ml.1.6.8)得到最終的分類器G(x)=sign(f(x))=sign(∑k=1KαkGk(x))(ml.1.6.9)}
AdaBoost算法描述說明
步驟（1）假設訓練數(shù)據(jù)集具有均勻（相同）的權(quán)值分布，即每個訓練樣本在基本分類器的學習中作用相同。
這一假設保證，第一步能在原始數(shù)據(jù)上學習基本分類器G1(x)G1(x)。
步驟（2）AdaBoost反復學習基本分類器，在每一輪k=1,2,?,Kk=1,2,?,K順序地執(zhí)行下列操作：
（a）學習基本分類器：使用當前分布DkDk加權(quán)的訓練數(shù)據(jù)集，學習基本分類器Gk(x)Gk(x)；
（b）誤差率：計算基本分類器Gk(x)Gk(x)在加權(quán)訓練數(shù)據(jù)集上的分類誤差率
ek=P(Gk(x(i))≠y(i))=∑Gk(x(i))≠y(i)wki(n.ml.1.6.5)ek=P(Gk(x(i))≠y(i))=∑Gk(x(i))≠y(i)wki(n.ml.1.6.5)
這里，wkiwki表示第kk輪中第ii個樣本的權(quán)值，∑Mi=1wki=1∑i=1Mwki=1。
這表明，Gk(x)Gk(x)在加權(quán)的訓練數(shù)據(jù)集上的分類誤差率 是 被Gk(x)Gk(x)誤分類樣本的權(quán)值之和。由此可以看出數(shù)據(jù)權(quán)值分布DkDk與基本分類器Gk(x)Gk(x)的分類誤差率的關系。
（c）分類器權(quán)重：計算基本分類器Gk(x)Gk(x)的系數(shù)αkαk，αkαk表示Gk(x)Gk(x)在最終分類器中的重要性
根據(jù)(ml.1.6.3)中公式可知，當ek≤0.5ek≤0.5時，αk≥0αk≥0，并且αkαk隨著ekek的減小而增大，所以分類誤差率越小的基本分類器在最終分類器中的作用越大。
（d）更新訓練數(shù)據(jù)的權(quán)值分布，為下一輪做準備，公式(ml.1.6.6)(ml.1.6.6)可以寫成：
wk+1,i={wkiZke?αk,wkiZkeαk,Gk(x(i))=y(i)Gk(x(i))≠y(i)(n.ml.1.6.6)wk+1,i={wkiZke?αk,Gk(x(i))=y(i)wkiZkeαk,Gk(x(i))≠y(i)(n.ml.1.6.6)
由此可知，被基本分類器Gk(x)Gk(x)誤分類樣本的權(quán)值得以擴大，而被正確分類樣本的權(quán)值卻得以縮小。相比較來說，誤分類樣本的權(quán)值被放大e2αk=ek1?eke2αk=ek1?ek倍。因此，誤分類樣本在下一輪學習中起更大的作用。
不改變所給的訓練數(shù)據(jù)，而不斷改變訓練數(shù)據(jù)權(quán)值的分布，使得訓練數(shù)據(jù)在基本分類器中起不同的作用，這也是AdaBoost的一個特點。
步驟（3）線性組合f(x)f(x)實現(xiàn)KK個基本分類器的加權(quán)表決。系數(shù)αkαk表示了極本分類器Gk(x)Gk(x)的重要性。
注意：在這里所有αkαk之和并不為1。f(x)f(x)的符號決定實例xx的類別，f(x)f(x)的絕對值表示分類的精確度。
利用基本分類器的線性組合構(gòu)建最終分類器是AdaBoost的另一個特點。
示例：AdaBoost算法
此示例參考李航老師的《統(tǒng)計學習方法》.
給定下表所示訓練數(shù)據(jù)。
序號12345678910
x0123456789
y111-1-1-1111-1
假設弱分類器由x≤v或x>vx≤v或x>v產(chǎn)生，其閾值vv使該分類器在訓練數(shù)據(jù)集上分類誤差率最低。試用AdaBoost算法學習一個強分類器。
解： 首先初始化數(shù)據(jù)權(quán)值分布（均勻分布）：
D1=(w1,1,w1,2,?,w1,10),w1,i=0.1,i=1,2,?,10D1=(w1,1,w1,2,?,w1,10),w1,i=0.1,i=1,2,?,10
對k=1k=1，
(a). 在權(quán)值分布為D1D1的訓練數(shù)據(jù)上，閾值vv取2.5時，分類誤差率最低，故基本分類器為：
G1(x)={1,?1,x<2.5x>2.5G1(x)={1,x<2.5?1,x>2.5
(b).?G1(x)G1(x)在訓練數(shù)據(jù)集上的誤差率e1=P(G1(x(i))≠y(i))=0.3e1=P(G1(x(i))≠y(i))=0.3;
(c). 計算G1(x)G1(x)的系數(shù)：α1=12log1?e1e1=0.4236α1=12log?1?e1e1=0.4236；
(d). 更新訓練數(shù)據(jù)的權(quán)值分布:
D2=(w2,1,w2,2,?,w2,10)w2,i=w1,iZ1exp(?α1y(i)G1(x(i))),i=1,2,?,10D2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)f1(x)=0.4236G1(x)D2=(w2,1,w2,2,?,w2,10)w2,i=w1,iZ1exp?(?α1y(i)G1(x(i))),i=1,2,?,10D2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)f1(x)=0.4236G1(x)
分類器sign[f1(x)]sign[f1(x)]在訓練數(shù)據(jù)上有3個誤分類點。
對k=2k=2，
(a). 在權(quán)值分布為D2D2的訓練數(shù)據(jù)上，閾值vv取8.5時，分類誤差率最低，基本分類器為：
G2(x)={1,?1,x<8.5x>8.5G2(x)={1,x<8.5?1,x>8.5
(b).?G2(x)G2(x)在訓練數(shù)據(jù)集上的誤差率e2=0.2143e2=0.2143;
(c). 計算G2(x)G2(x)的系數(shù)：α2=0.6496α2=0.6496；
(d). 更新訓練數(shù)據(jù)的權(quán)值分布:
D3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)f2(x)=0.4236?G1(x)+0.6496?G2(x)D3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)f2(x)=0.4236?G1(x)+0.6496?G2(x)
分類器sign[f2(x)]sign[f2(x)]在訓練數(shù)據(jù)上有3個誤分類點。
對k=3k=3，
(a). 在權(quán)值分布為D3D3的訓練數(shù)據(jù)上，閾值vv取5.5時，分類誤差率最低，基本分類器為：
G3(x)={1,?1,x<5.5x>5.5G3(x)={1,x<5.5?1,x>5.5
(b).?G3(x)G3(x)在訓練數(shù)據(jù)集上的誤差率e3=0.1820e3=0.1820;
(c). 計算G3(x)G3(x)的系數(shù)：α2=0.7514α2=0.7514；
(d). 更新訓練數(shù)據(jù)的權(quán)值分布:
D4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)D4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)
于是得到模型線性組合
f3(x)=0.4236?G1(x)+0.6496?G2(x)+0.7514?G3(x)f3(x)=0.4236?G1(x)+0.6496?G2(x)+0.7514?G3(x)
分類器sign[f3(x)]sign[f3(x)]在訓練數(shù)據(jù)上誤分類點個數(shù)為0。
于是最終分類器為：
G(x)=sign[f3(x)]=sign[0.4236?G1(x)+0.6496?G2(x)+0.7514?G3(x)]G(x)=sign[f3(x)]=sign[0.4236?G1(x)+0.6496?G2(x)+0.7514?G3(x)]
訓練誤差分析
AdaBoost算法最基本的性質(zhì)是它能在學習過程中不斷減少訓練誤差，即在訓練數(shù)據(jù)集上的分類誤差率。?對于這個問題，有個定理可以保證分類誤差率在減少－AdaBoost的訓練誤差界。
定理：AdaBoost訓練誤差界
［定理］AdaBoost訓練誤差界
1M∑i=1MI(G(x(i))≠y(i))≤1M∑iexp(?y(i)f(x(i)))=∏k=1KZk(ml.1.6.10)1M∑i=1MI(G(x(i))≠y(i))≤1M∑iexp?(?y(i)f(x(i)))=∏k=1KZk(ml.1.6.10)
其中，G(x),f(x)G(x),f(x)和ZkZk分別由公式(ml.1.6.9),(ml.1.6.8),(ml.1.6.7)(ml.1.6.9),(ml.1.6.8),(ml.1.6.7)給出
證明如下：
當G(x(i))≠y(i)G(x(i))≠y(i)時，y(i)f(x(i))<0y(i)f(x(i))<0，因而exp(?y(i)f(x(i)))≥1exp?(?y(i)f(x(i)))≥1。由此，可以直接推導出前半部分。
后半部分的推導要用到ZkZk的定義式(ml.1.6.7)(ml.1.6.7)和(ml.1.6.6)(ml.1.6.6)的變形:
wk,iexp(?αky(i)Gk(x(i)))=Zkwk+1,i(n.ml.1.6.7)wk,iexp?(?αky(i)Gk(x(i)))=Zkwk+1,i(n.ml.1.6.7)
推導如下：
1M∑i=1Mexp(?y(i)f(x(i)))=1M∑i=1M??????exp(?∑k=1Kαky(i)Gk(x(i)))=∑i=1Mw1,i??????∏k=1Kexp(?αky(i)Gk(x(i)))=∑i=1Mw1,iexp(?α1y(i))Gk(x(i))∏k=2Kexp(?αky(i)Gk(x(i)))???????????????????????????????????=Z1∑i=1Mw2,i∏k=2Kexp(?αky(i)Gk(x(i)))=Z1Z2∑i=1Mw3,i∏k=3Kexp(?αky(i)Gk(x(i)))=??=Z1Z2?ZK?1∑i=1MwK,iexp(?αKy(i)GK(x(i)))=∏k=1KZk(n.ml.1.6.8)1M∑i=1Mexp?(?y(i)f(x(i)))=1M∑i=1M_exp?(?∑k=1Kαky(i)Gk(x(i)))=∑i=1Mw1,i_∏k=1Kexp?(?αky(i)Gk(x(i)))=∑i=1Mw1,iexp?(?α1y(i))Gk(x(i))∏k=2Kexp?(?αky(i)Gk(x(i)))_=Z1∑i=1Mw2,i∏k=2Kexp?(?αky(i)Gk(x(i)))=Z1Z2∑i=1Mw3,i∏k=3Kexp?(?αky(i)Gk(x(i)))=??=Z1Z2?ZK?1∑i=1MwK,iexp?(?αKy(i)GK(x(i)))=∏k=1KZk(n.ml.1.6.8)
注意：w1,i=1Mw1,i=1M
這一定理說明：可以在每一輪選取適當?shù)腉kGk使得ZkZk最小，從而使訓練誤差下降最快。?對于二類分類問題，有如下定理。
定理：二類分類問題AdaBoost訓練誤差界
［定理］二類分類問題AdaBoost訓練誤差界
∏k=1KZk=∏k=1K[2ek(1?ek)????????√]=∏k=1K(1?4γ2k)????????√≤exp(?2∑k=1Kγ2k)(ml.1.6.9)∏k=1KZk=∏k=1K[2ek(1?ek)]=∏k=1K(1?4γk2)≤exp?(?2∑k=1Kγk2)(ml.1.6.9)
這里，γk=0.5?ekγk=0.5?ek
證明：由公式(ml.1.6.7)(ml.1.6.7)和(n.ml.1.6.5)(n.ml.1.6.5)可得：
Zk=∑i=1Mwk,iexp(?αky(i)Gk(x(i)))=∑y(i)=Gk(x(i))wk,i?e?αk+∑y(i)≠Gk(x(i))wk,i?eαk=(1?ek)?e?αk+ek?eαk=2ek(1?ek)????????√=1?4γ2m???????√(n.ml.1.6.9)Zk=∑i=1Mwk,iexp?(?αky(i)Gk(x(i)))=∑y(i)=Gk(x(i))wk,i?e?αk+∑y(i)≠Gk(x(i))wk,i?eαk=(1?ek)?e?αk+ek?eαk=2ek(1?ek)=1?4γm2(n.ml.1.6.9)
注：αk=12log1?ekek,eαk=1?ekek????√αk=12log?1?ekek,eαk=1?ekek
對于不等式部分
∏k=1K1?4γ2m???????√≤exp(?2∑k=1Kγ2k)(n.ml.1.6.10)∏k=1K1?4γm2≤exp?(?2∑k=1Kγk2)(n.ml.1.6.10)
則可根據(jù)exex和1?x????√1?x在點x=0x=0的泰勒展開式推出不等式1?4γ2m???????√≤exp(?2γ2m)1?4γm2≤exp?(?2γm2)。
[推論] AdaBoost訓練誤差指數(shù)速率下降
如果存在γ>0γ>0，對所有的mm有γk≥γγk≥γ，則有
1M∑i=1MI(G(x(i))≠y(i))≤exp(?2Kγ2)(ml.1.6.12)1M∑i=1MI(G(x(i))≠y(i))≤exp?(?2Kγ2)(ml.1.6.12)
|
推論表明，在此條件下，AdaBoost的訓練誤差是以指數(shù)速率下降的。這一性質(zhì)對于AdaBoost計算（迭代）效率是利好消息。
注意：AdaBoost算法不需要知道下界γγ，這正是Freund和Schapire設計AdaBoost時所考慮的。與一些早期的提升方法不同，AdaBoost具有適應性，即它能適應弱分類器各自的訓練誤差率。這也是其算法名稱的由來（適應的提升）。Ada是Adaptive的簡寫。
前向分步加法模型與Adaboost
AdaBoost算法還有另一個解釋，即可以認為AdaBoost算法是模型為加法模型、損失函數(shù)為指數(shù)函數(shù)、學習算法為前向分步算法時的學習方法。
根據(jù)前向分步算法可以推導出AdaBoost，用一句話敘述這一關系.
AdaBoost算法是前向分步加法算法的特例
此時，模型是由基本分類器組成的加法模型，損失函數(shù)是指數(shù)函數(shù)。
證明：前向分步算法學習的是加法模型，當基函數(shù)為基本分類器時，該加法模型等價于AdaBoost的最終分類器：
f(x)=∑k=1KαkGk(x)(n.ml.1.6.11)f(x)=∑k=1KαkGk(x)(n.ml.1.6.11)
由基本分類器Gk(x)Gk(x)及其系數(shù)αkαk組成，k=1,2,?,Kk=1,2,?,K。前向分步算法逐一學習基函數(shù)，這一過程與AdaBoost算法逐一學習基本分類器的過程一致。
下面證明：
前向分步算法的損失函數(shù)是指數(shù)損失函數(shù)（Exponential）L(y,f(x))=exp[?yf(x)]L(y,f(x))=exp?[?yf(x)]?時，其學習的具體操作等價于AdaBoost算法學習的具體操作。
假設經(jīng)過k?1k?1輪迭代，前向分步算法已經(jīng)得到fk?1(x)fk?1(x):
fk?1(x)=fk?2(x)+αk?1Gk?1(x)=α1G1(x)+?+αm?1Gm?1(x)(n.ml.1.6.12)fk?1(x)=fk?2(x)+αk?1Gk?1(x)=α1G1(x)+?+αm?1Gm?1(x)(n.ml.1.6.12)
在第kk輪迭代得到αk,Gk(x)αk,Gk(x)和fk(x)fk(x)。
fk(x)=fk?1(x)+αkGk(x)(n.ml.1.6.13)fk(x)=fk?1(x)+αkGk(x)(n.ml.1.6.13)
目標是使前向分步算法得到的αkαk和Gk(x)Gk(x)使fk(x)fk(x)在訓練數(shù)據(jù)集DD上的指數(shù)損失最小，即
(αk,Gk(x))=argminα,G∑i=1Mexp[?y(i)(fk?1(x)+αG(x(i)))]指數(shù)損失表達式(n.ml.1.6.14)(αk,Gk(x))=arg?minα,G∑i=1Mexp?[?y(i)(fk?1(x)+αG(x(i)))]?指數(shù)損失表達式(n.ml.1.6.14)
進一步可表示為：
(αk,Gk(x))=argminα,G∑i=1Mwˉˉˉˉk,i?exp[?y(i)αG(x(i))](n.ml.1.6.15)(αk,Gk(x))=arg?minα,G∑i=1Mwˉk,i?exp?[?y(i)αG(x(i))](n.ml.1.6.15)
其中，wˉˉˉˉk,i=exp[?y(i)fk?1(x(i))]wˉk,i=exp?[?y(i)fk?1(x(i))]表示第ii樣本在之前模型上的指數(shù)損失。因為wˉˉˉˉk,iwˉk,i既不依賴αα也不依賴GG，所以與最小化無關。但wˉˉˉˉk,iwˉk,i依賴于fk?1(x)fk?1(x)，隨著每一輪迭代而發(fā)生變化。
現(xiàn)在使公式(n.ml.1.6.15)(n.ml.1.6.15)達到最小的α?kαk?和G?kGk?就是AdaBoost算法所得到的αkαk和Gk(x)Gk(x)。求解公式(n.ml.1.6.15)(n.ml.1.6.15)可分為兩步：
第一步：求G?kGk?. 對于任意α>0α>0，使公式(n.ml.1.6.15)(n.ml.1.6.15)最小的G(x)G(x)由下式得到：
G?k(x)=argminG∑i=1Mwˉˉˉˉk,i?I(y(i)≠G(x(i)))(n.ml.1.6.16)Gk?(x)=arg?minG∑i=1Mwˉk,i?I(y(i)≠G(x(i)))(n.ml.1.6.16)
此分類器G?k(x)Gk?(x)即為AdaBoost算法的基本分類器Gk(x)Gk(x)，因為它是使第kk輪加權(quán)訓練數(shù)據(jù)分類誤差率最小的基本分類器。
之后，求α?kαk?。參考公式(n.ml.1.6.5)(n.ml.1.6.5)，公式(n.ml.1.6.15)(n.ml.1.6.15)中的：
∑i=1Mwˉˉˉˉk,i?exp[?y(i)αG(x(i))]?=∑y(i)=Gk(x(i))wˉˉˉˉk,i?e?α+∑y(i)≠Gk(x(i))wˉˉˉˉk,i?eα=(eα?e?α)∑i=1Mwˉˉˉˉk,iI(y(i)≠G(x(i)))+e?α∑i=1Mwˉˉˉˉk,i(n.ml.1.6.17)∑i=1Mwˉk,i?exp?[?y(i)αG(x(i))]=∑y(i)=Gk(x(i))wˉk,i?e?α+∑y(i)≠Gk(x(i))wˉk,i?eα?=(eα?e?α)∑i=1Mwˉk,iI(y(i)≠G(x(i)))+e?α∑i=1Mwˉk,i(n.ml.1.6.17)
把已得到的G?kGk?帶入公式(n.ml.1.6.17)(n.ml.1.6.17)，并對αα求導（導數(shù)為0），即得到使公式(n.ml.1.6.15)(n.ml.1.6.15)最小的αα。
α?k=12log1?ekekαk?=12log?1?ekek
ekek為分類誤差率
ek=∑Mi=1wˉˉˉˉk,iI(y(i)≠Gk(x(i)))∑Mi=1wˉˉˉˉk,i=∑i=1Mwk,iI(y(i)≠Gk(x(i)))ek=∑i=1Mwˉk,iI(y(i)≠Gk(x(i)))∑i=1Mwˉk,i=∑i=1Mwk,iI(y(i)≠Gk(x(i)))
可以看出，這里求得的α?kαk?與AdaBoost算法(2)?(c)(2)?(c)步的αkαk完全一致。
最后看一下每一輪樣本權(quán)值的更新。由：fk(x)=fk?1(x)+αkGk(x)fk(x)=fk?1(x)+αkGk(x)以及wˉˉˉˉk,i=exp[?y(i)fk?1(x(i))]wˉk,i=exp?[?y(i)fk?1(x(i))]，可得：
wˉˉˉˉk+1,i=wˉˉˉˉk,iexp[?y(i)αkGk(x)]wˉk+1,i=wˉk,iexp?[?y(i)αkGk(x)]
這與Adaboost算法的第(2)?(d)(2)?(d)步的樣本權(quán)值的更新，可看出二者是等價的（只相差規(guī)范化因子）。
AdaBoost算法缺點
對異常點敏感
指數(shù)損失存在的一個問題是不斷增加誤分類樣本的權(quán)重（指數(shù)上升）。如果數(shù)據(jù)樣本是異常點（outlier），會極大的干擾后面基本分類器學習效果；
模型無法用于概率估計
MLAPP中的原話：”e?y~fe?y~f?is not the logarithm of any pmf for binary variables?y~∈{?1,+1}y~∈{?1,+1}; consequently we cannot recover probability estimate from?f(x)f(x).”
意思就是說對于取值為y~∈{?1,+1}y~∈{?1,+1}的隨機變量來說，e?y~fe?y~f不是任何概率密度函數(shù)的對數(shù)形式，模型f(x)f(x)的結(jié)果無法用概率解釋。
Boosted Decision Tree
提升決策樹是指以分類與回歸樹（CART）為基本分類器的提升方法，被認為是統(tǒng)計學習中性能最好的方法之一。
提升決策樹簡稱提升樹，Boosting Tree.
提升樹模型
提升樹模型實際采用加法模型（即基函數(shù)的線性組合）與前向分步算法，以決策樹為基函數(shù)的提升方法稱為提升樹（Boosting Tree）。
對分類問題決策樹是二叉分類樹，對回歸問題決策樹是二叉回歸樹。在6.1.3節(jié)AdaBoost例子中，基本分類器是\(xv\)，可以看作是由一個跟結(jié)點直接連接兩個葉結(jié)點的簡單決策樹，即所謂的決策樹樁（Decision Stump）。
提升樹模型可以表示為CART決策樹的加法模型：
fK(x)=∑k=1KT(x;Θk)(ml.1.6.13)fK(x)=∑k=1KT(x;Θk)(ml.1.6.13)
其中，T(x;Θk)T(x;Θk)表示二叉決策樹，ΘkΘk為決策樹的參數(shù)，KK為樹的個數(shù)。
基本學習器－CART決策樹，請參考第03章：深入淺出ML之Tree-Based家族
提升樹算法
提升樹算法采用前向分步算法。首先確定初始提升樹f0(x)=0f0(x)=0，第kk步的模型為：
fk(x)=fk?1(x)+T(x;Θk)(ml.1.6.14)fk(x)=fk?1(x)+T(x;Θk)(ml.1.6.14)
其中，fk?1(x)fk?1(x)為當前模型，通過經(jīng)驗風險極小化確定下一顆決策樹的參數(shù)ΘkΘk，
Θ^k=argminΘk∑i=1ML(y(i),fk?1(x)+T(x(i);Θk))(ml.1.6.15)Θ^k=arg?minΘk∑i=1ML(y(i),fk?1(x)+T(x(i);Θk))(ml.1.6.15)
由于樹的線性組合可以很好的擬合訓練數(shù)據(jù)，即使數(shù)據(jù)中的輸入和輸出之間的關系很復雜也是如此，所以提升樹是一個高功能的學習算法。
提升樹家族
不同問題的提升樹學習算法，其主要區(qū)別在于損失函數(shù)不同。平方損失函數(shù)常用于回歸問題，用指數(shù)損失函數(shù)用于分類問題，以及絕對損失函數(shù)用于決策問題。
對于二類分類問題，提升樹算法只需要將AdaBoost算法例子中的基本分類器限制為二叉分類樹即可，可以說此時的決策樹算法時AdaBoost算法的特殊情況。
損失函數(shù)仍為指數(shù)損失，提升樹模型仍為前向加法模型。
已知訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))},x(i)∈X?Rn,y(i)∈YD={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))},x(i)∈X?Rn,y(i)∈Y??R,Y?R,Y為輸出空間。如果將輸入空間XX劃分為JJ個互不相交的區(qū)域R1,R2,?,RJR1,R2,?,RJ，并且在每個區(qū)域上確定輸出的常量cjcj，那么樹可以表示為：
T(x;Θ)=∑j=1JcjI(x∈Rj)(ml.1.6.16)T(x;Θ)=∑j=1JcjI(x∈Rj)(ml.1.6.16)
其中，參數(shù)Θ={(R1,c1),(R2,c2),?,(RJ,cJ)}Θ={(R1,c1),(R2,c2),?,(RJ,cJ)}表示樹的區(qū)域劃分和各區(qū)域上的常數(shù)。JJ是回歸樹的復雜度即葉結(jié)點的個數(shù)。
回歸問題提升樹－前向分步算法
回歸問題提升樹使用以下前向分步算法：
f0(x)fk(x)fK(x)=0=fk?1(x)+T(x;Θk)k=1,2,?,K=∑k=1KT(x;Θk)(n.ml1.6.17)f0(x)=0fk(x)=fk?1(x)+T(x;Θk)k=1,2,?,KfK(x)=∑k=1KT(x;Θk)(n.ml1.6.17)
在前向分布算法的第kk步，給定當前模型fk?1(x)fk?1(x)，需求解：
Θ^k=argminΘk∑i=1ML(y(i),fk?1(x)+T(x(i);Θk))損失函數(shù)(n.ml.1.6.18)Θ^k=arg?minΘk∑i=1ML(y(i),fk?1(x)+T(x(i);Θk))?損失函數(shù)(n.ml.1.6.18)
得到Θ^kΘ^k，即第kk顆樹的參數(shù)。
當采用平方誤差損失函數(shù)時，
L(y,f(x))=(y?f(x))2(n.ml.1.6.19)L(y,f(x))=(y?f(x))2(n.ml.1.6.19)
將平方誤差損失函數(shù)展開為：
L(y,fk?1(x)+T(x;Θk))=[y?fk?1(x)?T(x;Θk)]2=[r?T(x;Θk)]2(n.ml.1.6.20)L(y,fk?1(x)+T(x;Θk))=[y?fk?1(x)?T(x;Θk)]2=[r?T(x;Θk)]2(n.ml.1.6.20)
這里r=y?fk?1(x)r=y?fk?1(x)，表示當前模型的擬合數(shù)據(jù)的殘差（residual）。所以，對回歸問題的提升樹算法來說，只需要簡單地擬合當前模型的殘差。
由于損失函數(shù)是平方損失，因此該方法屬于L2Boosting的一種實現(xiàn)。
回歸問題提升樹－算法描述
{輸入：訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))},x(i)∈X?Rn,y(i)∈Y;輸出：提升樹fK(x).過程:(1).初始化模型f0(x)=0；(2).循環(huán)訓練K個模型k=1,2,?,K(a).計算殘差：rki=y(i)?fk?1(x(i)),i=1,2,?,M(b).擬合殘差rki學習一個回歸樹，得到T(x;Θk)(c).更新fk(x)=fk?1(x)+T(x;Θk)(3).得到回歸提升樹fK(x)=∑Kk=1T(x;Θk)}{輸入：訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))},x(i)∈X?Rn,y(i)∈Y;輸出：提升樹fK(x).過程:(1).初始化模型f0(x)=0；(2).循環(huán)訓練K個模型k=1,2,?,K(a).計算殘差：rki=y(i)?fk?1(x(i)),i=1,2,?,M(b).擬合殘差rki學習一個回歸樹，得到T(x;Θk)(c).更新fk(x)=fk?1(x)+T(x;Θk)(3).得到回歸提升樹fK(x)=∑k=1KT(x;Θk)}
Gradient Boosting
提升樹方法是利用加法模型與前向分布算法實現(xiàn)整個優(yōu)化學習過程。Adaboost的指數(shù)損失和回歸提升樹的平方損失，在前向分布中的每一步都比較簡單。但對于一般損失函數(shù)而言（比如絕對損失），每一個優(yōu)化并不容易。
針對這一問題。Freidman提出了梯度提升（gradient boosting）算法。該算法思想：
利用損失函數(shù)的負梯度在當前模型的值作為回歸問題提升樹算法中殘差的近似值，擬合一個回歸樹。
損失函數(shù)的負梯度為：
?[?L(y(i),f(x(i)))?f(x(i))]f(x)=fk?1(x)≈rm,i?[?L(y(i),f(x(i)))?f(x(i))]f(x)=fk?1(x)≈rm,i
Gradient Boosting－算法描述
{輸入：訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))},x(i)∈X?Rn,y(i)∈Y;損失函數(shù)L(y,f(x));輸出：提升樹f^(x).過程:(1).初始化模型f0(x)=argminc∑Mi=1L(y(i),c)；(2).循環(huán)訓練K個模型k=1,2,?,K(a).計算殘差：對于i=1,2,?,Mrki=?[?L(y(i),f(x(i)))?f(x(i))]f(x)=fk?1(x)(b).擬合殘差rki學習一個回歸樹，得到第k顆樹的葉結(jié)點區(qū)域Rkj，j=1,2,?,J(c).對j=1,2,?,J,計算：ckj=argminc∑x(i)∈RkjL(y(i),fk?1(x(i))+c)(d).更新模型：fk(x)=fk?1(x)+∑Jj=1ckjI(x∈Rkj)(3).得到回歸提升樹f^(x)=fK(x)=∑Kk=1∑Jj=1ckjI(x∈Rkj)}{輸入：訓練數(shù)據(jù)集D={(x(1),y(1)),(x(2),y(2)),?,(x(M),y(M))},x(i)∈X?Rn,y(i)∈Y;損失函數(shù)L(y,f(x));輸出：提升樹f^(x).過程:(1).初始化模型f0(x)=arg?minc∑i=1ML(y(i),c)；(2).循環(huán)訓練K個模型k=1,2,?,K(a).計算殘差：對于i=1,2,?,Mrki=?[?L(y(i),f(x(i)))?f(x(i))]f(x)=fk?1(x)(b).擬合殘差rki學習一個回歸樹，得到第k顆樹的葉結(jié)點區(qū)域Rkj，j=1,2,?,J(c).對j=1,2,?,J,計算：ckj=arg?minc∑x(i)∈RkjL(y(i),fk?1(x(i))+c)(d).更新模型：fk(x)=fk?1(x)+∑j=1JckjI(x∈Rkj)(3).得到回歸提升樹f^(x)=fK(x)=∑k=1K∑j=1JckjI(x∈Rkj)}
算法解釋：
第（1）步初始化，估計使損失函數(shù)極小化的常數(shù)值（是一個只有根結(jié)點的樹）；
第(2)(a)步計算損失函數(shù)的負梯度在當前模型的值，將它作為殘差的估計。(對于平方損失函數(shù)，他就是殘差；對于一般損失函數(shù)，它就是殘差的近似值)
第(2)(b)步估計回歸樹的結(jié)點區(qū)域，以擬合殘差的近似值；
第(2)(c)步利用線性搜索估計葉結(jié)點區(qū)域的值，使損失函數(shù)極小化；
第(2)(d)步更新回歸樹。
Boosting利器
Boosting類方法在不僅在二分類、多分類上有著出色的表現(xiàn)，在預估問題上依然出類拔萃。
2012年KDD cup競賽和Kaggle上的許多數(shù)據(jù)挖掘競賽，Boosting類方法幫助參賽者取得好成績提供了強有力的支持。
“工欲善其事，必先利其器”。Github上和機器學習工具包（如sklearn）中有很多優(yōu)秀的開源boosting實現(xiàn)。在這里重點介紹兩個Boosting開源工具。
說到Boosting開源工具，首推@陳天奇怪同學的XGBoost?(eXtreme Gradient Boosting)。上面說的各種競賽很多優(yōu)秀的戰(zhàn)果都是用@陳天奇同學的神器。
從名稱可以看出，該版本側(cè)重于Gradient Boosting方面，提供了Graident Boosting算法的框架，給出了GBDT，GBRT，GBM具體實現(xiàn)。提供了多語言接口（C++, Python, Java, R等），供大家方便使用。
更令人振奮的一件事情是，最新版本的xgboost是基于分布式通信協(xié)議rabit開發(fā)的，可部署在分布式資源調(diào)度系統(tǒng)上（如yarn，s3等）。我們完全可以利用最新版的xgboost在分布式環(huán)境下解決分類、預估等場景問題。
注：
XGBoost是DMLC（即分布式機器學習社區(qū)）下面的一個子項目，由@陳天奇怪，@李沐等機器學習大神發(fā)起。
Rabit是一個為分布式機器學習提供Allreduce和Broadcast編程范式和容錯功能的開源庫（也是@陳天奇同學的又一神器）。它主要是解決MPI系統(tǒng)機器之間無容錯功能的問題，并且主要針對Allreduce和Broadcast接口提供可容錯功能。
題外話：
2014年第一次用XGBoost時，用于Kaggle移動CTR預估競賽。印象比較深刻的是，同樣的訓練數(shù)據(jù)（特征工程后），分別用XGBoost中的GBDT和MLLib中的LR模型（LBFGS優(yōu)化），在驗證集上的表現(xiàn)前者比后者好很多（logloss和auc都是如此）。線上提交結(jié)果時，名次直接殺進前100名，當時給我留下了非常好的印象。后來，因為項目原因，沒有過多的使用xgboost，但一直關注著。
目前，我個人更加關注的是：基于Rabit開發(fā)/封裝一些在工業(yè)界真正能發(fā)揮重要價值的（分布式）機器學習工具，用于解決超大規(guī)模任務的學習問題。這里面會涉及到分布式環(huán)境下的編程范式，可以高效地在分布式環(huán)境下工作的優(yōu)化算法（admm等）和模型(loss + regularization term)等。
關于大數(shù)據(jù)下的機器學習發(fā)展，個人更看好將計算引擎模塊與資源調(diào)度模塊獨立開來，專注做各自的事情。計算引擎可以在任意的分布式資源調(diào)度系統(tǒng)上工作，實現(xiàn)真正的可插拔，是一個不錯的方向。
與之觀念對應的是，spark上集成的graphx和mllib中的許多計算模塊，雖然使用起來很簡便（幾十行核心代碼就能搭建一個學習任務的pipeline）。但可以想象的是，隨著spark的進一步發(fā)展，該分布式計算平臺會變的非常重，功能也會越來越多。離專注、專一和極致的解決某類問題越來越遠，對每一類問題給出的解決方案并不會特別好。
MultiBoost工具的側(cè)重點不同于XGBoost，是Adaboost算法的多分類版本實現(xiàn)，更偏向于解決multi-class / multi-label / multi-task的分類問題。
我們曾經(jīng)基于該工具訓練了用于用戶興趣畫像的多標簽（multi-label）分類模型，其分類效果（Precision / Recall作為指標）要比Naive Bayes好。
MultiBoost是用C++實現(xiàn)的。值得一提的是，由我們組的算法大神和男神@BaiGang實現(xiàn)了MulitBoost的spark版本（Scala語言），詳見Github: Spark_MultiBoost
