|
最近重點(diǎn)學(xué)習(xí)了gbdt算法，看了較多的博客文章，整理了一下這些比較有用的內(nèi)容，包括算法理論、算法分析、代碼剖析、注意事項(xiàng)等各個(gè)方面。 轉(zhuǎn)載來(lái)源： http://www.cnblogs.com/rocketfan/p/4324605.html http://www.cnblogs.com/rocketfan/p/4365950.html http://www.cnblogs.com/rocketfan/p/4366501.html http://blog.163.com/zhoulili1987619@126/blog/static/3530820120159852041442/ http://blog.csdn.NET/w28971023/article/details/43704775 http://www.cnblogs.com/leftnoteasy/archive/2011/03/07/random-forest-and-gbdt.html
GBDT的基本原理 這里以二元分類(lèi)為例子，給出最基本原理的解釋
GBDT 是多棵樹(shù)的輸出預(yù)測(cè)值的累加 GBDT的樹(shù)都是 回歸樹(shù) 而不是分類(lèi)樹(shù)
分裂的時(shí)候選取使得誤差下降最多的分裂
計(jì)算的技巧
最終分裂收益按照下面的方式計(jì)算，注意圓圈內(nèi)的部分是固定值
GBDT在實(shí)現(xiàn)中可以完全復(fù)用上面的計(jì)算方法框架，只是我們的優(yōu)化的目標(biāo)函數(shù)不同。 這里使用的是 指數(shù)誤差函數(shù)，不管是預(yù)測(cè)正確還是錯(cuò)誤 誤差值都存在，但是正確的預(yù)測(cè) 會(huì)使得誤差值小于錯(cuò)誤的預(yù)測(cè) 參考 AdaBoost and the Super Bowl of Classi?ers A Tutorial Introduction to Adaptive Boosting
關(guān)于常用誤差函數(shù) 參考 http://www.cnblogs.com/rocketfan/p/4083821.html
參考 Greedy Functon Approximation:A Gradient Boosting Machine 4.4節(jié)關(guān)于二分類(lèi)情況誤差函數(shù)的設(shè)計(jì)
這里其實(shí)和上面給出的一樣，只是增加了 log(1 +, 另外多了一個(gè)2,2yF), 參考前面的LossFunction http://www.cnblogs.com/rocketfan/p/4083821.html 的推導(dǎo)，其實(shí)這個(gè)應(yīng)該算作LogLoss或者說(shuō)是logistic regression, cross entropy error,也就是從probablity出發(fā)的logloss推導(dǎo)到output F(x)的表示就是上面的 式子，而它看上去剛好就是一個(gè)指數(shù)誤差函數(shù)。 嚴(yán)格意義上說(shuō)是LogLoss不是指數(shù)誤差 不過(guò)LogLoss和指數(shù)誤差看上去比較相似。
這個(gè)F值其實(shí)就是邏輯回歸的思路，類(lèi)似 語(yǔ)音語(yǔ)言處理一書(shū)27頁(yè)解釋?zhuān)€(xiàn)性加權(quán)的值（output)用來(lái)預(yù)測(cè) p(true)和p(false)的比例的log值（回歸值是實(shí)數(shù)范圍取值不適合預(yù)測(cè)0-1，做了一個(gè)轉(zhuǎn)換)，越是接近true，那么F(x)越接近+無(wú)窮(對(duì)應(yīng)最大可能性判斷true)， p(false)越大 那么越接近-無(wú)窮(對(duì)應(yīng)最大可能性判斷false)
F(X) 對(duì)應(yīng) feature X 當(dāng)前的回歸預(yù)測(cè)值也就是多棵樹(shù)經(jīng)過(guò)決策到達(dá)葉子節(jié)點(diǎn)的輸出值output(x)的累加值。N個(gè)樣本則F(x)N個(gè)維度，當(dāng)開(kāi)始沒(méi)有分裂的時(shí)候所有樣本在一個(gè)節(jié)點(diǎn)則所有F(x)對(duì)應(yīng)一個(gè)相同的值，分裂一次后兩個(gè)葉子節(jié)點(diǎn)則F(X)對(duì)應(yīng)可能到不同的葉子節(jié)點(diǎn)從而可能有兩個(gè)不同的值。 對(duì)誤差函數(shù)計(jì)算關(guān)于F的梯度，誤差函數(shù)是
變量是F(x)
考慮learning_rate之后是 （@TODO)
F(X) 對(duì)應(yīng) 葉子節(jié)點(diǎn)中一個(gè)樣本對(duì)應(yīng)它的feature X 當(dāng)前的預(yù)測(cè)值 參考 機(jī)器學(xué)習(xí)概率角度 一書(shū)的16章
我們的分裂目標(biāo)從上面回歸樹(shù)基本算法中的希望逼近y 變成了 逼近梯度值 r_im， 也就是說(shuō)當(dāng)前樹(shù)是預(yù)測(cè)負(fù)梯度值的。 F_m(x) = F_m-1(x) + learning_rate*(當(dāng)前樹(shù)的預(yù)測(cè)值(也就是預(yù)測(cè)負(fù)梯度..)) //@TODO check
再對(duì)比下ng課件最簡(jiǎn)單的梯度下降 針對(duì)regression的例子
我們采用的每顆樹(shù)更新策略是針對(duì)F(x)的，而F(x)沿著梯度的方向的累加，目標(biāo)是使得我們的
誤差函數(shù)達(dá)到最小。
考慮一個(gè)簡(jiǎn)單的例子來(lái)演示GBDT算法原理 下面是一個(gè)二分類(lèi)問(wèn)題，1表示可以考慮的相親對(duì)象，0表示不考慮的相親對(duì)象 特征維度有3個(gè)維度，分別對(duì)象 身高，金錢(qián)，顏值
cat dating.txt #id,label,hight,money,face _0,1,20,80,100 _1,1,60,90,25 _2,1,3,95,95 _3,1,66,95,60 _4,0,30,95,25 _5,0,20,12,55 _6,0,15,14,99 _7,0,10,99,2
這個(gè)例子僅僅為了試驗(yàn)，數(shù)據(jù)量很小沒(méi)有更多統(tǒng)計(jì)意義。
0,1,2,3對(duì)應(yīng)可以考慮的相親對(duì)象 4,5,6,7 對(duì)應(yīng)不考慮的相親對(duì)象
先看一下gbdt訓(xùn)練的結(jié)果 mlt dating.txt -cl gbdt -ntree 2 -nl 3 -lr 0.1 -mil 1 -c train -vl 1 -mjson=1 設(shè)置2棵樹(shù)，葉子節(jié)點(diǎn)最多3個(gè) 也就是最多2次分裂，learning rate設(shè)置為0.1， 葉子節(jié)點(diǎn)中的最少樣本數(shù)設(shè)置為1（僅供試驗(yàn)，一般不會(huì)設(shè)置為1，避免過(guò)擬合) 為了打印二叉樹(shù)設(shè)置輸出json格式的模型
Per feature gain: 0:face 1 1:hight 0.730992 2:money 0.706716 Sigmoid/PlattCalibrator calibrating [ 8 ] (0.00011 s)100% |******************************************| I0324 16:57:53.240083 17630 time_util.h:113] Train! finished using: [1.486 ms] (0.001486 s) I0324 16:57:53.240094 17630 time_util.h:102] Test itself! started
TEST POSITIVE RATIO: 0.5000 (4/(4+4))
Confusion table: ||===============================|| || PREDICTED || TRUTH || positive | negative || RECALL ||===============================|| positive|| 4 | 0 || 1.0000 (4/4) negative|| 0 | 4 || 1.0000 (4/4) ||===============================|| PRECISION 1.0000 (4/4) 1.0000(4/4) LOG LOSS/instance: 0.2981 TEST-SET ENTROPY (prior LL/in): 1.0000 LOG-LOSS REDUCTION (RIG): 70.1854%
OVERALL 0/1 ACCURACY: 1.0000 (8/8) POS.PRECISION: 1.0000 PPOS.RECALL: 1.0000 NEG.PRECISION: 1.0000 NEG.RECALL: 1.0000 F1.SCORE: 1.0000 AUC: [1.0000]
對(duì)應(yīng)這個(gè)例子，訓(xùn)練結(jié)果是perfect的，全部正確， 特征權(quán)重可以看出，對(duì)應(yīng)這個(gè)例子訓(xùn)練結(jié)果顏值的重要度最大，看一下訓(xùn)練得到的樹(shù)。 print-gbdt-tree.py --tree -1 Tree 0:
Tree 1:
GBDT原理實(shí)例演示 2
一開(kāi)始我們?cè)O(shè)定F(x)也就是每個(gè)樣本的預(yù)測(cè)值是0(也可以做一定的隨機(jī)化) Scores = { 0， 0， 0， 0， 0， 0， 0， 0}
那么我們先計(jì)算當(dāng)前情況下的梯度值
GetGradientInOneQuery = [this](int query, const Fvec& scores) { //和實(shí)際代碼稍有出入 簡(jiǎn)化版本 _gradient[query] = ((2.0 * label) * sigmoidParam) / (1.0 + std::exp(((2.0 * label) * sigmoidParam) * scores[query])); };
考慮 0號(hào)樣本 label是1 , learningRate也就是sigmoidParam設(shè)置為0.1, scores[query] = 0 當(dāng)前Scores全是0 2 * 1 * 0.1 / (1 + exp(2 * 1 * 0.1 * 0)) = 0.1 考慮 7號(hào)樣本 label是-1 2 * -1 * 0.1 / (1 + exp(2 * -1 * 0.1 * 0）) = -0.1
因此當(dāng)前計(jì)算的梯度值是 Gradient = { 0.1， 0.1， 0.1， 0.1， -0.1， -0.1， -0.1， -0.1}
于是我們要當(dāng)前樹(shù)的輸出F(x)擬合的targets就是這個(gè)Grandient Targets = { 0.1， 0.1， 0.1， 0.1， -0.1， -0.1， -0.1， -0.1} RegressionTree tree = TreeLearner->FitTargets(activeFeatures, AdjustTargetsAndSetWeights());
virtual RegressionTree FitTargets(BitArray& activeFeatures, Fvec& targets) override
現(xiàn)在我們考慮擬合這個(gè)梯度 gdb ./test_fastrank_train (gdb) r -in dating.txt -cl gbdt -ntree 2 -nl 3 -lr 0.1 -mil 1 -c train -vl 1 -mjson=1 p Partitioning $3 = {_documents = std::vector of length 8, capacity 8 = {0, 1, 2, 3, 4, 5, 6, 7}, _initialDocuments = std::vector of length 0, capacity 0, _leafBegin = std::vector of length 3, capacity 3 = {0, 0, 0}, _leafCount = std::vector of length 3, capacity 3 = {8, 0, 0}, _tempDocuments = std::vector of length 0, capacity 0}
gbdt對(duì)應(yīng)每個(gè)特征要做離散化分桶處理，比如分255個(gè)桶，這里樣本數(shù)據(jù)比較少，對(duì)應(yīng)height特征， 20, 60, 3, 66, 30, 20, 15, 10 分桶也就是變成 BinMedians = std::vector of length 7, capacity 7 = {3, 10, 15, 20, 30, 60, 66} p *Feature $11 = {_vptr.Feature = 0xce8650 <vtable for gezi::Feature+16>, Name = "hight", BinUpperBounds = std::vector of length 7, capacity 7 = {6.5, 12.5, 17.5, 25, 45, 63, 1.7976931348623157e+308}, BinMedians = std::vector of length 7, capacity 7 = {3, 10, 15, 20, 30, 60, 66}, Bins = {_vptr.TVector = 0xce8670 <vtable for gezi::TVector<int>+16>, indices = std::vector of length 0, capacity 0, values = std::vector of length 8, capacity 8 = {3, 5, 0, 6, 4, 3, 2, 1}, sparsityRatio = 0.29999999999999999, keepDense = false, keepSparse = false, normalized = false, numNonZeros = 7, length = 8, _zeroValue = 0}, Trust = 1}
Bins對(duì)應(yīng)分桶的結(jié)果，比如_0樣本hight 20，那么分桶結(jié)果是編號(hào)3的桶(0開(kāi)始index)
考慮Root節(jié)點(diǎn)的分裂，分裂前考慮是8個(gè)樣本在一個(gè)節(jié)點(diǎn)，我們選取一個(gè)最佳的特征，以及對(duì)應(yīng)該特征最佳的分裂點(diǎn) 考慮hight特征，我們要掃描所有可能的分裂點(diǎn) 這里也就是說(shuō) 考慮6個(gè)不同的分裂點(diǎn) for (int t = 0; t < (histogram.NumFeatureValues - 1); t += 1)
比如6.5這個(gè)分裂點(diǎn) 那么 就是左子樹(shù) 1個(gè)(_2樣本)， 右子樹(shù)7個(gè)，考慮下面公式 收益是 0.1^2/1 + (-0.1)^2/7 - CONSTANT = 0.01142857142857143 - CONSTANT
類(lèi)似的考慮分裂點(diǎn)12.5,17.5……….. 選取一個(gè)最佳分裂點(diǎn)
然后同樣的考慮 money, face 特征 選取最優(yōu)(特征，分裂點(diǎn)）組合， 這里最優(yōu)組合是(hight, 45)
左側(cè)得到
_0,_2,_4,_5,_6, _7 -> 0.1 + 0.1 - 0.1 - 0.1 - 0.1 -0.1
右側(cè)得到 _1,_3 -> 0.1 + 0.1 收益是 (-0.2)^2 /6 + (0.2)^2 / 2 - CONSTANT = 0.026666666666666665 - CONSTANT (gdb) p bestShiftedGain $22 = 0.026666666666666675
對(duì)應(yīng)>的子樹(shù)輸出應(yīng)該是 0.2 / 2 = 0.1 下圖對(duì)應(yīng)展示output是1，因?yàn)楹罄m(xù)還有AdjustOutput，因?yàn)橹辽傩枰?/span> F_m(x) = F_m-1(x) + learning_rate*(當(dāng)前樹(shù)的預(yù)測(cè)值(也就是預(yù)測(cè)負(fù)梯度..)) 黃色部分是最終該棵樹(shù)的輸出值
之后再選取兩個(gè)分裂后的組 選一個(gè)最佳(特征，分裂)組合 -> (face, 57.5)
(gdb) p tree $26 = {<gezi::OnlineRegressionTree> = {NumLeaves = 3, _gainPValue = std::vector of length 2, capacity 2 = {0.15304198078836101, 0.27523360741160119}, _lteChild = std::vector of length 2, capacity 2 = {1, -1}, _gtChild = std::vector of length 2, capacity 2 = {-2, -3}, _leafValue = std::vector of length 3, capacity 3 = {-0.10000000000000002, 0.10000000000000002, 0.033333333333333347}, _threshold = std::vector of length 2, capacity 2 = {4, 2}, _splitFeature = std::vector of length 2, capacity 2 = {0, 2}, _splitGain = std::vector of length 2, capacity 2 = {0.026666666666666675, 0.026666666666666679}, _maxOutput = 0.10000000000000002, _previousLeafValue = std::vector of length 2, capacity 2 = {0, -0.033333333333333333}, _weight = 1, _featureNames = 0x6e6a5a <gezi::FastRank::GetActiveFeatures(std::vector<bool, std::allocator<bool> >&)+34>}, _parent = std::vector of length 3, capacity 3 = {1, -1, -2}}
調(diào)整一下Output //GradientDecent.h virtual RegressionTree& TrainingIteration(BitArray& activeFeatures) override { RegressionTree tree = TreeLearner->FitTargets(activeFeatures, AdjustTargetsAndSetWeights()); if (AdjustTreeOutputsOverride == nullptr) { //如果父類(lèi)ObjectiveFunction里面沒(méi)有虛函數(shù) 不能使用dynamic_pointer_cast... @TODO (dynamic_pointer_cast<IStepSearch>(ObjectiveFunction))->AdjustTreeOutputs(tree, TreeLearner->Partitioning, *TrainingScores); } { UpdateAllScores(tree); } Ensemble.AddTree(tree); return Ensemble.Tree(); }
virtual void AdjustTreeOutputs(RegressionTree& tree, DocumentPartitioning& partitioning, ScoreTracker& trainingScores) override { //AutoTimer timer("dynamic_pointer_cast<IStepSearch>(ObjectiveFunction))->AdjustTreeOutputs"); for (int l = 0; l < tree.NumLeaves; l++) { Float output = 0.0; if (_bestStepRankingRegressionTrees) { * tree.GetOutput(l); } else { //現(xiàn)在走這里 * (tree.GetOutput(l) + 1.4E-45)) / (partitioning.Mean(_weights, Dataset.SampleWeights, l, false) + 1.4E-45); } if (output > _maxTreeOutput) { output = _maxTreeOutput; } else if (output < -_maxTreeOutput) { output = -_maxTreeOutput; } tree.SetOutput(l, output); } }
(gdb) p _weights $33 = std::vector of length 8, capacity 8 = {0.010000000000000002, 0.010000000000000002, 0.010000000000000002, 0.010000000000000002, 0.010000000000000002, 0.010000000000000002, 0.010000000000000002, 0.010000000000000002}
_learningRate * tree.Getoutput(1) / partioning.Mean(_weights..) = 0.1 * 0.1 / 0.01 = 1
(gdb) p tree $35 = (gezi::RegressionTree &) @0x7fffffffd480: {<gezi::OnlineRegressionTree> = { NumLeaves = 3, _gainPValue = std::vector of length 2, capacity 2 = {0.15304198078836101, 0.27523360741160119}, _lteChild = std::vector of length 2, capacity 2 = {1, -1}, _gtChild = std::vector of length 2, capacity 2 = {-2, -3}, _leafValue = std::vector of length 3, capacity 3 = {-1, 1, 0.33333333333333343}, _threshold = std::vector of length 2, capacity 2 = {4, 2}, _splitFeature = std::vector of length 2, capacity 2 = {0, 2}, _splitGain = std::vector of length 2, capacity 2 = {0.026666666666666675, 0.026666666666666679}, _maxOutput = 0.10000000000000002, _previousLeafValue = std::vector of length 2, capacity 2 = {0, -0.033333333333333333}, _weight = 1, _featureNames = 0x6e6a5a <gezi::FastRank::GetActiveFeatures(std::vector<bool, std::allocator<bool> >&)+34>}, _parent = std::vector of length 3, capacity 3 = {1, -1, -2}}
之后UpdateAllScores(tree); 是用來(lái)更新scores的值，這里就是8個(gè)樣本對(duì)應(yīng)的scores值，也就是計(jì)算F(x)，注意多棵樹(shù)則是對(duì)應(yīng)記錄多棵樹(shù)的輸出的值累加。 virtual void AddScores(RegressionTree& tree, DocumentPartitioning& partitioning, Float multiplier = 1) { for (int l = 0; l < tree.NumLeaves; l++) { int begin; int count; ivec& documents = partitioning.ReferenceLeafDocuments(l, begin, count); Float output = tree.LeafValue(l) * multiplier; int end = begin + count; #pragma omp parallel for for (int i = begin; i < end; i++) { Scores[documents[i]] += output; } SendScoresUpdatedMessage(); }
對(duì)應(yīng)第一個(gè)棵樹(shù)生成結(jié)束后
(gdb) p Scores $7 = std::vector of length 8, capacity 8 = {0.33333333333333343, 1, 0.33333333333333343, 1, -1, -1, 0.33333333333333343, -1}
這個(gè)時(shí)候再對(duì)應(yīng)計(jì)算梯度： for (int query = 0; query < Dataset.NumDocs; query++) { GetGradientInOneQuery(query, scores); }
_gradient[0] = 2 * 1 * 0.1 / (1 + exp(2 * 1 * 0.1 * 0.33333333333333343)) : 0.2/(1.0 + math.exp(2*0.1/3)) Out[2]: 0.09666790068611772
這時(shí)候 我們需要擬合的梯度變?yōu)?/span> (gdb) p _gradient $9 = std::vector of length 8, capacity 8 = {0.096667900686117719, 0.090033200537504438, 0.096667900686117719, 0.090033200537504438, -0.090033200537504438, -0.090033200537504438, -0.10333209931388229, -0.090033200537504438}
第二棵樹(shù) p tree $10 = {<gezi::OnlineRegressionTree> = {NumLeaves = 3, _gainPValue = std::vector of length 2, capacity 2 = {0.13944890100441296, 0.02357537149418417}, _lteChild = std::vector of length 2, capacity 2 = {-1, -2}, _gtChild = std::vector of length 2, capacity 2 = {1, -3}, _leafValue = std::vector of length 3, capacity 3 = {-0.9721949587186075, -0.30312179217966367, 0.94840573799486361}, _threshold = std::vector of length 2, capacity 2 = {1, 1}, _splitFeature = std::vector of length 2, capacity 2 = {1, 2}, _splitGain = std::vector of length 2, capacity 2 = {0.024924858166579064, 0.023238200798742146}, _maxOutput = 0.094456333969913306, _previousLeafValue = std::vector of length 2, capacity 2 = {0, 0.032222633562039242}, _weight = 1, _featureNames = 0x6e6a5a <gezi::FastRank::GetActiveFeatures(std::vector<bool, std::allocator<bool> >&)+34>}, _parent = std::vector of length 3, capacity 3 = {0, 1, -2}}
累加第二棵樹(shù)后的Scores，如果有第三棵樹(shù)，那么在這個(gè)Scores的基礎(chǔ)上再計(jì)算梯度值 (gdb) p Scores $11 = std::vector of length 8, capacity 8 = {1.2817390713281971, 0.69687820782033638, 1.2817390713281971, 1.9484057379948636, -1.3031217921796636, -1.9721949587186076, -0.63886162538527413, -1.3031217921796636} GBDT（MART） 迭代決策樹(shù)入門(mén)及源碼解析GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一種迭代的決策樹(shù)算法，該算法由多棵決策樹(shù)組成，所有樹(shù)的結(jié)論累加起來(lái)做最終答案。它在被提出之初就和SVM一起被認(rèn)為是泛化能力（generalization)較強(qiáng)的算法。近些年更因?yàn)楸挥糜谒阉髋判虻臋C(jī)器學(xué)習(xí)模型而引起大家關(guān)注。
GBDT主要由三個(gè)概念組成：Regression Decistion Tree（即DT)，Gradient Boosting（即GB)，Shrinkage (算法的一個(gè)重要演進(jìn)分枝，目前大部分源碼都按該版本實(shí)現(xiàn)）。搞定這三個(gè)概念后就能明白GBDT是如何工作的，要繼續(xù)理解它如何用于搜索排序則需要額外理解RankNet概念，之后便功德圓滿(mǎn)。下文將逐個(gè)碎片介紹，最終把整張圖拼出來(lái)。
一、 DT：回歸樹(shù) Regression Decision Tree 提起決策樹(shù)（DT, Decision Tree) 絕大部分人首先想到的就是C4.5分類(lèi)決策樹(shù)。但如果一開(kāi)始就把GBDT中的樹(shù)想成分類(lèi)樹(shù)，那就是一條歪路走到黑，一路各種坑，最終摔得都要咯血了還是一頭霧水說(shuō)的就是LZ自己啊有木有?？揉?，所以說(shuō)千萬(wàn)不要以為GBDT是很多棵分類(lèi)樹(shù)。決策樹(shù)分為兩大類(lèi)，回歸樹(shù)和分類(lèi)樹(shù)。前者用于預(yù)測(cè)實(shí)數(shù)值，如明天的溫度、用戶(hù)的年齡、網(wǎng)頁(yè)的相關(guān)程度；后者用于分類(lèi)標(biāo)簽值，如晴天/陰天/霧/雨、用戶(hù)性別、網(wǎng)頁(yè)是否是垃圾頁(yè)面。這里要強(qiáng)調(diào)的是，前者的結(jié)果加減是有意義的，如10歲+5歲-3歲=12歲，后者則無(wú)意義，如男+男+女=到底是男是女？ GBDT的核心在于累加所有樹(shù)的結(jié)果作為最終結(jié)果，就像前面對(duì)年齡的累加（-3是加負(fù)3），而分類(lèi)樹(shù)的結(jié)果顯然是沒(méi)辦法累加的，所以GBDT中的樹(shù)都是回歸樹(shù)，不是分類(lèi)樹(shù)，這點(diǎn)對(duì)理解GBDT相當(dāng)重要（盡管GBDT調(diào)整后也可用于分類(lèi)但不代表GBDT的樹(shù)是分類(lèi)樹(shù)）。那么回歸樹(shù)是如何工作的呢？
下面我們以對(duì)人的性別判別/年齡預(yù)測(cè)為例來(lái)說(shuō)明，每個(gè)instance都是一個(gè)我們已知性別/年齡的人，而feature則包括這個(gè)人上網(wǎng)的時(shí)長(zhǎng)、上網(wǎng)的時(shí)段、網(wǎng)購(gòu)所花的金額等。
作為對(duì)比，先說(shuō)分類(lèi)樹(shù)，我們知道C4.5分類(lèi)樹(shù)在每次分枝時(shí)，是窮舉每一個(gè)feature的每一個(gè)閾值，找到使得按照f(shuō)eature<=閾值，和feature>閾值分成的兩個(gè)分枝的熵最大的feature和閾值（熵最大的概念可理解成盡可能每個(gè)分枝的男女比例都遠(yuǎn)離1:1），按照該標(biāo)準(zhǔn)分枝得到兩個(gè)新節(jié)點(diǎn)，用同樣方法繼續(xù)分枝直到所有人都被分入性別唯一的葉子節(jié)點(diǎn)，或達(dá)到預(yù)設(shè)的終止條件，若最終葉子節(jié)點(diǎn)中的性別不唯一，則以多數(shù)人的性別作為該葉子節(jié)點(diǎn)的性別。
回歸樹(shù)總體流程也是類(lèi)似，不過(guò)在每個(gè)節(jié)點(diǎn)（不一定是葉子節(jié)點(diǎn)）都會(huì)得一個(gè)預(yù)測(cè)值，以年齡為例，該預(yù)測(cè)值等于屬于這個(gè)節(jié)點(diǎn)的所有人年齡的平均值。分枝時(shí)窮舉每一個(gè)feature的每個(gè)閾值找最好的分割點(diǎn)，但衡量最好的標(biāo)準(zhǔn)不再是最大熵，而是最小化均方差--即（每個(gè)人的年齡-預(yù)測(cè)年齡）^2 的總和 / N，或者說(shuō)是每個(gè)人的預(yù)測(cè)誤差平方和 除以 N。這很好理解，被預(yù)測(cè)出錯(cuò)的人數(shù)越多，錯(cuò)的越離譜，均方差就越大，通過(guò)最小化均方差能夠找到最靠譜的分枝依據(jù)。分枝直到每個(gè)葉子節(jié)點(diǎn)上人的年齡都唯一（這太難了）或者達(dá)到預(yù)設(shè)的終止條件（如葉子個(gè)數(shù)上限），若最終葉子節(jié)點(diǎn)上人的年齡不唯一，則以該節(jié)點(diǎn)上所有人的平均年齡做為該葉子節(jié)點(diǎn)的預(yù)測(cè)年齡。若還不明白可以Google "Regression Tree"。
二、 GB：梯度迭代 Gradient Boosting 好吧，我起了一個(gè)很大的標(biāo)題，但事實(shí)上我并不想多講Gradient Boosting的原理，因?yàn)椴幻靼自聿o(wú)礙于理解GBDT中的Gradient Boosting。喜歡打破砂鍋問(wèn)到底的同學(xué)可以閱讀這篇英文wikihttp://en./wiki/Gradient_boosted_trees#Gradient_tree_boosting
Boosting，迭代，即通過(guò)迭代多棵樹(shù)來(lái)共同決策。這怎么實(shí)現(xiàn)呢？難道是每棵樹(shù)獨(dú)立訓(xùn)練一遍，比如A這個(gè)人，第一棵樹(shù)認(rèn)為是10歲，第二棵樹(shù)認(rèn)為是0歲，第三棵樹(shù)認(rèn)為是20歲，我們就取平均值10歲做最終結(jié)論？--當(dāng)然不是！且不說(shuō)這是投票方法并不是GBDT，只要訓(xùn)練集不變，獨(dú)立訓(xùn)練三次的三棵樹(shù)必定完全相同，這樣做完全沒(méi)有意義。之前說(shuō)過(guò)，GBDT是把所有樹(shù)的結(jié)論累加起來(lái)做最終結(jié)論的，所以可以想到每棵樹(shù)的結(jié)論并不是年齡本身，而是年齡的一個(gè)累加量。GBDT的核心就在于，每一棵樹(shù)學(xué)的是之前所有樹(shù)結(jié)論和的殘差，這個(gè)殘差就是一個(gè)加預(yù)測(cè)值后能得真實(shí)值的累加量。比如A的真實(shí)年齡是18歲，但第一棵樹(shù)的預(yù)測(cè)年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹(shù)里我們把A的年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹(shù)真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹(shù)的結(jié)論就是A的真實(shí)年齡；如果第二棵樹(shù)的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹(shù)里A的年齡就變成1歲，繼續(xù)學(xué)。這就是Gradient Boosting在GBDT中的意義，簡(jiǎn)單吧。
三、 GBDT工作過(guò)程實(shí)例。 還是年齡預(yù)測(cè)，簡(jiǎn)單起見(jiàn)訓(xùn)練集只有4個(gè)人，A,B,C,D，他們的年齡分別是14,16,24,26。其中A、B分別是高一和高三學(xué)生；C,D分別是應(yīng)屆畢業(yè)生和工作兩年的員工。如果是用一棵傳統(tǒng)的回歸決策樹(shù)來(lái)訓(xùn)練，會(huì)得到如下圖1所示結(jié)果：
現(xiàn)在我們使用GBDT來(lái)做這件事，由于數(shù)據(jù)太少，我們限定葉子節(jié)點(diǎn)做多有兩個(gè)，即每棵樹(shù)都只有一個(gè)分枝，并且限定只學(xué)兩棵樹(shù)。我們會(huì)得到如下圖2所示結(jié)果：
在第一棵樹(shù)分枝和圖1一樣，由于A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預(yù)測(cè)值。此時(shí)計(jì)算殘差（殘差的意思就是： A的預(yù)測(cè)值 + A的殘差 = A的實(shí)際值），所以A的殘差就是16-15=1（注意，A的預(yù)測(cè)值是指前面所有樹(shù)累加的和，這里前面只有一棵樹(shù)所以直接是15，如果還有樹(shù)則需要都累加起來(lái)作為A的預(yù)測(cè)值）。進(jìn)而得到A,B,C,D的殘差分別為-1,1，-1,1。然后我們拿殘差替代A,B,C,D的原值，到第二棵樹(shù)去學(xué)習(xí)，如果我們的預(yù)測(cè)值和它們的殘差相等，則只需把第二棵樹(shù)的結(jié)論累加到第一棵樹(shù)上就能得到真實(shí)年齡了。這里的數(shù)據(jù)顯然是我可以做的，第二棵樹(shù)只有兩個(gè)值1和-1，直接分成兩個(gè)節(jié)點(diǎn)。此時(shí)所有人的殘差都是0，即每個(gè)人都得到了真實(shí)的預(yù)測(cè)值。
換句話(huà)說(shuō)，現(xiàn)在A,B,C,D的預(yù)測(cè)值都和真實(shí)年齡一致了。Perfect!： A: 14歲高一學(xué)生，購(gòu)物較少，經(jīng)常問(wèn)學(xué)長(zhǎng)問(wèn)題；預(yù)測(cè)年齡A = 15 – 1 = 14 B: 16歲高三學(xué)生；購(gòu)物較少，經(jīng)常被學(xué)弟問(wèn)問(wèn)題；預(yù)測(cè)年齡B = 15 + 1 = 16 C: 24歲應(yīng)屆畢業(yè)生；購(gòu)物較多，經(jīng)常問(wèn)師兄問(wèn)題；預(yù)測(cè)年齡C = 25 – 1 = 24 D: 26歲工作兩年員工；購(gòu)物較多，經(jīng)常被師弟問(wèn)問(wèn)題；預(yù)測(cè)年齡D = 25 + 1 = 26
那么哪里體現(xiàn)了Gradient呢？其實(shí)回到第一棵樹(shù)結(jié)束時(shí)想一想，無(wú)論此時(shí)的cost function是什么，是均方差還是均差，只要它以誤差作為衡量標(biāo)準(zhǔn)，殘差向量(-1, 1, -1, 1)都是它的全局最優(yōu)方向，這就是Gradient。
講到這里我們已經(jīng)把GBDT最核心的概念、運(yùn)算過(guò)程講完了！沒(méi)錯(cuò)就是這么簡(jiǎn)單。不過(guò)講到這里很容易發(fā)現(xiàn)三個(gè)問(wèn)題：
1）既然圖1和圖2 最終效果相同，為何還需要GBDT呢？ 答案是過(guò)擬合。過(guò)擬合是指為了讓訓(xùn)練集精度更高，學(xué)到了很多”僅在訓(xùn)練集上成立的規(guī)律“，導(dǎo)致?lián)Q一個(gè)數(shù)據(jù)集當(dāng)前規(guī)律就不適用了。其實(shí)只要允許一棵樹(shù)的葉子節(jié)點(diǎn)足夠多，訓(xùn)練集總是能訓(xùn)練到100%準(zhǔn)確率的（大不了最后一個(gè)葉子上只有一個(gè)instance)。在訓(xùn)練精度和實(shí)際精度（或測(cè)試精度）之間，后者才是我們想要真正得到的。
我們發(fā)現(xiàn)圖1為了達(dá)到100%精度使用了3個(gè)feature（上網(wǎng)時(shí)長(zhǎng)、時(shí)段、網(wǎng)購(gòu)金額），其中分枝“上網(wǎng)時(shí)長(zhǎng)>1.1h” 很顯然已經(jīng)過(guò)擬合了，這個(gè)數(shù)據(jù)集上A,B也許恰好A每天上網(wǎng)1.09h, B上網(wǎng)1.05小時(shí)，但用上網(wǎng)時(shí)間是不是>1.1小時(shí)來(lái)判斷所有人的年齡很顯然是有悖常識(shí)的；
相對(duì)來(lái)說(shuō)圖2的boosting雖然用了兩棵樹(shù) ，但其實(shí)只用了2個(gè)feature就搞定了，后一個(gè)feature是問(wèn)答比例，顯然圖2的依據(jù)更靠譜。（當(dāng)然，這里是LZ故意做的數(shù)據(jù)，所以才能靠譜得如此狗血。實(shí)際中靠譜不靠譜總是相對(duì)的） Boosting的最大好處在于，每一步的殘差計(jì)算其實(shí)變相地增大了分錯(cuò)instance的權(quán)重，而已經(jīng)分對(duì)的instance則都趨向于0。這樣后面的樹(shù)就能越來(lái)越專(zhuān)注那些前面被分錯(cuò)的instance。就像我們做互聯(lián)網(wǎng)，總是先解決60%用戶(hù)的需求湊合著，再解決35%用戶(hù)的需求，最后才關(guān)注那5%人的需求，這樣就能逐漸把產(chǎn)品做好，因?yàn)椴煌?lèi)型用戶(hù)需求可能完全不同，需要分別獨(dú)立分析。如果反過(guò)來(lái)做，或者剛上來(lái)就一定要做到盡善盡美，往往最終會(huì)竹籃打水一場(chǎng)空。
2）Gradient呢？不是“G”BDT么？ 到目前為止，我們的確沒(méi)有用到求導(dǎo)的Gradient。在當(dāng)前版本GBDT描述中，的確沒(méi)有用到Gradient，該版本用殘差作為全局最優(yōu)的絕對(duì)方向，并不需要Gradient求解.
3）這不是boosting吧？Adaboost可不是這么定義的。 這是boosting，但不是Adaboost。GBDT不是Adaboost Decistion Tree。就像提到?jīng)Q策樹(shù)大家會(huì)想起C4.5，提到boost多數(shù)人也會(huì)想到Adaboost。Adaboost是另一種boost方法，它按分類(lèi)對(duì)錯(cuò)，分配不同的weight，計(jì)算cost function時(shí)使用這些weight，從而讓“錯(cuò)分的樣本權(quán)重越來(lái)越大，使它們更被重視”。Bootstrap也有類(lèi)似思想，它在每一步迭代時(shí)不改變模型本身，也不計(jì)算殘差，而是從N個(gè)instance訓(xùn)練集中按一定概率重新抽取N個(gè)instance出來(lái)（單個(gè)instance可以被重復(fù)sample），對(duì)著這N個(gè)新的instance再訓(xùn)練一輪。由于數(shù)據(jù)集變了迭代模型訓(xùn)練結(jié)果也不一樣，而一個(gè)instance被前面分錯(cuò)的越厲害，它的概率就被設(shè)的越高，這樣就能同樣達(dá)到逐步關(guān)注被分錯(cuò)的instance，逐步完善的效果。Adaboost的方法被實(shí)踐證明是一種很好的防止過(guò)擬合的方法，但至于為什么則至今沒(méi)從理論上被證明。GBDT也可以在使用殘差的同時(shí)引入Bootstrap re-sampling，GBDT多數(shù)實(shí)現(xiàn)版本中也增加的這個(gè)選項(xiàng)，但是否一定使用則有不同看法。re-sampling一個(gè)缺點(diǎn)是它的隨機(jī)性，即同樣的數(shù)據(jù)集合訓(xùn)練兩遍結(jié)果是不一樣的，也就是模型不可穩(wěn)定復(fù)現(xiàn)，這對(duì)評(píng)估是很大挑戰(zhàn)，比如很難說(shuō)一個(gè)模型變好是因?yàn)槟氵x用了更好的feature，還是由于這次sample的隨機(jī)因素。
四、Shrinkage Shrinkage（縮減）的思想認(rèn)為，每次走一小步逐漸逼近結(jié)果的效果，要比每次邁一大步很快逼近結(jié)果的方式更容易避免過(guò)擬合。即它不完全信任每一個(gè)棵殘差樹(shù)，它認(rèn)為每棵樹(shù)只學(xué)到了真理的一小部分，累加的時(shí)候只累加一小部分，通過(guò)多學(xué)幾棵樹(shù)彌補(bǔ)不足。用方程來(lái)看更清晰，即 沒(méi)用Shrinkage時(shí)：（yi表示第i棵樹(shù)上y的預(yù)測(cè)值， y(1~i)表示前i棵樹(shù)y的綜合預(yù)測(cè)值） y(i+1) = 殘差(y1~yi)， 其中： 殘差(y1~yi) = y真實(shí)值 - y(1 ~ i) y(1 ~ i) = SUM(y1, ..., yi) Shrinkage不改變第一個(gè)方程，只把第二個(gè)方程改為： y(1 ~ i) = y(1 ~ i-1) + step * yi
即Shrinkage仍然以殘差作為學(xué)習(xí)目標(biāo)，但對(duì)于殘差學(xué)習(xí)出來(lái)的結(jié)果，只累加一小部分（step*殘差）逐步逼近目標(biāo)，step一般都比較小，如0.01~0.001（注意該step非gradient的step），導(dǎo)致各個(gè)樹(shù)的殘差是漸變的而不是陡變的。直覺(jué)上這也很好理解，不像直接用殘差一步修復(fù)誤差，而是只修復(fù)一點(diǎn)點(diǎn)，其實(shí)就是把大步切成了很多小步。本質(zhì)上，Shrinkage為每棵樹(shù)設(shè)置了一個(gè)weight，累加時(shí)要乘以這個(gè)weight，但和Gradient并沒(méi)有關(guān)系。這個(gè)weight就是step。就像Adaboost一樣，Shrinkage能減少過(guò)擬合發(fā)生也是經(jīng)驗(yàn)證明的，目前還沒(méi)有看到從理論的證明。
五、 GBDT的適用范圍 該版本GBDT幾乎可用于所有回歸問(wèn)題（線(xiàn)性/非線(xiàn)性），相對(duì)logistic regression僅能用于線(xiàn)性回歸，GBDT的適用面非常廣。亦可用于二分類(lèi)問(wèn)題（設(shè)定閾值，大于閾值為正例，反之為負(fù)例）。
六、 搜索引擎排序應(yīng)用 RankNet 搜索排序關(guān)注各個(gè)doc的順序而不是絕對(duì)值，所以需要一個(gè)新的cost function，而RankNet基本就是在定義這個(gè)cost function，它可以兼容不同的算法（GBDT、神經(jīng)網(wǎng)絡(luò)...）。
實(shí)際的搜索排序使用的是LambdaMART算法，必須指出的是由于這里要使用排序需要的cost function，LambdaMART迭代用的并不是殘差。Lambda在這里充當(dāng)替代殘差的計(jì)算方法，它使用了一種類(lèi)似Gradient*步長(zhǎng)模擬殘差的方法。
就像所有的機(jī)器學(xué)習(xí)一樣，搜索排序的學(xué)習(xí)也需要訓(xùn)練集，這里一般是用人工標(biāo)注實(shí)現(xiàn)，即對(duì)每一個(gè)(query,doc) pair給定一個(gè)分值（如1,2,3,4）,分值越高表示越相關(guān)，越應(yīng)該排到前面。然而這些絕對(duì)的分值本身意義不大，例如你很難說(shuō)1分和2分文檔的相關(guān)程度差異是1分和3分文檔差距的一半。相關(guān)度本身就是一個(gè)很主觀的評(píng)判，標(biāo)注人員無(wú)法做到這種定量標(biāo)注，這種標(biāo)準(zhǔn)也無(wú)法制定。但標(biāo)注人員很容易做到的是”AB都不錯(cuò)，但文檔A比文檔B更相關(guān)，所以A是4分，B是3分“。RankNet就是基于此制定了一個(gè)學(xué)習(xí)誤差衡量方法，即cost function。具體而言，RankNet對(duì)任意兩個(gè)文檔A,B，通過(guò)它們的人工標(biāo)注分差，用sigmoid函數(shù)估計(jì)兩者順序和逆序的概率P1。然后同理用機(jī)器學(xué)習(xí)到的分差計(jì)算概率P2（sigmoid的好處在于它允許機(jī)器學(xué)習(xí)得到的分值是任意實(shí)數(shù)值，只要它們的分差和標(biāo)準(zhǔn)分的分差一致，P2就趨近于P1）。這時(shí)利用P1和P2求的兩者的交叉熵，該交叉熵就是cost function。它越低說(shuō)明機(jī)器學(xué)得的當(dāng)前排序越趨近于標(biāo)注排序。為了體現(xiàn)NDCG的作用（NDCG是搜索排序業(yè)界最常用的評(píng)判標(biāo)準(zhǔn)），RankNet還在cost function中乘以了NDCG。
好，現(xiàn)在我們有了cost function，而且它是和各個(gè)文檔的當(dāng)前分值yi相關(guān)的，那么雖然我們不知道它的全局最優(yōu)方向，但可以求導(dǎo)求Gradient，Gradient即每個(gè)文檔得分的一個(gè)下降方向組成的N維向量，N為文檔個(gè)數(shù)（應(yīng)該說(shuō)是query-doc pair個(gè)數(shù)）。這里僅僅是把”求殘差“的邏輯替換為”求梯度“，可以這樣想：梯度方向?yàn)槊恳徊阶顑?yōu)方向，累加的步數(shù)多了，總能走到局部最優(yōu)點(diǎn)，若該點(diǎn)恰好為全局最優(yōu)點(diǎn)，那和用殘差的效果是一樣的。這時(shí)套到之前講的邏輯，GDBT就已經(jīng)可以上了。那么最終排序怎么產(chǎn)生呢？很簡(jiǎn)單，每個(gè)樣本通過(guò)Shrinkage累加都會(huì)得到一個(gè)最終得分，直接按分?jǐn)?shù)從大到小排序就可以了（因?yàn)闄C(jī)器學(xué)習(xí)產(chǎn)生的是實(shí)數(shù)域的預(yù)測(cè)分，極少會(huì)出現(xiàn)在人工標(biāo)注中常見(jiàn)的兩文檔分?jǐn)?shù)相等的情況，幾乎不同考慮同分文檔的排序方式）
另外，如果feature個(gè)數(shù)太多，每一棵回歸樹(shù)都要耗費(fèi)大量時(shí)間，這時(shí)每個(gè)分支時(shí)可以隨機(jī)抽一部分feature來(lái)遍歷求最優(yōu)。
GBDT源碼剖析
如今，GBDT被廣泛運(yùn)用于互聯(lián)網(wǎng)行業(yè)，他的原理與優(yōu)點(diǎn)這里就不細(xì)說(shuō)了，網(wǎng)上google一大把。但是，我自認(rèn)為自己不是一個(gè)理論牛人，對(duì)GBDT的理論理解之后也做不到從理論舉一反三得到更深入的結(jié)果。但是學(xué)習(xí)一個(gè)算法，務(wù)必要深入細(xì)致才能領(lǐng)會(huì)到這個(gè)算法的精髓。因此，在了解了足夠的GBDT理論之后，就需要通過(guò)去閱讀其源碼來(lái)深入學(xué)習(xí)GBDT了。但是，網(wǎng)上有關(guān)這類(lèi)資料甚少，因此，我不得不自己親自抄刀，索性自己從頭學(xué)習(xí)了一下GBDT源碼。幸好，這個(gè)算法在機(jī)器學(xué)習(xí)領(lǐng)域中的其它算法還是非常簡(jiǎn)單的。這里將心得簡(jiǎn)單分享，歡迎指正?；貜?fù)本公眾號(hào)“GBDT”可下載源碼。
首先，這里需要介紹一下程序中用到的結(jié)構(gòu)體，具體的每一個(gè)結(jié)構(gòu)體的內(nèi)容這里就不再贅述了，源碼里面都有。這里只再細(xì)說(shuō)一下每個(gè)結(jié)構(gòu)體的作用，當(dāng)然一些重要的結(jié)構(gòu)體會(huì)詳細(xì)解釋。 struct gbdt_model_t:GBDT模型的結(jié)構(gòu)體，也就是最終我們訓(xùn)練得到的由很多棵決策樹(shù)組成的模型。
typedef struct { struct gbdt_tree_t:
當(dāng)然就代表模型中的一棵樹(shù)的各種信息了。為了后面能理解，這里需要詳細(xì)解釋一下這個(gè)結(jié)構(gòu)體。splitid[k]保存該棵樹(shù)的第k個(gè)結(jié)點(diǎn)分裂的feature下標(biāo)，splitvalue[k]保存該棵樹(shù)第k個(gè)結(jié)點(diǎn)的分裂值，nodestatus[k]代表該棵樹(shù)的第k個(gè)結(jié)點(diǎn)的狀態(tài)，如果為GBDT_INTERIOR，代表該結(jié)點(diǎn)已分裂，如果為GBDT_TOSPLIT，代表該結(jié)點(diǎn)需分裂，如果為GBDT_TERMINAL表示該結(jié)點(diǎn)不需再分裂，一般是由于該結(jié)點(diǎn)的樣本數(shù)ndcount[k]少于等于一閾值gbdt_min_node_size；depth[ncur+1]代表左子樹(shù)的深度，depth[ncur+2]表示右子樹(shù)的深度，其中ncur的增長(zhǎng)步長(zhǎng)為2，表示每次+2都相關(guān)于跳過(guò)當(dāng)前結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)，到達(dá)下一個(gè)結(jié)點(diǎn)。ndstart[ncur+1]代表劃分到左子樹(shù)開(kāi)始樣本的下標(biāo)，ndstart[ncur+2]代表劃分到右子樹(shù)開(kāi)始樣本的下標(biāo)，其中到底這個(gè)下標(biāo)是代表第幾個(gè)樣本是由index的一個(gè)結(jié)構(gòu)保存。ndcount[ncur + 1]代表劃分到左子樹(shù)的樣本數(shù)量，ndcount[ncur + 2]代表劃分到右子樹(shù)的樣本數(shù)量。ndavg[ncur+1]代表左子樹(shù)樣本的均值，同理是右子樹(shù)樣本的均值。nodestatus[ncur+1] = GBDT_TOSPLIT表示左子樹(shù)可分裂。lson[k]=ncur+1表示第k個(gè)結(jié)點(diǎn)的左子樹(shù)，同理表示第k個(gè)結(jié)點(diǎn)的右子樹(shù)。
gbdt_info_t保存模型配置參數(shù)。
typedef struct bufset代表訓(xùn)練數(shù)據(jù)池，它保存了訓(xùn)練當(dāng)前一棵樹(shù)所用到的一些數(shù)據(jù)。fea_pool保存了訓(xùn)練數(shù)據(jù)的特征的下標(biāo)，循環(huán)rand_fea_num（feature隨機(jī)采樣量）次，隨機(jī)地從fea_pool中選取特征來(lái)計(jì)算分裂的損失函數(shù)（先過(guò)的feature不會(huì)再選）。fvalue_list保存在當(dāng)前選擇特征fid時(shí)，所有采樣的樣本特征fid對(duì)應(yīng)的值。fv與favlue_list一樣。y_list表示采樣樣本的y值。order_i保存左子樹(shù)與右子樹(shù)結(jié)點(diǎn)下標(biāo)。 nodeinfo代表節(jié)點(diǎn)的信息。
typedef struct splitinfo代表分裂的信息。pivot代表分裂點(diǎn)在order_i中的下標(biāo)。bestsplit表示分裂值。bestid表示分裂的feature。 好了，解釋完關(guān)鍵的一些結(jié)構(gòu)體，下面要看懂整個(gè)gbdt的流程就非常簡(jiǎn)單了。這里我就簡(jiǎn)單的從頭至尾敘述一下整個(gè)訓(xùn)練的流程。
首先申請(qǐng)分配模型空間gbdt_model，并且計(jì)算所有樣本在每一維特征上的平均值。假如我們需要訓(xùn)練infbox.tree_num棵樹(shù)，每一棵的訓(xùn)練流程為：從x_fea_value中采樣gbdt_inf.sample_num個(gè)樣本，index[i]記錄了第i個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的樣本集合x(chóng)_fea_value中的下標(biāo)，其始終保存了訓(xùn)練本棵樹(shù)的所有采樣樣本對(duì)應(yīng)樣本空間的下標(biāo)值，同時(shí)，結(jié)點(diǎn)的順序是按該棵樹(shù)所有結(jié)點(diǎn)按廣度優(yōu)先遍歷算法遍歷的結(jié)果的。即當(dāng)前樹(shù)gbdt_single_tree只有一個(gè)根結(jié)點(diǎn)0，其中g(shù)bdt_single_tree->nodestatus為GBDT_TOSPLIT，ndstart[0]=0，ndcount[0]=sample_num，ndavg為所有采樣樣本的y的梯度值均值。下面就是對(duì)這個(gè)結(jié)點(diǎn)進(jìn)行分裂的過(guò)程：首先nodeinfo ninf這個(gè)結(jié)構(gòu)體保存了當(dāng)前分裂結(jié)點(diǎn)的一些信息，比如結(jié)點(diǎn)中樣本開(kāi)始的下標(biāo)（指相對(duì)于index的下標(biāo)值，index指向的值才是樣本空間中該樣本的下標(biāo)），樣本結(jié)束下標(biāo)（同上），樣本結(jié)點(diǎn)數(shù)，樣本結(jié)點(diǎn)的y的梯度之和等。循環(huán)rand_fea_num次，隨機(jī)采樣feature，來(lái)計(jì)算在該feature分裂的信息增益,計(jì)算方式為（左子樹(shù)樣子目標(biāo)值和的平方均值+右子樹(shù)目標(biāo)值和的平方均值-父結(jié)點(diǎn)所有樣本和的平方均值）。選過(guò)的feature就不會(huì)再選中來(lái)計(jì)算信息增益了。利用data_set來(lái)保存當(dāng)前分裂過(guò)程所用到的一些信息，包括候選feature池，選中feature對(duì)應(yīng)的采樣樣本的特征值及其y值。data_set->order_i保存了左右子樹(shù)對(duì)應(yīng)結(jié)點(diǎn)在樣本集合中的下標(biāo)。計(jì)算每個(gè)feature的信息增益，并取最大的，保存分點(diǎn)信息到spinf中，包括最優(yōu)分裂值，最優(yōu)分裂feature。然后，將該結(jié)點(diǎn)小于分裂值的結(jié)點(diǎn)樣本下標(biāo)與大于分裂值的結(jié)點(diǎn)樣本下標(biāo)都保存在data_set->order_i中，nl記錄了order_i中右子樹(shù)開(kāi)始的位置。更新index數(shù)組，將order_i中copy到index中。將nl更新到spinf中。注意index數(shù)組從左至右保存了最終分裂的左子樹(shù)與右子樹(shù)樣本對(duì)應(yīng)在樣本空間的下標(biāo)。
至此，我們找到了這個(gè)結(jié)點(diǎn)的最優(yōu)分裂點(diǎn)。gbdt_single_tree->ndstart[1]保存了左孩子的開(kāi)始下標(biāo)（指相對(duì)于index的下標(biāo)值，index指向的值才是樣本下標(biāo)），gbdt_single_tree->ndstart[2]保存了右孩子的開(kāi)始下標(biāo)，即nl的值。同理，ndcount，depth等也是對(duì)就保存了左右孩子信息。gbdt_single_tree->lson[0]=1，gbdt_single_tree->lson[0]=2即表示當(dāng)前結(jié)點(diǎn)0的左子樹(shù)是1，右子樹(shù)是2。當(dāng)前結(jié)點(diǎn)分裂完了之后，下一次就同理廣度優(yōu)先算法，對(duì)該結(jié)點(diǎn)的孩子繼續(xù)上述步驟。
該棵樹(shù)分裂完成之后，對(duì)每一個(gè)樣本，都用目前模型（加上分裂完成的這棵樹(shù)）計(jì)算預(yù)測(cè)值，并且更新每一個(gè)樣本的殘差y_gradient。計(jì)算過(guò)程：選取當(dāng)前結(jié)點(diǎn)的分裂feature以及分裂值，小于則走左子樹(shù)，大于則走右子樹(shù)，直到葉子結(jié)點(diǎn)。預(yù)測(cè)值為shrink*該葉子結(jié)點(diǎn)的樣本目標(biāo)值的均值。
訓(xùn)練第二棵樹(shù)同理，只是訓(xùn)練的樣本的目標(biāo)值變成了前面模型預(yù)測(cè)結(jié)果的殘差了。這點(diǎn)就體現(xiàn)在梯度下降的尋優(yōu)過(guò)程。
好了，這里只是簡(jiǎn)單的對(duì)gbdt代碼做了說(shuō)明，當(dāng)然如果沒(méi)有看過(guò)本文引用的源碼，是不怎么能看懂的，如果結(jié)合源碼來(lái)看，就很容易看懂了?？傊?，個(gè)人感覺(jué)，只有結(jié)合原碼來(lái)學(xué)習(xí)gbdt，才真正能體會(huì)到事個(gè)模型的學(xué)習(xí)以及樹(shù)的生成過(guò)程。 GBDT理解二三事一、要理解GBDT當(dāng)然要從GB(Gradient Boosting)和DT(Decision Tree)兩個(gè)角度來(lái)理解了； 二、GB其實(shí)是一種理念，他并不是這一個(gè)具體的算法，意思是說(shuō)沿著梯度方向，構(gòu)造一系列的弱分類(lèi)器函數(shù)，并以一定權(quán)重組合起來(lái)，形成最終決策的強(qiáng)分類(lèi)器；注意，這里的梯度下降法是在函數(shù)空間中通過(guò)梯度下降法尋找使得LOSS最小的一個(gè)函數(shù)，即L(y,f)對(duì)f求層，區(qū)別于傳統(tǒng)的梯度下降法選擇一個(gè)方向（對(duì)x求導(dǎo)）；那么問(wèn)題就來(lái)了，對(duì)函數(shù)求導(dǎo)？這也太難了吧。所以就有了一個(gè)近似的方法，根據(jù)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則，我們認(rèn)為在訓(xùn)練集上使得LOSS最小的函數(shù)，往往在測(cè)試集上表現(xiàn)會(huì)好，即在訓(xùn)練集上尋優(yōu)；因此，把求導(dǎo)的函數(shù)理解成在訓(xùn)練集上該函數(shù)對(duì)應(yīng)的離散的函數(shù)值，對(duì)函數(shù)求導(dǎo)就變成了對(duì)樣本的函數(shù)值向量求導(dǎo)；因此就可以得到一個(gè)梯度向量，表示尋找到的最優(yōu)函數(shù)， 這個(gè)函數(shù)就是一個(gè)新的弱分類(lèi)器； 三、通過(guò)回歸樹(shù)來(lái)擬合這個(gè)梯度向量，就得到了DT，而每棵樹(shù)就對(duì)應(yīng)上面的函數(shù)，其預(yù)測(cè)值就是函數(shù)值； 四、當(dāng)我們選擇平方差損失函數(shù)時(shí)，函數(shù)向量就表示成前一棵回歸樹(shù)在樣本空間上的預(yù)測(cè)值，則對(duì)函數(shù)向量求梯度就等于目標(biāo)值減去預(yù)測(cè)值，即我們所說(shuō)的殘差向量；因此，下一棵回歸樹(shù)就是在擬合這個(gè)殘差向量； 五、回歸樹(shù)擬合可以通過(guò)平均最小均方差來(lái)尋找分裂點(diǎn)，生成一個(gè)樹(shù)；當(dāng)然這棵樹(shù)不可能完全擬合得好，因此，又會(huì)通過(guò)對(duì)損失函數(shù)求梯度，得到新的殘差向量； 六、對(duì)初始分類(lèi)器（函數(shù)）的選擇就可以直接用0，通過(guò)平方差LOSS函數(shù)求得的殘差當(dāng)然就是樣本本身了；也可以選擇樣本的均值； 七、一棵樹(shù)的分裂過(guò)程只需要找到找到每個(gè)結(jié)點(diǎn)的分裂的特征id與特征值，而尋找的方法可以是平均最小均方差，也可以是使得（左子樹(shù)樣本目標(biāo)值和的平方均值+右子樹(shù)樣本目標(biāo)值和的平方均值-父結(jié)點(diǎn)所有樣本目標(biāo)值和的平方均值）最大的那個(gè)分裂點(diǎn)與分裂特征值等等方法；從而將樣本分到左右子樹(shù)中，繼續(xù)上面過(guò)程；
八、用殘差更新每個(gè)樣本的目標(biāo)值：葉子節(jié)點(diǎn)的均值作為落到該葉子節(jié)點(diǎn)的樣本的預(yù)測(cè)值，使用目標(biāo)值減去預(yù)測(cè)值，得到該樣本的殘差，作為下一棵樹(shù)的訓(xùn)練目標(biāo)； 九、對(duì)于使用logistic作為損失函數(shù)的多分類(lèi)問(wèn)題，下面單獨(dú)進(jìn)行推導(dǎo)說(shuō)明： 1、多分類(lèi)問(wèn)題與回歸問(wèn)題不同，每棵樹(shù)的樣本的目標(biāo)就不是一個(gè)數(shù)值了，而是每個(gè)樣本在每個(gè)分類(lèi)下面都有一個(gè)估值Fk(x)；
2、同邏輯回歸一樣，假如有K類(lèi)，每一個(gè)樣本的估計(jì)值為F1(x)...Fk(x),對(duì)其作logistic變化之后得到屬于每一類(lèi)的概率是P1(x)...pk(x)，則損失函數(shù)可以定義為負(fù)的log似然： 可以看出對(duì)多分類(lèi)問(wèn)題，新的一棵樹(shù)擬合的目標(biāo)仍是殘差向量； 3、訓(xùn)練過(guò)程如下：
對(duì)第一棵樹(shù)，可以初始化每個(gè)樣本在每個(gè)分類(lèi)上的估計(jì)值Fk(x)都為0；計(jì)算logistic變換pk(x)，計(jì)算殘差向量，作為當(dāng)前樹(shù)的回歸的目標(biāo)，回歸樹(shù)的分裂過(guò)程仍可采用【左子樹(shù)樣本目標(biāo)值（殘差）和的平方均值+右子樹(shù)樣本目標(biāo)值（殘差）和的平方均值-父結(jié)點(diǎn)所有樣本目標(biāo)值（殘差）和的平方均值】最大的那個(gè)分裂點(diǎn)與分裂特征值等方法；當(dāng)回歸樹(shù)的葉子節(jié)點(diǎn)數(shù)目達(dá)到要求示，則該樹(shù)建立完成；對(duì)每個(gè)葉子節(jié)點(diǎn)，利用落到該葉子節(jié)點(diǎn)的所有樣本的殘差向量，計(jì)算增益rjkm；更新每一個(gè)樣本的估計(jì)值Fk(x)；因此，又可以對(duì)估計(jì)進(jìn)行l(wèi)ogistic變化，利用樣本的目標(biāo)值計(jì)算殘差向量，訓(xùn)練第二棵樹(shù)了； 4、注意樣本的估計(jì)值Fk(x)是前面所有樹(shù)的估值之和，因此，計(jì)算殘差時(shí)，用樣本的目標(biāo)值減去Fk(x)就可以得到殘差了； 十、GBDT并行化： 1、按行并行化，將樣本按行分成N份，分別在N個(gè)節(jié)點(diǎn)上做計(jì)算； 2、并行建立一棵的過(guò)程： 1>在0號(hào)節(jié)點(diǎn)上對(duì)特征隨機(jī)采樣，生成建立一棵樹(shù)需要用到的特征，并分發(fā)到N個(gè)節(jié)點(diǎn)上； 2>在0號(hào)結(jié)點(diǎn)上維護(hù)每一維采樣特征所有可能的特征值； 3>將每一維特征的每一個(gè)可能的特征值分發(fā)到N個(gè)節(jié)點(diǎn)上； 4>每一個(gè)節(jié)點(diǎn)并行計(jì)算該節(jié)點(diǎn)上所有樣本與分發(fā)得到的特征值的比較結(jié)果，分割成左右子樹(shù)，并計(jì)算增益； 5>歸并所有節(jié)點(diǎn)的增益，在0號(hào)結(jié)點(diǎn)得到每一個(gè)特征在每一個(gè)特征值的增益(f，v，incr)； 6>在0號(hào)結(jié)點(diǎn)上找出最大的(f，v，incr)，并作為本次的最佳裂點(diǎn)，分發(fā)到N個(gè)節(jié)點(diǎn)上； 7>N個(gè)節(jié)點(diǎn)將樣本分割成左右子樹(shù)； 8>對(duì)左右子樹(shù)繼續(xù)上面過(guò)程，直到葉子節(jié)點(diǎn)數(shù)目滿(mǎn)足要求； 3、并行建立第二棵樹(shù)； 因此，GBDT并行化包括了樣本并行化與特征分裂點(diǎn)計(jì)算的并行化；其中最耗時(shí)的仍然是需要遍歷特征的所有可能的特征值，并計(jì)算增益尋找最優(yōu)分裂點(diǎn)的過(guò)程；可以采用對(duì)特征值直方圖采樣，不用遍歷所有特征值來(lái)優(yōu)化。
這里參考了http://www.cnblogs.com/leftnoteasy/archive/2011/03/07/random-forest-and-gbdt.html對(duì)分類(lèi)問(wèn)題的解釋?zhuān)瑢?xiě)得非常好，treelink里面的代碼基本就是按照這個(gè)流程實(shí)現(xiàn)的。 |
|
|
