1 提升方法
1.1 概率近似正確（PAC）學(xué)習(xí)框架
- 在概率近似正確（PAC）學(xué)習(xí)框架中京景，一個概念确徙，如果存在一個多項式的學(xué)習(xí)算法能夠?qū)W習(xí)它，并且正確率很高厦凤，那么就稱這個概念是強可學(xué)習(xí)的较鼓；一個概念博烂，如果存在一個多項式的學(xué)習(xí)算法能夠?qū)W習(xí)它漱竖，但正確率僅比隨機猜測好一點馍惹，則稱這個概念是弱可學(xué)習(xí)的玛界。
- 強可學(xué)習(xí)和弱可學(xué)習(xí)是等價的慎框。
- 因此笨枯，若發(fā)現(xiàn)了弱學(xué)習(xí)器遇西，可以將其提升為強學(xué)習(xí)器.
1.2 提升方法的問題
- 如何在每一輪訓(xùn)練中改變訓(xùn)練數(shù)據(jù)的權(quán)值或者概率分布粱檀？
- 如何將弱分類器組成一個強分類器梧税？
2 AdaBoost 算法（最具代表性的提升算法）
2.1 主要思想
- 提高被前一輪弱分類器錯誤分類錯誤分類樣本的權(quán)值第队，降低被正確分類的樣本權(quán)值刨秆；
- 采取多數(shù)表決的方式組合弱分類器衡未，加大分類誤差小的弱分類器權(quán)值。
2.2 步驟
3 提升樹
3.1 定義
- 提升方法采用加法模型與前向分步算法，以決策樹為基函數(shù)的提升方法稱為提升樹（boosting tree）送粱。
- 當提升樹算法為二分類算法時抗俄，就成了Adaboost算法的一種特例。
- 提升樹都是回歸樹槽卫。
3.2 提升樹算法
采用前向分布算法的提升樹歼培，第m步的模型為：
其中
當損失函數(shù)為
平方誤差損失時读跷，
當前模型學(xué)習(xí)的目標就是你擬合殘差
3.2 梯度提升決策樹（GBDT）
提升樹利用加法模型與前向分步算法實現(xiàn)優(yōu)化過程无切，當損失函數(shù)是平方損失時丐枉，每一步優(yōu)化是簡單的，但對一般損失函數(shù)而言籍嘹，問題就復(fù)雜了辱士，因此颂碘，F(xiàn)reidman提出了梯度提升算法（Gradient Boosting）椅挣，這是最速下降的近似方法鼠证，其關(guān)鍵是利用損失函數(shù)的負梯度在當前模型的值作為上述殘差的近似值量九，擬合一個回歸樹。
3.3 XGboost (Extreme Gradient Boosting)
3.3.1 改進點
XGboost本質(zhì)上是GBDT思想的一種實現(xiàn)方式攻谁，它主要在以下幾個方面做了改變：
- GBDT在訓(xùn)練時戚宦，只采用了損失函數(shù)的一階導(dǎo)數(shù)信息锈嫩，XGBoost對損失函數(shù)進行了二階展開，理論上講艳汽，收斂速度更快
- 加入了正則項，L1和L2分別用于限制葉子節(jié)點的數(shù)量和節(jié)點權(quán)重
- GBDT采用CART二叉樹米绕，分裂準則為平方誤差,XGboost支持多種分類器栅干，樹的分裂準則如下：
a當決策樹結(jié)構(gòu)已知時碱鳞，令損失函數(shù)二階泰勒近似函數(shù)的導(dǎo)數(shù)為0窿给，可以求出每個葉子節(jié)點的預(yù)測值：;
b將預(yù)測值代入到損失函數(shù)中崩泡，可以求得損失函數(shù)的最小值;
c計算分裂前后損失函數(shù)的差值為，采用差值最大的分裂節(jié)點進行分裂圈浇；具體而言（>https://zhuanlan.zhihu.com/p/125594314） ：
1）先計算未分裂時一階導(dǎo)和二階導(dǎo)在各個樣本處的值召耘，
2）然后遍歷所有特征（這里特征屬性為連續(xù)值）褐隆，每個特征下按特征值大小對樣本排序庶弃，
3）然后從左往右依次選擇分割點歇攻，計算該分割點下的損失差值缴守，
4）找到損失差值最大時對應(yīng)的特征與分割點镇辉，以此為當前節(jié)點進行分裂忽肛。
這樣做確實能準確的找到特征與分割點屹逛，但是太耗時了煎源。如果有幾百個特征香缺，幾百萬個訓(xùn)練樣本图张，按這種方式遍歷黃花菜都涼了祸轮，所以需要一種較為快速的近似方法去替代精確解适袜。 - GBDT在每輪迭代時，使用全部的訓(xùn)練數(shù)據(jù)售貌，XGBoost則加入了行采樣(樣本)和列采樣(特征)颂跨；
- GBDT沒有對缺失值進行處理，XGBoost能夠自動學(xué)習(xí)
缺失值的處理策略钓丰；
3.3.2 近似算法
不遍歷訓(xùn)練樣本所有特征值去找最佳分割點斑粱，而是人為設(shè)計一些分割點则北，然后將訓(xùn)練樣本劃分到不同的分割區(qū)間中尚揣，步驟如下：
對于每一個特征快骗，進行固定的分割點選取，其中對于第k個特征方篮，分割點的首尾分別是該特征屬性值的最小最大值名秀。這樣每個特征下每個分割點都能計算出損失差，選取最小損失差對應(yīng)的特征藕溅、分割點即可匕得。這里分割點的用法也用兩種，一種是global巾表，一種是local汁掠。global意味著只進行一次初始的分割選取，后面每個節(jié)點的都是在初始分割點上選取最優(yōu)點集币；local則是每分裂一次考阱，重新調(diào)整分割點的選取，分割區(qū)間會越來越小鞠苟，因為分裂后的每個節(jié)點的樣本數(shù)在減少。用local方法吃既，則分割點不用設(shè)計太多扼鞋，分割區(qū)間也不用太細；用global方法則需要較多的分割點溃槐，同樣分割區(qū)間也要更細。在數(shù)據(jù)集上的驗證結(jié)果表明拂共，用遠少于訓(xùn)練樣本數(shù)的分割點抚恒，這種近似算法的效果與前面提到的遍歷所有樣本的效果差不多盒音，如下圖：
3.3.3 缺失值處理
每次分裂時，對缺失值樣本分別放在左右兩個葉節(jié)點，計算損失下降值碾盐，哪邊增益大就放哪邊。
3.3.4 工程優(yōu)化
特征值排序并存儲pre-sorted
上文提到對于每個特征春霍，需要遍歷所有的特征值去選擇最佳分割點。如果在訓(xùn)練之前就排好序并存儲在內(nèi)存block中莲趣，每一個特征對應(yīng)一個block潘鲫。這樣在構(gòu)建第k棵樹的過程中浊竟，可以同時對所有的葉結(jié)點進行分割點的遍歷肉拓，也可以同時對所有特征進行分割點的遍歷，這樣特征的選擇和葉結(jié)點的分裂可以同時進行胧后，達到并行化計算的目的镇草，可以進行分布式或多線程計算因宇，縮短訓(xùn)練時間修肠。cache-aware預(yù)取
在分塊并行中吃靠，block存儲了排序的列夕冲，并建立和原來樣本的一一映射，這樣可以通過特征值來找到原始樣本獲得梯度弥姻，但是原始樣本是存放是按照列值的原始順序的秧廉，相鄰內(nèi)存的樣本他們對應(yīng)的列值可能不是連續(xù)的，而我們現(xiàn)在根據(jù)排序后的列值來找原樣本，那么肯定會出現(xiàn)在內(nèi)存上的跳躍式查找婴氮，就非連續(xù)內(nèi)存訪問，可能導(dǎo)致CPU cache命中率降低骏啰。所以在線程中開辟一塊連續(xù)空間帚豪，對需要用到的梯度 進行預(yù)取和存儲烛亦。在數(shù)據(jù)集較大的時候委粉，緩存機制效果比較好out-of-core computation
當訓(xùn)練樣本太大無法全部加載到內(nèi)存中時汁汗，會把數(shù)據(jù)分成許多個block并存儲在硬盤中，需要計算的時候忿墅，用另一個線程加載數(shù)據(jù)到內(nèi)存中棍弄，這樣讀取與計算可以同步進行故慈。但是我們知道從磁盤讀取數(shù)據(jù)會比較耗時竭贩，因此作者又提出了兩個優(yōu)化方法去解決這個問題。
第一個方法叫做Block compression莺禁，將block按列壓縮存儲留量，讀取的時候用另外的線程邊讀取邊解壓；第二個方法叫做Block sharding哟冬，是將數(shù)據(jù)劃分到不同磁盤上楼熄，為每個磁盤分配一個預(yù)讀取線程，并將數(shù)據(jù)提取到內(nèi)存緩沖區(qū)中浩峡，然后訓(xùn)練線程交替地從每個緩沖區(qū)讀取數(shù)據(jù)可岂。這有助于在多個磁盤可用時增加磁盤讀取的吞吐量。
4 LightGBM
LightGBM和XGBoost一樣是對GBDT的高效實現(xiàn)翰灾，原理上它和GBDT及XGBoost類似缕粹，都采用損失函數(shù)的負梯度作為當前決策樹的殘差近似值，去擬合新的決策樹纸淮。
LightGBM在很多方面會比XGBoost表現(xiàn)的更為優(yōu)秀致开。它有以下優(yōu)勢：
- 更快的訓(xùn)練效率
- 低內(nèi)存使用
- 更高的準確率
- 支持并行化學(xué)習(xí)
- 可處理大規(guī)模數(shù)據(jù)
- 支持直接使用category特征
參考資料
XGBoost的優(yōu)化方法: https://zhuanlan.zhihu.com/p/125594314
XGBoost入門系列第一講: https://zhuanlan.zhihu.com/p/27816315
《統(tǒng)計學(xué)習(xí)方法》 李航
