超級女王XGBoost到底「絕」在哪裡？
全文共3492字，預計學習時長15分鐘
前幾天，Z同學面試完一臉生無可戀地問我，「你知道XGBoost嗎？」
「當然知道啊，前幾天不看你還在手推來著。」
「嗯，那你知道XGBoost的中英文全稱是啥么？」
「ummmmm...X的話難道是羅馬數字10? G的話Gradient梯度，Boost的Boosting tree？所以是第十代梯度提升樹？」
「。。。換你答，你也涼。」
學習演算法的最大誤區
還記得那個吐槽清華某畢業生連手寫紅黑樹都不會卻張口就要一萬八的HR嗎？
這事曾一度引起網友的廣泛關注和熱烈討論，不過圈子不同，影響不同。
對於普通吃瓜群眾，「HR說得對，太膨脹。」
對於某些資深程序猿，「我也不會，我月薪30k。」
對於求職小白，「好慌，手寫紅黑樹？面試不會還要手推SVM、XGBoost吧？溜了溜了，去推泰勒二次展開了。」
然後，就像我的同學小Z一樣，只顧著埋頭推導XGBoost的二階泰勒展開，卻連XGBoost的中英文全稱都答不上來。
顧此失彼，乃是兵家大忌。很多時候，我們在學習演算法時，要麼過於糾結弄懂原理而忽略了從宏觀上對演算法有一個總體的了解和把握，要麼是囫圇吞棗一口氣看個十來篇博客介紹卻往往還是一知半解不求甚解，可能還會莫名自我感覺良好。
基於此，本文就從宏觀上來幫大家梳理梳理XGBoost，力求通俗易懂，精準得當。至於演算法原理和資源鏈接嘛，請直接拜讀陳天奇博士的論文XGBoost: A Scalable Tree Boosting System，同時請參考Github上的開源資源進行源碼的學習和實戰（https://github.com/dmlc/xgboost）。
什麼是 XGBoost?
十幾年前，回歸建模是預測分析中毫無爭議的女王。但如今回歸建模的時代已經結束，XGBoost已被成功加冕！
XGBoost的英文全稱為Extreme Gradient Boosting, 中文可以解釋為極端梯度提升（Extreme，一聽就很牛X），它是一種基於決策樹的集成機器學習演算法，採用了梯度提升（Gradient Boosting）框架。在預測有關非結構化數據（如圖像、文本等）的問題時，人工神經網路往往表現得比其他演算法或框架更出色。但在有關中小型結構/表格數據方面，基於決策樹的演算法則是目前為止的最佳方式。
請參閱以下圖表，了解幾年來基於決策樹的演算法演變。
XGBoost演算法最初由華盛頓大學的一個研究項目發展而來。2016年，陳天奇和卡洛斯·格斯特林在知識發現和數據挖掘（SIGKDD）會議上共同發表了一篇論文，一時間這轟動了整個機器學習領域。
自演算法提出以來，它不僅幫助競賽者贏得了多場Kaggle競賽的勝利，還被幾款尖端行業的應用所採納。在GitHub上，有一群強大的數據科學家們為XGBoost開源項目提供幫助，約有350名科學家，總提交次數約為3,600次。總體而言，XGBoost具有以下特徵：
1. 應用廣泛：可用於解決回歸、分類、排名和用戶定義的預測問題。
2. 移植性強：可在Windows、Linux和OS X上流暢運行。
3. 語言支持：支持目前主要的全部編程語言，包括C ++、Python、R、Java、Scala和Julia。
4. 雲集成：支持AWS、GCE、Azure和 Yarn集群，可以與 Flink、Spark和其他雲數據流系統集成。
通俗理解基於決策樹的演算法演變
假設你是一名面試官，正在面試幾位資歷優秀的候選人。基於決策樹的演算法演變中的每一環，都可看作面試過程的一部分。
1. 決策樹：每名面試官都有一套面試評價標準，如教育水平、工作經驗以及面試表現，通過決策樹來預測分析，就類似於面試官根據他自己的標準面試候選人。
2. Bagging：假設現在面試官不止一名，而是一個面試小組，每名面試官都有一票，Bagging（也稱作bootstrap aggregating）意味著通過民主投票方式，將所有面試官的投票結果進行輸入，從而做出最終決定。
3. 隨機森林：這是一種基於bagging的演算法，與bagging的不同在於僅隨機選擇特徵的子集。換句話說，每名面試官只會根據某些隨機的資質測試方式（例如，測試編程技能的技術面試和非技術技能評估的行為面試）來考查面試者。
4. Boosting：這是一種動態評估方法，每位面試官根據前一位面試官的反饋，改變評估標準。通過部署更加動態的評估流程，「提高」面試流程的效率。
5. Gradient Boosting：這是Boosting的一種特殊情況，通過梯度下降演算法將誤差最小化，打個比方說，就好比戰略諮詢公司利用面試案例，剔除不合格的候選人。
6. XGBoost：將XGBoost視為強化版的的gradient boosting，畢竟extreme不是隨隨便便就能「冠」名的。它是軟體和硬體優化技術的完美結合，可在最短的時間內，使用較少的計算資源，得到較為出色的結果。
XGBoost為什麼這麼「絕」？
XGBoost之所以能叫XGBoost，因為她夠「絕」（夠Extreme）。
XGBoost和Gradient Boosting Machines（GBMs）都是基於決策樹的集合方法，通過梯度下降架構來提升較弱學習者（通常是CARTs）。通過系統優化和演算法增強，XGBoost進一步改進了基礎GBM框架。
系統優化：
1. 並行化：XGBoost通過多線程實現了回歸樹的並行構建。由於用於構建基礎學習者的循環具有可互換性，因此設計並行是可能的。外部循環枚舉樹的節點，內部循環則計算特徵。這種循環嵌套在一定程度上限制了並行化，當沒有完成內部循環，外部循環就無法啟動。
因此，為改善運行時間，可通過對所有實例的全局掃描實現初始化，使用並行線程分類來交換循環順序。這一交換通過抵消計算中的並行化開銷，提高演算法性能。
2. 決策樹剪枝：當剪枝分裂遇到一個負損失時，GBM會停止分裂。因此GBM實際上是一個貪心演算法（只求達到局部最優解就ok）。但XGBoost會一直分裂到指定的最大深度(max_depth)，然後回過頭來剪枝。這種「深度優先」方法顯著提高了計算性能。
3.硬體優化：該演算法旨在有效利用硬體資源。通過在每個線程中分配內部緩衝區，存儲梯度統計信息，獲取緩存感知。諸如「核外」計算等進一步增強功能可優化可用磁碟空間，同時處理不適合保存的大數據幀。
演算法增強：
1. 正則化：通過LASSO（L1）和Ridge（L2）正則化來對更為複雜的模型進行懲罰，防止過度擬合。
2. 稀疏性感知：XGBoost具有稀疏性的離散特徵，根據訓練缺失自動「學習」最佳缺失值，並且可以更有效率地處理數據中不同類型的稀疏模式。
3. 加權分位數草圖：XGBoost採用分散式加權分位數草圖演算法，有效地找到加權數據集中的最佳分裂點。
4. 交叉驗證：在每次迭代時，該演算法都有內置的交叉驗證方法，無需顯式地對搜索進行編程或明確在指定單次運行中所需的增強迭代數量。
有何證據？
我們使用Scikit-learn的「Make_Classification」數據包創建了一個包含20類特徵（2類信息型和2類冗餘型）的100萬個數據點的隨機樣本。我們測試了幾種演算法，如邏輯回歸、隨機森林、標準Gradient Boosting和XGBoost。
使用SKLearn的Make_Classification數據集比較XGBoos與其他機器學習演算法
如上圖所示，與其他演算法相比，XGBoost模型是兼顧預測性能和處理時間的最佳預測方式。其他嚴格的基準研究也產生相同結果。正因如此，XGBoost在最近的數據科學競賽中被廣泛使用。
如有疑問，請使用XGBoost。——Kaggle網站上Avito Context Ad Click Prediction競賽的獲獎者OwenZhang
XGBoost的未來
儘管就目前而言，XGBoost的王座還難以撼動。但機器學習這一領域的學者大都比較活躍，而且不畏權貴，一心戀戰。
目前已有幾種據說可以匹敵XGBoost的新演算法框架被提出，比如微軟研究中心新發布的LightGBM框架和Yandex Technology開發的CatBoost框架。
每當NIPS/ICML/KDD等頂級會議上一有新的演算法被提出，最忙活的可能就是數據科學家了。數據科學家們必須測試所有可能的數據演算法，以保證最終選擇的演算法是最佳的。此外，選擇正確的演算法還遠遠不夠，還必須通過不斷調整超參數，正確對演算法數據集進行配置。
此外，如何選擇最佳的演算法還有其他幾個值得考慮的因素，例如演算法的計算複雜度、可解釋性以及實現的難易程度。而這正是機器學習開始從科學走向藝術的時刻。
歷史的車輪總是在不斷向前滾動。XGBoost的鐵王座早就被許多人覬覦垂涎，開發一個優於XGBoost的更強大的模型框架只是時間上的早晚問題。
然而，在強大的挑戰者出現之前，XGBoost將繼續統治機器學習的世界！
留言 點贊 關注
我們一起分享AI學習與發展的乾貨
歡迎關注全平台AI垂類自媒體 「讀芯術」
推薦閱讀：
