xgb的其它要點的收藏
下文均直接賦值自上述地址。作為資料儲存和增強記憶。
分裂查詢演算法
關於最優特徵以及最優切分點的選取XGBoost提供了兩個演算法。
Basic Exact Greedy Algorithm （精確貪心演算法）
Approximate Algorithm（近似演算法）
精確貪心演算法類似於CART中最優特徵與切分點的查詢，透過遍歷每個特徵下的每個可能的切分點取值，計算切分後的增益，選擇增益最大的特徵及切分點。具體演算法流程如下
因為精確貪心演算法需要遍歷所有特徵和取值，當資料量非常大的時候，無法將所有資料同時載入進記憶體時，精確貪心演算法會非常耗時，XGBoost的作者引進了近似演算法。近似演算法對特徵值進行了近似處理，即根據每個特徵k的特徵值分佈，確定出候選切分點
，即按特徵分佈將連續的特徵值劃分到
個候選點對應的桶（buckets）中，並且對每個桶中每個樣本的
進行累加。候選切分點的劃分以及
的累加過程如下：
劃分好候選切分點之後，按照精確貪心演算法描述的演算法步驟進行選擇最優切分特徵與最優切分點，不同的是切分點被上述候選切分點所代替，但原理和操作過程是一樣的。
在近似演算法的虛擬碼圖中，作者提到可以按照global的方式提出候選切分點，也可以按照local的方式提出候選切分點。
什麼是global方式？什麼是local方式？簡單的說就是什麼時候提取候選切分點，即在哪一個步驟進行候選切分點的提取。global表示在生成樹之前進行候選切分點的提取，即開始之前為整顆樹做一次提取即可，在每次的節點劃分時都使用已經提取好的候選切分點。而local則是在每次節點劃分時才進行候選切分點的提取。那麼區別是什麼呢？
global方式進行候選切分點提取的次數少。因為只是在初始化的階段進行一次即可，以後的節點切分均使用同一個，而local方式是在每次節點切分時才進行，需要很多次的提取。
global方式需要更多的候選點，即對候選點提取數量比local更多，因為沒有像local方式一樣每次節點劃分時，對當前節點的樣本進行細化，local方式更適合樹深度較大的情況。
上圖是作者在Higgs boson 資料集上對兩種方式的測試，可以看出local需要更少的候選切分點，當global方式有足夠多的候選點時正確率與local相當。
下面對近似演算法舉個栗子做為說明。
圖示中特徵值被切分成三個候選切分點，位於0~
處的樣本被劃分到第一個桶中， 位於
之間的樣本分別被劃分到第二個和第三個桶中。那麼在計算最優切分點時，就有兩種劃分方式，第一種方式，即第一個桶的樣本被切分到左節點中，第二、三個桶的樣本被切分到右節點中。其增益gain為max函式中第二項。第二種劃分方式為，第一、二個桶中的樣本切分到左節點中，第三個桶中的樣本切分到右節點中，其增益為max函式中第三項。那麼max函式第一項表示什麼呢？第一項表示的是其他特徵切分點確認後的最大增益，與當前特徵的兩種切分方式比較，選擇最優的特徵及其切分點。
注意到栗子在對樣本進行劃分時，考慮的是樣本的個數，即每個桶中樣本個數相同為出發點來劃分的，如果樣本有權重呢？直觀上的想法是，那就考慮權重而不是個數唄。那麼每個樣本應該賦予什麼樣的權重？又怎樣去處理這個權重？
加權分位數略圖（Weighted Quantile Sketch）
為了處理帶權重的候選切分點的選取，作者提出了Weighted Quantile Sketch演算法。加權分位數略圖演算法提出一種資料結構，這種資料結構支援merge和prune操作。作者在論文中給出了該演算法的詳細描述和證明連結（ps：已經失效），這裡不做詳細介紹。可以參考連結加權分位數略圖定義及證明說明。簡單介紹加權分位數略圖侯選點的選取方式。
設資料集
表示每個樣本的第k個特徵值（
）和二階導數（
）的集合。定義排名函式
：
（式14）
（式14）表示資料集中第k個特徵值小於z的樣本所在比例（公式看起來貌似有點奇怪，簡單來說就是特徵值小於z的樣本的權重和，佔所有樣本權重總和的百分比）。我們的目標是找到一個候選切分點（也就是說怎麼去劃分候選點的問題），可以根據下式進行侯選點的選取
（式15）
簡單的說（式15）表示落在兩個相鄰的候選切分點之間樣本佔比小於某個值
（很小的常數），那麼我們就有
個候選切分點。
由（式14）看的樣本是以二階導數作為加權考慮佔比的，那麼問題來了，為什麼使用二階導數作為加權呢？
對目標函式（式8）進行改寫，過程如下：
![L^{(t)}= \sum_{i=1}^{n}{[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]}+\Omega(f_{t})\\=\sum_{i=1}^{n}{\frac{1}{2}h_{i}[\frac{2g_{i}f_{t}(x_{i})}{h_{i}}+f_{t}^{2}(x_{i})]}+\Omega(f_{t}) \\=\sum_{i=1}^{n}{\frac{1}{2}h_{i}[\frac{2g_{i}f_{t}(x_{i})}{h_{i}}+f_{t}^{2}(x_{i})+\left( \frac{g_{i}}{h_{i}} \right)^2-\left( \frac{g_{i}}{h_{i}} \right)^2]}+\Omega(f_{t}) \\=\sum_{i=1}^{n}{\frac{1}{2}h_{i}\left[ f_{t}\left( x_{i} \right) -\left( -\frac{g_{i}}{h_{i}} \right)\right]^2}+\Omega(f_{t}) -\sum_{i=1}^{n}{\frac{1}{2}\frac{g_{i}^{2}}{h_{i}}}\\=\sum_{i=1}^{n}{\frac{1}{2}h_{i}\left[ f_{t}\left( x_{i} \right) -\left( -\frac{g_{i}}{h_{i}} \right)\right]^2}+\Omega(f_{t}) -constant （式16）](https://img.beesask.com/upload/website_attach/v-p-FTsHQqyWvwukt_64vw1BtU_ZvB4+=5Z-D4uO7XpesbR_E9HQA0EjOMAkqT0wJm9xHIdxM7xeeGe6s1RLA0EjlLHnZ_ehIUobnHdhKklZDMvbE9vTA05j=-ibSFC3AGudlb5hKklxDMvbE9lNlIjy7TBzMdD_AG=VPmMSC1Gf3ODn3JLC8Mfy7T9bSFBwAGudDe5hKkliDMvb4YyiIxN=OMldMd4jAGuI-qdBM79pfS6lE9vTvH1EG+H7Tc0F9J9xHIdwLL9kpTzX41vWA0CF=aibSFCEAGudPmLNC1GfDMHaE9ejA05zEw3ZKx0B8Smb--Y+C1u+DMHcE9vTs91EG+HxYX0F8x27=4shKk=4DMvbE9vTj91EGRpEMdDSvm9xHIdFLL9kpU3K31hiIxCT=-ibSFC3AGudlb5hKklxDMvbE9lNlIjy7TBzMdD_AG=VPmq_C1u64dyZfRD4A0EgOMldMdCSucPbn-MEC1u+DMHcE9vTj91EG+H7TEq9AGuIDMdBM79pfLLTreLC961TmpHUYFjzu5upPmLCsfPeeTDSE9vjA0CAP6HUYx0F8n9nHIdFLXdk52yZfRD4A06gTLHxZT0F9m9xGRBhKkoeeTlZfMelt-+VOMlIsc0B9J9xG8LhKkph16LUq_GiIxMy7GAbSfK=tSZ8PmqSRUuBDMvf58LC9UtqOMlIqT0B9J97oTk9C1u64LLUreLxJH1EG+HxYlq9AGuIDMdBM79Wq+LKq_3LA0EjF+HxZT0F9m9xG8LhKkoehr6w2JLC8-4y7T9bsZ3hj3=bnHSyss2xDMlwFJLA8VtTt3QbSFC14n9xGR+hKkoeeTpZfRD34p1EmQ2bSFLhIUohPmIilUWg4SpZipGiI21TSLHUYB2huyob-8x5C1Gf3ODn3JLC8-EqOMlInc0B9J9xHIdBLUKBDMvf58LC961EG+YbSfKwv5uyAIdw609kqMlZfMpiIxMyT1AbSfKUs5GP=Mdw6w2BDMvfseLC961TnLYbSfRhI0gb--YhK3dqv3RlE9vTvH1-GbdbSFLhI09bn-MOC1u+DMvfE9H_ugNwt6HxYZehIUobn-LwC1u+4dyZfRD4A0EgOM3coD4==J9UGqy=uq9WpOpZfRpiI26N=3v-MdBCBkKEPmqSt09Wq+kZfMexvvEHF+H7TcZzAGGcESI=D79pf+kXE9H_ugNwt6HxYlD9AGuIDMdBM79Wq+LUq_6LA0EjlLHxZT0B9JxbnHSwtsuhv+LK+8LA8WN0=Up-Md4_AGGe-qdBM79pppLTqRzguvEwOMAk7i_hIUl-Pmq_C1=YE6QZfMek=vxqOMlInc0x9dYbn-YhK39eeTDkE9vjA0EjOM3c72CV5n9xG8ihKkoeeTlKE9vjA05z=OBp6x0B8SuEPmqSt09Wq+LTr8LC8MCy7T9bSFLhIUlyt7dBLUmeeTpZfRpiIxMy7GQbSfRhjUobnHSxDsQBDMvf58Lk9ffy7T9bSf0hIUlWPmq_C1u6DMHa4CDW5p1EmrdbSFLhIU=7Pmq_tJPeeTDPE9vjA05zDR3RqT0F8rkRt7dBLhoeeTpZfMezuvt=OMAkmCq9AGuIDMdBM7xeeGeK51v3=61TnLYZMd4isTGRAIdw67xcDMHa4CDW5p1EmQlEMdDSvm9xHIdBM79WpQ6lE9vTvH1EG+HxZTZhI0d7D4q2D79pfLLTq-D4uVr=OM3dMd4jjr9xHIdwLL9kpTzX41vWA0CF=aibSFCEAGudPmLNNqQM5UU6sjaP=6a2P6YbZfvh83gbocxhM19ep1hZ+a2II95hGp3IYx0CJLVa7.jpeg)
（式16）可以看成權重 為
的label為
（ps：這個值比作者論文中多出一個負號，有文章說作者論文裡面少寫了負號。個人覺得這個正負號不是關注重點，它不是一種定量的計算，而是表示一種以二階導數作為加權的合理性說明。）的平方損失函式，其權重
則為二階導數。由此表明將二階導數作為樣本權重的考慮是合理的。
其他最佳化方法
稀疏值處理（Sparsity-aware Split Finding）。
實際工程中一般會出現輸入值稀疏的情況。比如資料的缺失、one-hot編碼都會造成輸入資料稀疏。論文中作者提出了關於稀疏值的處理，思路是：對於缺失資料讓模型自動學習預設的劃分方向。演算法具體的方法如下：
從演算法中可以看出，作者採用的是在每次的切分中，讓缺失值分別被切分到左節點以及右節點，透過計算得分值比較兩種切分方法哪一個更優，則會對每個特徵的缺失值都會學習到一個最優的預設切分方向。乍一看這個演算法會多出相當於一倍的計算量，但其實不是的。因為在演算法的迭代中只考慮了非缺失值資料的遍歷，缺失值資料直接被分配到左右節點，所需要遍歷的樣本量大大減小。
作者透過在Allstate-10K資料集上進行了實驗，從結果可以看到稀疏演算法比普通演算法在處理資料上快了超過50倍。
分塊並行(預排序)（Column Block for Parallel Learning）。
在樹生成過程中，需要花費大量的時間在特徵選擇與切分點選擇上，並且這部分時間中大部分又花費在了對特徵值得排序上。那麼怎麼樣減小這個排序時間開銷呢？
作者提出透過按特徵進行分塊並排序，在塊裡面儲存排序後的特徵值及對應樣本的引用，以便於獲取樣本的一階、二階導數值。具體方式如圖
：
透過順序訪問排序後的塊遍歷樣本特徵的特徵值，方便進行切分點的查詢。
此外分塊儲存後多個特徵之間互不干涉，可以使用多執行緒同時對不同的特徵進行切分點查詢，即特徵的並行化處理
。注意到，在順序訪問特徵值時，訪問的是一塊連續的記憶體空間，但透過特徵值持有的索引（樣本索引）訪問樣本獲取一階、二階導數時，這個訪問操作訪問的記憶體空間並不連續，這樣可能造成cpu快取命中率低，影響演算法效率。那麼怎麼解決這個問題呢？快取訪問
Cache-aware Access 。
快取訪問（Cache-aware Access）。
為了減小非連續記憶體的訪問帶來快取命中率低問題，作者提出了快取訪問最佳化機制。解決思路是：既然是非連續記憶體訪問帶來問題，那麼去掉非連續記憶體訪問就可以解決。那麼怎麼能去掉非連續記憶體空間的訪問呢？
轉非連續為連續----快取預取。
即提起將要訪問的非連續記憶體空間中的梯度統計資訊（一階、二階導數），放置到連續的記憶體空間中。
具體的操作上就是為每個執行緒在記憶體空間中分配一個連續的buffer快取區，將需要的梯度統計資訊存放在緩衝區中。這種方式對資料量大的時候很有用，因為大資料量時，不能把所有樣本都加入到記憶體中，因此可以動態的將相關資訊加入到記憶體中。
上圖給出了在Higgs資料集上使用快取訪問和不使用快取訪問的式樣對比。可以發現在資料量大的時候，基於精確的貪心演算法使用快取預取得處理速度幾乎是普通情況下的兩倍。那麼對於block塊應該選擇多大才合理呢？作者透過實驗證明選擇每個塊存放
個樣本時效率最高。
"核外"塊計算（Blocks for Out-of-core Computation）。
當資料量非常大的是時候我們不能把所有資料都載入記憶體中，因為裝不下。那麼就必須的將一部分需要載入進記憶體的資料先存放在硬碟中，當需要時在載入進記憶體。這樣操作具有很明顯的瓶頸，即硬碟的IO操作速度遠遠低於記憶體的處理速度，那麼肯定會存在大量等待硬碟IO操作的情況。針對這個問題作者提出了“核外”計算的最佳化方法。
具體操作為，將資料集分成多個塊存放在硬碟中，使用一個獨立的執行緒專門從硬碟讀取資料，載入到記憶體中，這樣演算法在記憶體中處理資料就可以和從硬碟讀取資料同時進行。
為了載入這個操作過程，作者提出了兩種方法。
塊壓縮
（
Block Compression
）。論文使用的是按列進行壓縮，讀取的時候用另外的執行緒解壓。對於行索引，只儲存第一個索引值，然後用16位的整數儲存與該block第一個索引的差值。作者透過測試在block設定為
個樣本大小時，壓縮比率幾乎達到26%
29%（貌似沒說使用的是什麼壓縮方法……。）。
塊分割槽
（
Block Sharding
）。塊分割槽是將特徵block分割槽存放在不同的硬碟上，以此來增加硬碟IO的吞吐量。
防止過擬合。
從XGBoost的模型上可以看到，為了防止過擬合加入了兩項懲罰項
、
，除此之外XGBoost還有另外兩個防止過擬合的方法。
1.學習率。
和GBDT一樣XGBoost也採用了學習率（步長）來防止過擬合，表現為：
，其中
就是學習率，通常取0。1。
2.行、列取樣。
和隨機森林一樣XGBoost支援對樣本以及特徵進行取樣，取取樣後的樣本和特徵作為訓練資料，進一步防止過擬合。