本文是我最近學(xué)習(xí)的一個總結(jié)，之前的文章多是和功能特別是廣告主界面有關(guān)，而本篇文章則是和策略有關(guān)。在文章會講述計算廣告（主要是DSP）中的主要模塊、用到的策略及其場景。希望大家能和我一樣，在了解廣告業(yè)務(wù)的同時，還能對策略的設(shè)計有一定了解，總結(jié)出一些通用的方法。

本文分三個部分，功能和策略，主講功能型產(chǎn)品和策略型產(chǎn)品的區(qū)別；架構(gòu)綜述，主講廣告系統(tǒng)的流程、模塊和技術(shù)架構(gòu)；算法和場景，主講各個模塊和場景中用到的算法。功能和策略、架構(gòu)綜述在上篇已經(jīng)講了，在此下篇中將接著講算法和場景。

GBDT模型

GBDT的全稱是（Gradien Boosting Decision Trees），是一種決策樹，屬于Boosting族，能將弱學(xué)習(xí)器提升為強學(xué)習(xí)器。GBDT中文叫梯度提升決策樹，由多棵決策樹構(gòu)成，最終的預(yù)測結(jié)果是將所有決策樹的結(jié)果累加得到。

提升即迭代，是不斷縮小殘差（真實值-預(yù)測值）的過程，建立M個決策樹模型，每個模型都是弱分類器，每次分類后對分錯的數(shù)據(jù)的權(quán)重增加后再分類，一直到訓(xùn)練和測試數(shù)據(jù)獲得較好結(jié)果。

訓(xùn)練一個提升樹模型來預(yù)測年齡：訓(xùn)練集是4個人，A，B，C，D年齡分別是14，16，24，26。樣本中有購物金額、上網(wǎng)時長、經(jīng)常到百度知道提問等特征。

提升樹的過程如下：

該例子很直觀的能看到，預(yù)測值等于所有樹值得累加（GBDT是加權(quán)累加），如A的預(yù)測值=樹1左節(jié)點值15+ 樹2左節(jié)點-1=14。可以看到第二顆樹是對第一顆樹的補充，學(xué)術(shù)的描述就是每一次建立模型是在之前建立模型的損失函數(shù)的梯度下降方向，這就是梯度提升的過程，也用到了損失函數(shù)。

F0在這里是初始值，Ti是一棵棵的決策樹，不同的問題選擇不同的損失函數(shù)和初始值。損失函數(shù)可以用平方損失函數(shù)或者指數(shù)損失函數(shù)等。

此外，在使用特征或?qū)傩赃M(jìn)行分支時，分支規(guī)則采用最小均方差的方式，即預(yù)測誤差的殘差的平方和去除以N，誤差越多錯的越多，通過這種方式找到最好的分支依據(jù)。

GBDT的損失函數(shù)和邏輯回歸中的概念類似，描述的是當(dāng)前模型偏差的程度，損失函數(shù)越大，偏差越大，模型出錯程度越高。

訓(xùn)練目的就是讓損失函數(shù)的值不斷下降，每次修正的過程中按梯度下降的方向作為修正方向，步長選擇不能過大，過大的逼近可能會導(dǎo)致過擬合，每次走一小步可以避免這種情況，但步長范圍設(shè)置過小也會導(dǎo)致計算和預(yù)測時間大大增加。步長等超參數(shù)的如何設(shè)置的問題，幾乎在絕大部分模型中都會遇到。

在《在線廣告DSP平臺實時競價算法的研究與實現(xiàn)》 中，運用GBDT來預(yù)估CTR預(yù)估，是用開源的xgboost實現(xiàn)，設(shè)置樹深度為4，訓(xùn)練了300棵數(shù)，學(xué)習(xí)速率設(shè)為0.1。

決策樹的個數(shù)越多學(xué)習(xí)越充分，但也會導(dǎo)致過擬合。學(xué)習(xí)速率可以稍微設(shè)快，可以減少樹的數(shù)量。

實驗中特征變量選取的都是連續(xù)值變量，如不同地區(qū)的特征變量則計算出它的發(fā)生頻率和點擊率，并將其作為梯度提升決策樹的兩個特征。廣告的底價由于是連續(xù)值，可直接用于梯度提升決策樹的變量值。

并非所有變量都能對模型產(chǎn)生很大影響，因此在特征選取時不會像邏輯回歸那樣需要選擇很多特征，GBDT會放棄大多數(shù)特征而保留一小部分，學(xué)習(xí)過程中選用了72個特征作為訓(xùn)練和預(yù)測的變量。而邏輯回歸在實驗中共選取了61萬余個特征。

GBDT+LR模型

由于GBDT所需特征量遠(yuǎn)小于邏輯回歸的特征數(shù)量，自然想到利用GBDT來選擇特征。Facebook基于GBDT提出了GBDT+LR模型，這是一種利用GBDT自動進(jìn)行特征篩選和組合，進(jìn)而生成新的離散特征向量，再把該特征向量當(dāng)作LR模型輸入，預(yù)估CTR的模型結(jié)構(gòu)。

模型結(jié)構(gòu)

其中用GBDT實現(xiàn)特征工程和用LR預(yù)估CTR兩步是獨立訓(xùn)練的，因此不存在如何將LR梯度會傳到GBDT這類復(fù)雜問題。

GBDT中每棵樹生成的過程是一棵標(biāo)準(zhǔn)的回歸樹生成過程，因此每個節(jié)點的分裂是一個自然的特征選擇的過程，而多層節(jié)點的結(jié)構(gòu)自然進(jìn)行了有效的特征組合，也就非常高效的解決了過去非常棘手的特征選擇和特征組合的問題。

利用訓(xùn)練集訓(xùn)練好GBDT模型之后，就可以利用該模型完成從原始特征向量到新的離散型特征向量的轉(zhuǎn)化。

具體過程是這樣的，一個訓(xùn)練樣本在輸入GBDT的某一子樹后，會根據(jù)每個節(jié)點的規(guī)則最終落入某一葉子節(jié)點，那么我們把該葉子節(jié)點置為1，其他葉子節(jié)點置為0，所有葉子節(jié)點組成的向量即形成了該棵樹的特征向量，把GBDT所有子樹的特征向量連接起來，即形成了后續(xù)LR輸入的特征向量。

GBDT生成特征向量的過程

舉例來說，如上圖所示，GBDT由三顆子樹構(gòu)成，每個子樹有4個葉子節(jié)點，一個訓(xùn)練樣本進(jìn)來后，先后落入“子樹1”的第3個葉節(jié)點中，那么特征向量就是[0,0,1,0]，“子樹2”的第1個葉節(jié)點，特征向量為[1,0,0,0]，“子樹3”的第4個葉節(jié)點，特征向量為[0,0,0,1]，最后連接所有特征向量，形成最終的特征向量[0,0,1,0,1,0,0,0,0,0,0,1]。

由于決策樹的結(jié)構(gòu)特點，決策樹的深度就決定了特征交叉的維度。如果決策樹的深度為4，通過三次節(jié)點分裂，最終的葉節(jié)點實際上是進(jìn)行了3階特征組合后的結(jié)果，如此強的特征組合能力顯然是FM系的模型不具備的。

但由于GBDT容易產(chǎn)生過擬合，以及GBDT這種特征轉(zhuǎn)換方式實際上丟失了大量特征的信息，因此我們不能簡單說GBDT由于特征交叉的能力更強，效果就比FFM好，在模型的選擇和調(diào)試上，永遠(yuǎn)都是多種因素綜合作用的結(jié)果。GBDT+LR比FM重要的意義在于，它大大推進(jìn)了特征工程模型化這一重要趨勢。

POLY2、FM、FFM模型

由于LR模型的表達(dá)能力非常初級，只能使用單一特征，無法利用高維信息。而針對這個問題，工程師通常需要人工組合特征，但是人力畢竟有限，因此就有了POLY2模型。并從POLY2進(jìn)化到FM再到FFM，這其中體現(xiàn)出的方向、思維和方法論，比模型本身更值得我們學(xué)習(xí)。

POLY2

在上面POLY2二階部分的目標(biāo)函數(shù)中（上式省略一階部分和sigmoid函數(shù)的部分），可以看到POLY2對所有特征進(jìn)行了兩兩交叉，并對所有的特征組合賦予了權(quán)重。POLY2通過暴力組合特征的方式一定程度上解決了特征組合的問題。并且由于本質(zhì)上仍是線性模型，其訓(xùn)練方法與LR并無區(qū)別，便于工程上的兼容。

而POLY2的缺陷在于是對特征組合賦予權(quán)重，特征組合會讓原本就很稀疏的特征向量更加稀疏，如果樣本中沒有出現(xiàn)這個組合特征就學(xué)習(xí)不到權(quán)重；同時權(quán)重參數(shù)的數(shù)量由n上升到n^2，極大增加了訓(xùn)練復(fù)雜度和收斂難度。

FM

相比POLY2，主要區(qū)別是用兩個向量的內(nèi)積（wj1·wj2）取代了單一的權(quán)重。FM為每個特征都學(xué)習(xí)一個隱向量（latent vector），在特征交叉時，使用兩個特征隱向量的內(nèi)積作為交叉特征的權(quán)重。每一個隱向量都包含k個latent factors，k是人為設(shè)定的超參數(shù)，例如上述的k就是2。

訓(xùn)練數(shù)據(jù)

以此訓(xùn)練數(shù)據(jù)為例，在ESPN廣告中，Adidas的樣本只有一個，預(yù)測結(jié)果是-1，那么Poly2對于這個組合特征會學(xué)到一個非常大的負(fù)的權(quán)重。但是，F(xiàn)M對于樣本(ESPN，Adidas)的預(yù)測，是由兩個向量決定的：W_espn * W_adidas 。 而這兩個向量，可以單獨的去從其他的樣本中學(xué)習(xí)，比如：（ESPN，Nike），（BBC，Adidas）。 所以FM這樣學(xué)習(xí)的更加準(zhǔn)確。

通過引入特征隱向量的方式，直接把原先n^2級別的權(quán)重數(shù)量減低到了n*k（k為隱向量維度，n>>k）。也許FM相比POLY2丟失了某些信息的記憶能力，但是泛化能力大大提高，這對于互聯(lián)網(wǎng)的數(shù)據(jù)特點是非常重要的。

FFM

FFM模型學(xué)習(xí)每個特征在f個域上的k維隱向量，交叉特征的權(quán)重由特征在對方特征域上的隱向量內(nèi)積得到，權(quán)重數(shù)量共n*k*f個?？傊?，F(xiàn)FM引入了域的概念，為模型引入了更多的信息，模型建模更加準(zhǔn)確，但是計算復(fù)雜度較高達(dá)到kn^2。

損失函數(shù)

損失函數(shù)可以用logistic loss，加上L2懲罰項，因此只能用于二分類。其中，yi是-1，+1表示label，L是樣本數(shù)量，lambda是懲罰項系數(shù)。

CTR預(yù)估平臺

在實際業(yè)務(wù)中CTR預(yù)估的場景有很多，例如點評猜你喜歡、點評商品詳情頁推薦、美團(tuán)猜你喜歡等等多款應(yīng)用多個業(yè)務(wù)，而CTR預(yù)估中模塊等都是一致的，這就涉及到造輪子的問題。

廣告排序架構(gòu)圖

廣告架構(gòu)圖中最重要的就是精排，前文也有講，離線要為在線提供模型等等，離線訓(xùn)練和在線預(yù)估統(tǒng)稱為CTR預(yù)估。

從多套流程到統(tǒng)一框架

而一開始美團(tuán)使用的是【多套流程】方案，一方面是不同位置之間區(qū)別較大，點評和美團(tuán)是差異很大的兩個應(yīng)用，猜你喜歡和詳情頁推薦差異也很大；另一方面也是有很多隱藏的歷史原因，因此不能簡單的把輪子組合到一起。

多套流程

如上圖所示，為了快速支持業(yè)務(wù)，在不同位置上有不同的團(tuán)隊和人員負(fù)責(zé)，但是存在以下幾個問題：

1. 分位置優(yōu)化成本高，對某個鏈路的優(yōu)化不能迅速的擴(kuò)大到其他位置；
2. 對人員要求高，要求掌握全鏈路所有模塊，整個流程復(fù)雜；
3. 在線還要做很多工作，很容易出錯，離線效果不等于在線效果。

要調(diào)整到【統(tǒng)一框架】方案，其中有三個問題：

1. 雙平臺多業(yè)務(wù)，代碼如何統(tǒng)一合并；
2. 如何保證線下線上效果一致；
3. 復(fù)雜的離線回溯中涉及到半年的數(shù)據(jù)數(shù)百個任務(wù)如何調(diào)度。

市面上有在線到離線和離線到在線兩個流派，前者重在線，在線做特征速度很快，而且能保證線上線下一致，但是對特征工程和海量數(shù)據(jù)不友好；后者重離線，離線做歷史數(shù)據(jù)的拼接、樣本、模型訓(xùn)練等，更適合海量數(shù)據(jù)量，例如百度要用最近半年的數(shù)據(jù)。美團(tuán)用的是離線到在線。

統(tǒng)一框架

• Match是個基本的打分單元，在不同場景下打分單元不同，由業(yè)務(wù)定義，例如：在廣告推薦場景就是遇到某個廣告并對其打分。
• Cube則是CTR預(yù)估流程的抽象，所有的CTR預(yù)估都是這個流程，與業(yè)務(wù)無關(guān)。
• Tesla是業(yè)務(wù)插件，用來定義Match是什么、特征是什么等。
• Solar則是離線復(fù)雜邏輯調(diào)度以及基本算子，包括多天數(shù)據(jù)、user context ad如何構(gòu)建、怎么match等多天任務(wù)流，以及整個離線過程中的功能因子，例如：數(shù)據(jù)庫常見操作join，在千億樣本和千億特征中，join會傾斜，而抽象出來后只要用Solar中的算子即可無需考慮傾斜的情況。

解決離線在線一致的情況，要從數(shù)據(jù)一致和代碼一致兩個角度去考慮。由于離線在線用的Cube是同一套，代碼自然一致。此外，離線ETL加工數(shù)據(jù)并同步到線上，對于一個請求User Context Ad三元組，拼成一樣的Match，以此實現(xiàn)數(shù)據(jù)的一致。

統(tǒng)一框架中的分工

統(tǒng)一框架就是每個平臺+虛線框就有某個人負(fù)責(zé)，大大提高開發(fā)和部署效率。但是仍然存在幾個問題，業(yè)務(wù)代碼接口較多，實現(xiàn)較難，美團(tuán)推薦接入要2周；仍舊要掌握全鏈路，離線在線都要做，容易出錯；數(shù)據(jù)、代碼共享復(fù)雜，管理也較為復(fù)雜。

從統(tǒng)一框架到框架平臺化

框架平臺化

上圖中不存在Cube和Tesla，可總結(jié)為一句話：一份數(shù)據(jù)三個流程。

數(shù)據(jù)就是offline entity，之前的User Context Ad都是entity，是排序中的實體，實際用的時候可以選擇是在線entity還是離線回溯的entity。

• 第一個流程就是match joiner，指要把哪些entity join成match。
• 第二個流程是特征提取。
• 第三個流程是模型訓(xùn)練和預(yù)估。

全部都可以抽象出來，通過配置實現(xiàn)，在除了特征處理以外的流程，不同業(yè)務(wù)不一樣的參數(shù)較少，所以比較好做，但是特征處理有點麻煩。

特征抽取

element中是基本算子，operator、generator等都是定義好的，只需要配置即可使用。

框架平臺化的分工

根據(jù)上圖中的分工，可以很明顯看到，專人負(fù)責(zé)專模塊，數(shù)據(jù)、特征、模型、業(yè)務(wù)等都有人負(fù)責(zé)，業(yè)務(wù)則是把數(shù)據(jù)定義好、把各個流程組裝好，無需寫代碼直接配置即可。新業(yè)務(wù)通過復(fù)用已有entity只需要1天時間，模塊化流水線化效率大大提升，模塊專人優(yōu)化降低門檻做深做精。

總結(jié)美團(tuán)CTR預(yù)估平臺的特點，能力強勁，支持千億樣本百億特征的海量數(shù)據(jù)處理，支持LR、XGB、DNN等多模型；使用簡便，全流程可配置，拖拽可視化即可實現(xiàn)。

效果優(yōu)化

優(yōu)化目標(biāo)有兩點，讓CTR預(yù)估更準(zhǔn)確或者是廣告樣式更吸引人點擊。優(yōu)化方向則有數(shù)據(jù)、特征、模型、策略和樣式。

優(yōu)化方向

從美團(tuán)上來說，模型經(jīng)過XGBoost→LR→FFM→DNN能力越來越強，樣本量從億級→十億級→百億級→More越來越大，特征維度從百級→億級→千億級越來越高。樣本量、特征維度與模型之間并不是孤立的，模型并非簡單的使用，而是要與合適量級的樣本量和特征維度相配合，才能發(fā)揮模型的能力。

從XBGoost到大規(guī)模稀疏模型LR，模型描述能力更強，復(fù)雜低維特征到簡單高維特征，從百萬樣本到億級別樣本，CTR大約提升10%；從億級別樣本到百億樣本，從百萬特征到億特征，CTR大約提升5%。

從LR到FFM，F(xiàn)FM能夠自動學(xué)習(xí)特征交叉似的表達(dá)能力更強，適用于未知場景的預(yù)估能力更強，CTR大約提升3%。

總體來看，隨著樣本來那個增加，效果整體提升并趨于收斂；隨著特征規(guī)模增加，效果先變好后變差，前期特征變多模型表達(dá)能力變強，稀疏特征變多，過擬合嚴(yán)重，泛化能力變?nèi)酢?/p>

樣本量特征維度和AUC

從提升CTR效果上來說，特征＞樣式＞模型＞策略＞數(shù)據(jù)，模型要與合適量級的樣本量和特征維度相配合才能真正發(fā)揮能力，而非簡單的更換模型。

數(shù)據(jù)和策略上的調(diào)整很多時候還不如一個標(biāo)紅的樣式，但是不可否認(rèn)數(shù)據(jù)和策略等的價值，要根據(jù)不同優(yōu)化方向的效果和當(dāng)前場景和瓶頸，排出不同優(yōu)先級，選擇不同的資源投入。

Y>N>Z>M>X

出價

下圖中的Bidding Engine就是競價模塊，其中包括實時的出價計算（Bid Calculation）、曝光價值評估（Impression Evaluation）和離線的競價函數(shù)優(yōu)化（Bidding Function Optimisation）、CTR/CVR預(yù)估、勝出模型。出價計算和競價函數(shù)優(yōu)化是核心，其他功能并非所有公司都會用到的。

競價引擎

核心問題

競價的目的就是約束下最大化DSP利潤，考慮因素包括預(yù)算約束、曝光價值、競價勝出率等。不同的競價策略考慮的因素不同，并非每種策略都要考慮所有因素。

約束下最大化DSP利潤模型

把流量、廣告分為供給節(jié)點、需求節(jié)點，約束一是某個供給節(jié)點提供給某個需求節(jié)點的占比≤1，某個供給節(jié)點的總供給量就是1，約束二是某個需求節(jié)點購買某個供給節(jié)點的總花費≤需求節(jié)點預(yù)算，DSP利潤則是所有供給節(jié)點與需求節(jié)點之間的每次分配的（收益r-成本m）之和。

流量節(jié)點往小了看，可以是每個曝光就是一個流量節(jié)點。收益r則是此次曝光的曝光價值，曝光價值=點擊率*點擊價值=點擊率*轉(zhuǎn)化率*轉(zhuǎn)化價值，成本m則是此次曝光的曝光成本，即此次曝光最后結(jié)算費用，對于歷史曝光來說，成本是已知的，而對于此次曝光，成本是未知的，且不一定是出價，勝率也是未知的。

曝光價值預(yù)估（收益r）

曝光價值=點擊率*點擊價值=點擊率*轉(zhuǎn)化率*轉(zhuǎn)化價值，如果廣告主是對每次曝光出價，那么曝光價值直接用廣告主的出價價格即可；如果廣告主是對每次點擊出價，那么點擊價值直接用廣告主的出價價格即可，點擊率仍然需要預(yù)估；如果廣告主是對每次安裝/購物等轉(zhuǎn)化行為出價，那么轉(zhuǎn)化價值直接用廣告主的出價價格即可，轉(zhuǎn)化率仍然需要預(yù)估。

其實除了轉(zhuǎn)化率之外，還有到達(dá)率也會影響點擊價值，點擊價值(a,u,c)=到達(dá)率(a,c)*轉(zhuǎn)化率(a,u)*轉(zhuǎn)化價值(a)，a是廣告主，c是媒體，u是用戶，但是達(dá)到率dsp控制不了，不在討論范圍內(nèi)。

點擊率預(yù)估方式上文已經(jīng)講過了，而轉(zhuǎn)化率的預(yù)估則大有不同。目標(biāo)、轉(zhuǎn)化行為、廣告主等多種多樣，不同目標(biāo)甚至用的模型都不同，而且轉(zhuǎn)化樣本少，數(shù)據(jù)很稀疏，同時廣告投放次數(shù)對轉(zhuǎn)化率影響很大。一定要注意廣告投放次數(shù)和轉(zhuǎn)化率冷啟動兩個點。

同一個廣告針對同一個人群進(jìn)行連續(xù)投放，越到后面效果肯定越差，所以要把廣告投放次數(shù)放入模型中。以特定廣告與人群的歷史投放數(shù)據(jù)為基礎(chǔ)，采用時間序列分析方法，訓(xùn)練出轉(zhuǎn)化率隨投放重復(fù)次數(shù)變化的曲線模型參數(shù)。該模型可以用來預(yù)測特定特定廣告、人群、重復(fù)投放次數(shù)下的轉(zhuǎn)化率。

轉(zhuǎn)化率預(yù)測時，要特別注意是否有足夠的歷史數(shù)據(jù)，此外預(yù)測不可貿(mào)然交給機(jī)器完成，要把統(tǒng)計、經(jīng)驗等結(jié)合起來估算轉(zhuǎn)化率。當(dāng)然，如果是DSP廣告主類型和轉(zhuǎn)化流程基本一致，例如專注于游戲客戶的DSP或者是專注于阿里體系內(nèi)電商的阿里媽媽，那么在轉(zhuǎn)化數(shù)據(jù)充分情況下可采用機(jī)器學(xué)習(xí)建模方法預(yù)測。

若沒有足夠歷史數(shù)據(jù)，則要引入基于規(guī)則的簡單方法，核心思想就是以最相似廣告最近一次對該人群進(jìn)行投放的轉(zhuǎn)化率作為參考。

對應(yīng)的廣告與人群在最近1周內(nèi)有投放記錄時，取最近一天投放時的轉(zhuǎn)化率；對應(yīng)的廣告與人群在歷史上有投放記錄時，取歷史中選定的最近一段時間內(nèi)投放轉(zhuǎn)化率放入率平均值；若對應(yīng)的廣告與人群在歷史上沒投放記錄，但同類廣告與該人群有投放記錄時，取歷史中選定的最近一段時間內(nèi)投放轉(zhuǎn)化率放入平均值；若對應(yīng)的廣告或同類廣告與該人群在歷史上都沒投放記錄，取平臺平均的投放轉(zhuǎn)化率值。

成本m和勝率函數(shù)

可直接把出價當(dāng)做成本m，但是多是采用第二高價競價，出價比成本要低，最好建立一個專門的市價預(yù)測模型來估計m，但遠(yuǎn)沒有曝光價值的預(yù)估可靠，不宜使用過于復(fù)雜的模型和算法，主要使用時間、地域、媒體屬性等影響明確的因素來進(jìn)行預(yù)估。

有些競價策略還考慮了勝率函數(shù)，勝率函數(shù)可根據(jù)歷史樣本得到，但是要注意針對每個廣告主進(jìn)行訂制，且ADX發(fā)來的競價請求一般是有低價的，低于底價的競價都是不成功，而高于一定價格，競價一般都會成功，因此勝率函數(shù)兩端的曲率要高。此外，點擊率低于某個值，還可直接不出價。

在這個過程中，還存在幸存者偏差和刪失兩個問題。幸存者偏差是指，作為DSP贏下了所有bidding請求，并可以觀察到所有bidding的市場價格。然而，在實際RTB中，各家DSP的策略不斷調(diào)整，導(dǎo)致每家DSP都無法得到競標(biāo)失敗的數(shù)據(jù)的反饋，且這種數(shù)據(jù)缺失是非隨機(jī)的。

這會導(dǎo)致非常嚴(yán)重的后果：從ADX得到的反饋用于訓(xùn)練的數(shù)據(jù)和測試的數(shù)據(jù)分布不同。

競價動態(tài)數(shù)據(jù)過濾器

競價過程等同于一個動態(tài)的數(shù)據(jù)過濾器，隨bid value而不同。由于競價失敗的請求無法得到曝光，不能出現(xiàn)在模型依賴的訓(xùn)練數(shù)據(jù)中，整個訓(xùn)練數(shù)據(jù)相對于full-volume data是有偏的。

訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)的總體分布相同是監(jiān)督學(xué)習(xí)（supervised learning）的理論基石。在常見的業(yè)務(wù)場景如推薦中，訓(xùn)練樣本與測試樣本存在采樣偏差，但總體分布是相同的；而在DSP中，樣本的總體分布都不相同。

在有偏分布下，任何監(jiān)督學(xué)習(xí)方法都是低效且過擬合的；需要的一種解決思路是將有偏的訓(xùn)練數(shù)據(jù)分布試圖重構(gòu)到整體分布上。例如用Kaplan-Meier Product-Limit可針對“存在非隨機(jī)數(shù)據(jù)缺失”的情況進(jìn)行分布估計。

在實時競價廣告系統(tǒng)中普遍存在一個“軟地板價”的機(jī)制，若最高價低于軟地板價則采用第一高價，此時無關(guān)DSP贏標(biāo)與否都只能觀測到第一高價（即支付價格）。也就是說，會出現(xiàn)贏標(biāo)后只得到自己出價的情況，只能作出估計第二高價最高不超過自己實際支付價格，因此這種得到的估價是估值過高的。這種就叫刪失?？梢砸敫們r失敗價格因素。

競價策略

前文雖然說了很多因素，但是競價策略有很多種，并非每種都會考慮上面所有因素。例如下圖中就是一些競價策略考慮到的因素，當(dāng)然除了這些以外還有其他競價策略。

幾種競價策略

出價邏輯

定值出價：對所有展示請求都出同一個價格，模型的唯一參數(shù)就是其價格。簡單粗暴，但很多DSP在用。

隨機(jī)出價：在一個給定價格區(qū)間中隨機(jī)出價，唯一參數(shù)是競價的區(qū)間上限，一般也給定，下限一般是0。

真實出價：就是按照計算的曝光價值出價，計算多少就出價多少，當(dāng)然轉(zhuǎn)化率預(yù)估的問題之前也有提到。

受限點擊成本出價：在CPC模式下，廣告主一般會設(shè)定可接受的最高點擊成本(mCPC)，這時就可以通過計算mCPC*CTR來出價。如果點擊率預(yù)估準(zhǔn)確，該策略可以保證其支出小于收入。

線性出價：出價與估計的點擊率成正比，但要設(shè)置基準(zhǔn)出價，即：

b0是基準(zhǔn)出價，θ0、θ分別是該廣告的平均點擊率以及該請求下預(yù)測的點擊率。此外，還可以引入其他邏輯，例如θ/θ0低于0.8不出價，高于1.2出價翻倍等。

非線性出價：出價模型在有預(yù)算限制的情況下最大化收益(點擊數(shù)或轉(zhuǎn)化數(shù))。假設(shè)某個廣告推廣在一定時期T內(nèi)總共符合其定向的廣告請求共NT個，每個廣告請求特征向量為x,滿足定向條件的x先驗為px(x)。給定收益函數(shù)θ(x)，競價函數(shù)b(θ(x))，競價成功率函數(shù)w(b(θ(x)))，假設(shè)該廣告的預(yù)算為B, 則優(yōu)化目標(biāo)可以寫成：

由于x和θ(x)的關(guān)系是確定的

進(jìn)而可以把優(yōu)化目標(biāo)寫成：

利用拉格朗日乘子法，目標(biāo)函數(shù)變?yōu)椋?/p>

其中λ為拉格朗日乘子。通過對b(θ)求偏導(dǎo)并令其等于零，可以得到：

競價成功率與出價的函數(shù)可以表示為：

其中c是一個常量。將此函數(shù)代入上式，得到：

可以看出，最優(yōu)的出價是收益的一個非線性函數(shù)。

該策略的出價函數(shù)中有兩個參數(shù)，分別是c和λ。其中c可以通過一段時間的盲投（比如利用隨機(jī)出價策略），得到多個出價與成功率的離散點，再利用最小二乘法擬合曲線得到；λ可以通過網(wǎng)格遍歷的方法，利用歷史日志計算不同取值時的收益，從中選取最高的那個。

預(yù)算

預(yù)算也是另一個重要的策略點，廣告主在投放廣告時，會為每個廣告活動（campaign或者adset）設(shè)置一個時間范圍內(nèi)的預(yù)算，預(yù)算就是上文提及的最大化DSP利潤中的約束。

如果不對預(yù)算進(jìn)行合理管控，會出現(xiàn)三種情況：

1. 預(yù)算迅速消耗完畢，但是贏得了很多價值不高的請求，更失去了贏得后續(xù)收益更高請求的機(jī)會，導(dǎo)致最終廣告效果較差 ；
2. 時間范圍結(jié)束后，預(yù)算仍有大量剩余，導(dǎo)致輸了很多高價值的請求；
3. 由于市場競爭變化及其他因素變化，導(dǎo)致市場波動，似的預(yù)算消耗速度忽高忽低，無法管控和預(yù)測預(yù)算消耗。這三種情況都會導(dǎo)致預(yù)算利用率下降，從而使得廣告整體的量級和ROI均下滑，可嘗試?yán)脛討B(tài)規(guī)劃算法來求解。

因此，控制預(yù)算消耗的主要目標(biāo)是：

1. 同時得到廣告的投放和性能目標(biāo)，效果類廣告是根據(jù)廣告主所給出的優(yōu)化目標(biāo)，提升活動整體的ROI，品牌類廣告則需要觸達(dá)更多人群，提高廣告回想度；
2. 滿足廣告主設(shè)定的預(yù)算使用速率，勻速的預(yù)算使用速率能讓廣告在時間范圍內(nèi)勻速消耗預(yù)算，保證在更長時間內(nèi)有曝光效果，每個時間段內(nèi)花費相對平穩(wěn)。而加速的預(yù)算使用速率用于時效性更強的推廣，例如雙十一電商廣告投放等；
3. 降低數(shù)據(jù)咨詢花費，DSP通常要用自有第一方數(shù)據(jù)和來自DMP第三方用戶數(shù)據(jù)來做出理想決策，除了性能以外，DMP還要收取額外費用，降低數(shù)據(jù)咨詢次數(shù)能降低這方面的開銷。

（a）預(yù)算過早耗盡 （b）預(yù)算波動劇烈

主要目標(biāo)1可由效果預(yù)估和出價算法做較大提升，主要目標(biāo)2和3則極大依賴于預(yù)算步進(jìn)算法。所謂預(yù)算步進(jìn)算法（Budget Pacing）是指通過對歷史行為數(shù)據(jù)的分析，得出一個符合近期趨勢的廣告預(yù)算分配計劃，具體計劃是預(yù)算花費與時間的變化趨勢，且通過控制實際的花銷進(jìn)度去接近這個分配計劃，最終保證預(yù)算的按計劃分配。

結(jié)合實時競價實際場景，給定一個廣告活動（設(shè)置預(yù)算廣告級別）一天的預(yù)算限制（總預(yù)算則換算成每日預(yù)算），在設(shè)計一個依照時間變化的分配策略，保證實際花銷與理想進(jìn)度盡可能接近。

業(yè)界一開始用簡易的預(yù)算步進(jìn)算法，用于保證單位時間內(nèi)的花銷大約均等。但一天中廣告流量等都在變化，這種方案難以顧及這些問題。Joaquin等人利用動態(tài)規(guī)劃和變分法證明了理想的預(yù)算花費并非線性也并非單位時間均等，而是正比于廣告交易量。

ipinyou數(shù)據(jù)集中03月11日的競標(biāo)和曝光次數(shù)趨勢圖

分配計劃正比于廣告流量的變化趨勢，廣告投放到一天內(nèi)任意一個用戶的幾率均等，從而保證廣告均勻的分配到受眾群體上，重點是分配機(jī)會的均等而非時間段均等。此外，廣告關(guān)鍵指標(biāo)（優(yōu)化目標(biāo)）和廣告市場的競爭程度也是需要考慮的點。不同時間段內(nèi)的點擊率、轉(zhuǎn)化率等關(guān)鍵指標(biāo)并非恒定，因此對于廣告主來說價值不同。

關(guān)于廣告市場競爭程度，根據(jù)Yuan Shuai等人研究RTB基本問題時，統(tǒng)計的數(shù)據(jù)圖（下圖）所示，0到5時由于激烈市場競爭加上較少的用戶數(shù)會導(dǎo)致非常高的市場成交價，此時廣告主投入較多預(yù)算得不償失，競標(biāo)的廣告主數(shù)量的變化趨勢與廣告流量變化有很大出入。

競標(biāo)廣告主、展示量與時間的變化趨勢

預(yù)算步進(jìn)算法示意圖

因此，要基于廣告流量、廣告質(zhì)量、市場競爭程度確定分配計劃。步驟1用來計算分配計劃，對廣告請求進(jìn)行過濾，控制參與競標(biāo)的廣告請求數(shù)量滿足預(yù)算等限制條件。當(dāng)贏得交易后扣除預(yù)算，步驟2根據(jù)實際花銷與預(yù)計花銷之間的差異來實時調(diào)整下一個時刻的分配計劃。

預(yù)算步進(jìn)定義

本文提出的預(yù)算步進(jìn)方案采用了概率過濾機(jī)制，概率過濾值成為步進(jìn)率（Pacing Rate），是一個隨時間t的函數(shù)：

表示某個廣告主發(fā)起的廣告活動adc（campaign或者adset，看預(yù)算設(shè)置層級）在時段t參與投標(biāo)的概率。限定廣告活動adc是因為不同廣告活動設(shè)置不同行業(yè)、不同目標(biāo)、不同受眾群體等，導(dǎo)致不同廣告活動之間差異極大，必須為不同類廣告活動設(shè)置不同的廣告分配計劃，可用目標(biāo)一致，受眾群體相似的廣告活動作為冷啟動時的歷史數(shù)據(jù)。

實際操作中難以將p(t)當(dāng)做連續(xù)函數(shù)處理，一般將一天時間分段。若一天時間分為T段，則在時段的預(yù)計預(yù)算花銷為：

一天總預(yù)算：

在時間段t內(nèi)從ADX到來的共n個廣告請求為：

定義時間段t的請求數(shù)函數(shù)為req(t)，p(t)需要對廣告請求進(jìn)行第一次篩選，初步?jīng)Q定參與投標(biāo)的廣告請求為：

0表示未投標(biāo)，1表示通過初次篩選。那么步進(jìn)率可表示為：

而若投標(biāo)后贏得競標(biāo)的廣告請求序列為：

1表示贏得，則贏標(biāo)概率為：

這些廣告請求最終的花銷序列為：

未投標(biāo)和投標(biāo)失敗的花銷為0。時段t的實際花費與預(yù)計花費的差距越小越好，即：

在時段t中平均展示價格為：

此處的平均展示價格并非千次，且可根據(jù)經(jīng)驗及歷史記錄統(tǒng)計，線性回歸是一個業(yè)界常用解決方案。每個指標(biāo)函數(shù)都被指定到一個廣告活動adc中，因為不同廣告活動在個指標(biāo)函數(shù)中可能存在差異。

廣告質(zhì)量度

廣告展示質(zhì)量可通過不同時段的關(guān)鍵指標(biāo)變化體系，點擊、轉(zhuǎn)化等等均可作為變化趨勢。在質(zhì)量高的時段投入更多預(yù)算能夠提高廣告效果，應(yīng)當(dāng)照顧質(zhì)量較高的時段。本文定義廣告展示質(zhì)量度量應(yīng)該能夠反映當(dāng)前時段展示質(zhì)量與平均展示質(zhì)量的差距，為：

取值范圍再0到1之間，可利用一個映射函數(shù)：

將其控制在所需要的范圍內(nèi)，如logistic函數(shù)。定義某廣告活動adc的廣告展示質(zhì)量系數(shù)函數(shù)為：

α控制其變化速度，建議取值范圍：當(dāng)某時段展示質(zhì)量接近平均水平是其取值在1附近。

市場競爭程度

作為DSP本身是拿不到每次請求其他買家的數(shù)量，這個數(shù)量只有ADX掌握，且廣告流量與參與投標(biāo)的買家數(shù)量的變化趨勢不相同。然后思考贏標(biāo)價格或贏標(biāo)概率能否評價市場競爭程度，是由市場交易機(jī)制、參與投標(biāo)賣家策略、自身出價策略變化而決定，總結(jié)出贏標(biāo)價的高低受廣告質(zhì)量與競爭程度影響。刨除贏標(biāo)價中對廣告展示質(zhì)量的提現(xiàn)，剩下能夠影響到贏標(biāo)價的因素即競爭程度。

定義某時段成交價（記作cpm，注意此時是每次展示）與一天的平均成交價的差距為：

為了規(guī)范α(t)和β(t)量級，以便能求差值，需要先求得兩數(shù)的平方平均數(shù)：

能夠反映時段t的競爭程度，當(dāng)kpi恒定情況下，cpm越高，這個值越大，同等質(zhì)量的曝光卻又更高的成交價，說明競爭程度高；而另一方面，當(dāng)cpm穩(wěn)定而kpi更高時，即用較低的花銷買到更好質(zhì)量的展示，競爭程度低于正常水平。

同理經(jīng)過以平滑映射函數(shù)，定義廣告活動adc在時段t內(nèi)的競爭程度系數(shù)為：

注意兩個系數(shù)函數(shù)的參數(shù)α和β控制函數(shù)變化速度，且當(dāng)競爭程度較高時，步進(jìn)算法應(yīng)當(dāng)降低出價時機(jī)，即降低該因子系數(shù)從而最終降低該時刻出價概率，而映射函數(shù)

定義為單調(diào)遞增的平滑函數(shù)，所以應(yīng)取負(fù)號。

預(yù)算分配計劃

根據(jù)Joaquin等人證明不考慮其他因素時，最佳的分配計劃應(yīng)該完全正比于廣告流量，再加上本文提出的廣告質(zhì)量與競爭程度度量，則定義廣告活動adc在其t時段的分發(fā)概率為：

廣告活動adc在一天的總預(yù)算為：

則與之前的個指標(biāo)有如下關(guān)系：

利用以上公式可輕易計算出分發(fā)概率基準(zhǔn)值：

并由此得到廣告活動adc在各時段的理論下分發(fā)概率：

應(yīng)注意算法適用于目標(biāo)廣告庫存量遠(yuǎn)大于購買量的廣告活動，對于本身存在欠交付風(fēng)險買家的廣告活動，例如平均分發(fā)概率：

大于某閾值θ時，表示可能出現(xiàn)欠交付（Under-Delivery）的可能，可能由于設(shè)置受眾定向目標(biāo)過于嚴(yán)苛，或是競價算法出價太低導(dǎo)致競標(biāo)成功率過低。這種情況極其常見，強制使用可能由于數(shù)據(jù)量稀疏而導(dǎo)致較大的算法誤差。

預(yù)算步進(jìn)措施

實際情況中由于市場波動或是預(yù)測精度等原因，實際花費進(jìn)度可能與預(yù)定分配計劃有所偏差。為了對這種情況進(jìn)行調(diào)整，本文提出兩種措施。

第一種措施，是概率過濾方式，利用計算的理論分發(fā)概率，結(jié)合實際的花費情況不斷地調(diào)整實際分發(fā)概率。定義在時段t實際花費的預(yù)算為：

那么下一個時段應(yīng)該將fe分發(fā)比率調(diào)整為：

可見，除t=1時，系統(tǒng)在t+1時段使用校準(zhǔn)過的分發(fā)概率，并以此類推保證預(yù)算分發(fā)進(jìn)度。而且，實際情況RTB出售的大多是媒體的剩余流量，用戶好感度不高，用戶點擊行為具有很大隨機(jī)性。這種方法保證每次曝光都有機(jī)會參與競標(biāo)，盡可能降低系統(tǒng)性能導(dǎo)致的分發(fā)風(fēng)險，是很實用的一種方案。

第二種措施，KPI閾值過濾方式，利用公式求出KPI閾值，根據(jù)所處KPI閾值范圍確定以何種預(yù)算策略參與此次投標(biāo)。

KPI閾值過濾廣告流量

如上圖所示，利用歷史數(shù)據(jù)得到時段長度內(nèi)廣告流量在不同KPI的分布函數(shù)：

找到KPI閾值：

使得：

同時注意到廣告點擊性能在某時段t的分布與在一整天的分布趨勢是相近的，只是絕對數(shù)量不同，從而可降低系統(tǒng)的統(tǒng)計復(fù)雜程度，只需在求出此時段的點擊次數(shù)clks(t)和一天中的點擊分布：

那么有：

運用品友數(shù)據(jù)集測試后發(fā)現(xiàn)，時間迭代模型的去進(jìn)行廣告流量這類預(yù)測表現(xiàn)出了較好穩(wěn)定性，能夠反映出歷史數(shù)據(jù)的時效性因素。概率過濾模型在實驗中表現(xiàn)出良好的穩(wěn)定性，受預(yù)測精度影響較??；而性能指標(biāo)閾值過濾在某些時候可以獲得更佳的收益，但會略微增加計算難度。

本文終于結(jié)束了，希望讀者對計算廣告中主要模塊、策略及其場景有個較好的認(rèn)識和理解，本篇文章僅適合入門了解，不適合深度分析。想要深度分析的話，建議去看國外論文，分享兩個GitHub上的論文集：

• https://github.com/wzhe06/Ad-papers
• https://github.com/wnzhang/rtb-papers

此外，閱讀也有局限性，還是得結(jié)合實踐，特別是我在復(fù)盤本篇文章中的一些思路時，是發(fā)現(xiàn)了一些漏洞的，而作者好像故意忽略了這些漏洞。閱讀+實踐+思考，才是學(xué)習(xí)的良好方法，與君共勉。

參考文獻(xiàn)

• https://blog.csdn.net/taoqick/article/details/72822727GBDT：梯度提升決策樹
• https://zhuanlan.zhihu.com/p/61154299前深度學(xué)習(xí)時代CTR預(yù)估模型的演化之路
• https://daxue.qq.com/content/content/id/3682美團(tuán)點評柳明海：O2O推薦廣告CTR預(yù)估實踐
• http://www.huxmarket.com/detail/2966DSP的bidding算法
• 計算廣告 劉鵬、王超
• http://tech.youmi.net/2016/06/158883267.html淺析RTB中的競價策略
• https://dolantinlist.github.ioRTB廣告競價系統(tǒng)的算法介紹
• 韓靜. 在線廣告DSP平臺實時競價算法的研究與實現(xiàn)[D].上海交通大學(xué),2015.
• 李佩倫. 實時競價系統(tǒng)中出價算法的研究與實現(xiàn)[D].電子科技大學(xué),2017.
• 郭威. 針對在線廣告實時競價系統(tǒng)的相關(guān)算法研究[D].電子科技大學(xué),2013.

相關(guān)閱讀

計算廣告中主要模塊、策略及其場景（上篇）

#專欄作家#

Vency，公眾號：Vency不二，人人都是產(chǎn)品經(jīng)理專欄作家。海外商業(yè)產(chǎn)品經(jīng)理，關(guān)注海外、廣告、商業(yè)化、營銷等領(lǐng)域，追求用戶、技術(shù)、商業(yè)、社會價值的統(tǒng)一，喜好看書、逛館。

本文原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載。

題圖來自 Unsplash，基于CC0協(xié)議。