文章來(lái)源:?mp.weixin.qq.com/s/4i5O0QlKpWz......

背景

廣告排序的核心問(wèn)題是CTR預(yù)估，CTR預(yù)估的準(zhǔn)確度，很大程度上決定了最終排序的質(zhì)量。工業(yè)界目前用的比較多的是基于LR的線性策略，該方法的主要問(wèn)題之一是需要人工大量的時(shí)間去挑選和組合特征，而使用樹(shù)模型(tree model)則可以大大減輕這個(gè)工作量。

XGBoost是GBRT的一個(gè)工程實(shí)現(xiàn)，GBRT算法由多棵決策樹(shù)構(gòu)成，每一顆樹(shù)都是從之前所有樹(shù)的殘差中來(lái)學(xué)習(xí)的，具有很好的性能，并且泛化性能較強(qiáng)。自從dmlc/XGBoost面世以來(lái)，已經(jīng)越來(lái)越多的應(yīng)用在各種機(jī)器學(xué)習(xí)問(wèn)題的場(chǎng)合，當(dāng)然也不乏廣告排序中的CTR預(yù)估問(wèn)題，并且從2015年的kaggle競(jìng)賽獲獎(jiǎng)情況來(lái)看，一半以上的獲獎(jiǎng)團(tuán)隊(duì)使用了XGBoost方法。

鑒于XGBoost優(yōu)異的性能，蘑菇街廣告排序很早就引入了XGBoost作為CTR預(yù)估策略，并且嘗試了其分布式（spark）的實(shí)現(xiàn)，本文即從XGBoost的原理應(yīng)用等方面來(lái)展開(kāi)介紹。

XGBoost與ctr預(yù)估模型

目前廣告排序的主要公式是?c???b?i?d?,因此本文主要討論廣告算法排序的ctr預(yù)估問(wèn)題。

我們采用機(jī)器學(xué)習(xí)上gradient boosted tree[1]的模型去解決廣告算法排序的ctr預(yù)估問(wèn)題。boosted tree的目標(biāo)函數(shù)為：

上圖是對(duì)于一個(gè)用戶是否點(diǎn)擊某廣告的決策樹(shù)森林(ensembled trees)的例子。給定樣本?X1:”不常訪問(wèn)蘑菇街app的女性用戶“看到一個(gè)“喜歡數(shù)為20000，售價(jià)為35元的裙子”。該樣本時(shí)在上述ensemble trees中的權(quán)重為

在我們ctr預(yù)估模型中采用的損失函數(shù)類型采用了二分類的logistic函數(shù),因此上述樣本的預(yù)測(cè)ctr為：

為了精準(zhǔn)的預(yù)測(cè)ctr,我們需要構(gòu)建GBDT模型（gradient boosting decision tree)。首先定義損失函數(shù)為

X?1?：”不常訪問(wèn)蘑菇街app的女性用戶“看到一個(gè)“喜歡數(shù)為20000，售價(jià)為35元的裙子”。該樣本時(shí)在上述ensemble trees中的權(quán)重為?y?1?ˉ?=?(?1)?+?(?2)?=1.0?+0.4?=1.4?y?1?ˉ?=?f?(?t?r?e?e?1?)+?f?(?t?r?e?e?2?)?=?1.0?+?0.4?=?1.4?。在我們ctr預(yù)估模型中采用的損失函數(shù)類型采用了二分類的logistic函數(shù),因此上

其中

其中?Ω?(?f?)?為模型復(fù)雜度，取決于決策樹(shù)的深度和對(duì)于葉子節(jié)點(diǎn)的正則。將上述??公式根據(jù)泰勒公式展開(kāi)，可以獲得

其中?g?i?和?h?i?分別為損失函數(shù)?l?(?y?i?,?y?ˉ?(?t???1?)?)?的一階和二階偏導(dǎo)。

在迭代第?t?輪時(shí)，我們可以獲得目標(biāo)函數(shù)為

以上詳細(xì)公式推導(dǎo)可以參見(jiàn)論文[2].

XGBoost較于其它機(jī)器學(xué)習(xí)包優(yōu)勢(shì)在于基本原理之外的實(shí)踐細(xì)節(jié)的優(yōu)化。其中對(duì)于決策樹(shù)分裂點(diǎn)的選擇就是是在訓(xùn)練損失值(信息熵)和正則化約束(剪枝)中尋找平衡點(diǎn)。其參考論文[3]中通過(guò)將數(shù)據(jù)分到有序桶中從而尋找隊(duì)列中rank_n數(shù)值的方法，XGBoost在線性實(shí)踐內(nèi)對(duì)于某維度的特征進(jìn)行排序，從而降低了分裂點(diǎn)的實(shí)踐復(fù)雜度。此外，XGBoost還借鑒了隨機(jī)森林的思路，除了基本的樣本采樣，構(gòu)造每棵決策樹(shù)的時(shí)候?qū)τ谶x用的樣本特征進(jìn)行了采樣; 而且在boosting的過(guò)程中引入了學(xué)習(xí)率?λ?，在增加第t棵樹(shù)時(shí)，通過(guò)當(dāng)前學(xué)習(xí)率?λ?，降低已經(jīng)構(gòu)建好的前t-1棵樹(shù)的權(quán)重w,??w?=?w???λ。這種通過(guò)控制學(xué)習(xí)率和列采樣的方法能有效的避免了過(guò)擬合和模型效果的優(yōu)化。此外針對(duì)稀疏樣本，不同于之前的相關(guān)工作，XGBoost還通過(guò)將常見(jiàn)的二叉樹(shù)轉(zhuǎn)化為三叉樹(shù)，增加了對(duì)于缺失值的處理。此外在系統(tǒng)層面基于IO和CPU效率等方面XGBoost也有相當(dāng)優(yōu)秀的工作。

廣告排序的應(yīng)用

在蘑菇街的cpc廣告的ctr預(yù)估模型中，我們使用的特征按照特征來(lái)源區(qū)分，主要分為三類:query, ad和context。分類見(jiàn)下表:

特征來(lái)源特征舉例

query	前臺(tái)類目，搜索詞等
ad	商品特征,包括價(jià)格，標(biāo)題，圖片質(zhì)量，銷量，喜歡數(shù)等
context	廣告位置，時(shí)間因素等

在query類別中，除了圖墻場(chǎng)景中使用的前臺(tái)類目,我們使用的特征還包括搜索場(chǎng)景中的搜索詞,以及對(duì)該短文本搜索詞進(jìn)行后處理的結(jié)果；在ad類別中，除了使用后臺(tái)類目，原價(jià)，折扣價(jià)，圖片，評(píng)論，描述等商品單一維度特征，還增加了若干統(tǒng)計(jì)特征，如各種維度的歷史點(diǎn)擊曝光數(shù)，喜歡數(shù)，銷量，gmv等；在context類別，選用特征包括了廣告位置和時(shí)間這兩個(gè)bias因素。

考慮到GBDT模型能夠很好的解決交叉特征，我們沒(méi)有額外增加人為交叉特征；模型使用的特征中我們依然選用了離散特征，雖然考慮到gbdt通常只適用于連續(xù)特征，但是在樹(shù)的規(guī)模足夠大的情況下，對(duì)離散特征也會(huì)具有一定學(xué)習(xí)能力。我們選用的離散特征包括分類特征前臺(tái)類目，商品各級(jí)類目等; 以及其它id類特征，如商品id, 文本id等。

訓(xùn)練樣本預(yù)處理: 考慮到訓(xùn)練數(shù)據(jù)中負(fù)樣本偏多，我們會(huì)對(duì)訓(xùn)練數(shù)據(jù)按照采樣率?α?進(jìn)行負(fù)樣本采樣，將正負(fù)樣本比例控制在一定范圍內(nèi)。在GBDT中，單決策樹(shù)的構(gòu)造和樹(shù)的融合會(huì)對(duì)預(yù)測(cè)結(jié)果產(chǎn)生較高bias,因此采用保序回歸方法進(jìn)行校驗(yàn)。此后將獲得pred_ctr按照公式

進(jìn)行采樣校準(zhǔn)。

XGBoost還提供了參數(shù)?early stopping rounds?，其作用是當(dāng)訓(xùn)練損失在指定迭代數(shù)中趨于穩(wěn)定時(shí)，訓(xùn)練會(huì)提前終止迭代。需要注意的是此終止參數(shù)參數(shù)不能設(shè)置太小，如果太小可能會(huì)由于采樣不均勻等干擾因素導(dǎo)致訓(xùn)練不充分缺提前結(jié)束。

模型效果評(píng)估: 在GBDT模型中，除了計(jì)算特征和目標(biāo)值之間的皮爾森相關(guān)性，我們還可以參考?特征重要性?指標(biāo)來(lái)幫助我們進(jìn)行篩選。該重要性通俗講可以通過(guò)該特征在我們的決策樹(shù)森林的結(jié)點(diǎn)中出現(xiàn)的次數(shù)進(jìn)行衡量。

目前我們?cè)趫D墻場(chǎng)景中遇到較多的挑戰(zhàn)。圖墻場(chǎng)景上用戶的搜索意圖不強(qiáng)烈，以“逛”為主，我們很難抽取出有用特征，特別是文本特征更難以被有效利用。在后續(xù)工作中我們會(huì)引入個(gè)性化特征以及點(diǎn)擊反饋等來(lái)解決上述困難。

XGBoost分布式

分布式實(shí)現(xiàn)的兩個(gè)主要問(wèn)題：

分割點(diǎn)的確定

在XGBoost設(shè)計(jì)之初，就考慮了分布式的實(shí)現(xiàn)。樹(shù)模型最重要的一個(gè)問(wèn)題即是分割點(diǎn)的確定，XGBoost在單機(jī)的環(huán)境中，數(shù)據(jù)全部load進(jìn)內(nèi)存，feature已經(jīng)按照值的大小排好序，采用一個(gè)叫做“exact greedy algorithm”算法，經(jīng)過(guò)線性掃描，就可以快速的找到最佳的分割點(diǎn)；但是在分布式環(huán)境中，數(shù)據(jù)分布在各個(gè)節(jié)點(diǎn)，這種情況下，要找到最佳的分割點(diǎn)是很不容易的，XGBoost提供了一個(gè)近似算法來(lái)解決這個(gè)問(wèn)題，近似算法的核心在于根據(jù)特征的分布來(lái)提供一組候選的分割點(diǎn)，至于如何保證候選分割集的有效性和理論上的完備性，不在本文的討論范圍，有興趣的讀者可以參考文獻(xiàn)[4]。

容錯(cuò)

分布式環(huán)境中，多個(gè)節(jié)點(diǎn)共同工作，結(jié)果采用Allreduce的機(jī)制來(lái)同步，xgboost依賴dmlc/rabit來(lái)完成這個(gè)工作

rabit：可容錯(cuò)的Allreduce庫(kù)

Allreduce是MPI提供的一個(gè)主要功能，但是MPI一般不是特別受到廣泛歡迎，原因之一就是它本身不容錯(cuò)，但如果砍掉MPI的多余接口，只保留Allreduce和Broadcast，支持容錯(cuò)則簡(jiǎn)單很多。原因是Allreduce有一個(gè)很好的性質(zhì)，每一個(gè)節(jié)點(diǎn)最后拿到的是一樣的結(jié)果，這意味著我們可以讓一些節(jié)點(diǎn)記住結(jié)果。當(dāng)有節(jié)點(diǎn)掛掉重啟的時(shí)候，可以直接向還活著的節(jié)點(diǎn)索要結(jié)果就可以了。

容錯(cuò)過(guò)程：

1、Node1在第二個(gè)checkpoint之后的第一次和第二次allreduce中間掛了

2、當(dāng)Node1重啟，它會(huì)調(diào)用LoadCheckPoint，這樣可以從其他節(jié)點(diǎn)得到最近的一次CheckPoint

3、Node1從當(dāng)前的CheckPoint開(kāi)始跑，并進(jìn)行第一次Allreduce,這時(shí)其他節(jié)點(diǎn)已經(jīng)知道了結(jié)果并把結(jié)果告訴Node1

4、當(dāng)Node1執(zhí)行到第二個(gè)Allreduce，這時(shí)大家就已經(jīng)完全同步上了

有了Allreduce容錯(cuò)機(jī)制和近似算法確定分割點(diǎn)，XGBoost算法可以運(yùn)行在很多已知的集群上，如MPI,Yarn...

XGBoost on spark

由于spark等基于JVM平臺(tái)的大數(shù)據(jù)處理系統(tǒng)應(yīng)用越來(lái)越廣泛，于2016.4月XGBoost推出了基于spark/Flink的XGBoost4J(XGBoost for JVM Platform)。

XGBoost4J的核心與XGBoost一樣，分布式實(shí)現(xiàn)仍然采用rabit Allreduce，但是抽象了一套Java/Scala接口，供spark平臺(tái)使用。

XGBoost-spark應(yīng)用

XGBoost-spark在蘑菇街廣告排序中的特征處理和參數(shù)選擇與單機(jī)版本基本一致，在分布式環(huán)境中需要注意的幾個(gè)問(wèn)題：

1、numWorker參數(shù)應(yīng)該與executor數(shù)量設(shè)置一致，executor-cores設(shè)置為1(筆者認(rèn)為的最優(yōu)化的配置)

2、在train的過(guò)程中，每個(gè)partition占用的內(nèi)存最好限制在executor-memory的1/3以內(nèi)，因?yàn)槌吮緛?lái)訓(xùn)練樣本需要駐留的內(nèi)存外，xgboost為了速度的提升，為每個(gè)線程申請(qǐng)了額外的內(nèi)存，并且這些內(nèi)存是JVM所管理不到的

3、對(duì)于需要在集群機(jī)器上共享的資源，比如字典/庫(kù)文件等，spark提供了一套類似于hadoop distribute cached的機(jī)制來(lái)滿足需求

XGBoost與LR的結(jié)合

看到這里，其實(shí)本文的主題已經(jīng)結(jié)束了，這里是bonus。

XGBoost+LR結(jié)合的思想源于facebook的研究論文[5],使用樹(shù)模型來(lái)做特征選擇，最后用LR來(lái)輸出CTR分?jǐn)?shù)，充分利用了兩種模型的優(yōu)點(diǎn)，實(shí)踐證明，XGBoost+LR離線評(píng)估和線上AB都優(yōu)于單獨(dú)XGBoost。除了論文中提供的方案帶來(lái)的收益外，我們還將這種stacking的想法做了發(fā)揮，工程上單獨(dú)抽取出LR層，這樣做有如下優(yōu)點(diǎn)：

1、對(duì)于一些類似于ID類的非連續(xù)特征，可以單獨(dú)使用LR層來(lái)承載

2、事實(shí)上很多feature extraction 強(qiáng)大的模型稍作處理都可以作為L(zhǎng)R層的輸入，處理得當(dāng)?shù)脑?#xff0c;LR還是很強(qiáng)大的

3、通過(guò)在LR層組合不同的特征來(lái)源，方便的做到“刻畫(huà)”和“泛化”的結(jié)合，類似于deep and wide這樣的思想

4、LR本身的優(yōu)勢(shì)，適合大規(guī)模并行，online learning算法成熟等等。。。

總結(jié)

本文首先簡(jiǎn)要介紹了XGBoost的原理和相比其他機(jī)器學(xué)習(xí)方法的優(yōu)勢(shì)，并以蘑菇街CPC廣告中的CTR預(yù)估為例，介紹了XGBoost的應(yīng)用，最后闡述了分布式實(shí)現(xiàn)的問(wèn)題和在spark上應(yīng)用的注意事項(xiàng)。

廣告排序是計(jì)算廣告的核心問(wèn)題，未來(lái)我們會(huì)嘗試更多的方案，更大的數(shù)據(jù)集，以取得更加好的效果。

• 參考文獻(xiàn)

  [1]: Greedy function approximation: a gradient boosting machine

  [2]: XGBoost: A Scalable Tree Boosting System（KDD16）

  [3]: A fast algorithm for approximate quantiles in high speed data streams [4]: XGBoost: A Scalable Tree Boosting System Supplementary Material [5]: Practical Lessons from Predicting Clicks on Ads at Facebook

總結(jié)

以上是生活随笔為你收集整理的XGBoost 与 Spark 在广告排序中的应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。