GBDT
梯度提升樹實(shí)在提升樹的基礎(chǔ)上發(fā)展而來的一種使用范圍更廣的方法，當(dāng)處理回歸問題時(shí)绷跑，提升樹可以看作是梯度提升樹的特例(分類問題時(shí)是不是特例椅野？)。 因?yàn)樘嵘龢湓跇?gòu)建樹每一步的過程中都是去擬合上一步獲得模型在訓(xùn)練集上的殘差榜旦。后面我們將會(huì)介紹幽七，這個(gè)殘存正好是損失函數(shù)的梯度，對(duì)應(yīng)于GBDT每一步要擬合的對(duì)象溅呢。
主要思想
在目標(biāo)函數(shù)所在的函數(shù)空間中做梯度下降澡屡，即把待求的函數(shù)模型當(dāng)作參數(shù)猿挚，每一步要擬合目標(biāo)函數(shù)關(guān)于上一步獲得的模型的梯度，從而使得參數(shù)朝著最小化目標(biāo)函數(shù)的方向更新驶鹉。
一些特性
- 每次迭代獲得的決策樹模型都要乘以一個(gè)縮減系數(shù)绩蜻，從而降低每棵樹的作用，提升可學(xué)習(xí)空間室埋。
- 每次迭代擬合的是一階梯度办绝。
XGBoost
XGBoost 是GBDT的一個(gè)變種，最大的區(qū)別是xgboost通過對(duì)目標(biāo)函數(shù)做二階泰勒展開词顾，從而求出下一步要擬合的樹的葉子節(jié)點(diǎn)權(quán)重（需要先確定樹的結(jié)構(gòu)）八秃，從而根據(jù)損失函數(shù)求出每一次分裂節(jié)點(diǎn)的損失減小的大小，從而根據(jù)分裂損失選擇合適的屬性進(jìn)行分裂肉盹。
這個(gè)利用二階展開的到的損失函數(shù)公式與分裂節(jié)點(diǎn)的過程是息息相關(guān)的昔驱。先遍歷所有節(jié)點(diǎn)的所有屬性進(jìn)行分裂，假設(shè)選擇了這個(gè)a屬性的一個(gè)取值作為分裂節(jié)點(diǎn)上忍，根據(jù)泰勒展開求得的公式可計(jì)算該樹結(jié)構(gòu)各個(gè)葉子節(jié)點(diǎn)的權(quán)重骤肛，從而計(jì)算損失減小的程度，從而綜合各個(gè)屬性選擇使得損失減小最大的那個(gè)特征作為當(dāng)前節(jié)點(diǎn)的分裂屬性窍蓝。依次類推腋颠，直到滿足終止條件。
一些特性
除了類似于GBDT的縮減系數(shù)外吓笙，xgboost對(duì)每棵樹的葉子節(jié)點(diǎn)個(gè)數(shù)和權(quán)重都做了懲罰淑玫，避免過擬合
類似于隨機(jī)森林，XGBoost在構(gòu)建樹的過程中面睛，對(duì)每棵樹隨機(jī)選擇一些屬性作為分裂屬性絮蒿。
分裂算法有兩種，一種是精確的分裂叁鉴，一種是近似分裂算法土涝，精確分裂算法就是把每個(gè)屬性的每個(gè)取值都當(dāng)作一次閾值進(jìn)行遍歷，采用的決策樹是CART幌墓。近似分裂算法是對(duì)每個(gè)屬性的所有取值進(jìn)行分桶但壮，按照各個(gè)桶之間的值作為劃分閾值，xgboost提出了一個(gè)特殊的分桶策略常侣，一般的分桶策略是每個(gè)樣本的權(quán)重都是相同 的蜡饵，但是xgboost使每個(gè)樣本的權(quán)重為損失函數(shù)在該樣本點(diǎn)的二階導(dǎo)(泰勒展開不應(yīng)該是損失函數(shù)關(guān)于模型的展開嗎？為什么會(huì)有在該樣本點(diǎn)的二階導(dǎo)這種說法袭祟？ 因?yàn)槟Ｐ褪菍?duì)所有樣本點(diǎn)都通用的验残，把該樣本輸入到二階導(dǎo)公式中就可以得到了)。
xgboost添加了對(duì)稀疏數(shù)據(jù)的支持，在計(jì)算分裂收益的時(shí)候只利用沒有missing值的那些樣本您没，但是在推理的時(shí)候鸟召，也就是在確定了樹的結(jié)構(gòu)，需要將樣本映射到葉子節(jié)點(diǎn)的時(shí)候氨鹏，需要對(duì)含有缺失值的樣本進(jìn)行劃分欧募，xgboost分別假設(shè)該樣本屬于左子樹和右子樹，比較兩者分裂增益仆抵，選擇增益較大的那一邊作為該樣本的分裂方向跟继。
xgboost在實(shí)現(xiàn)上支持并行化，這里的并行化并不是類似于rf那樣樹與樹之間的并行化镣丑，xgboost同boosting方法一樣舔糖，在樹的粒度上是串行的，但是在構(gòu)建樹的過程中莺匠，也就是在分裂節(jié)點(diǎn)的時(shí)候支持并行化金吗，比如同時(shí)計(jì)算多個(gè)屬性的多個(gè)取值作為分裂特征及其值，然后選擇收益最大的特征及其取值對(duì)節(jié)點(diǎn)分裂趣竣。
xgboost 在實(shí)現(xiàn)時(shí)摇庙，需要將所有數(shù)據(jù)導(dǎo)入內(nèi)存，做一次pre-sort（exact algorithm）遥缕，這樣在選擇分裂節(jié)點(diǎn)時(shí)比較迅速卫袒。
缺點(diǎn)
- level-wise 建樹方式對(duì)當(dāng)前層的所有葉子節(jié)點(diǎn)一視同仁，有些葉子節(jié)點(diǎn)分裂收益非常小单匣，對(duì)結(jié)果沒影響夕凝，但還是要分裂，加重了計(jì)算代價(jià)户秤。
- 預(yù)排序方法空間消耗比較大迹冤，不僅要保存特征值，也要保存特征的排序索引虎忌，同時(shí)時(shí)間消耗也大，在遍歷每個(gè)分裂點(diǎn)時(shí)都要計(jì)算分裂增益(不過這個(gè)缺點(diǎn)可以被近似算法所克服)
lightGBM
xgboost采用的是level-wise的分裂策略橱鹏，而lightGBM采用了leaf-wise的策略膜蠢，區(qū)別是xgboost對(duì)每一層所有節(jié)點(diǎn)做無差別分裂，可能有些節(jié)點(diǎn)的增益非常小莉兰，對(duì)結(jié)果影響不大挑围，但是xgboost也進(jìn)行了分裂，帶來了務(wù)必要的開銷糖荒。 leaft-wise的做法是在當(dāng)前所有葉子節(jié)點(diǎn)中選擇分裂收益最大的節(jié)點(diǎn)進(jìn)行分裂杉辙，如此遞歸進(jìn)行，很明顯leaf-wise這種做法容易過擬合捶朵，因?yàn)槿菀紫萑氡容^高的深度中蜘矢，因此需要對(duì)最大深度做限制狂男，從而避免過擬合。
lightgbm使用了基于histogram的決策樹算法品腹，這一點(diǎn)不同與xgboost中的 exact 算法岖食，histogram算法在內(nèi)存和計(jì)算代價(jià)上都有不小優(yōu)勢(shì)。
-. 內(nèi)存上優(yōu)勢(shì)：很明顯舞吭，直方圖算法的內(nèi)存消耗為(#data* #features * 1Bytes)(因?yàn)閷?duì)特征分桶后只需保存特征離散化之后的值)泡垃，而xgboost的exact算法內(nèi)存消耗為：(2 * #data * #features* 4Bytes)，因?yàn)閤gboost既要保存原始feature的值羡鸥，也要保存這個(gè)值的順序索引蔑穴，這些值需要32位的浮點(diǎn)數(shù)來保存。
-. 計(jì)算上的優(yōu)勢(shì)惧浴，預(yù)排序算法在選擇好分裂特征計(jì)算分裂收益時(shí)需要遍歷所有樣本的特征值存和，時(shí)間為(#data),而直方圖算法只需要遍歷桶就行了，時(shí)間為(#bin)直方圖做差加速
-. 一個(gè)子節(jié)點(diǎn)的直方圖可以通過父節(jié)點(diǎn)的直方圖減去兄弟節(jié)點(diǎn)的直方圖得到赶舆，從而加速計(jì)算哑姚。lightgbm支持直接輸入categorical 的feature
-. 在對(duì)離散特征分裂時(shí)，每個(gè)取值都當(dāng)作一個(gè)桶芜茵，分裂時(shí)的增益算的是”是否屬于某個(gè)category“的gain叙量。類似于one-hot編碼。但實(shí)際上xgboost的近似直方圖算法也類似于lightgbm這里的直方圖算法九串，為什么xgboost的近似算法比lightgbm還是慢很多呢绞佩？
-. xgboost在每一層都動(dòng)態(tài)構(gòu)建直方圖， 因?yàn)閤gboost的直方圖算法不是針對(duì)某個(gè)特定的feature猪钮，而是所有feature共享一個(gè)直方圖(每個(gè)樣本的權(quán)重是二階導(dǎo)),所以每一層都要重新構(gòu)建直方圖品山，而lightgbm中對(duì)每個(gè)特征都有一個(gè)直方圖，所以構(gòu)建一次直方圖就夠了烤低。
-. lightgbm做了cache優(yōu)化肘交？lightgbm哪些方面做了并行？
-. feature parallel
一般的feature parallel就是對(duì)數(shù)據(jù)做垂直分割（partiion data vertically扑馁，就是對(duì)屬性分割）涯呻，然后將分割后的數(shù)據(jù)分散到各個(gè)workder上，各個(gè)workers計(jì)算其擁有的數(shù)據(jù)的best splits point, 之后再匯總得到全局最優(yōu)分割點(diǎn)腻要。但是lightgbm說這種方法通訊開銷比較大复罐，lightgbm的做法是每個(gè)worker都擁有所有數(shù)據(jù)，再分割雄家？（沒懂效诅，既然每個(gè)worker都有所有數(shù)據(jù)了，再匯總有什么意義？這個(gè)并行體現(xiàn)在哪里乱投？咽笼？）
-. data parallel
傳統(tǒng)的data parallel是將對(duì)數(shù)據(jù)集進(jìn)行劃分，也叫 平行分割(partion data horizontally)篡腌， 分散到各個(gè)workers上之后褐荷，workers對(duì)得到的數(shù)據(jù)做直方圖，匯總各個(gè)workers的直方圖得到全局的直方圖嘹悼。 lightgbm也claim這個(gè)操作的通訊開銷較大叛甫，lightgbm的做法是使用”Reduce Scatter“機(jī)制，不匯總所有直方圖杨伙，只匯總不同worker的不同feature的直方圖(原理其监？)，在這個(gè)匯總的直方圖上做split限匣，最后同步抖苦。
