最近看了陳天奇老師的論文XGBoost: A Scalable Tree Boosting Sysem，寫個筆記整理一下思路。本文主要叙述算法idea以及自己的了解，不嚴謹的地方敬請諒解。如有錯誤歡迎指出，非常感謝！！（大三狗，并且本人對于工程方面不是很了解，主要記錄算法上面的内容，不會提及論文後半部分對于資料存儲系統的改進）
論文内容介紹
XGBoost可算是打比賽的一個網紅算法，如果去看Kaggle的Top排行榜，基本都是被XGBoost占領。它是目前最快最好的開源算法，比常見的工具包快10倍以上，并且很少有别的內建算法學習效果能比得過調好參數的XGBoost（不過因為參數過多，XGBoost對調參要求也很高orz）。在資料量日益增大的情況下，XGBoost既能快速處理大資料量，并且由于其為端到端的系統（基本不用資料預處理），使其一躍成為競賽寵兒。
論文主要貢獻大緻分為四個方面：
- 設計并建立可擴充的，端到端的提升樹系統。
- 提供有效且可理論證明的weighted quantile sketch來計算候選集。
- 介紹新穎的sparsity-aware algorithm來處理稀疏資料。
- 提出高效的cache-aware block structure用于外存樹學習。（涉及工程部分，暫不提及）
論文整體順序也是基于這四個方面依次展開。
算法總結
基本思路：通過殘差逼近思想拟合模型。
創新點：
- 通過泰勒二次展開，提高對目标函數的拟合精度。
- 定義正則化項，防止過拟合。
- 提供可理論驗證的‘分箱’方法，減輕決策樹分枝過程中周遊所有特征數值的負擔。
- 工程優化（考慮硬體問題），①通過特征提前排序，實作并行化計算，同時避免重複計算；②block compression，盡可能把資料儲存在記憶體中（記憶體讀取更快）；③block sharing，将block放到多個磁盤，增大磁盤帶寬，使讀取更快。
或許可以提升的point：
- 對缺失值的處理增加一些随機性。
- 疊代過程使用自适應步長。
提出問題
機器學習的問題一般可分為：回歸、分類、探索資料結構等。XGBoost是GBDT的改進版本，其每個基分類器是CART回歸樹，也就是解決
回歸問題的。當然，通過對回歸問題的處理，也可以擴充到分類問題。
由于是解決回歸問題，XGBoost的輸入和輸出都是一系列數值，并且由于其可對稀疏資料進行學習，我們唯一需要做的預處理就是對類别型變量進行轉換。（獨熱編碼等處理）
正如它的名稱，XGBoost屬于提升算法家族（boosting），是一個疊代過程，用來自适應地改變訓練樣本的分布。但是它的思想和家族另一成員Adaboost不同，Adaboost是在每一次提升結束時更新訓練樣本的權值，通過提高被錯誤分類樣本的權重，降低被正确分類樣本的權重，來使後面的分類器更關注那些被錯誤分類的樣本。而XGBoost的思想屬于提升樹，下一個分類器是對于上個分類器的殘差進行分類，即通過計算上個分類器的結果和正确答案的內插補點，将這個內插補點代入下個分類器進行計算。
個人認為boosting作為內建算法，就是召集一個團隊一起解決一個問題。而這兩種boosting的不同在于，Adaboost這個團隊中每個人做的事情都差不多，隻不過下一個人是基于他‘前輩’的經驗來做決策，前輩把他沒分出來的樣本告訴下一個人，這樣下一個人就能重點處理這些‘問題兒童’；而Gradient boosting團隊裡每個人都有自己擅長的一個方面，對于同一個問題，第一個人先處理一部分，得到一定成果（數值），但一個人力量不夠大，這個數值離最終目标還有一定距離，而這個‘距離’（殘差）就由後面的人來補上，最後團隊做出來的結果就是所有人成果的總和。
目标函數
任何模型的學習都依賴于目标函數。
上文我們有提到，梯度提升最終的結果是所有基分類器的總和，這就意味着XGBoost是采用
分步前向加性模型，我們的預測值
是所有基分類樹結果的總和。
假設我們樣本集D裡有n個樣本，m個特征，我們将這m個特征分别表示為
，則可以将樣本集寫為：
。
由于決策樹的效果是空間分塊，無法像線性回歸那樣，用固定參數表示目标函數，我們先用
來表示整個算法的效果，則我們的目标函數可以表示為：
這裡的f可以了解為對于一個輸入樣本，單個基CART回歸樹的輸出結果，即該樣本所處葉子節點權重。
（題外話：最開始看的時候糾結了很久這裡為什麼叫‘權重’，後來想了一下，回歸的本質就是自變量權重求和，應用到決策樹中也是相似，而決策樹能做到非線性邊界，隻是因為其在決策的時候将空間分了很多‘塊’，在每一塊内分别進行回歸權重，是以葉子節點的輸出相當于權重。另外還想到一種了解，在下文，進行泰勒展開後w就相當于對目标函數的一次導和二次導的權重。）
我們可以基于這個目标函數，
自己定義損失函數，XGBoost的可延展性的一個展現就在于此。隻要保證定義的損失函數是
二次可導即可，這是由于在後面求導過程中需要用到泰勒二次展開。（其實也可以多項展開的，但是考慮到運作速度以及系統優化，作者在此進行了權衡。）
損失函數
XGBoost的其中一個改進點在于其在損失函數中添加正則項，可有效防止過拟合。基于上文定義的目标函數
，我們可以用
來表示對于每個CART樹的損失函數，則算法的損失函數可表示為：
式中第二項即為正則項，T是該基回歸樹葉節點的數量，
就是每棵樹葉子節點的輸出權重的範數。正則項從基模型大小和其輸出結果兩個方面對整個模型進行懲罰。
（題外話：看到這裡我總是想到AIC和BIC，特别是BIC，同時通過模型複雜度和樣本數量兩個方面對模型進行衡量；這裡是通過模型複雜度（葉子節點數量）結合所有樣本點預測
進行懲罰。莫名有點既視感www）
這裡如果把正則項去掉，就是最原始的gradient tree boosting。
有了損失函數，我們就可以算梯度了。
這裡展現了XGBoost基于梯度樹的第二個改進點，
使用泰勒二次展開，使得預測函數f更快速、精确的逼近真實值。（梯度樹相當于一次展開）
由于提升樹是将所有輸出結果相加，并且我們之前提到了，這個團隊裡是‘每個人擅長的領域都不同’，也就是說每個人處理的問題其實是不一樣的，可以某種程度上抽象為每棵樹‘獨立’。（下一棵樹的輸入是上一棵樹的殘差，也就是說下一棵樹預測的結果是要等于這個內插補點，而不是真實标簽值）
我們在看第t棵樹的時候（第t次疊代），前（t-1）棵樹的結果都是已定的，并且和本次模組化‘無關’。是以我們隻需要使得加上這次結果後，損失函數能最有效的降低即可。第t次疊代可寫成：
可以發現就是前（t-1）次疊代結果
加上本次疊代結果
。
回顧一下泰勒二階展開：
這裡說一個我自己的了解：可以想象一下，整個boosting算法裡面是有很多棵樹的，并且由于我們加的正則之類的懲罰，每棵樹的影響力可以算是比較小的，而我們的預測值
是關于f的函數，那麼我們每次加入的f可以看做泰勒展開中的
。則
可展開為：
将展開結果寫進損失函數，可以得到：
具體關于為什麼目标函數關于目前模型的負梯度是殘差的近似，請參考這位大大：
梯度提升樹中為什麼說目标函數關于目前模型的負梯度是殘差的近似值？www.zhihu.com
由于前（t-1）次疊代都已經有結果了，損失函數第一項是個定值，對于我們最小化損失函數沒有影響，可以去掉以簡化計算，得到：
還記得正則項裡有
嗎？
把正則項拆開，将
和方括号内的
合并可得：
令
，求得最優權重為：
得到最優解了！！？？慢着
定睛一看怎麼有個下标
？？
作者這裡定義的
是本次疊代中生成的基分類樹在葉子節點j處樣本的集合，也就是說我們要知道本輪疊代生成的
樹的結構，才能知道此最優解。
列舉出所有可能生成的結構是不太可能的（這是個NP問題），我們需要用貪心算法找到盡可能好的分枝政策。根據預剪枝的原理，我們可以根據損失函數來衡量，分枝前後的效果，選擇效果最好的特征進行分枝。即每次嘗試分裂一個葉節點，根據分裂後的資訊增益（在這裡就是損失函數值）進行判斷。
套用一個圖：（查資料的時候順手存的，忘記出處了orz）
由于推導的時候使用了以上打分公式，并且引入了正則項，XGBoost就不需要剪枝操作了。（普通決策樹在生成的時候并不考慮樹的複雜度，是以才需要進行剪枝操作）
再發散一下思維，還有沒有其他方法進一步防止過拟合？（內建算法因為其自适應的改變訓練樣本的分布，天生容易引起過拟合，能避免就盡量避免）
XGBoost還提供兩種方式防止過拟合
- Shrinkage （相當于增加learning rate，進一步減小每棵樹的影響力）
- Column Subsampling （靈感來自随機森林的列采樣，每次都随機抽取部分特征考慮分枝，提高特征資訊使用率，還能加快選擇速度）
關于shrinkage我聯想到的一個可能改進的點在于自适應步長。（最近學微分方程用到的orz）
Adaboost對于每棵樹輸出值是有進行權重的，因為後面的樹更注重分錯的值，是以給它們加了更大的權重。XGBoost後面的樹是根據前面的樹的殘差建立，如果可以給前面的樹稍大一些的權值，後面的樹稍小一些的權值，能進一步提高精度。（不過本來自适應步長在微分方程那裡就很雞助...這裡如果用了說不定會進一步拖慢算法速度，是以應該隻是理論上可行吧www）
尋找分裂點
有了目标函數、損失函數、衡量分枝的Gain函數，要知道回歸樹的結構，我們還需要知道具體是根據哪個特征的哪個值進行分裂。（這也是樹算法中最關鍵以及最耗時耗力的一個步驟）
作者在文中提供了三種尋找分裂點的方式：
- 貪心周遊所有可分裂節點
- 等距找到一些候選分裂節點
- 通過二次導h，定義rank函數，通過對節點rank值排序，找出備選點
前兩個都是已經提出的做法，第三個是作者論文的主要貢獻之一。
貪心建樹政策就是周遊所有特征以及所有分裂點，每次去選最好的那個。分裂算法會對特征的所有值枚舉，但是對于數值型變量，可能取值的數量極其多，可以想象如果真的通過枚舉速度會非常慢。
一個自然的想法是通過離散化進行分箱，對分箱後産生的分位點進行判斷即可。但是對于如何分桶，以往的分位法通過排序或啟發式算法，沒有理論保證，但是由于XGBoost通過二次展開進行改進，使得分箱方法有了理論支撐。——
使用 樣本點具體的特征值對于我們分箱是沒有用的（在哪分裂主要是看分完後的節點純不純），那怎麼去衡量每個樣本對于損失函數減少的影響呢？
作者提出使用二階梯度衡量樣本點對損失函數減小的貢獻程度，并且不是使用等頻/等寬分箱，而是采用‘
等貢獻度分箱’。（沒有這個名詞，是我為了描述瞎編的...）
分箱思想裡的等頻/等寬分箱是出現在資料預進行中，希望的是每個桶的樣本個數相同，或值分布相同。但是這裡不是真的要做分箱呀！是為了更有效地分枝，也就是希望分完之後左右子樹能以大緻相同的程度一起降低loss。
為什麼使用二階導作為權重？
我們将損失函數進行變形：
關于具體怎麼分箱，作者提出了rank function
：
尋找分裂點
就可以通過以下過程進行描述：
這裡相當于找到
個備選點，使得備選點與備選點之間的
值之間的差距小于
。這樣處理之後，分枝的依據就可轉化為選擇
值最大的那個節點。
（題外話：隻使用一階導的時候相當于隻是根據殘差方向進行學習，引入二階導之後相當于通過‘殘差變化方向’對樣本點進行權重。讓變化快的人有機會跑的更遠，變化慢的人就留下來不要拖累團隊。）
分完箱，我們已經做到了‘weighted quantile’，但問題是作者提出來的算法是‘
Weighted Quantile Sketch’呀！sketch去哪了？
通過分箱離散後的資料，可以用
直方圖來觀察其分布。我們可以‘sketch’出該特征的直方圖，不需要導入全部資料即可完成近似。（這部分還沒有仔細研究，目前的宏觀image大概如下圖）
直方圖近似算法在周遊完所有特征之後，最後彙總所有特征的直方圖來尋找分裂點。這個算法有兩種實作，一種是
globa variant，在建立這棵樹之前先提出所有候選分裂，是以隻建立一次直方圖；另一種是
local variant，在分完枝之後都會重新繪制一次直方圖。
全局方法雖然隻畫一次圖比較友善，但是因為在每次分裂之後并沒有改善，需要較多的候選點才能保證和局部方法一樣準确。
處理稀疏資料
關于XGBoost端到端系統的一個重要展現，是它自帶對稀疏資料的學習。作者提出預設方向（default direction），讓算法學習當出現缺失資料的時候應該如何進行決策，省去我們提前對缺失資料進行處理。
算法實作過程很簡單：
- 讓該特征所有缺失值都到左子樹，對結果進行打分
- 讓該特征所有缺失值都到右子樹，對結果進行打分
哪個最終得分高，就讓缺失資料自己去哪邊~複雜度僅依賴于缺失資料量，還是很劃算的。
在這裡想到的一個改進點在于對預設方向加一些随機，讓其适當‘分錯’幾個缺失值，畢竟本來就沒有具體數值，這裡隻是模拟一個大分類方向。但是這樣改進隻有在缺失值較多才會有效果，缺失值少的時候隻是徒增複雜度而已orz
使用（持續更新）
推薦一個下載下傳方法
簡單到一步安裝 xgboost (Windows環境)blog.csdn.net
具體使用參考官方文檔
https://xgboost.readthedocs.io/en/latest/index.html#xgboost.readthedocs.io
--------------------------TBC--------------------------
- 第 1 次編輯（2020.5.27）
- 第 2 次編輯（2020.5.31）