1. 什麼是 Budget Pacing ?
所謂 Budget Pacing , 就是一個勻速投放功能，讓廣告主每天花的錢消耗的更均勻。更詳細的闡述可以看我們的上一篇公眾號文章，《LinkedIn 是怎麼做 Budget Pacing的》
2. Yahoo 為什麼要做 Budget Pacing ?
Yahoo 認為廣告主的核心需求主要有三種：
a. 觸達足夠多的人群同時廣告效果（點擊率）儘可能滿足預期
b. 更平穩的消耗預算
c. 建廣告的成本儘可能的少
Yahoo 希望為 DSPs（Demand-Side Platforms 可以理解為廣告代理平臺, 為廣告主購買廣告資源）提供一種能力：能聰明的進行預算分配，讓廣告主的需求得到滿足。
3. Yahoo 做之前做了哪些研究工作 ？（歐文）
Yahoo 的研究人員發現目前廣告行業裡大部分的paper都主要研究廣告點擊率(CTR)的預測及 Action rate(用戶行為率)的研究，但研究怎樣平穩消耗預算的研究並不多。
在有限的關於 budget pacing的論文中，Yahoo發現以下幾篇比較有價值：
Bhalgat 和 Mirrokni 2012年的Paper Online allocation of display ads with smooth delibery 中提出了廣告流量最優的分配方式，但是他們的分配方式是從平臺收入的角度看的，也就是他們研究的是怎樣分配流量可以給平臺帶來最大收入。而Yahoo主要想的是更合理的分配流量，讓廣告的效果更好。
另外一篇2014年發表的paper The English ACM International Conference on Web Search and Data Mining 裡的觀點其實跟Yahoo的想法有些相似, 都想通過budget pacing來提高廣告效果，但是他們其實paper中並沒有對smooth delivery進行太詳細的描述。
還有另外幾篇paper, 例如 Optimal delivery of sponsored search advertisements subject to budget constraints, Adwords and generalized online matching 和 Partner tiering in display advertising 都建議使用bid modfification的方式進行 pacing.
但是LinkedIn的paper Budget pacing for targeted online advertisements at linkedin. (我們上一篇公眾號聊過這篇paper ) 和 paper The Seventh International Workshop 都闡述了利用probabilistic throttling 的方式來達到pacing control的效果
在權衡之下，Yahoo最終選擇使用probabilistic throttling的方式來做budget pacing，主要是出於以下的幾點考慮：
a. probabilistic throttling 直接影響了廣告預算的消耗，然而bid modification
是改變win-rate來控制廣告的消耗，但是在RTB的環境下比較困難
其一，bid win rate curve 通常不夠smooth， 所以一旦改變出價會嚴重影響budget spending. 其二，Yahoo發現bid landscape會隨著時間大幅度改變
b. SSPs平臺通常會設置出價區間，所以可能調價算法根本無法生效
下面這張圖簡單的介紹了probabilistic throttling 和 bid modification的區別。
簡單的講，probabilistic throttling 用出廣告的概率來調節廣告預算的消耗而
bid modification則通過動態調價影響廣告的得分（得高分的時候廣告出得越多）最終影響廣告預算的消耗。
4. Yahoo 是怎麼思考budget pacing問題的 ？（小東）
在線廣告基於其投放目標的差異，可以統一規約為三種產品形態：品牌廣告、效果廣告以及前述二者的混合。對在線廣告做預算分配，即是分別優化品牌廣告和效果廣告二者的預算分配策略。
我們首先描述一個具體的廣告Ad完整的投遞過程：
1、在Ad正式投放前，廣告主會預定一個預算分配方案。以確保在整個投遞過程中，預算大致以廣告主預期的節奏被消耗。將整個投遞過程切分為K個時間片段，基於預算分配方案，我們可以得到廣告主在這K個時間片段裡的預算：B(1)、B(2)、...、B(K)，顯然K個時間片的預算累加之和就是廣告主的總預算B，即：
2、Ad自投放開始便競爭順序到來的流量Req1、Req2、...、Reqn以獲得向用戶展示廣告的機會。針對流量Reqi(i=1、2、...、n)：
a. Ad首先決定是否競爭Reqi。如果Ad參與競爭，則si=1，否則si=0。
b. 在參與競爭Reqi的基礎上，Ad給出一個出價ci以嘗試贏取本次曝光。
c. 給定出價ci後，系統會決定展示機會的最終歸屬。我們用符號wi來標識Ad是否最終贏取此次展示機會，如果Ad贏取Reqi，則wi=1，否則wi=0。
因此，Ad在流量Reqi上的最終花費是si*ci*wi。而在整個廣告投放過程中，在順序到來的所有流量Req1、Req2、...、Reqn上，Ad的真實總開銷是C即：
與1的做法類似，我們同樣將廣告投放周期切分為K個時間片段，並分別統計獲得Ad在這K個時間片段裡的真實開銷C(1)、C(2)、...、C(K)，顯然也有：
在K個時間片段上，廣告主的預算分別是B(1)、B(2)、...、B(K)。而在真實的在線環境中，Ad的開銷分別是C(1)、C(2)、...、C(K)。真實開銷與預算在這K個時間片段上的偏差分別是C(1)-B(1)、C(2)-B(2)、...、C(K)-B(K)。我們使用如下的公式來衡量真實開銷與廣告主預算之間的差異：
理想情況下，真實的開銷與廣告主的預算應當相同，即Ω(C,B)=0。但是如文章一所描述，預算控制並不是廣告主唯一關注的目標。
在在線廣告產品中，廣告的投遞效果也是廣告主所關注的。
具體而言，在競爭贏取流量Reqi後，系統會將廣告Ad展示給用戶。用戶有一定的概率關注廣告並產生廣告主想要的轉化行為，比如點擊廣告、購買推薦商品等。我們使用符號qi來標識用戶是否產生轉化行為，如果用戶產生了轉化，則qi=1，反之，qi=0。
因此，經過如下三步：
1、si：決策是否參與競爭；
2、wi：決定參與競爭後，是否贏取展示機會；
3、qi：贏取展示機會後，是否帶來轉化行為。
一次流量Reqi給Ad最終帶來的轉化即：si*wi*qi。
而在Ad的整個投放周期中，總轉化數量是：
由於在整個投放周期中，廣告主的真實開銷是C，故而每個轉化的成本P是：
對於品牌廣告，履行合約，花光廣告主的預算是最優先的目標，即保證C=B。其次是優化預算分配策略，從而保證預算以廣告主期望的節奏被消耗，即保證 Ω(C,B)≤ε，其中ε表示廣告主可以容忍的預算分配偏離程度。最後才是優化投遞效果，以最小的花費贏取更多的轉化，即 min P。數學形式化品牌廣告的預算分配問題，即下圖所示（1）：
對於效果廣告而言，沒有保量需求，但約束條件變成了讓廣告的點擊成本或轉換成本小於廣告主的目標出價，同時儘可能多消耗完預算，因此對應的優化目標就變成了：
5. 品牌廣告的 budget pacing怎麼做？（小東）
在品牌廣告中，針對廣告Ad，廣告主為每次曝光Reqi所支付的花費ci是固定的。在固定的出價ci面前，我們也無法決定Ad最終能否贏取Reqi。即在章節3描述的4個階段：a.決定是否參與競價、b.出價、c.贏取曝光、d.獲得轉化中，我們無法控制b、c階段，只能優化a、d階段。具體而言，我們能做的只是在高轉化概率的流量到來時，我們儘可能的提升Ad參與競爭的概率ri（符號ri表示Ad競爭流量Reqi的概率），高ri意味著更頻繁地參與流量競爭，更快地消耗預算。由於競爭概率ri與預算消耗速度的等價性，後文，我們也使用ri表徵預算的消耗速率，即pacing rate。同時，基於預算真實的消耗節奏，我們動態的調整ri，最終達到花完預算、合適地分配預算、獲得高轉化這三個目標。
具體而言，求解（1）的過程可以細分為如下的三步：
a. 基於已有的廣告投遞效果日誌，使用機器學習模型預測：當我們在流量Reqi上向用戶展示廣告Ad時，用戶C產生轉化行為的概率pi，即訓練獲得如下模型：
b. 基於pi，為Ad賦予一個合適的競爭概率ri。原則上，當pi越大時，ri也越大，以優化廣告的投遞效果。
c. 基於預算的真實消耗節奏，我們動態的調整ri，以保證：C=B 且 Ω(C,B)≤ε。
下面具體介紹這三步：
步驟a：預估pi，目前學術界已經有大量的方法。文章借鑑了已有的做法並做出了部分改進。具體而言，預估pi細分為兩個方面：
1、基於廣告信息與已有的轉化數據，使用LR或者GBDT等模型預估得到一個初始值；
2、基於流量信息修正初始值，得到最終的預估值pi。
步驟b：基於pi確定ri，文中使用分層的數據結構以簡化求解過程。具體而言，我們將pi大致相同的廣告請求（即Ad，Reqi組合）劃分為同一層，並基於本層所有廣告請求的平均pi，即average reponse rate，來確定本層的優先級priority及參與流量競爭的概率ri。在確定priority和ri時，我們遵循如下的兩個準則：
1）平均pi高的層擁有更高的優先級priority；
2）如果層layer1比層layer2的優先級高，則layer1的ri不應小於layer2對應的ri。
步驟c：基於預算的真實消耗速率動態的調整ri。在步驟a、b中，通過為pi高的廣告請求賦予更高的流量競爭概率ri，我們可以優化品牌廣告的投放效果。然而，如何滿足廣告主更核心的兩個需求：花光預算和以合適的節奏消耗預算？文章的解決方法是基於已有的預算消耗數據，動態的調整ri，以保證預算以我們預期的節奏消耗完。
想像一下真實的廣告投放場景，我們將整個投放周期切分為K個時間片段，目前已經投放了m個時間片段，這m個時間片段中，我們分別使用如下的流量競爭概率r(1)、r(2)、...、r(m)，並分別消耗預算C(1)、...C(m)。經過m個時間片段後，廣告預算剩餘Bm，此時我們待優化的問題轉變為如何分配接下來m+1，...，K這幾個時間段的預算，以保證預算以我們預期的節奏消耗完，數學形式化問題即（2）：
求解（2），我們得到最優解如下：
文章的解決思路是基於前m個時間段的競爭概率r(1)、r(2)、...、r(m)，以及該競爭概率下，廣告的真實預算消耗C(1)、...C(m)，動態的調整接下來m+1、...、K時間段的競爭概率r(m+1)、...、r(K)，以保證預算以我們預期的節奏被消耗。
具體而言，如果與時間片段m+1預期分配的預算相比，前一時間片段，即第m個時間段我們消耗了更多的預算，則應該降低r(m)以獲得r(m+1)，反之則基於r(m)提升獲得r(m+1)，以保證我們可以在m+1時刻花完預定分配的預算。
6. 效果廣告的 budget pacing怎麼做？（bran）
效果廣告一般是按用戶的行為計費，常見的有點擊，有轉換等方式計費。在DSP平臺上，廣告主往往會給出一個可以接受的價格，例如一個點擊廣告主出價10元（ eCPC=10）。當從一個請求來臨時，系統需要判定該廣告是否參與此次競爭。若參與競爭，則會進入到廣告的精排過程。不同於LinkedIn，Wechat這樣大的流量方自有廣告平臺。DSP上的效果廣告流量波動會比較大，流量聯盟中隨時會有流量方的離開或接入。
對於yahoo，他們DSP的pacing方案相比與LinkedIn的方案主要把點擊率作為了廣告的質量得分，然後按質量得分對廣告的每個請求做了不同等級的劃分，然後對不同等級的廣告請求的pacing速度分別進行 控制，控制的算法不再使用LinkedIn中的方法，而是使用啟發式的控制算法。下面我們具體描述其方案。
首先，效果廣告裡廣告主主要對CPC出價，因此我們需要先計算不同等級廣告請求對應的eCPC。在yahoo DSP的業務場景下，我們假設每個廣告請求（ad request）的CPM一定，則對應請求從上到下隨著CTR逐層降低，eCPC逐級變大，eCPC與與CPM和CTR的關係為（這裡的CTR實際上是pCTR，原文中描述的時候不夠嚴謹）：
不同層級的請求對應的信息為：
效果廣告的pacing和上面提到的合約品牌廣告的pacing基本理念類似，同樣是在每個時刻對廣告的曝光量進行控制，並且同樣會根據廣告請求的優先級進行pacing，點擊率更高的請求會獲得更高的pacing權重。不同的是效果廣告的pacing過程中還要考慮到eCPC能不能達到廣告主的要求。為了能在算法中考慮到這種需求，我們的算法需要引入一個判定函數：
公式中的參數含義如下：
判定函數的作用是計算從第i層開始往上如果使用合約廣告模型算法的計算出來的pacing速率在t時刻消耗廣告對應的整體平均eCPC。通過整體的eCPC與廣告主的出價目標進行比較，判定是否需要調整pacing 速率。這個公式太長了，由於我們關心的是參數是i，因此下面的描述中我們用一個函數來代表這個公式，表示從第i層往上到第L層所有廣告請求的eCPC，即：
而廣告主的出價表示為goal，如果當前從第i層往上的平均eCPC：
，那我們就需要調整pacing的速率，而從表格中可以知道，我們的廣告請求從上往下eCPC是逐層變大了。因此平均eCPC沒有達到目標一定是低層的廣告請求消耗速度太大了，那我們需要降低這層的速度，讓高層的廣告請求消耗預算的權重增加來降低平均eCPC。
為了達到這個目標，我們的算法需要從下到上不斷計算平均eCPC，對比當前廣告主的出價目標。
1. 若當前層i的上一層i+1平均eCPC 大於廣告主的出價目標，
則這層的pacing 速率需要降到0，因為此時無論如何調整i層的pacing 速率都沒有用（它上面各層比它小的eCPC對應的平均eCPC都大於了廣告主的目標）。
2. 如果當前層i的上一層以上各層的eCPC 小於廣告主的出價，
而由於從當前層開始算平均eCPC會超過廣告主的出價目標（算法是從下往上遍歷），那麼問題出在當前層的速率太快了，上層的沒有問題，因此調整當前層的pacing速率到整體的eCPC等於廣告主出價目標即可，所以調整的幅度的包含兩個部分：
1. t-1時刻上層相比廣告主出價目標少消耗的部分：
2. t-1時刻當前層相比廣告主出價目標多消耗的部分：
上述二者的比值則為當前層的pacing 速度 r 需要調整的幅度。
上述算法的用偽代碼可描述為：
廣告請求層數、初始速率和嘗試速率
在上述算法實現過程中有三個參數是需要我們進行設定的，它們分別是：
1. 廣告請求層數，層數的多少決定了控制的粒度，層數設定過多則可能出現某些層的廣告請求數比較少，抖動比較大，這樣對調節速率是很不利。而層數過少，則不利於廣告請求的分類。
2. 初始速率， 這個速率用於設定算法各層消耗的初始值。
3. 嘗試速率，這個速率是在pacing速度為0的那層之上的那層對應的速度，主要作用是用來搜集廣告請求的消耗數據。
對於廣告請求層數，Yahoo的策略是通過計算與該廣告最相似的廣告然後預估一個能消耗完廣告主預算的速率：
，層數的選擇就為這個速率的倒數，並向上取整：
同時所有層的初始速率就置為這個速率。
那最後就只剩嘗試速率（trial rate）的確定了，嘗試速率層相當於一個用來收集廣告消耗數據的變量，一般而言這個值會選取一個非常小的值（例如：0.005），Yahoo的paper中提出了一個計算公式，但這個公式的計算意義不大，這裡就不再描述了。
7. 如何衡量效果？ (歐文)
為了驗證pacing的效果，雅虎分別做了線上實驗和模擬來驗證。
雅虎從DSP裡找了3個廣告做AB測試組，另外找了4個廣告做overtime的測試組。這7個廣告都是CPM廣告並且其中的2個有非常明確的eCPC目標。
AB測試組中，廣告1和3是沒有轉化目標的，
而廣告2是有轉化目標的：轉化目標為2.5元。
下圖展現了測試的結果
與大盤評價值相比，這三組實驗的eCPC的價格分別下降了 72％， 67％ 和 79％。yahoo 發現對於第二個實驗，沒有pacing的時候廣告其實沒有讓廣告達成eCPC的目標。從另外一個方面說，廣告的消耗達成率其實加了pacing的廣告和沒加pacing的廣告一致。
over-time的實驗在下圖中進行了展示，
在這個實驗裡，yahoo 起了4個廣告並且讓廣告保持2周的在線狀態。
其中一周採用的是沒有加pacing的方式，另外一周採用了加pacing的方式。在這四組實驗中，只有實驗組4有一個明確的eCPC目標：7美元。最後yahoo的團隊發現，當採用pacing的時候，4個廣告的eCPC都發生了下降。最高的一組下降50％。 此外yahoo的團隊還做了模擬的實驗來驗證pacing的效用，最終也取得了正面的效果。
8. 結論
Yahoo給我們展現了一個使用在DSP系統中的budget pacing方式，通過讓預算更平穩的消耗來達到廣告效果的提升。並且通過實驗對budget pacing的效果進行了驗證，得到了正面的反饋。
9. 寫在最後
以上內容均來自 Yahoo 的論文 Smart Pacing for Effective Online Ad Campaign Optimization. 由於這次是三個人一起研究，所以我們進行了分工，每個人summarize了不同的部分，各章節標題後面註明了編寫人。目前 budget pacing 相關的實驗我們已經學習了兩篇，有了些許收穫和成長。下一篇文章我們會看看 oCPC 相關的東西。