計算廣告中主要模塊、策略及其場景(下)

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

本文分三個部分，功能和策略，主講功能型產品和策略型產品的區別；架構綜述，主講廣告系統的流程、模塊和技術架構；算法和場景，主講各個模塊和場景中用到的算法。功能和策略、架構綜述在上篇已經講了，在此下篇中將接著講算法和場景。

GBDT模型

GBDT的全稱是（Gradien Boosting Decision Trees），是一種決策樹，屬於Boosting族，能將弱學習器提升為強學習器。GBDT中文叫梯度提升決策樹，由多棵決策樹構成，最終的預測結果是將所有決策樹的結果累加得到。

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

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

提升樹的過程如下：

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

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

此外，在使用特徵或屬性進行分支時，分支規則採用最小均方差的方式，即預測誤差的殘差的平方和去除以N，誤差越多錯的越多，通過這種方式找到最好的分支依據。

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

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

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

決策樹的個數越多學習越充分，但也會導致過擬合。學習速率可以稍微設快，可以減少樹的數量。

實驗中特徵變量選取的都是連續值變量，如不同地區的特徵變量則計算出它的發生頻率和點擊率，並將其作為梯度提升決策樹的兩個特徵。廣告的底價由於是連續值，可直接用於梯度提升決策樹的變量值。

並非所有變量都能對模型產生很大影響，因此在特徵選取時不會像邏輯回歸那樣需要選擇很多特徵，GBDT會放棄大多數特徵而保留一小部分，學習過程中選用了72個特徵作為訓練和預測的變量。而邏輯回歸在實驗中共選取了61萬餘個特徵。

GBDT+LR模型

由於GBDT所需特徵量遠小於邏輯回歸的特徵數量，自然想到利用GBDT來選擇特徵。Facebook基於GBDT提出了GBDT+LR模型，這是一種利用GBDT自動進行特徵篩選和組合，進而生成新的離散特徵向量，再把該特徵向量當作LR模型輸入，預估CTR的模型結構。

模型結構

其中用GBDT實現特徵工程和用LR預估CTR兩步是獨立訓練的，因此不存在如何將LR梯度會傳到GBDT這類複雜問題。

GBDT中每棵樹生成的過程是一棵標準的回歸樹生成過程，因此每個節點的分裂是一個自然的特徵選擇的過程，而多層節點的結構自然進行了有效的特徵組合，也就非常高效的解決了過去非常棘手的特徵選擇和特徵組合的問題。

利用訓練集訓練好GBDT模型之後，就可以利用該模型完成從原始特徵向量到新的離散型特徵向量的轉化。

具體過程是這樣的，一個訓練樣本在輸入GBDT的某一子樹後，會根據每個節點的規則最終落入某一葉子節點，那麼我們把該葉子節點置為1，其他葉子節點置為0，所有葉子節點組成的向量即形成了該棵樹的特徵向量，把GBDT所有子樹的特徵向量連接起來，即形成了後續LR輸入的特徵向量。

GBDT生成特徵向量的過程

舉例來說，如上圖所示，GBDT由三顆子樹構成，每個子樹有4個葉子節點，一個訓練樣本進來後，先後落入「子樹1」的第3個葉節點中，那麼特徵向量就是[0,0,1,0]，「子樹2」的第1個葉節點，特徵向量為[1,0,0,0]，「子樹3」的第4個葉節點，特徵向量為[0,0,0,1]，最後連接所有特徵向量，形成最終的特徵向量[0,0,1,0,1,0,0,0,0,0,0,1]。

由於決策樹的結構特點，決策樹的深度就決定了特徵交叉的維度。如果決策樹的深度為4，通過三次節點分裂，最終的葉節點實際上是進行了3階特徵組合後的結果，如此強的特徵組合能力顯然是FM系的模型不具備的。

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

POLY2、FM、FFM模型

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

POLY2

在上面POLY2二階部分的目標函數中（上式省略一階部分和sigmoid函數的部分），可以看到POLY2對所有特徵進行了兩兩交叉，並對所有的特徵組合賦予了權重。POLY2通過暴力組合特徵的方式一定程度上解決了特徵組合的問題。並且由於本質上仍是線性模型，其訓練方法與LR並無區別，便於工程上的兼容。

而POLY2的缺陷在於是對特徵組合賦予權重，特徵組合會讓原本就很稀疏的特徵向量更加稀疏，如果樣本中沒有出現這個組合特徵就學習不到權重；同時權重參數的數量由n上升到n^2，極大增加了訓練複雜度和收斂難度。

FM

相比POLY2，主要區別是用兩個向量的內積（wj1·wj2）取代了單一的權重。FM為每個特徵都學習一個隱向量（latent vector），在特徵交叉時，使用兩個特徵隱向量的內積作為交叉特徵的權重。每一個隱向量都包含k個latent factors，k是人為設定的超參數，例如上述的k就是2。

訓練數據

以此訓練數據為例，在ESPN廣告中，Adidas的樣本只有一個，預測結果是-1，那麼Poly2對於這個組合特徵會學到一個非常大的負的權重。但是，FM對於樣本(ESPN，Adidas)的預測，是由兩個向量決定的：W_espn * W_adidas 。 而這兩個向量，可以單獨的去從其他的樣本中學習，比如：（ESPN，Nike），（BBC，Adidas）。 所以FM這樣學習的更加準確。

通過引入特徵隱向量的方式，直接把原先n^2級別的權重數量減低到了n*k（k為隱向量維度，n>>k）。也許FM相比POLY2丟失了某些信息的記憶能力，但是泛化能力大大提高，這對於網際網路的數據特點是非常重要的。

FFM

FFM模型學習每個特徵在f個域上的k維隱向量，交叉特徵的權重由特徵在對方特徵域上的隱向量內積得到，權重數量共n*k*f個。總之，FFM引入了域的概念，為模型引入了更多的信息，模型建模更加準確，但是計算複雜度較高達到kn^2。

損失函數

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

CTR預估平臺

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

廣告排序架構圖

廣告架構圖中最重要的就是精排，前文也有講，離線要為在線提供模型等等，離線訓練和在線預估統稱為CTR預估。

從多套流程到統一框架

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

多套流程

如上圖所示，為了快速支持業務，在不同位置上有不同的團隊和人員負責，但是存在以下幾個問題：

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

要調整到【統一框架】方案，其中有三個問題：

1. 雙平臺多業務，代碼如何統一合併；
2. 如何保證線下線上效果一致；
3. 複雜的離線回溯中涉及到半年的數據數百個任務如何調度。

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

統一框架

• Match是個基本的打分單元，在不同場景下打分單元不同，由業務定義，例如：在廣告推薦場景就是遇到某個廣告並對其打分。
• Cube則是CTR預估流程的抽象，所有的CTR預估都是這個流程，與業務無關。
• Tesla是業務插件，用來定義Match是什麼、特徵是什麼等。
• Solar則是離線複雜邏輯調度以及基本算子，包括多天數據、user context ad如何構建、怎麼match等多天任務流，以及整個離線過程中的功能因子，例如：資料庫常見操作join，在千億樣本和千億特徵中，join會傾斜，而抽象出來後只要用Solar中的算子即可無需考慮傾斜的情況。

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

統一框架中的分工

統一框架就是每個平臺+虛線框就有某個人負責，大大提高開發和部署效率。但是仍然存在幾個問題，業務代碼接口較多，實現較難，美團推薦接入要2周；仍舊要掌握全鏈路，離線在線都要做，容易出錯；數據、代碼共享複雜，管理也較為複雜。

從統一框架到框架平臺化

框架平臺化

上圖中不存在Cube和Tesla，可總結為一句話：一份數據三個流程。

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

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

全部都可以抽象出來，通過配置實現，在除了特徵處理以外的流程，不同業務不一樣的參數較少，所以比較好做，但是特徵處理有點麻煩。

特徵抽取

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

框架平臺化的分工

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

總結美團CTR預估平臺的特點，能力強勁，支持千億樣本百億特徵的海量數據處理，支持LR、XGB、DNN等多模型；使用簡便，全流程可配置，拖拽可視化即可實現。

效果優化

優化目標有兩點，讓CTR預估更準確或者是廣告樣式更吸引人點擊。優化方向則有數據、特徵、模型、策略和樣式。

優化方向

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

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

從LR到FFM，FFM能夠自動學習特徵交叉似的表達能力更強，適用於未知場景的預估能力更強，CTR大約提升3%。

總體來看，隨著樣本來那個增加，效果整體提升並趨於收斂；隨著特徵規模增加，效果先變好後變差，前期特徵變多模型表達能力變強，稀疏特徵變多，過擬合嚴重，泛化能力變弱。

樣本量特徵維度和AUC

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

數據和策略上的調整很多時候還不如一個標紅的樣式，但是不可否認數據和策略等的價值，要根據不同優化方向的效果和當前場景和瓶頸，排出不同優先級，選擇不同的資源投入。

Y>N>Z>M>X

出價

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

競價引擎

核心問題

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

約束下最大化DSP利潤模型

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

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

曝光價值預估（收益r）

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

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

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

同一個廣告針對同一個人群進行連續投放，越到後面效果肯定越差，所以要把廣告投放次數放入模型中。以特定廣告與人群的歷史投放數據為基礎，採用時間序列分析方法，訓練出轉化率隨投放重複次數變化的曲線模型參數。該模型可以用來預測特定特定廣告、人群、重複投放次數下的轉化率。

轉化率預測時，要特別注意是否有足夠的歷史數據，此外預測不可貿然交給機器完成，要把統計、經驗等結合起來估算轉化率。當然，如果是DSP廣告主類型和轉化流程基本一致，例如專注於遊戲客戶的DSP或者是專注於阿里體系內電商的阿里媽媽，那麼在轉化數據充分情況下可採用機器學習建模方法預測。

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

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

成本m和勝率函數

可直接把出價當做成本m，但是多是採用第二高價競價，出價比成本要低，最好建立一個專門的市價預測模型來估計m，但遠沒有曝光價值的預估可靠，不宜使用過於複雜的模型和算法，主要使用時間、地域、媒體屬性等影響明確的因素來進行預估。

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

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

這會導致非常嚴重的後果：從ADX得到的反饋用於訓練的數據和測試的數據分布不同。

競價動態數據過濾器

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

訓練數據與測試數據的總體分布相同是監督學習（supervised learning）的理論基石。在常見的業務場景如推薦中，訓練樣本與測試樣本存在採樣偏差，但總體分布是相同的；而在DSP中，樣本的總體分布都不相同。

在有偏分布下，任何監督學習方法都是低效且過擬合的；需要的一種解決思路是將有偏的訓練數據分布試圖重構到整體分布上。例如用Kaplan-Meier Product-Limit可針對「存在非隨機數據缺失」的情況進行分布估計。

在實時競價廣告系統中普遍存在一個「軟地板價」的機制，若最高價低於軟地板價則採用第一高價，此時無關DSP贏標與否都只能觀測到第一高價（即支付價格）。也就是說，會出現贏標後只得到自己出價的情況，只能作出估計第二高價最高不超過自己實際支付價格，因此這種得到的估價是估值過高的。這種就叫刪失。可以引入競價失敗價格因素。

競價策略

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

幾種競價策略

出價邏輯

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

隨機出價：在一個給定價格區間中隨機出價，唯一參數是競價的區間上限，一般也給定，下限一般是0。

真實出價：就是按照計算的曝光價值出價，計算多少就出價多少，當然轉化率預估的問題之前也有提到。

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

線性出價：出價與估計的點擊率成正比，但要設置基準出價，即：

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

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

由於x和θ(x)的關係是確定的

進而可以把優化目標寫成：

利用拉格朗日乘子法，目標函數變為：

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

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

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

可以看出，最優的出價是收益的一個非線性函數。

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

預算

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

如果不對預算進行合理管控，會出現三種情況：

1. 預算迅速消耗完畢，但是贏得了很多價值不高的請求，更失去了贏得後續收益更高請求的機會，導致最終廣告效果較差 ；
2. 時間範圍結束後，預算仍有大量剩餘，導致輸了很多高價值的請求；
3. 由於市場競爭變化及其他因素變化，導致市場波動，似的預算消耗速度忽高忽低，無法管控和預測預算消耗。這三種情況都會導致預算利用率下降，從而使得廣告整體的量級和ROI均下滑，可嘗試利用動態規划算法來求解。

因此，控制預算消耗的主要目標是：

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

（a）預算過早耗盡 （b）預算波動劇烈

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

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

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

ipinyou數據集中03月11日的競標和曝光次數趨勢圖

分配計劃正比於廣告流量的變化趨勢，廣告投放到一天內任意一個用戶的機率均等，從而保證廣告均勻的分配到受眾群體上，重點是分配機會的均等而非時間段均等。此外，廣告關鍵指標（優化目標）和廣告市場的競爭程度也是需要考慮的點。不同時間段內的點擊率、轉化率等關鍵指標並非恆定，因此對於廣告主來說價值不同。

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

競標廣告主、展示量與時間的變化趨勢

預算步進算法示意圖

因此，要基於廣告流量、廣告質量、市場競爭程度確定分配計劃。步驟1用來計算分配計劃，對廣告請求進行過濾，控制參與競標的廣告請求數量滿足預算等限制條件。當贏得交易後扣除預算，步驟2根據實際花銷與預計花銷之間的差異來實時調整下一個時刻的分配計劃。

預算步進定義

本文提出的預算步進方案採用了概率過濾機制，概率過濾值成為步進率（Pacing Rate），是一個隨時間t的函數：

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

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

一天總預算：

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

定義時間段t的請求數函數為req(t)，p(t)需要對廣告請求進行第一次篩選，初步決定參與投標的廣告請求為：

0表示未投標，1表示通過初次篩選。那麼步進率可表示為：

而若投標後贏得競標的廣告請求序列為：

1表示贏得，則贏標概率為：

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

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

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

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

廣告質量度

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

取值範圍再0到1之間，可利用一個映射函數：

將其控制在所需要的範圍內，如logistic函數。定義某廣告活動adc的廣告展示質量係數函數為：

α控制其變化速度，建議取值範圍：當某時段展示質量接近平均水平是其取值在1附近。

市場競爭程度

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

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

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

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

同理經過以平滑映射函數，定義廣告活動adc在時段t內的競爭程度係數為：

注意兩個係數函數的參數α和β控制函數變化速度，且當競爭程度較高時，步進算法應當降低出價時機，即降低該因子係數從而最終降低該時刻出價概率，而映射函數

定義為單調遞增的平滑函數，所以應取負號。

預算分配計劃

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

廣告活動adc在一天的總預算為：

則與之前的個指標有如下關係：

利用以上公式可輕易計算出分發概率基準值：

並由此得到廣告活動adc在各時段的理論下分發概率：

應注意算法適用於目標廣告庫存量遠大於購買量的廣告活動，對於本身存在欠交付風險買家的廣告活動，例如平均分發概率：

大於某閾值θ時，表示可能出現欠交付（Under-Delivery）的可能，可能由於設置受眾定向目標過於嚴苛，或是競價算法出價太低導致競標成功率過低。這種情況極其常見，強制使用可能由於數據量稀疏而導致較大的算法誤差。

預算步進措施

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

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

那麼下一個時段應該將fe分發比率調整為：

可見，除t=1時，系統在t+1時段使用校準過的分發概率，並以此類推保證預算分發進度。而且，實際情況RTB出售的大多是媒體的剩餘流量，用戶好感度不高，用戶點擊行為具有很大隨機性。這種方法保證每次曝光都有機會參與競標，儘可能降低系統性能導致的分發風險，是很實用的一種方案。

第二種措施，KPI閾值過濾方式，利用公式求出KPI閾值，根據所處KPI閾值範圍確定以何種預算策略參與此次投標。

KPI閾值過濾廣告流量

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

找到KPI閾值：

使得：

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

那麼有：

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

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

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

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

參考文獻

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

相關閱讀

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

#專欄作家#

Vency，公眾號：Vency不二，人人都是產品經理專欄作家。海外商業產品經理，關注海外、廣告、商業化、營銷等領域，追求用戶、技術、商業、社會價值的統一，喜好看書、逛館。

本文原創發布於人人都是產品經理。未經許可，禁止轉載。

題圖來自 Unsplash，基於CC0協議。