介紹
在開始介紹XGBoost之前，我們先來了解一下什麼事Boosting？
所謂的Boosting 就是一種將許多弱學習器(weak learner)集合起來變成一個比較強大的學習器(strong learner)，大致上的核心思想就是「三個臭皮匠勝過一個諸葛亮」。透過提高舊模型的錯誤權重，然後再訓練新的模型，這樣新的模型就會學習到錯誤的資訊，進而提升結果，所以前後每一個模型都是有關連的。
XGBoost ( Extreme Gradient Boosting )，是一種Gradient Boosted Tree(GBDT)，每一次保留原來的模型不變，並且加入一個新的函數至模型中，修正上一棵樹的錯誤，以提升整體的模型。主要用於解於監督是學習，可以用於分類也可以用於迴歸問題
Tree Boosting
上面提到XGBoost是一組分類和回歸樹(classification and regression trees — CART)，每一顆回歸樹的葉子都會對應到一組分數，這個分數作為之後分類的依據。上面的式子可以對應下面的圖片，所謂y^就是模型所計算出來的分數。
- Tree Ensemble
有學過機器學習的人應該可以知道，由上面的式子可以看到，L指的是loss function，式子後面加入一個懲罰項Ω，它可以避免我們的模型overfitting，幫助找到較好的模型。
優化模型最常使用的模型就是透過梯度來解決，但我們無法在一次訓練所有的樹，因此會透過增量訓練 (additive training) 的方式，每一步都是在前一步的基礎上增加一棵樹來做修正。
我們把loss function展開來看就會變成：
再將loss function以MSE表示：
再利用泰勒展開式做展開 ：
其中gi及hi定義如下：
把常數項拿掉即可得到下面式子：
- 計算每一棵樹葉子的分數
將上式重新整理後可得：
其中Gi及Hi分別為：
所以我們可以從上面的一元二次方程式得到：
所以loss function為：
上面所得到的式子可以用來判斷一棵樹的好壞
- 建構一棵樹時所進行的特徵劃分
在這裡所使用的方式為exact greedy algorithm及approximate algorithm，就是在樹的每個層構建的過程中，來優化目標。
1. exact greedy algorithm: 此方法會列出所有的特徵，並以此特徵當作劃分條件，透過下面的式子把每個特徵所對應的參數帶入，值越大代表損失下降越多，並找出最好的劃分點。
2. approximate algorithm: 對於某個特徵，算法首先根據特徵分佈的分位數找到切割點的集合Sk={sk1,sk2,…,skl}；然後將特徵k的值根據集合Sk劃分到bucket中，接著對每個bucket的樣本統計值G、H進行累加統計，最後在這些累計的統計量上尋找最佳分裂點。
3. weighted quantile sketch: 是為了解決數據無法一次載入內存或者在分佈式情況下（exact greedy algorithm）效率低的問題
4. Sparsity-aware Split Finding : 很多時候訓練數據都是稀疏的，數據都是有缺失值的。訓練數據的時候，它使用沒有缺失的數據去進行節點分支。然後我們將特徵上缺失的數據嘗試放左右節點上，看缺失值應當分到那個分支節點上(default分支)。
- System Design: 在建構一棵樹時最耗時間的就是尋找特徵的劃分過程中，必須先將每一個特徵先做排序。為了減少排序的時間，所以採用block來存取數據。
- block中的數據以稀疏格式CSC存取(目的是為了壓縮矩陣，減少矩陣存儲所佔用的空間)
- block中的特徵進行排序，只需要排序一次，以後分裂樹的過程可以重複使用
- Cache-aware Access: 對於有大量數據或者說分佈式系統來說，我們不可能將所有的數據都放進內存裡面。因此我們都需要將其放在外存上或者分佈式存儲。但是這有一個問題，這樣做每次都要從外存上讀取數據到內存，這將會是十分耗時的操作。因此我們使用預讀取（prefetching）將下一塊將要讀取的數據預先放進內存裡面。其實就是多開一個線程，該線程與訓練的線程獨立並負責數據讀取。此外，還要考慮block的大小問題。如果我們設置最大的block來存儲所有樣本在k特徵上的值和梯度的話，cache未必能一次性處理如此多的梯度做統計。如果我們設置過少block size，這樣不能充分利用的多線程的優勢，也就是訓練線程已經訓練完數據，但是prefetching thread還沒把數據放入內存或者cache中。作者發現block size設置為2¹⁶個examples最好。
- Blocks for Out-of-core Computation: 對於超大型的數據，不可能都放入放入內存，因此大部分都放入外存上。假如將數據存於外存上將帶來讀寫速度受限的問題。paper有提到兩種方法，一種是對數據進行壓縮存於外存中，到內存中需要訓練時再解壓，這樣來增加系統的吞吐率，儘管消耗了一些時間來做編碼和解碼但還是值得的。另一種就是多外存存儲，其實本質上就是分佈式存儲。
參考文獻
