江佳偉,符芳誠(chéng),邵鎣俠,崔 斌

1(高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(北京大學(xué)),北京 100871)

2(北京郵電大學(xué) 計(jì)算機(jī)學(xué)院,北京 100876)

梯度提升樹(gradient boosting decision tree,簡(jiǎn)稱 GBDT)是一種使用 Boosting策略的集成機(jī)器學(xué)習(xí)算法.集成機(jī)器學(xué)習(xí)算法通常使用Bagging,Boosting,AdBoost等策略[1,2],基本思想是訓(xùn)練多個(gè)弱分類器來生成更準(zhǔn)確的結(jié)果.GBDT使用的 Boosting策略通過依次學(xué)習(xí)多個(gè)弱學(xué)習(xí)器不斷地提升性能,梯度提升樹使用樹模型作為弱學(xué)習(xí)器.梯度提升樹算法在分類、回歸、排序等諸多問題上取得了優(yōu)異的性能[3-5],在學(xué)術(shù)界和工業(yè)界中被廣泛地使用[6],也是例如Kaggle等數(shù)據(jù)競(jìng)賽中最受歡迎的算法之一.在大數(shù)據(jù)時(shí)代,由于單機(jī)的計(jì)算能力和存儲(chǔ)能力有限,無法有效地處理動(dòng)輒達(dá)到TB甚至PB級(jí)別的數(shù)據(jù),因而需要在分布式環(huán)境下設(shè)計(jì)和執(zhí)行梯度提升樹算法,分布式梯度提升樹算法因而成為目前的研究熱點(diǎn).

梯度提升樹算法的訓(xùn)練主要包括3個(gè)關(guān)鍵過程.

1) 建立梯度直方圖.對(duì)于給定的損失函數(shù),對(duì)輸入的訓(xùn)練數(shù)據(jù),計(jì)算它們的梯度,將所有的梯度數(shù)據(jù)組織成梯度直方圖的數(shù)據(jù)結(jié)構(gòu);

2) 尋找最佳分裂點(diǎn).根據(jù)建立的所有特征的梯度直方圖,計(jì)算出樹節(jié)點(diǎn)的最佳分裂點(diǎn),包括特征和分裂特征值;

3) 分裂樹節(jié)點(diǎn).根據(jù)計(jì)算出的最佳分裂點(diǎn)來分裂樹節(jié)點(diǎn),建立子節(jié)點(diǎn),根據(jù)分裂點(diǎn)將訓(xùn)練數(shù)據(jù)劃分到子節(jié)點(diǎn)上,并回到步驟1)開始下一輪迭代.

在分布式環(huán)境下設(shè)計(jì)機(jī)器學(xué)習(xí)算法,有數(shù)據(jù)并行和特征并行兩種策略:數(shù)據(jù)并行將訓(xùn)練數(shù)據(jù)集按行進(jìn)行切分,每個(gè)計(jì)算節(jié)點(diǎn)處理一部分?jǐn)?shù)據(jù)子集;而特征并行將訓(xùn)練數(shù)據(jù)集按列進(jìn)行切分,每個(gè)計(jì)算節(jié)點(diǎn)處理一部分特征子集.已有的分布式梯度提升樹系統(tǒng),例如MLlib[7],XGBoost[8],LightGBM[9,10]等,通常使用數(shù)據(jù)并行策略在分布式環(huán)境下訓(xùn)練.目前,沒有工作系統(tǒng)性地比較數(shù)據(jù)并行和特征并行策略的優(yōu)劣,數(shù)據(jù)并行是否在所有情況下都能取得最佳的性能,是一個(gè)仍然未被討論和解決的問題.

筆者發(fā)現(xiàn),在多種情況下,采用數(shù)據(jù)并行的分布式梯度提升樹算法會(huì)遇到性能瓶頸:一方面,在梯度提升樹算法所處理的多種問題中,多分類問題由于較高的計(jì)算復(fù)雜度和空間復(fù)雜度,采用數(shù)據(jù)并行的梯度提升樹算法目前無法在分布式環(huán)境下有效地處理;另一方面,隨著各行業(yè)的飛速發(fā)展,數(shù)據(jù)的來源越來越多,因而數(shù)據(jù)集的特征維度越來越高,這樣的高維特征給數(shù)據(jù)并行的梯度提升樹算法帶來了新的挑戰(zhàn).為了解決以上存在的問題,本文關(guān)注在高維特征和多分類問題下如何高效地訓(xùn)練分布式梯度提升樹算法.

在分布式環(huán)境下訓(xùn)練梯度提升樹算法時(shí),數(shù)據(jù)并行和特征并行采用不同的方式:數(shù)據(jù)并行策略將訓(xùn)練數(shù)據(jù)集按行切分到計(jì)算節(jié)點(diǎn),計(jì)算節(jié)點(diǎn)建立局部梯度直方圖,然后通過網(wǎng)絡(luò)匯總計(jì)算節(jié)點(diǎn)的局部梯度直方圖;特征并行策略將訓(xùn)練數(shù)據(jù)集按列切分到計(jì)算節(jié)點(diǎn),計(jì)算節(jié)點(diǎn)建立梯度直方圖并計(jì)算出最佳分裂點(diǎn),然后通過網(wǎng)絡(luò)交換分裂結(jié)果.由于梯度直方圖的大小與特征數(shù)量和類別數(shù)量成正比,對(duì)于高維和多分類問題,數(shù)據(jù)并行需要通過網(wǎng)絡(luò)傳輸大量的梯度直方圖,因而存在性能不佳的問題.相比之下,特征并行需要通過網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)只與數(shù)據(jù)量大小有關(guān),因而更適合高維和多分類的場(chǎng)景.

為了使用梯度提升樹算法高效地求解高維和多分類問題,本文提出了一種基于特征并行的梯度提升樹算法FP-GBDT.通過從理論上比較數(shù)據(jù)并行和特征并行,本文證明特征并行更適合高維和多分類場(chǎng)景,然后設(shè)計(jì)了特征并行的分布式梯度提升樹算法.本文的貢獻(xiàn)可以總結(jié)如下:在提出代價(jià)模型的基礎(chǔ)上,從理論上比較了數(shù)據(jù)并行和特征并行兩種訓(xùn)練策略的開銷,證明對(duì)于高維和多分類數(shù)據(jù)集,特征并行具有較小的網(wǎng)絡(luò)開銷、內(nèi)存開銷和可擴(kuò)展性;提出了基于特征并行的分布式梯度提升樹算法FP-GBDT.首先,設(shè)計(jì)了一種分布式矩陣轉(zhuǎn)置方法轉(zhuǎn)換數(shù)據(jù)表征;然后,在建立梯度直方圖時(shí)使用了稀疏感知的方法;最后,在分裂樹節(jié)點(diǎn)時(shí)提出了比特圖壓縮方法來減少數(shù)據(jù)傳輸;通過與現(xiàn)有分布式梯度提升樹算法進(jìn)行詳盡的實(shí)驗(yàn)比較,證明了FP-GBDT算法的高效性.

本文第 1節(jié)介紹梯度提升樹算法的預(yù)備知識(shí)和相關(guān)工作,包括算法模型和訓(xùn)練方法.第 2節(jié)從理論上比較數(shù)據(jù)并行和特征并行的開銷.第3節(jié)介紹FP-GBDT算法的細(xì)節(jié).第4節(jié)給出實(shí)驗(yàn)對(duì)比結(jié)果.第5節(jié)總結(jié)全文.

1 預(yù)備知識(shí)及相關(guān)工作

在本節(jié)中,主要介紹研究對(duì)象梯度提升樹算法的模型和訓(xùn)練方法.其中,第 1.1節(jié)介紹數(shù)據(jù)集表征,第 1.2節(jié)簡(jiǎn)要介紹梯度提升樹算法,第1.3節(jié)介紹梯度提升樹的訓(xùn)練方法,第1.4節(jié)介紹分布式梯度提升樹的研究進(jìn)展.

1.1 輸入數(shù)據(jù)集

1.2 梯度提升樹算法概述

梯度提升樹算法是基于樹的集成機(jī)器學(xué)習(xí)方法[8],梯度提升樹算法會(huì)依次訓(xùn)練多個(gè)回歸樹模型.在一棵樹中,從根節(jié)點(diǎn)開始,每個(gè)樹節(jié)點(diǎn)需要給出一個(gè)分裂規(guī)則,此分裂規(guī)則包括分裂特征和分裂特征值,根據(jù)分裂規(guī)則將數(shù)據(jù)樣本切分到下一層的子樹節(jié)點(diǎn),最終,每個(gè)數(shù)據(jù)樣本xi被分配到一個(gè)葉子節(jié)點(diǎn),葉子節(jié)點(diǎn)將其上的數(shù)據(jù)樣本預(yù)測(cè)為w.與決策樹不同之處在于:梯度提升樹的葉子節(jié)點(diǎn)給出的是連續(xù)值,而不是類別,在訓(xùn)練完一棵樹之后,將w加到每個(gè)數(shù)據(jù)樣本的預(yù)測(cè)值上,然后以新的預(yù)測(cè)值開始訓(xùn)練下一棵樹.梯度提升樹累加所有樹的預(yù)測(cè)值作為最終的預(yù)測(cè)值[1]:

其中,T是樹的數(shù)量,ft(xi)是第t棵樹的預(yù)測(cè)結(jié)果,η是一個(gè)叫學(xué)習(xí)速度的超參數(shù).

圖1展示了梯度提升樹算法的例子,目的是預(yù)測(cè)一個(gè)購(gòu)物網(wǎng)站上用戶的消費(fèi)能力.

Fig.1 An example of gradient boosting decision tree圖1 梯度提升樹算法示例

第1棵樹使用年齡是否小于20和工資是否小于5 000作為分裂規(guī)則,得到第1棵樹的預(yù)測(cè)值,并以此更新數(shù)據(jù)樣本的預(yù)測(cè)值;接著,以新的預(yù)測(cè)值開始訓(xùn)練第2棵樹,第2棵樹以是否為男性作為分裂規(guī)則,得到第2棵樹的預(yù)測(cè)值.最終的預(yù)測(cè)值為兩棵樹的預(yù)測(cè)值之和,例如,標(biāo)識(shí)為“/”的用戶,預(yù)測(cè)值為5加上5,等于10.

1.3 訓(xùn)練方法

梯度提升樹算法是有監(jiān)督機(jī)器學(xué)習(xí)算法,其目標(biāo)是最小化一個(gè)目標(biāo)函數(shù),對(duì)于梯度提升樹來說,在建立第t棵樹時(shí),需要最小化以下的代價(jià)函數(shù):

這里,l對(duì)于真實(shí)值和預(yù)測(cè)值給出損失,例如,logistic損失,square損失.Ω是正則項(xiàng),可以避免過擬合.依照XGBoost的選擇[8],選擇如下的正則項(xiàng):

L是樹中葉子節(jié)點(diǎn)的數(shù)量,w是葉子節(jié)點(diǎn)的預(yù)測(cè)值組成的向量,γ和λ是超參數(shù).LogitBoost算法用二階近似來擴(kuò)展F(t):

這里,gi和hi是數(shù)據(jù)的一階和二階梯度:.用Ij={i|xi∈leafj}代表屬于第j個(gè)葉子節(jié)點(diǎn)的數(shù)據(jù)樣本的集合,去掉常數(shù)項(xiàng)之后,可以得到F(t)的近似表達(dá):

根據(jù)以上的公式,第j個(gè)葉子節(jié)點(diǎn)的最佳預(yù)測(cè)值和最佳目標(biāo)函數(shù)是:

以上的結(jié)果假設(shè)已經(jīng)知道樹的結(jié)構(gòu)和數(shù)據(jù)樣本的分布,可以遍歷所有可能的樹結(jié)構(gòu)和數(shù)據(jù)樣本分布來找到最佳的解.但是這種方法的計(jì)算復(fù)雜度太高,在實(shí)際中不可行.因此,現(xiàn)有的方法采用一種貪心的方法,從根節(jié)點(diǎn)開始逐層地分裂樹節(jié)點(diǎn),見算法1.

算法1.訓(xùn)練梯度提升樹的貪心分裂算法.

輸出增益最大的分裂結(jié)果

在計(jì)算一個(gè)樹節(jié)點(diǎn)的最佳分裂點(diǎn)時(shí),首先對(duì)每個(gè)特征計(jì)算出K個(gè)候選分裂點(diǎn),然后掃描一遍所有數(shù)據(jù)樣本,用梯度數(shù)據(jù)建立梯度直方圖.例如:Gmk對(duì)應(yīng)第m個(gè)特征,累加所有對(duì)應(yīng)特征值處在第k-1和第k個(gè)候選分裂點(diǎn)之間的數(shù)據(jù)樣本的一階梯度;Hmk以同樣的方式累加二階梯度.建立完所有特征的梯度直方圖之后,根據(jù)下面公式找到代價(jià)函數(shù)增益最大的分裂結(jié)果:

這里,IL和IR代表分裂之后的左子節(jié)點(diǎn)和右子節(jié)點(diǎn).選擇候選分裂點(diǎn)有多種方式,精確的方法依據(jù)每個(gè)特征對(duì)所有數(shù)據(jù)樣本進(jìn)行排序,然后選擇所有可能的分裂點(diǎn).但這種方法需要反復(fù)地排序,在數(shù)據(jù)量很大時(shí),計(jì)算開銷和時(shí)間開銷過于昂貴.另外一種叫分位數(shù)據(jù)草圖的方法使用基于概率的近似數(shù)據(jù)結(jié)構(gòu),對(duì)每個(gè)特征產(chǎn)生對(duì)應(yīng)特征值的近似分布[11].經(jīng)典的分位數(shù)據(jù)草圖的算法是GK[12],基于GK的變種有DataSketches[13]和WQS[8]等.

梯度提升樹算法中,兩種避免過擬合的方法是衰減和特征下采樣:衰減方法在累加樹的預(yù)測(cè)值時(shí)乘以一個(gè)叫做學(xué)習(xí)速度的超參數(shù)η;特征下采樣方法對(duì)每棵樹采樣一個(gè)特征子集,這種方法被證明能夠加快訓(xùn)練速度和提高模型的泛化能力.

1.4 分布式訓(xùn)練

目前已經(jīng)有一些研究工作提出了分布式梯度提升樹算法,例如 XGBoost[8],LightGBM[10],TencentBoost[14],DimBoost[18]等.XGBoost由華盛頓大學(xué)的研究者提出,采用數(shù)據(jù)并行的訓(xùn)練模式,在單個(gè)計(jì)算節(jié)點(diǎn)上將數(shù)據(jù)集按列切分,以列存塊的形式存儲(chǔ)數(shù)據(jù)樣本,為每個(gè)特征值增加一個(gè)指針指向其屬于的數(shù)據(jù)樣本,這樣帶來了很大的額外內(nèi)存開銷.XGBoost提出了一系列的優(yōu)化方法,包括一種對(duì)數(shù)據(jù)加權(quán)的分位數(shù)據(jù)草圖算法、一種稀疏感知的尋找分裂點(diǎn)算法、一種將列存塊存儲(chǔ)到磁盤的塊壓縮和塊切分的算法.LightGBM由微軟亞洲研究院的研究者提出,默認(rèn)采用數(shù)據(jù)并行的訓(xùn)練模式,提出了深度優(yōu)先的策略.實(shí)驗(yàn)證明,這能夠提高準(zhǔn)確率.除了數(shù)據(jù)并行之外,LightGBM 也實(shí)現(xiàn)了特征并行.但是這個(gè)簡(jiǎn)單的實(shí)現(xiàn)不支持?jǐn)?shù)據(jù)集按列切分,需要在每個(gè)計(jì)算節(jié)點(diǎn)上存儲(chǔ)完整的數(shù)據(jù)集,這在超大規(guī)模數(shù)據(jù)和真實(shí)的工業(yè)界環(huán)境中是不可行的.TencentBoost和DimBoost由北京大學(xué)和騰訊聯(lián)合設(shè)計(jì),采用數(shù)據(jù)并行的訓(xùn)練模式,利用參數(shù)服務(wù)器[16-18]架構(gòu)分布式存儲(chǔ)算法模型,以支持高維度的數(shù)據(jù)集,在建立梯度直方圖階段提出了稀疏感知的算法,只需要讀取數(shù)據(jù)樣本中的非零特征;同時(shí),用高效的并行機(jī)制加速梯度直方圖的建立,在尋找最佳分裂點(diǎn)階段提出了量化壓縮算法減少梯度數(shù)據(jù)的傳輸.針對(duì)參數(shù)服務(wù)器的特殊架構(gòu)提出了兩階段的方法,在參數(shù)服務(wù)器端計(jì)算局部最佳分裂點(diǎn),在計(jì)算節(jié)點(diǎn)端匯總得到全局最佳分裂點(diǎn).可以看到,目前的分布式梯度提升樹算法的系統(tǒng)基本都采用數(shù)據(jù)并行的訓(xùn)練方式,或者實(shí)現(xiàn)的特征并行方式在實(shí)際中不可行,不能有效地處理本文針對(duì)的高維特征和多分類問題.

2 并行策略比較

將一個(gè)串行的機(jī)器學(xué)習(xí)算法并行化,首先需要設(shè)計(jì)如何將數(shù)據(jù)樣本在多個(gè)計(jì)算節(jié)點(diǎn)之間分配.常用的并行策略包括數(shù)據(jù)并行和特征并行.假設(shè)訓(xùn)練數(shù)據(jù)集是一個(gè)矩陣,每一行是一個(gè)數(shù)據(jù)樣本,數(shù)據(jù)并行按行切分?jǐn)?shù)據(jù)集,這樣,每個(gè)計(jì)算節(jié)點(diǎn)負(fù)責(zé)一個(gè)數(shù)據(jù)子集.與此相對(duì)應(yīng)的,特征并行按列切分?jǐn)?shù)據(jù)集,每個(gè)計(jì)算節(jié)點(diǎn)負(fù)責(zé)一個(gè)特征子集.

本節(jié)將針對(duì)內(nèi)存開銷和網(wǎng)絡(luò)開銷兩個(gè)方面,從理論上比較運(yùn)用兩種并行策略的分布式梯度提升樹算法,并針對(duì)本文研究的高維和多分類問題選擇合適的并行策略.為了形式化地描述結(jié)果,本文中用到的符號(hào)定義見表1,其中,訓(xùn)練數(shù)據(jù)集是一個(gè)N×D的矩陣,N是數(shù)據(jù)樣本的數(shù)量,D是數(shù)據(jù)樣本的特征數(shù)量;集群中有W個(gè)計(jì)算節(jié)點(diǎn),梯度提升樹模型包含T棵樹,每棵樹有L層,每個(gè)特征的候選分裂點(diǎn)的個(gè)數(shù)是q;對(duì)于多分類問題,用C來表示類別數(shù)量.

Table 1 Definition of symbols表1 符號(hào)定義

2.1 梯度直方圖大小

梯度提升樹算法的核心操作是建立梯度直方圖和尋找分裂點(diǎn).梯度直方圖的大小與3個(gè)因素有關(guān).

1) 特征維度D.由于需要為每種特征建立兩個(gè)梯度直方圖(一階梯度直方圖和二階梯度直方圖),因而梯度直方圖的總數(shù)量與2D成比例;

2) 候選分裂點(diǎn)的數(shù)量q.一個(gè)梯度直方圖中箱子的數(shù)量等于候選分裂點(diǎn)的個(gè)數(shù);

3) 類別數(shù)量C.在多分類問題中,每個(gè)梯度數(shù)據(jù)是一個(gè)向量,表示在所有類別上的偏微分,因此,梯度直方圖的大小與C成比例.二分類是一個(gè)特例,二分類時(shí)C=1.

綜上,一個(gè)樹節(jié)點(diǎn)的梯度直方圖大小為Sh=8×2×D×q字節(jié),其中,8字節(jié)表示一個(gè)雙精度浮點(diǎn)數(shù)的大小.

2.2 內(nèi)存開銷

梯度提升樹訓(xùn)練中的一個(gè)技巧是,只要樹節(jié)點(diǎn)之間不存在數(shù)據(jù)重疊,就可以同時(shí)處理多個(gè)樹節(jié)點(diǎn),代價(jià)是存儲(chǔ)更多的梯度直方圖.對(duì)于目前普遍采用的逐層訓(xùn)練的方式,樹的同一層的樹節(jié)點(diǎn)之間不存在數(shù)據(jù)重疊,因而可以同時(shí)被處理,樹的深度最大為L(zhǎng),因此,同時(shí)處理的樹節(jié)點(diǎn)的最大數(shù)量是2L-1.

使用數(shù)據(jù)并行策略時(shí),每個(gè)計(jì)算節(jié)點(diǎn)需要建立所有待處理樹節(jié)點(diǎn)上每個(gè)特征的直方圖,因此,每個(gè)計(jì)算節(jié)點(diǎn)上梯度直方圖的內(nèi)存開銷最多是Sh×2L-1.但是用特征并行時(shí),每個(gè)計(jì)算節(jié)點(diǎn)只需要負(fù)責(zé)計(jì)算一部分特征的梯度直方圖,因此內(nèi)存開銷是Sh×2L-1/W,與數(shù)據(jù)并行相比要低得多.

2.3 通信開銷

當(dāng)使用數(shù)據(jù)并行時(shí),主要的通信開銷是梯度直方圖的匯總.盡管目前存在多種在分布式環(huán)境下聚合數(shù)據(jù)的分布式架構(gòu),例如 MapReduce[7],AllReduce[8],ReduceScatter[10],Parameter Server[14-17]等,但是每個(gè)計(jì)算節(jié)點(diǎn)至少需要通過網(wǎng)絡(luò)傳輸本地存儲(chǔ)的梯度直方圖,因此,一棵樹需要傳輸?shù)奶荻戎狈綀D的大小至少是Sh×W×(2L-1).

當(dāng)使用特征并行時(shí),由于每個(gè)計(jì)算節(jié)點(diǎn)上存儲(chǔ)著一個(gè)特征的全部特征值,因此,梯度提升樹算法不需要在計(jì)算節(jié)點(diǎn)之間匯總梯度直方圖.但由于按列切分?jǐn)?shù)據(jù)集,在尋找最佳分裂點(diǎn)時(shí),每個(gè)計(jì)算節(jié)點(diǎn)從本地存儲(chǔ)的梯度直方圖中計(jì)算出一個(gè)局部最佳分裂點(diǎn),然后從所有計(jì)算節(jié)點(diǎn)中選擇出一個(gè)全局最佳分裂點(diǎn),這樣的代價(jià)是只有一個(gè)計(jì)算節(jié)點(diǎn)知道數(shù)據(jù)樣本的分裂結(jié)果,也就是數(shù)據(jù)樣本被分到左子節(jié)點(diǎn)還是右子節(jié)點(diǎn).這樣,在完成樹節(jié)點(diǎn)分裂之后,此計(jì)算節(jié)點(diǎn)需要向其他計(jì)算節(jié)點(diǎn)廣播數(shù)據(jù)樣本的位置(左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)),帶來了一定的通信開銷.這部分的通信開銷與數(shù)據(jù)樣本的數(shù)量成正比,因此當(dāng)樹的深度增大時(shí),通信量保持不變.綜上,一棵樹的總通信開銷是4×N×W×L字節(jié),其中,4字節(jié)表示32位整型數(shù)的大小.這樣簡(jiǎn)單地實(shí)現(xiàn)存在的問題是,直接用整型來發(fā)送數(shù)據(jù)樣本的位置開銷較大.為了解決這個(gè)問題,本文提出將數(shù)據(jù)樣本的位置編碼為比特圖,每個(gè)比特代表一個(gè)數(shù)據(jù)樣本的位置,0代表左子節(jié)點(diǎn),1代表右子節(jié)點(diǎn).這種方法能夠顯著降低通信開銷,對(duì)于一個(gè)L層的樹,總的通信開銷是字節(jié).

2.4 分析結(jié)果總結(jié)

根據(jù)之前的分析結(jié)果,使用數(shù)據(jù)并行策略最多需要Sh×2L-1的內(nèi)存開銷和Sh×W×(2L-1)的通信開銷,特征并行需要Sh×2L-1/W的內(nèi)存開銷和的通信開銷.

下面以公開數(shù)據(jù)集 RCV1-multi為例,定量地比較兩種策略的內(nèi)存開銷和通信開銷.RCV1-multi數(shù)據(jù)集有53.4萬個(gè)樣本、4.7萬個(gè)特征和53個(gè)類別,使用8個(gè)計(jì)算節(jié)點(diǎn)建立深度為7的樹,候選分裂點(diǎn)的個(gè)數(shù)設(shè)置為100,每棵樹上梯度直方圖的大小是 3.7GB.當(dāng)使用數(shù)據(jù)并行時(shí),建立一棵樹的內(nèi)存開銷最大是 118.4GB,通信開銷最差情況下總共是 1.8TB;當(dāng)使用特征并行時(shí),建立一棵樹的內(nèi)存開銷是 14.8GB,通信開銷是 3.8MB.由此可見,對(duì)于高維和多分類問題,特征并行與數(shù)據(jù)并行相比,在通信開銷和內(nèi)存開銷上明顯更為高效.

3 算法介紹

本節(jié)首先從整體上介紹本文提出的算法FP-GBDT,然后分別詳細(xì)介紹FP-GBDT的關(guān)鍵技術(shù).

3.1 整體介紹

圖2是FP-GBDT整體工作流程,主要包括以下幾個(gè)關(guān)鍵步驟.

(1) 訓(xùn)練數(shù)據(jù)集存儲(chǔ)在分布式文件系統(tǒng)上,例如 HDFS,GFS,Ceph等,默認(rèn)的存儲(chǔ)方式是按行切分.FPGBDT從分布式文件系統(tǒng)上加載訓(xùn)練數(shù)據(jù)集到計(jì)算節(jié)點(diǎn),讀入內(nèi)存中;

(2) FP-GBDT對(duì)訓(xùn)練數(shù)據(jù)集執(zhí)行數(shù)據(jù)集轉(zhuǎn)置操作,將原本按行切分的數(shù)據(jù)集轉(zhuǎn)換為按列切分的方式,以特征行的方式存儲(chǔ)在計(jì)算節(jié)點(diǎn)上;

(3) 每個(gè)計(jì)算節(jié)點(diǎn)獨(dú)立地建立梯度直方圖.為了有效地處理普遍存在的高維稀疏數(shù)據(jù),本文提出了一種稀疏感知的方法來加速梯度直方圖的建立;

(4) 建立完梯度直方圖之后,每個(gè)計(jì)算節(jié)點(diǎn)從本地的梯度直方圖中找出一個(gè)局部最佳分裂點(diǎn),然后通過一個(gè)主節(jié)點(diǎn)從所有候選中找到全局最佳分裂點(diǎn);

(5) 產(chǎn)生全局最佳分裂點(diǎn)的計(jì)算節(jié)點(diǎn)執(zhí)行分裂樹節(jié)點(diǎn)的操作,并產(chǎn)生數(shù)據(jù)樣本在樹中的位置;然后,使用一種比特圖的壓縮方法發(fā)送數(shù)據(jù)樣本的位置給其他計(jì)算節(jié)點(diǎn).

Fig.2 Framework of FP-GBDT圖2 FP-GBDT的架構(gòu)

3.2 數(shù)據(jù)集轉(zhuǎn)置

原始的訓(xùn)練數(shù)據(jù)集由多行組成,每行包含了一個(gè)數(shù)據(jù)樣本的特征和標(biāo)簽.目前的數(shù)據(jù)集常常是稀疏格式,因此經(jīng)常將數(shù)據(jù)樣本的特征存儲(chǔ)為鍵值對(duì)的形式,其中,鍵是特征索引、值是特征值.數(shù)據(jù)集常常按行切分并存儲(chǔ)在分布式文件系統(tǒng)上,例如HDFS等,這種存儲(chǔ)格式天然不適合特征并行,因?yàn)樘卣鞑⑿行枰趩蝹€(gè)計(jì)算節(jié)點(diǎn)上匯總一個(gè)特征的所有特征值.為了解決這個(gè)問題,需要在梯度提升樹算法執(zhí)行之前對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行轉(zhuǎn)置操作,將按行存儲(chǔ)的數(shù)據(jù)集轉(zhuǎn)換為按列存儲(chǔ)的方式.本文設(shè)計(jì)了一種高效的分布式數(shù)據(jù)集轉(zhuǎn)置算法,如圖3所示.

Fig.3 Distributed dataset transposition圖3 分布式數(shù)據(jù)集轉(zhuǎn)置

本方法的計(jì)算流程包括4個(gè)步驟.

(1) 計(jì)算數(shù)據(jù)樣本的偏移.為了唯一標(biāo)識(shí)每個(gè)數(shù)據(jù)樣本,每個(gè)計(jì)算節(jié)點(diǎn)將本地?cái)?shù)據(jù)樣本的數(shù)量發(fā)送給主節(jié)點(diǎn),然后,主節(jié)點(diǎn)從全局上統(tǒng)計(jì)數(shù)據(jù)樣本的數(shù)量,給每個(gè)計(jì)算節(jié)點(diǎn)發(fā)送一個(gè)全局偏移值,限定了每個(gè)計(jì)算節(jié)點(diǎn)上數(shù)據(jù)樣本標(biāo)識(shí)范圍.這樣,每個(gè)數(shù)據(jù)樣本的標(biāo)識(shí)就等于計(jì)算節(jié)點(diǎn)的全局偏移加上本地偏移;

(2) 轉(zhuǎn)置數(shù)據(jù)集.每個(gè)計(jì)算節(jié)點(diǎn)對(duì)本地的數(shù)據(jù)樣本進(jìn)行轉(zhuǎn)置操作.原始的數(shù)據(jù)集由樣本行組成,每個(gè)樣本行存儲(chǔ)著(特征索引,特征值)的鍵值對(duì).本節(jié)的數(shù)據(jù)集轉(zhuǎn)置方法將這種數(shù)據(jù)表示方式轉(zhuǎn)換為特征行,每個(gè)特征行存儲(chǔ)著一個(gè)特征出現(xiàn)的所有位置,也就是(樣本索引,特征值)的鍵值對(duì),表示此特征在每個(gè)數(shù)據(jù)樣本中的非零值,這里的樣本索引根據(jù)上一步產(chǎn)生的樣本偏移計(jì)算而出;

(3) 重切分特征行.由于一個(gè)特征的特征值可能存在多個(gè)計(jì)算節(jié)點(diǎn)上,因而每個(gè)特征在多個(gè)計(jì)算節(jié)點(diǎn)上存在局部特征行.本方法通過MapReduce操作重切分所有計(jì)算節(jié)點(diǎn)上的局部特征行,使得每個(gè)特征的所有局部特征行在一個(gè)計(jì)算節(jié)點(diǎn)行進(jìn)行匯總,形成此特征完整的特征行.通過這個(gè)操作,每個(gè)計(jì)算節(jié)點(diǎn)負(fù)責(zé)一個(gè)特征子集,存儲(chǔ)著這個(gè)特征子集中所有特征的特征行,由(樣本索引,特征值)的鍵值對(duì)組成;

(4) 廣播樣本標(biāo)簽.主節(jié)點(diǎn)從所有計(jì)算節(jié)點(diǎn)收集數(shù)據(jù)樣本的標(biāo)簽,然后廣播給計(jì)算節(jié)點(diǎn).這些標(biāo)簽被每個(gè)計(jì)算節(jié)點(diǎn)用來計(jì)算數(shù)據(jù)樣本的梯度.

3.3 建立梯度直方圖

在數(shù)據(jù)集轉(zhuǎn)置之后,每個(gè)計(jì)算節(jié)點(diǎn)使用特征行來建立梯度直方圖.首先掃描特征行,為每個(gè)特征建立分位數(shù)據(jù)草圖,然后使用數(shù)據(jù)草圖產(chǎn)生候選分裂點(diǎn),具體而言,使用一組 0～1之間的分位值,例如{0,0.1,0.2,…,1.0},從分位數(shù)據(jù)草圖中查詢出每個(gè)特征的候選分裂值.

特征并行策略下,一個(gè)計(jì)算節(jié)點(diǎn)包含了某個(gè)特征所有出現(xiàn)的特征值,而數(shù)據(jù)并行策略下,一個(gè)計(jì)算節(jié)點(diǎn)只包含了某個(gè)特征的部分特征值.因此在特征并行策略下,一個(gè)樹節(jié)點(diǎn)建立梯度直方圖的操作比數(shù)據(jù)并行策略的計(jì)算量更大.由此可見:針對(duì)特征并行的特點(diǎn),設(shè)計(jì)高效的機(jī)制來加速梯度直方圖的建立是非常有意義的.

· 稀疏感知的建立梯度直方圖方法.

建立梯度直方圖需要直接處理數(shù)據(jù)樣本,要達(dá)到優(yōu)化的目標(biāo),應(yīng)該考慮數(shù)據(jù)樣本的特點(diǎn).在實(shí)際應(yīng)用中,很多真實(shí)的數(shù)據(jù)集常常是稀疏的,一個(gè)數(shù)據(jù)樣本中只有一部分非常少的特征有非零值.傳統(tǒng)的建立梯度直方圖的方法需要數(shù)據(jù)樣本的所有特征值,包括值為零和值非零的特征,因此計(jì)算復(fù)雜度是O(N×D),這里,N是數(shù)據(jù)樣本的數(shù)量,D是特征數(shù)量.對(duì)于數(shù)據(jù)量大、特征維度高的情況,這樣的計(jì)算復(fù)雜度過高.考慮到稀疏的數(shù)據(jù)特點(diǎn)和存在的問題,一個(gè)直觀的想法是,能否利用數(shù)據(jù)稀疏性來加速梯度直方圖的建立.基于這樣的思路,本文提出一種稀疏感知的建立梯度直方圖的技術(shù),如圖4所示,主要技術(shù)細(xì)節(jié)如下所述.

(1) 在讀取數(shù)據(jù)樣本之前,假設(shè)數(shù)據(jù)樣本的所有特征值都為 0.一般情況下會(huì)認(rèn)為特征值為非零是正常情況,特征值為0是異常情況,但真實(shí)情況是,數(shù)據(jù)樣本中大部分特征值為0,從概率的角度來看,特征值為0是大多數(shù)情況,而特征值為非零是極少數(shù)情況.基于這樣的觀察,本方法在讀取數(shù)據(jù)樣本之前,假設(shè)它們所有的特征值都為0;

(2) 累加數(shù)據(jù)樣本的梯度.經(jīng)過數(shù)據(jù)集轉(zhuǎn)置之后,每個(gè)計(jì)算節(jié)點(diǎn)上保存著所有數(shù)據(jù)樣本的標(biāo)簽,使用數(shù)據(jù)樣本的標(biāo)簽和預(yù)測(cè)值,計(jì)算數(shù)據(jù)樣本的梯度,接著累加所有的梯度;

(3) 將梯度和增加到零桶中.一個(gè)特征的梯度直方圖中,每個(gè)桶包含特征值的一個(gè)區(qū)間,這里將零桶定義為包含特征值為零的桶.本方法的第 1步中假設(shè)所有特征值都為零,這樣應(yīng)該將每個(gè)數(shù)據(jù)樣本的梯度放入零桶中,因此,本方法將第2步求得的梯度和加到每個(gè)特征的梯度直方圖的零桶中;

(4) 重定位非零特征值.依次讀取特征行存儲(chǔ)的非零特征值,根據(jù)特征值的大小找到對(duì)應(yīng)的梯度直方圖的桶,然后將此特征值對(duì)應(yīng)的數(shù)據(jù)樣本的梯度加到此梯度直方圖桶中;同時(shí),為了保證梯度直方圖的正確性,從零桶中減去此數(shù)據(jù)樣本的梯度.

Fig.4 Sparsity-aware histogram construction圖4 稀疏感知的建立梯度直方圖方法

· 計(jì)算復(fù)雜度分析.

使用本文提出的稀疏感知建立梯度直方圖的方法,首先需要掃描一遍數(shù)據(jù)樣本計(jì)算梯度和,然后將梯度和加到每個(gè)特征的梯度直方圖的零桶中,最后掃描一遍非零特征值.這樣的計(jì)算復(fù)雜度是.這里,N是數(shù)據(jù)樣本的數(shù)量,D是特征的數(shù)量,W是集群計(jì)算節(jié)點(diǎn)的數(shù)量,d代表一個(gè)數(shù)據(jù)樣本中非零特征值的平均數(shù)量.與傳統(tǒng)方法的計(jì)算復(fù)雜度O(N×D)相比,由于d<

3.4 分裂樹節(jié)點(diǎn)

找到一個(gè)樹節(jié)點(diǎn)的最佳分裂點(diǎn)后,下一步是分裂樹節(jié)點(diǎn).使用特征并行策略時(shí),某個(gè)計(jì)算節(jié)點(diǎn)產(chǎn)生了全局最佳分裂點(diǎn),樹節(jié)點(diǎn)的分裂結(jié)果(數(shù)據(jù)樣本的位置)也只有此計(jì)算節(jié)點(diǎn)知道,因而,此計(jì)算節(jié)點(diǎn)需要將數(shù)據(jù)樣本的位置廣播給其他計(jì)算節(jié)點(diǎn).為了減少通信開銷,本文設(shè)計(jì)了一種比特圖的方法來壓縮數(shù)據(jù)樣本的位置,如圖5所示.

Fig.5 Bitmap compression圖5 比特圖壓縮方法

· 比特圖壓縮.

如果使用整型的表達(dá)方式,廣播數(shù)據(jù)樣本位置的通信開銷是4×N×W字節(jié).一個(gè)數(shù)據(jù)樣本的位置是左子節(jié)點(diǎn)或者右子節(jié)點(diǎn),因此,本方法使用一個(gè)比特圖來二進(jìn)制編碼樣本位置,左子節(jié)點(diǎn)編碼為 0,右子節(jié)點(diǎn)編碼為 1.使用這種方法,通信開銷降低為N×W/8字節(jié),帶來了32倍的提升.當(dāng)其他計(jì)算節(jié)點(diǎn)接收到比特圖后,逐個(gè)比特地讀取,然后更新數(shù)據(jù)樣本在樹中的位置.

除了能夠節(jié)省通信開銷,特征并行相比數(shù)據(jù)并行還有另外一個(gè)優(yōu)勢(shì):當(dāng)樹的層數(shù)加深時(shí),同層樹節(jié)點(diǎn)的數(shù)量指數(shù)增長(zhǎng),數(shù)據(jù)并行策略下通信開銷也會(huì)指數(shù)級(jí)增長(zhǎng);而使用特征并行策略時(shí),樹的一層的通信開銷與樹節(jié)點(diǎn)的數(shù)量無關(guān),樹深度的增加不會(huì)造成通信開銷的增加.

4 實(shí)驗(yàn)對(duì)比

本節(jié)通過詳盡的實(shí)驗(yàn)來驗(yàn)證FP-GBDT算法的有效性.

4.1 實(shí)驗(yàn)設(shè)置

· 原型實(shí)現(xiàn).

FP-GBDT在Spark[19]的基礎(chǔ)上實(shí)現(xiàn),數(shù)據(jù)存儲(chǔ)在HDFS上,機(jī)器學(xué)習(xí)任務(wù)提交到一個(gè)8節(jié)點(diǎn)的Yarn[20]集群上.每個(gè)機(jī)器配置了4個(gè)E3-1220 v3 CPU,32GB內(nèi)存和1Gb網(wǎng)絡(luò).

· 數(shù)據(jù)集.

本文的實(shí)驗(yàn)使用了3個(gè)數(shù)據(jù)集,見表2.RCV1[21]和 RCV1-multi[22]是兩個(gè)公開的文本分類數(shù)據(jù)集[23],樣本數(shù)量分別為69.7萬和53.4萬,特征數(shù)量均為4.7萬,RCV1有2種類別,RCV1-multi有53種類別.Synthesis是一個(gè)人造數(shù)據(jù)集,包含1千萬個(gè)樣本和10萬個(gè)特征.Synthesis是一個(gè)二分類數(shù)據(jù)集,用來評(píng)估本文提出的優(yōu)化方法的效果和特征維度的影響,RCV1和RCV1-multi的特征相同而類別數(shù)量不同,被用來評(píng)估類別數(shù)量的影響.

· 基準(zhǔn)方法.

如前所述,目前有多種分布式梯度提升樹算法的實(shí)現(xiàn),例如Mllib,XGBoost和LightGBM等.本文基于兩個(gè)原因選擇 XGBoost作為數(shù)據(jù)并行策略的代表:第一,XGBoost是目前使用最廣泛的分布式梯度提升樹系統(tǒng);第二,XGBoost有基于Spark實(shí)現(xiàn)的版本,因而實(shí)驗(yàn)對(duì)比是公平的.

· 超參數(shù).

除非另外聲明,對(duì)RCV1和RCV1-multi數(shù)據(jù)集選擇L=7,對(duì)Synthesis數(shù)據(jù)集選擇L=8,計(jì)算節(jié)點(diǎn)數(shù)量W=10.對(duì)于其他超參數(shù),候選分裂點(diǎn)數(shù)量q=100,學(xué)習(xí)速度η=0.1,特征采樣率設(shè)為1.0,樹的數(shù)量設(shè)為100.

Table 2 Datasets表2 數(shù)據(jù)集

4.2 優(yōu)化方法有效性

本節(jié)的實(shí)驗(yàn)用來評(píng)估本文提出的優(yōu)化方法,驗(yàn)證它們的有效性,這些優(yōu)化方法包括數(shù)據(jù)集轉(zhuǎn)置、稀疏感知建立梯度直方圖和比特圖壓縮.

· 數(shù)據(jù)集轉(zhuǎn)置.

首先展示分布式數(shù)據(jù)集轉(zhuǎn)置方法的性能,實(shí)驗(yàn)數(shù)據(jù)如圖6所示,從HDFS上加載3個(gè)數(shù)據(jù)集的時(shí)間分別是17s、12s和 106s.使用簡(jiǎn)單的直接數(shù)據(jù)集轉(zhuǎn)置,在 RCV1,RCV1-multi和 Synthesis數(shù)據(jù)集上需要的時(shí)間分別是20s、13s和168s;而FP-GBDT執(zhí)行數(shù)據(jù)集轉(zhuǎn)置的操作,在3個(gè)數(shù)據(jù)集上的耗時(shí)分別是9s、6s和95s,相比原始的數(shù)據(jù)集轉(zhuǎn)置方法,速度得到了最高 2倍的提升.雖然相比于數(shù)據(jù)并行的策略,FP-GBDT帶來了額外的時(shí)間開銷,但是在后面的實(shí)驗(yàn)中將顯示,FP-GBDT顯著提升了整體的性能.

· 稀疏感知建立梯度直方圖.

當(dāng)使用稀疏感知的方法時(shí),對(duì)Synthesis數(shù)據(jù)集,建立樹的根節(jié)點(diǎn)的梯度直方圖的時(shí)間是9s.但是當(dāng)不使用這種方法時(shí),在1h之內(nèi)無法完成建立根節(jié)點(diǎn)的梯度直方圖,原因是需要讀取一個(gè)數(shù)據(jù)樣本的所有特征.

· 比特圖壓縮.

找到最佳分裂點(diǎn)后,處理分裂樹節(jié)點(diǎn)的任務(wù)時(shí),FP-GBDT廣播數(shù)據(jù)樣本的位置時(shí)使用比特圖的壓縮方法.本實(shí)驗(yàn)在 Synthesis數(shù)據(jù)集上訓(xùn)練梯度提升樹算法,建立一棵樹的總時(shí)間開銷中分裂樹節(jié)點(diǎn)需要 18s;當(dāng)使用了比特圖壓縮方法后,此部分時(shí)間開銷降低為8s,帶來了2倍的速度提升.

Fig.6 Effects of dataset transposition圖6 數(shù)據(jù)集轉(zhuǎn)置的效果

4.3 性能對(duì)比

4.3.1 FP-GBDT與XGBoost的性能對(duì)比

本節(jié)的實(shí)驗(yàn)比較FP-GBDT與XGBoost,FP-GBDT使用特征并行策略,XGBoost使用數(shù)據(jù)并行策略,下面分別評(píng)估特征數(shù)量、類別數(shù)量等因素對(duì)結(jié)果的影響.

· 特征數(shù)量的影響.

本文提出的FP-GBDT適合高維特征的數(shù)據(jù)集,為了評(píng)估特征數(shù)量對(duì)于實(shí)驗(yàn)結(jié)果的影響,本文使用Synthesis數(shù)據(jù)集的一部分特征子集,例如Synthesis-25K代表使用Synthesis數(shù)據(jù)集前2.5萬個(gè)特征,Synthesis-100K代表Synthesis數(shù)據(jù)集的全部特征.分別用FP-GBDT與XGBoost在Synthesis的多個(gè)數(shù)據(jù)子集上訓(xùn)練梯度提升樹算法,FP-GBDT與XGBoost對(duì)比的實(shí)驗(yàn)結(jié)果如圖7所示.當(dāng)特征數(shù)量從2.5萬增加到5萬和10萬時(shí),XGBoost建立一棵樹的時(shí)間從80s增加到了144s和301s,性能分別下降了1.8倍和3.7倍.原因是特征數(shù)量增大1倍時(shí),梯度直方圖的大小也增加 1倍,XGBoost使用數(shù)據(jù)并行,通信開銷線性增大,從而造成性能幾乎線性下降;FPGBDT的性能下降較小,分別慢了1.4倍和2.2倍,FP-GBDT使用特征并行,通信開銷與特征數(shù)量無關(guān),樹的每一層的開銷一樣,因而只會(huì)受到計(jì)算開銷增大的影響.總的來說,特征數(shù)量增大時(shí)FP-GBDT比XGBoost更加高效.

· 類別數(shù)量的影響.

如前文所分析,對(duì)于多分類問題,類別數(shù)量對(duì)梯度直方圖的大小有直接的影響.為了更好地顯示結(jié)果,本實(shí)驗(yàn)選擇了兩分類的RCV1數(shù)據(jù)集和53分類的RCV1-multi數(shù)據(jù)集,同時(shí)又將RCV1-multi的53類合并為5類.用8個(gè)計(jì)算節(jié)點(diǎn)對(duì)這3個(gè)數(shù)據(jù)集訓(xùn)練梯度提升樹模型,圖8顯示了實(shí)驗(yàn)結(jié)果,統(tǒng)計(jì)了建立一棵樹的平均時(shí)間.在2分類上的RCV1數(shù)據(jù)集上,XGBoost平均需要53s訓(xùn)練一棵樹,而FP-GBDT只需要26s,訓(xùn)練速度快了2倍,所以FP-GBDT的收斂速度比 XGBoost快得多.在 5分類的RCV1-multi數(shù)據(jù)集上,XGBoost需要251s訓(xùn)練一棵樹,FP-GBDT只需要41s,快了6.1倍.類別增加到5類時(shí),梯度直方圖的大小增大了5倍,XGBoost的性能下降了接近5倍,而FP-GBDT只慢了1.5倍,這說明FP-GBDT更適合多分類問題.當(dāng)使用53類的RCV1-multi數(shù)據(jù)集時(shí),FP-GBDT訓(xùn)練一棵樹需要 161s,而 XGBoost出現(xiàn)了內(nèi)存溢出(out of memory,簡(jiǎn)稱 OOM)的錯(cuò)誤,這證明了XGBoost使用的數(shù)據(jù)并行策略的內(nèi)存開銷較大.總的來說,FP-GBDT比XGBoost更適合多分類任務(wù),特別是類別數(shù)量較大的情況.

Fig.7 Impact of feature dimensionality圖7 特征數(shù)量的影響

Fig.8 Impact of class number圖8 類別數(shù)量的影響

· 樹深度的影響.

接下來的實(shí)驗(yàn)將評(píng)估樹的深度對(duì)性能的影響.一般來說,樹的深度越大,訓(xùn)練時(shí)間越長(zhǎng),模型準(zhǔn)確率更高.本實(shí)驗(yàn)在RCV1數(shù)據(jù)集上訓(xùn)練梯度提升樹算法,逐步地增加樹的深度,實(shí)驗(yàn)結(jié)果顯示在圖9和圖10中.

深度增大時(shí),XGBoost和 FP-GBDT的誤差均下降,證明更深的樹可以提高模型的準(zhǔn)確率,代價(jià)是訓(xùn)練時(shí)間的增大.當(dāng)樹的深度從8增大到9時(shí),數(shù)據(jù)并行策略下梯度直方圖的大小增大1倍,因此,XGBoost的運(yùn)行速度慢了2倍;繼續(xù)將樹的深度增大到10時(shí),XGBoost出現(xiàn)了內(nèi)存溢出的錯(cuò)誤.

與此相對(duì)應(yīng),FP-GBDT使用特征并行,能夠高效地處理更深的樹,樹的深度增大時(shí),每一層的通信開銷保持不變,因此性能下降較為平穩(wěn),在可接受范圍之內(nèi);同時(shí),FP-GBDT的內(nèi)存開銷較小,樹的深度增加時(shí)沒有出現(xiàn)資源不足的情況.

Fig.9 Impact of tree depth (time to build one tree)圖9 樹深度的影響(建立一棵樹的平均時(shí)間)

Fig.10 Impact of tree depth (error after the first tree)圖10 樹深度的影響(第1棵樹后的誤差)

4.3.2 FP-GBDT與LightGBM的性能對(duì)比

如第1.4節(jié)所述,LightGBM也實(shí)現(xiàn)了一個(gè)特征并行的梯度提升樹算法,但是LightGBM的實(shí)現(xiàn)需要每個(gè)計(jì)算節(jié)點(diǎn)上已經(jīng)存有完整的數(shù)據(jù)集,訓(xùn)練時(shí),LightGBM 將整個(gè)數(shù)據(jù)集加載進(jìn)內(nèi)存,這樣,LightGBM 不需要進(jìn)行數(shù)據(jù)集轉(zhuǎn)置的處理,也不需要在節(jié)點(diǎn)之間廣播分裂后數(shù)據(jù)樣本的位置.嚴(yán)格意義上,這不是一種真正的特征并行方式,在真實(shí)的應(yīng)用中,單機(jī)的內(nèi)存常常無法存儲(chǔ)完整的數(shù)據(jù)集;在真實(shí)的環(huán)境中,數(shù)據(jù)集常常以存儲(chǔ)在分布式文件系統(tǒng)上,LightGBM在這種情況下無法工作.因此,LightGBM的特征并行實(shí)現(xiàn)無法用在實(shí)際中.

但是為了給出更加全面的結(jié)果,本節(jié)使用Synthesis數(shù)據(jù)集比較了FP-GBDT和LightGBM的性能,實(shí)驗(yàn)設(shè)置與之前的實(shí)驗(yàn)保持一致.由于LightGBM無法從分布式文件系統(tǒng)讀取數(shù)據(jù),首先使用hadoop fs命令從HDFS上下載到每一個(gè)計(jì)算節(jié)點(diǎn)上,在所有計(jì)算節(jié)點(diǎn)下載完成之后,在每個(gè)計(jì)算節(jié)點(diǎn)上啟動(dòng) LightGBM,從 HDFS下載數(shù)據(jù)集加上本地讀取數(shù)據(jù)的總時(shí)間是LightGBM的數(shù)據(jù)預(yù)處理的時(shí)間.

圖11給出了實(shí)驗(yàn)結(jié)果,FP-GBDT的數(shù)據(jù)預(yù)處理(包括加載數(shù)據(jù)集和數(shù)據(jù)集轉(zhuǎn)置)時(shí)間是201s,而LightGBM需要 820s來對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,比 FP-GBDT慢了 4倍多;在訓(xùn)練階段,FP-GBDT建立一棵樹的平均時(shí)間是105s,LightGBM需要90s;在內(nèi)存開銷方面,LightGBM由于需要在每個(gè)節(jié)點(diǎn)上存儲(chǔ)完整的數(shù)據(jù)集,因此每臺(tái)機(jī)器上消耗了30GB的內(nèi)存,是FP-GBDT的內(nèi)存開銷的6倍.總體來看,LightGBM單棵樹的速度略快.這主要是因?yàn)槊總€(gè)計(jì)算節(jié)點(diǎn)加載完整的數(shù)據(jù)集,從而避免了通過網(wǎng)絡(luò)傳輸數(shù)據(jù)樣本的分裂位置;很多工業(yè)界的數(shù)據(jù)集大小常常達(dá)到 TB級(jí)別,單個(gè)計(jì)算節(jié)點(diǎn)的內(nèi)存顯然無法存儲(chǔ)這樣大的數(shù)據(jù)集;對(duì)于存儲(chǔ)在分布式文件系統(tǒng)上的數(shù)據(jù)集,LightGBM 首先需要將數(shù)據(jù)集下載到每個(gè)計(jì)算節(jié)點(diǎn)上,這帶來了很大的開銷.因此,對(duì)于較小的數(shù)據(jù)集和實(shí)驗(yàn)室級(jí)別的環(huán)境,并且資源較充裕時(shí),LightGBM 是一個(gè)不錯(cuò)的選擇;但是對(duì)于較大的數(shù)據(jù)集和真實(shí)的生產(chǎn)環(huán)境,LightGBM常常是不可用的,而FP-GBDT的適用性很廣,更加適合大數(shù)據(jù)時(shí)代的需求和發(fā)展趨勢(shì).

Fig.11 Performance comparison of FP-GBDT and LightGBM圖11 FP-GBDT與LightGBM的性能對(duì)比

5 總 結(jié)

本文研究面向高維特征和多分類問題的分布式梯度提升樹算法.根據(jù)一個(gè)嚴(yán)格的代價(jià)模型,比較了數(shù)據(jù)并行策略和特征并行策略,證明了特征并行策略更適合高維和多分類場(chǎng)景;基于理論分析的結(jié)果,本文提出一種使用特征并行的分布式梯度提升樹算法FP-GBDT.FP-GBDT首先利用對(duì)數(shù)據(jù)集進(jìn)行分布式轉(zhuǎn)置,轉(zhuǎn)換為特征并行需要的數(shù)據(jù)表征;在建立梯度直方圖時(shí),FP-GBDT設(shè)計(jì)了稀疏感知的方法;在分裂樹節(jié)點(diǎn)時(shí),FP-GBDT使用一種比特圖壓縮的方法傳輸數(shù)據(jù)樣本的位置.實(shí)驗(yàn)結(jié)果顯示,FP-GBDT與使用數(shù)據(jù)并行的 XGBoost相比,性能的提升最高達(dá)到6倍以上,證明了特征并行的FP-GBDT在高維和多分類問題上的高效性.