面試中出現(xiàn)有關(guān)Xgboost總結(jié)

介紹

Xgboost是GB算法的高效實(shí)現(xiàn)，xgboost中的基學(xué)習(xí)器除了可以是CART（gbtree）也可以是線性分類器（gblinear）。

與GBDT不同之處

xgboost在目標(biāo)函數(shù)中顯示的加上了正則化項(xiàng)，基學(xué)習(xí)為CART時(shí)，正則化項(xiàng)與樹(shù)的葉子節(jié)點(diǎn)的數(shù)量T和葉子節(jié)點(diǎn)的值有關(guān)。

GB中使用Loss Function對(duì)f（x）的一階導(dǎo)數(shù)計(jì)算出偽殘差用于學(xué)習(xí)生成fm（x），xgboost不僅使用到了一階導(dǎo)數(shù)，還使用二階導(dǎo)數(shù)。GB中使用Loss Function對(duì)f（x）的一階導(dǎo)數(shù)計(jì)算出偽殘差用于學(xué)習(xí)生成fm（x），xgboost不僅使用到了一階導(dǎo)數(shù)，還使用二階導(dǎo)數(shù)

上面提到CART回歸樹(shù)中尋找最佳分割點(diǎn)的衡量標(biāo)準(zhǔn)是最小化均方差，xgboost尋找分割點(diǎn)的標(biāo)準(zhǔn)是最大化，lamda，gama與正則化項(xiàng)相關(guān) 上面提到CART回歸樹(shù)中尋找最佳分割點(diǎn)的衡量標(biāo)準(zhǔn)是最小化均方差，xgboost尋找分割點(diǎn)的標(biāo)準(zhǔn)是最大化，lamda，gama與正則化項(xiàng)相關(guān)

支持并行化，這是XGBoost的閃光點(diǎn)，雖然樹(shù)與樹(shù)之間是串行關(guān)系，但是同層級(jí)節(jié)點(diǎn)可并行。具體的對(duì)于某個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)選擇最佳分裂點(diǎn)，候選分裂點(diǎn)計(jì)算增益用多線程并行。訓(xùn)練速度快。

xgboost算法的步驟和GB基本相同，都是首先初始化為一個(gè)常數(shù)，gb是根據(jù)一階導(dǎo)數(shù)ri，xgboost是根據(jù)一階導(dǎo)數(shù)gi和二階導(dǎo)數(shù)hi，迭代生成基學(xué)習(xí)器，相加更新學(xué)習(xí)器。

優(yōu)化內(nèi)容

xgboost與gdbt除了上述三點(diǎn)的不同，xgboost在實(shí)現(xiàn)時(shí)還做了許多優(yōu)化：

在尋找最佳分割點(diǎn)時(shí)，考慮傳統(tǒng)的枚舉每個(gè)特征的所有可能分割點(diǎn)的貪心法效率太低，xgboost實(shí)現(xiàn)了一種近似的算法。大致的思想是根據(jù)百分位法列舉幾個(gè)可能成為分割點(diǎn)的候選者，然后從候選者中根據(jù)上面求分割點(diǎn)的公式計(jì)算找出最佳的分割點(diǎn)。

xgboost考慮了訓(xùn)練數(shù)據(jù)為稀疏值的情況，可以為缺失值或者指定的值指定分支的默認(rèn)方向，這能大大提升算法的效率，paper提到50倍。

特征列排序后以塊的形式存儲(chǔ)在內(nèi)存中，在迭代中可以重復(fù)使用；雖然boosting算法迭代必須串行，但是在處理每個(gè)特征列時(shí)可以做到并行。

按照特征列方式存儲(chǔ)能優(yōu)化尋找最佳的分割點(diǎn)，但是當(dāng)以行計(jì)算梯度數(shù)據(jù)時(shí)會(huì)導(dǎo)致內(nèi)存的不連續(xù)訪問(wèn)，嚴(yán)重時(shí)會(huì)導(dǎo)致cache miss，降低算法效率。paper中提到，可先將數(shù)據(jù)收集到線程內(nèi)部的buffer，然后再計(jì)算，提高算法的效率。

xgboost 還考慮了當(dāng)數(shù)據(jù)量比較大，內(nèi)存不夠時(shí)怎么有效的使用磁盤，主要是結(jié)合多線程、數(shù)據(jù)壓縮、分片的方法，盡可能的提高算法的效率。