XGBoost號(hào)稱“比賽奪冠的必備大殺器”，橫掃機(jī)器學(xué)習(xí)競(jìng)賽罕逢敵手

XGBoost號(hào)稱“比賽奪冠的必備大殺器”，橫掃機(jī)器學(xué)習(xí)競(jìng)賽罕逢敵手，堪稱機(jī)器學(xué)習(xí)算法中的新女王！

在涉及非結(jié)構(gòu)化數(shù)據(jù)（圖像、文本等）的預(yù)測(cè)問(wèn)題中，人工神經(jīng)網(wǎng)絡(luò)顯著優(yōu)于所有其他算法或框架。但當(dāng)涉及到中小型結(jié)構(gòu)/表格數(shù)據(jù)時(shí)，基于決策樹的算法現(xiàn)在被認(rèn)為是最佳方法。而基于決策樹算法中最驚艷的，非XGBoost莫屬了。

打過(guò)Kaggle、天池、DataCastle、Kesci等國(guó)內(nèi)外數(shù)據(jù)競(jìng)賽平臺(tái)之后，一定對(duì)XGBoost的威力印象深刻。XGBoost號(hào)稱“比賽奪冠的必備大殺器”，橫掃機(jī)器學(xué)習(xí)競(jìng)賽罕逢敵手。最近甚至有一位大數(shù)據(jù)/機(jī)器學(xué)習(xí)主管被XGBoost在項(xiàng)目中的表現(xiàn)驚艷到，盛贊其為“機(jī)器學(xué)習(xí)算法中的新女王”！

XGBoost最初由陳天奇開發(fā)。陳天奇是華盛頓大學(xué)計(jì)算機(jī)系博士生，研究方向?yàn)榇笠?guī)模機(jī)器學(xué)習(xí)。他曾獲得KDD CUP 2012 Track 1第一名，并開發(fā)了SVDFeature，XGBoost，cxxnet等著名機(jī)器學(xué)習(xí)工具，是Distributed (Deep) Machine Learning Common的發(fā)起人之一。

XGBoost實(shí)現(xiàn)了高效、跨平臺(tái)、分布式gradient boosting (GBDT, GBRT or GBM) 算法的一個(gè)庫(kù)，可以下載安裝并應(yīng)用于C++，Python，R，Julia，Java，Scala，Hadoop等。目前Github上超過(guò)15700星、6500個(gè)fork。

項(xiàng)目主頁(yè)：

https://XGBoost.ai/

XGBoost是什么

XGBoost全稱：eXtreme Gradient Boosting，是一種基于決策樹的集成機(jī)器學(xué)習(xí)算法，使用梯度上升框架，適用于分類和回歸問(wèn)題。優(yōu)點(diǎn)是速度快、效果好、能處理大規(guī)模數(shù)據(jù)、支持多種語(yǔ)言、支持自定義損失函數(shù)等，不足之處是因?yàn)閮H僅推出了不足5年時(shí)間，需要進(jìn)一步的實(shí)踐檢驗(yàn)。

XGBoost選用了CART樹，數(shù)學(xué)公式表達(dá)XGBoost模型如下：

K是樹的數(shù)量，F(xiàn)表示所有可能的CART樹，f表示一棵具體的CART樹。這個(gè)模型由K棵CART樹組成。

模型的目標(biāo)函數(shù)，如下所示：

XGBoost具有以下幾個(gè)特點(diǎn)：

靈活性：支持回歸、分類、排名和用戶定義函數(shù)

跨平臺(tái)：適用于Windows、Linux、macOS，以及多個(gè)云平臺(tái)

多語(yǔ)言：支持C++, Python, R, Java, Scala, Julia等

效果好：贏得許多數(shù)據(jù)科學(xué)和機(jī)器學(xué)習(xí)挑戰(zhàn)。用于多家公司的生產(chǎn)

云端分布式：支持多臺(tái)計(jì)算機(jī)上的分布式訓(xùn)練，包括AWS、GCE、Azure和Yarn集群?？梢耘cFlink、Spark和其他云數(shù)據(jù)流系統(tǒng)集成

下圖顯示了基于樹的算法的發(fā)展歷程：

決策樹：由一個(gè)決策圖和可能的結(jié)果（包括資源成本和風(fēng)險(xiǎn)）組成， 用來(lái)創(chuàng)建到達(dá)目標(biāo)的規(guī)劃。

Bagging：是一種集合元算法，通過(guò)多數(shù)投票機(jī)制將來(lái)自多決策樹的預(yù)測(cè)結(jié)合起來(lái)，也就是將弱分離器 f_i(x) 組合起來(lái)形成強(qiáng)分類器 F(x) 的一種方法

隨機(jī)森林：基于Bagging算法。隨機(jī)選擇一個(gè)包含多種特性的子集來(lái)構(gòu)建一個(gè)森林，或者決策樹的集合

Boosting：通過(guò)最小化先前模型的誤差，同時(shí)增加高性能模型的影響，順序構(gòu)建模型

梯度上升：對(duì)于似然函數(shù)，要求最大值，叫做梯度上升

XGBoost：極端梯度上升，XGBoost是一個(gè)優(yōu)化的分布式梯度上升庫(kù)，旨在實(shí)現(xiàn)高效，靈活和跨平臺(tái)

為什么XGBoost能橫掃機(jī)器學(xué)習(xí)競(jìng)賽平臺(tái)？

下圖是XGBoost與其它gradient boosting和bagged decision trees實(shí)現(xiàn)的效果比較，可以看出它比R, Python，Spark，H2O的基準(zhǔn)配置都快。

XGBoost和Gradient Boosting Machines（GBMs）都是集合樹方法，使用梯度下降架構(gòu)來(lái)提升弱學(xué)習(xí)者（通常是CART）。而XGBoost通過(guò)系統(tǒng)優(yōu)化和算法增強(qiáng)改進(jìn)了基礎(chǔ)GBM框架，在系統(tǒng)優(yōu)化和機(jī)器學(xué)習(xí)原理方面都進(jìn)行了深入的拓展。

系統(tǒng)優(yōu)化：

并行計(jì)算：

由于用于構(gòu)建base learners的循環(huán)的可互換性，XGBoost可以使用并行計(jì)算實(shí)現(xiàn)來(lái)處理順序樹構(gòu)建過(guò)程。

外部循環(huán)枚舉樹的葉節(jié)點(diǎn)，第二個(gè)內(nèi)部循環(huán)來(lái)計(jì)算特征，這個(gè)對(duì)算力要求更高一些。這種循環(huán)嵌套限制了并行化，因?yàn)橹灰獌?nèi)部循環(huán)沒(méi)有完成，外部循環(huán)就無(wú)法啟動(dòng)。

因此，為了改善運(yùn)行時(shí)，就可以讓兩個(gè)循環(huán)在內(nèi)部交換循環(huán)的順序。此開關(guān)通過(guò)抵消計(jì)算中的所有并行化開銷來(lái)提高算法性能。

Tree Pruning：

GBM框架內(nèi)樹分裂的停止標(biāo)準(zhǔn)本質(zhì)上是貪婪的，取決于分裂點(diǎn)的負(fù)損失標(biāo)準(zhǔn)。XGBoost首先使用'max_depth'參數(shù)而不是標(biāo)準(zhǔn)，然后開始向后修剪樹。這種“深度優(yōu)先”方法顯著的提高了計(jì)算性能。

硬件優(yōu)化：

該算法旨在有效利用硬件資源。這是通過(guò)在每個(gè)線程中分配內(nèi)部緩沖區(qū)來(lái)存儲(chǔ)梯度統(tǒng)計(jì)信息來(lái)實(shí)現(xiàn)緩存感知來(lái)實(shí)現(xiàn)的。諸如“核外”計(jì)算等進(jìn)一步增強(qiáng)功能可優(yōu)化可用磁盤空間，同時(shí)處理不適合內(nèi)存的大數(shù)據(jù)幀。

算法增強(qiáng)：

正則化：

它通過(guò)LASSO（L1）和Ridge（L2）正則化來(lái)懲罰更復(fù)雜的模型，以防止過(guò)擬合。

稀疏意識(shí)：

XGBoost根據(jù)訓(xùn)練損失自動(dòng)“學(xué)習(xí)”最佳缺失值并更有效地處理數(shù)據(jù)中不同類型的稀疏模式。

加權(quán)分位數(shù)草圖：

XGBoost采用分布式加權(quán)分位數(shù)草圖算法，有效地找到加權(quán)數(shù)據(jù)集中的最優(yōu)分裂點(diǎn)。

交叉驗(yàn)證：

該算法每次迭代時(shí)都帶有內(nèi)置的交叉驗(yàn)證方法，無(wú)需顯式編程此搜索，并可以指定單次運(yùn)行所需的增強(qiáng)迭代的確切數(shù)量。

為了測(cè)試XGBoost到底有多快，可以通過(guò)Scikit-learn的'Make_Classification'數(shù)據(jù)包，創(chuàng)建一個(gè)包含20個(gè)特征（2個(gè)信息和2個(gè)冗余）的100萬(wàn)個(gè)數(shù)據(jù)點(diǎn)的隨機(jī)樣本。

下圖為邏輯回歸，隨機(jī)森林，標(biāo)準(zhǔn)梯度提升和XGBoost效率對(duì)比：