合約廣告的關(guān)鍵特征，是廣告投放的價格和量由雙方協(xié)商約定，合約廣告的最初形式是按廣告位售賣的CPT廣告嗅辣。

合約廣告的重點(diǎn)形式是按指定受眾購買的、按CPM計(jì)費(fèi)的展示量合約廣告挠说。展示量合約廣告的投送系統(tǒng)稱為擔(dān)保式投送系統(tǒng)澡谭。它依賴于受眾定向、流量預(yù)測损俭、點(diǎn)擊率預(yù)測這三項(xiàng)基本技術(shù)蛙奖，并采用在線分配的方式完成實(shí)時決策。

合約廣告的擔(dān)保式投送決策邏輯比較復(fù)雜杆兵，這里主要從兩個方面介紹此問題的一般性思路：
一是在未來流量分布未知的情形下雁仲，如何估計(jì)在線分配算法的極限性能；
二是在根據(jù)歷史數(shù)據(jù)能進(jìn)行相對合理的瀏覽預(yù)測的情形下琐脏，如何利用這些預(yù)測搭建一個實(shí)用的在線分配系統(tǒng)攒砖。

1. 廣告排期系統(tǒng)

對于按CPT結(jié)算的廣告位合約，媒體一般采用廣告排期系統(tǒng)來管理和執(zhí)行。這里需要注意的是祭衩，廣告排期系統(tǒng)并不是一個個性化系統(tǒng)灶体，也不太需要服務(wù)器端的動態(tài)決策。

廣告排期系統(tǒng)的一般技術(shù)方案是將廣告素材按照預(yù)先確定的排期直接插入媒體頁面掐暮，并通過內(nèi)容分發(fā)網(wǎng)絡(luò)（Content Delivery Network蝎抽，CDN）加速訪問。這樣可以使得廣告投放延遲很小路克，也沒有服務(wù)端的壓力和開銷樟结。

當(dāng)一些橫幅廣告位上沒有廣告位合約，需要用其他服務(wù)器動態(tài)決策的廣告補(bǔ)足時精算，由于服務(wù)器可能出現(xiàn)超時或其他錯誤導(dǎo)致廣告未能返回瓢宦，那么也需要在頁面上展示一個默認(rèn)廣告防止出現(xiàn)廣告位的空白，這樣的廣告稱為防天窗廣告灰羽。防天窗廣告由于需要在服務(wù)器不工作的情形下補(bǔ)位驮履，因此也應(yīng)該放在CDN上實(shí)現(xiàn)。

1.1 排期與動態(tài)廣告混合系統(tǒng)

（1）首先廉嚼，前端的廣告位代碼從CDN上獲取一個默認(rèn)廣告素材以及標(biāo)示此廣告是優(yōu)先的CPT廣告還是防天窗廣告的參數(shù)玫镐。
（2）根據(jù)上述參數(shù)，如果CDN上獲得的是一個CPT廣告怠噪，那么直接將素材渲染在頁面上即可恐似。
（3）如果CDN上獲得的是一個防天窗廣告，則優(yōu)先向廣告投放機(jī)發(fā)送請求傍念，如果在指定延遲時間內(nèi)有廣告返回矫夷，則將其渲染在頁面上。
（4）如果服務(wù)器在指定延遲時間內(nèi)沒有廣告返回或發(fā)生其他錯誤憋槐，則將從CDN里得到的防天窗廣告渲染在頁面上双藕。

實(shí)際的排期和動態(tài)廣告混合系統(tǒng)，由于有輪播模式的存在和地域定向的需求秦陋，會比上述的邏輯更加復(fù)雜一些蔓彩，不過沒有原理上的差異治笨。

2. 擔(dān)保式投送系統(tǒng)

與展示量合約對應(yīng)的廣告系統(tǒng)稱為擔(dān)保式投送（Guaranteed Delivery驳概，GD）系統(tǒng)。在展示量合約這樣的交易結(jié)構(gòu)中旷赖，只要合約都被滿足顺又，系統(tǒng)的收益就是一定的，于是公式2.2中的優(yōu)化目標(biāo)變成了常數(shù)等孵。

第二章提到的公式2.2

不過稚照，這一系統(tǒng)多了合約帶來的一組量的約束條件，因此變成了一個帶約束優(yōu)化問題。關(guān)于此問題的具體描述和解法將放在后面的在線分配部分中介紹果录。有時上枕，展示量合約還會約定投放量未達(dá)到時的懲罰。

在此系統(tǒng)中弱恒，在線投放引擎接收用戶觸發(fā)的廣告請求辨萍，根據(jù)用戶標(biāo)簽和上下文標(biāo)簽找到可以匹配的廣告合約，然后由在線分配模塊決定本次展示投放哪個廣告返弹。完成決策后锈玉，將展示和點(diǎn)擊日志送入數(shù)據(jù)高速公路。這些日志一方面進(jìn)入離線分布式計(jì)算平臺以后义起，通過日志的整理拉背，完成合約的計(jì)劃，即確定在線分配算法的參數(shù)默终，再將分配方案送給線上投放機(jī)使用椅棺；另一方面，日志也送到流計(jì)算平臺齐蔽，在反作弊和計(jì)價的基礎(chǔ)上土陪，再對索引進(jìn)行快速調(diào)整‰妊可以看出鬼雀，這一系統(tǒng)的核心技術(shù)是在線分配的算法策略與執(zhí)行過程。

擔(dān)保式投送需要用到的核心技術(shù)蛙吏，最重要的就是在線分配源哩。除了在線分配以外，擔(dān)保式投送還有另外兩項(xiàng)主要的支持技術(shù)：流量預(yù)測和頻次控制鸦做。首先對這兩項(xiàng)進(jìn)行解釋励烦。

2.1 流量預(yù)測

流量預(yù)測的問題可以描述為：給定一組受眾標(biāo)簽組合以及一個 eCPM 的閾值，估算在將來某個時間段內(nèi)符合這些受眾標(biāo)簽組合的條件泼诱、并且市場價在該 eCPM閾值以下的廣告展示量坛掠。這里的 eCPM 閾值主要是用于競價廣告系統(tǒng)中，目的是了解在某出價水平下的流量情形治筒。對于展示量合約式廣告來說屉栓，這個閾值是不需要的，或者為了工程上一致耸袜，將該閾值設(shè)為一個很大的常數(shù)友多。

流量預(yù)測一般的方法其實(shí)并不是預(yù)測，而是根據(jù)歷史數(shù)據(jù)的統(tǒng)計(jì)來擬合未來的流量堤框。當(dāng)然域滥，也可以引入時間序列分析的方法纵柿，從流量在時間軸上的規(guī)律預(yù)測未來某個時間段的流量，這主要適用于需要短時預(yù)測的場景启绰，對廣告業(yè)務(wù)來說并不十分必要昂儒。

流量預(yù)測的一般步驟如下：

（1）準(zhǔn)備文檔。將歷史流量中委可，(u,c)上的所有標(biāo)簽的展示合并為一個供給節(jié)點(diǎn)i荆忍，并統(tǒng)計(jì)其總流量s(i)以及這部分流量上eCPM的直方圖hist(i)。這樣的每個供給節(jié)點(diǎn)作為流量預(yù)測反向索引的一篇文檔撤缴。
（2）建立索引刹枉。對上一步生成的每個供給節(jié)點(diǎn)建立倒排索引，文檔的terms即為此供給節(jié)點(diǎn)(u,c)上的所有標(biāo)簽屈呕。同時微宝，在索引的正排表部分記錄s(i)和hist(i) 。
（3）查詢結(jié)果虎眨。對一條輸入的廣告a蟋软，將其限定的標(biāo)簽條件作為查詢，得到所有符合條件的供給節(jié)點(diǎn)的集合嗽桩。
（4）估算流量岳守。遍歷上一步得到的每個供給節(jié)點(diǎn)，對于某個供給節(jié)點(diǎn)i碌冶，首先計(jì)算其與該廣告 a 的 eCPM 即 r(a,ui,ci)=μ(a,ui,ci)*bid(a) 湿痢，然后根據(jù)相應(yīng)的 eCPM 直方圖hist(i)計(jì)算a能獲得的流量。這樣扑庞，就可以估算出a在出價bid a 情形下近似能獲得的流量譬重。

2.2 頻次控制

頻次，指的是某個用戶在一段時間內(nèi)看到某個或某組廣告的曝光次數(shù)罐氨。

頻次控制有客戶端和服務(wù)器端兩種解決方案臀规。客戶端的方案就是把某個用戶對某個廣告創(chuàng)意的頻次值記錄在瀏覽器cookie中栅隐，投放決策時再把這個值傳給服務(wù)器來決策創(chuàng)意塔嬉。這一方案的好處是簡單易行，而且服務(wù)成本低租悄。缺點(diǎn)是擴(kuò)展性不好谨究，當(dāng)同時跟蹤多個廣告的頻次時，cookie可能會變得很重恰矩，從而影響廣告響應(yīng)時間记盒。當(dāng)然，在移動應(yīng)用廣告中利用SDK做前端投放控制的場景外傅，客戶端的方案是非常好的選擇纪吮。服務(wù)器端的方案是在后臺設(shè)置一個專門用于頻次記錄和更新的緩存，當(dāng)廣告請求到來時萎胰，在緩存中查詢候選廣告的頻次碾盟，并根據(jù)最后實(shí)際投放的廣告更新頻次。

對于頻次控制技竟，有兩個特點(diǎn)需要注意：

（1）頻次存儲的規(guī)模是有上界的冰肴。如果我們在某個時間周期內(nèi)控制頻次，那么上述的頻次變量總數(shù)一定不會超過這個時間周期內(nèi)的展示總數(shù)榔组，這會遠(yuǎn)遠(yuǎn)小于所有可能的(a,u)的組合數(shù)量熙尉。因此，緩存實(shí)際的存儲規(guī)模沒有我們想象的那么大搓扯。

（2）當(dāng)用(a,u)的組合生成緩存中對應(yīng)的鍵時检痰，實(shí)際上并不需要處理沖突，因?yàn)閺臉I(yè)務(wù)角度來說锨推，對極少比例的沖突組合上的頻次控制不準(zhǔn)是可以接受的铅歼。因此，我們用簡單的MD5之類的散列方法生成鍵就可以换可，這會比哈希表的方案要簡便高效一些椎椰。這實(shí)際上也反映了廣告系統(tǒng)投放過程弱一致的設(shè)計(jì)原則。

3. 在線分配

在線分配問題指的是在通過對每一次廣告展示進(jìn)行實(shí)時在線決策沾鳄，從而達(dá)到在滿足某些量的約束的前提下慨飘，優(yōu)化廣告產(chǎn)品整體收益的過程。很容易理解译荞，此問題計(jì)算上最困難的地方在于“在線”套媚，也就是在信息尚不全面的時候作出決策；而系統(tǒng)上最困難的地方在于分配策略需要是弱狀態(tài)的磁椒，同時各廣告投放機(jī)之間耦合程度也要盡量低堤瘤。

在線分配是計(jì)算廣告中比較關(guān)鍵的算法框架之一，它適用于許多量約束下的效果優(yōu)化問題浆熔，而這實(shí)際上是廣告業(yè)務(wù)非常本質(zhì)的需求本辐。

在線分配問題的重要性已經(jīng)超越了擔(dān)保式投送本身。

3.1 在線分配問題

3.1.1 供給與需求二部圖

以擔(dān)保式投送為代表医增，在線分配問題有兩個主要的挑戰(zhàn)：一是要在量的約束下優(yōu)化效果慎皱；二是要實(shí)時對每一次展示作出決策。直接在這兩個要求下優(yōu)化叶骨，會使得求解過程相當(dāng)困難茫多。因此，在在線分配問題中忽刽，一般將此問題簡化為一個二部圖（bipartite graph）匹配的問題天揖。這里的“二部”指的是代表廣告庫存的供給節(jié)點(diǎn)（集合記為 I夺欲，其中某個節(jié)點(diǎn)代表的是所有標(biāo)簽都相同的流量庫存）和代表廣告合約的需求節(jié)點(diǎn)（集合記為A）。

在線分配中的二部圖匹配問題示意

在這個示例中今膊，左邊的6個節(jié)點(diǎn)為供給節(jié)點(diǎn)些阅，右邊的三個節(jié)點(diǎn)為需求節(jié)點(diǎn)。如果某個供給節(jié)點(diǎn)的受眾標(biāo)簽?zāi)軌驖M足某個需求節(jié)點(diǎn)的要求斑唬，就在相應(yīng)的兩個節(jié)點(diǎn)間建立一條連接邊市埋。我們把這個二部圖記為G=(I∪A,E)，其中 E 為 I 與 A之間邊的集合恕刘，并用 Γ（a）表示所有與需求節(jié)點(diǎn) a∈A相鄰的供給節(jié)點(diǎn)的集合缤谎，而 Γ（i） 表示所有與供給節(jié)點(diǎn) i∈I 相鄰的需求節(jié)點(diǎn)的集合。在線分配的任務(wù)就是求解由i∈I 到a∈A的分配比例褐着，使得滿足供給方和需求方的約束的同時坷澡，某個與廣告效果相關(guān)的目標(biāo)函數(shù)達(dá)到最優(yōu)，下面給出一種形式的最優(yōu)化目標(biāo)函數(shù)献起。

目標(biāo)函數(shù)

3.1.2 需求約束與供給約束

在線分配問題的第一個約束條件是分配給某廣告合約 a的收益要至少等于其約定的量da ，這個約束稱為需求約束（demand constraint）:

需求約束

其中 q(ia) 為將供給節(jié)點(diǎn) i 連接到需求節(jié)點(diǎn) a 的單位流量懲罰岂嗓，

實(shí)際產(chǎn)品中常見的需求約束有兩類：一類是預(yù)算汁展、服務(wù)成本等的上限要求；另一類是合約量的下限要求厌殉。在后一種情形下食绿，q(ia)為負(fù)數(shù)，需求約束實(shí)際上描述的是一個收益項(xiàng)的下界公罕。

在線分配問題的另一個約束條件是每個供給節(jié)點(diǎn)被分配出去的量不能多于其總流量器紧，這個約束稱為供給約束（supply constraint），其意義很容易理解楼眷。供給約束可以表示成下面的形式：

供給約束

3.1.3 問題框架

根據(jù)上面的討論铲汪，從公式2.2定義的計(jì)算廣告目標(biāo)出發(fā)，引入供給約束與需求約束罐柳，得到下面的在線分配優(yōu)化問題框架表示：

在線分配優(yōu)化問題整體框架

除了供給約束和需求約束掌腰，上式中還有第三個約束，它用以保證分配變量非負(fù)张吉。公式11.4是一個比較一般性的數(shù)學(xué)表達(dá)齿梁，不僅僅適用于GD問題，也適用于其他量約束下的在線分配問題肮蛹。

3.2 在線分配問題舉例

3.2.1 GD問題

在線分配的最典型應(yīng)用就是 GD（擔(dān)保式投送）問題勺择。在此主要考慮按 CPM結(jié)算的市場创南。在GD合約的情形下，由于按CPM售賣廣告在所有合約都滿足時酵幕，如果不考慮合約a未完成的懲罰扰藕，收益是一定的常數(shù)缓苛。那么GD的優(yōu)化問題可以寫成：

GD優(yōu)化問題

GD問題的兩個約束都非常容易理解：供給約束的含義是每個供給節(jié)點(diǎn)分配給所有需求節(jié)點(diǎn)的流量比例之和不超過1芳撒；需求約束的含義是每個需求節(jié)點(diǎn)被分配到的流量總和應(yīng)該大于等于對應(yīng)合約的展示量要求。

3.2.2 AdWords問題

AdWords問題未桥，也被稱為有預(yù)算約束的出價（budgeted bidder）問題笔刹，討論的是在CPC結(jié)算的競價廣告環(huán)境下，給定各個廣告主的預(yù)算冬耿，整體化市場營收的問題舌菜。在這種情形下，問題的目標(biāo)函數(shù)和需求約束都有所變化亦镶，其對應(yīng)的在線分配問題體現(xiàn)為如下的形式：

AdWords優(yōu)化問題

q(ia)代表的是將關(guān)鍵詞i的一次點(diǎn)擊分配給廣告a的期望收益日月，即廣告a對關(guān)鍵詞i的出價,s(i)為關(guān)鍵詞 i的總點(diǎn)擊量；而 x(ia)為關(guān)鍵詞i分配給廣告a的流量比例缤骨。AdWords問題的優(yōu)化目標(biāo)是整個市場的收入最大化爱咬；而需求約束的含義是每個廣告主的花費(fèi)應(yīng)該小于該廣告主的預(yù)算。

3.4 實(shí)用優(yōu)化算法

假如未來一段時間內(nèi)需要投放的合約廣告是已知的绊起，如果廣告流量的分布在各個循環(huán)周期內(nèi)是近似一致的精拟，那么在線分配的問題就可以在流量預(yù)測的指導(dǎo)下進(jìn)行，這是大多數(shù)在線分配實(shí)用工程方法的基本出發(fā)點(diǎn)虱歪，下面給出實(shí)際工程中的幾種方法蜂绎。

1. 直接求解的原始分配方案
2. 基于對偶算法的緊湊分配方案
3. 綜合分配方案SHALE
4. 啟發(fā)式的分配方案HWM

章節(jié)相關(guān)名詞

• ADX 廣告交易平臺 AD Exchange
• CDN 內(nèi)容分發(fā)網(wǎng)絡(luò) Content Delivery Network
• GD 擔(dān)保式投送 Guaranteed Delivery