OMG合約廣告大腦之分配演算法：合約廣告分配

一、序言

隨著以CPM(cost per mille)結算的展示量合約廣告成為當今互聯網廣告的主流，合約廣告的售賣形式也從過去基於廣告位、時間等包段形式向以細分流量定向為基礎的精準式售賣進行轉變。實現高精度的媒體流量的售賣，關係著媒體方平台能否充分挖掘媒體流量的變現價值，並最終影響媒體方的整體收益。

在售賣階段，不同於效果廣告隨到隨買，實時競價的流量採買方式，展示量合約廣告主往往提前數周開始進行採買，媒體平台需具備在投放期數周前對未來流量的管理能力。一般來說，品牌展示量合約廣告的整個售賣流程包含如下幾個階段：1）詢量階段： 廣告位通過售賣系統查詢定向下的可預定流量；2）下單階段：廣告主和媒體主間制定流量預定合約；3） 廣告投放階段：媒體方對合約約定流量提供擔保式投放。與上述流程對應的合約廣告系統模塊框架一般如下圖所示：

圖1-合約廣告售賣系統整體框架

其中「售賣分配系統」作為詢量和下單階段的業務核心模塊，承擔了對未來數周（月）內廣告位流量的庫存詢量、預訂下單、預定量分配等重要功能，銜接和打通了廣告主流量預定和庫存消耗的整個流程，是實現流量的精確售賣和運營的關鍵一環。

二、問題描述

在品牌合約廣告業務中，售賣分配的核心是實現具體流量預定需求和預估曝光流量之間的最優化匹配方案，其本質是預估流量與保量訂單（Guarantee Delivery）之間的二部圖匹配問題（Display Ads Knows-IID類型）：由於是針對未來一段時間內的流量進行分配，因此這裡用於分配的曝光流量是由通過預估得到的；由於進行分配的訂單合約都帶有量的約束，因此這裡需要實現訂單保量約束下的流量分配。其原理可用如下二部圖[1]進行表達：

圖2-合約廣告售賣分配問題模型

其中Supply側節點是供應頂點，代表某類定向下的曝光流量; Demand側節點是需求節點，代表帶有某類預定需求的訂單。對任意需求節點，若節點代表的受眾標籤滿足其定向需求，則在和之間建立連線。因此，整個二部圖我們可以用表示，其中為所有供應節點與需求節點之間的供求關係集合。對於售賣庫存分配系統而言，其主要任務就是求解到的分配比例，使得滿足供給方和需求約束的同時，系統整體的收益函數目標值最大：

其中表示將展示按比例分配給訂單所帶來的收益。對於單個訂單而言，我們把Supply側所有滿足需求的供給節點的集合用表示，用代表Demand側所有和供給節點存在需求關係的訂單節點集合。式（2.1.1~2.1.3）分別對應了合約展示廣告售賣過程中的幾大主要約束條件：

（1） 供給約束：流量分配綜合佔比小於等於100%。

（2） 需求約束：訂單投放量應大於等於需求量，即保量投放。

（3） 非負約束：變數取值為正值。

通過將廣告售賣中流量和預定需求建模為上述的二部圖模型，並結合業務需求定義合適的目標函數及約束條件，我們可以很方便的將合約廣告系統中流量預定的分配問題轉化為類似上述形式的帶約束最優化問題，並應用合適的優化演算法進行求解。

本文將從互聯網合約廣告的發展歷程出發，結合業界以及騰訊OMG合約廣告系統在合約廣告售賣分配領域的一些精彩實踐，為大家簡述合約廣告售賣分配系統在模型演進以及演算法迭代等方面的發展歷程。

三、售賣分配演算法演進

由於互聯網廣告流量售賣不斷向精細化的方向發展、訂單數較多（百萬級別）並保持快速增長，以及訂單在流量分配過程中存在量的約束，共同導致了廣告售賣分配系統面臨的最優化問題的產品和技術複雜度較高，很難直接應用傳統的各類最優化演算法直接進行求解。售賣分配演算法的演進發展也經歷了從粗放到精確的階梯式發展歷程：

3.1 基於流量建模的貪心演算法

為解決大型合約廣告系統中訂單眾多以及定向條件複雜導致的供給節點和需求節點規模龐大的問題，Yahoo！在2012年提出了一種基於貪心規則的緊湊分配方案：HWM(High Water Mark)[2]演算法，是針對計算廣告領域的一種啟發式的、輕量快速的合約廣告流量分配演算法。演算法的核心啟發規則有如下兩條：1）根據需求訂單定向下可用庫存的緊缺程度，確定訂單之間的分配優先順序，高優先順序訂單優先進行分配；2）計算每個需求訂單在其優先順序下的播放比例值，在投放時僅憑該播放比例即可確定所有供給節點在該訂單上的分配量，即分配方案的緊湊性。基於上述規則，HWM演算法整體思路可描述如下：

該演算法的核心是提供了一種以維度流量為基礎進行建模並執行分配的緊湊解決方案，由於該演算法基於訂單優先順序順序進行分配，且分配策略具有一定的無狀態性，因此該演算法可基於預估維度流量提供快速、無狀態的緊湊分配方案，可滿足售賣流程中訂單快速詢量的業務需求。

3.2 基於流量建模的全局最優解演算法

上述HWM分配方案演算法，雖然在應用中具有快速求解、分配方案緊湊和無狀態的特點，但是在方案求解精度上仍存在很大提升空間：1) 演算法基於貪心策略對訂單按投放概率（）進行流量分配，優先考慮高優先順序訂單的流量分配需求，而非從全局訂單流量需求的角度出發尋找最優解；2) 演算法只考慮了訂單之間的優先順序關係，卻忽略了不同維度流量之間的優先順序(價值)差異，不是對媒體流量變現最優的方案。為了克服HWM演算法的上述問題，Yahoo！在同年發布的SHALE演算法[3]中，提出了流量庫存維度優先順序的概念，並應用對偶演算法求解售賣分配中的約束問題，通過優化對偶問題的求解，給出了一種可快速求解售賣問題最優解的緊湊解決方案，該演算法優化目標如下：

SHALE演算法同樣基於圖2所示的基於曝光的流量分配模型來進行方案求解，在該演算法中，SHALE將售賣分配的目標劃分為兩部分：1）最小化訂單總體缺量，對應式中目標函數的後半部分； 2）最大化流量分配方案的代表性(Representativeness)指標，對應式中目標函數的前半部分。每個需求節點都對應一個缺量代價以及 對應的缺量值。SHALE演算法通過對兩部分目標的求解，使得訂單對應的播放概率儘可能貼近其理論均值(Set) ；同時整個系統保持較低的缺量風險。

SHALE通過將式中兩類約束轉化為其的對偶問題(對應需求約束的對偶變數；對應供給約束側的對偶變數)，並對求解對偶變數的步驟進行了優化，採用原始對偶方法迭代進行求解，每次迭代的過程中不斷改善對偶解，並最終接近其最優解。其偽代碼流程如下：

Initialize:

Set

Setfor all.

Stage 1:

Repeat until we run out of time:

1. For each impression, findthat satisfies:

Ifor no solution exists, update.

2. For each contract, findthat satisfies:

Ifor no solution exists, update.

Stage 2:

1. Initializefor all i.

2. For each impression, findthat satisfies:

Ifor no solution exists, update

3. For each contract, in allocation order, do:

(a) Findthat satisfies :

,

settingif there is no solution.

(b) For each impressioneligible for, update:

OutPut:

Theandvalues for eachandfor each.

簡單來說，SHALE演算法的主要流程可總結為：在Stage1部分，迭代計算合適的的對偶變數取值；Stage 2 部分，通過對相應對偶問題的K.K.T條件的分析，將對偶變數帶入原問題進一步推導出最終的分配概率參數：

SHALE演算法通過採用基於迭代求解對偶問題的方式，加快了最優化問題的求解速度，並使得演算法具有良好的可伸縮性以及隨時即停的特點，非常適合售賣系統中增量的處理詢量訂單的場景，並且由於SHALE演算法通過構建訂單和流量兩個維度的優先順序，優化系統總體的收益情況，可最大程度優化流量資源的利用效率和價值，是當前OMG合約廣告流量售賣系統分配演算法的基礎。

3.3 基於用戶建模的全局最優解演算法

在實際應用中發現，基於流量建模的分配演算法在處理售賣分配問題時存在如下缺陷：1. 無法實現複雜類型的分配約束：投放節奏控制、競品去重等；2. 無法實現基於用戶的分配限制：人群定向、頻次控制等。尤其頻次控制(frequence capping)[4]作為合約廣告中最常見的定向約束之一，會極大的影響售賣問題中訂單和流量之間的匹配關係：

頻次，指的是某個用戶在一段時間內看到某個或某組廣告的曝光次數，並可具體分為最多看n次或最少看n次等多種限制方式。

傳統的基於流量的售賣分配演算法，由於基於流量對應的統計屬性(地域、性別等)進行建模得到對應的流量供應單元，這樣雖然會簡化售賣分配問題的複雜度，但同時也會丟失掉流量單元內部以及流量單元之間用戶的關聯關係，無法實現用戶級別的精確的頻控限制。

針對目前基於流量的售賣分配演算法無法有效處理用戶層面的分配限制的現狀，A Hojjat 在2014年提出了基於用戶行為模式(user pattern)建模的模式列生成演算法[5]並在2016年進一步提出了演算法的升級版本：分層級的模式列生成演算法(Pattern-HCG)[6]，上述兩個演算法的本質都是通過對廣告位流量按照用戶行為模式建模成不同層級的用戶行為序列，並在此基礎上執行廣告-流量之間的售賣分配，由於演算法綜合考慮用戶行為信息以及流量屬性相關特徵信息進行分配，因此可有效提高分配方案中各類約束條件的分配精度，如：1）流量在屬性維度分布的均勻性控制；2）廣告頻次控制；3）廣告投放的節奏控制；4）廣告內容多樣性控制等。在實踐中，Pattern-HCG演算法將售賣分配問題建模為如下二部圖優化的問題：

圖3-Pattern-HCG演算法問題建模

即在基於用戶行為建模的售賣問題中不僅要處理訂單-流量之間的分配問題（求解），還需要兼顧用戶-訂單之間的分配問題（求解）。Pattern-HCG演算法通過將上述二部圖優化問題分解為主問題和次問題兩個優化目標，並應用列生成演算法[7]進行迭代求解理想的訂單流量配方案：

1）主問題：訂單-流量節點之間的流量分配問題，保證訂單的流量預定需求能夠得到滿足。

2）次問題：頂單-用戶之間的分配多樣性問題，從訂單和用戶的角度優化廣告的投放效果和用戶體驗。

雖然Pattern-HCG在具體演算法實現上較為複雜，但總體包含三個關鍵模塊：流量分配模塊（reach allocation）、用戶模式分配（Pattern assignment）和模式生成模塊（pattern generation），Pattern-HCG演算法通過集成和迭代三個模塊的執行來實現流量分配問題的求解：在求解主問題和次問題時，首先得到一個粗略的流量分配方案，隨後在此基礎上不斷應用用戶模式分配和模式生成模塊挖掘新的更優的用戶分配模板來替換粗略方案中的用戶分配模板並對目標函數進行重新求解，直到收斂到理想的方案（即不再有更優的分配模板被生成）。Pattern-HCG演算法的兩個優化目標的求解過程分別對應如下兩個階段：

1. 流量分配階段

訂單-流量節點之間的流量分配問題作為演算法的主問題是演算法的核心優化目標，是解決其他目標問題的基礎，需要優先求解。在Pattern-HCG演算法中，作為衡量當前售賣流量的可利用率，被用來衡量當前分配方案合理程度的指標。在初始階段，演算法在設置每類用戶下的的條件下應用對偶演算法對售賣流量分配問題進行求解，然後不斷應用列生成優化演算法來優化該解下的流量分配方案並更新各類用戶下的值，並觸發流量分配方案的重新計算；當不再更新時，表明演算法已經收斂到最優的流量利用比例，該階段整體流程如下：

對於所有用戶類型，設置為 1

[1]: 應用 SHALE 對偶演算法的思路，求解帶利用率的售賣流量分配問題:

對[1]所得方案中的每類用戶(v, i)執行步驟[2]、[3]生成新的用戶分配模板：

[2]: 根據[1]中的分配結果，將用戶按照模板分配對應的訂單序列(PA-F) :

獲取需求約束對應解對偶變數。

[3]: 應用列生成演算法，生成更優的用戶分配模板序列 (PG-F)：

若，則將新生成的模板序列添加到模式序列空間中；

若， 則更新

當發現任意用戶類型對應的值降低了，說明當前流量分配方案和用戶分配方案不匹配，需重新回到步驟[1]求解當前下的流量分配方案，否則進入下一階段。

其中，代表不同用戶類型（高頻、中頻、低頻）用戶 （v, i）的預估用戶數；為不同用戶類型 v 對應的預估訪問次數；對應訂單投放期內的頻控限制數；為訂單對應的所有可用用戶類型列表；為某類用戶對應的所有可用訂單列表；為訂單是否出現在新生成的模板中。通過流量分配階段的求解，可以得到關於主優化目標的理想分配方案，後續將以此售賣流量分配方案為基礎對次優化目標進行迭代優化求解。

2. 分配方案迭代優化階段

在經歷了流量分配階段的處理後，我們已經可以得到一組可用於訂單投放的分配方案了，即實現演算法的主優化目標的求解；在本階段將基於上一階段得到的訂單-流量分配方案，從訂單多樣性及廣告投放節奏等方面優化訂單在各用戶流量上的分配結果：

對所有的用戶類型(v, i)執行如下操作：

[4] 將用戶按照上一階段得到的模板進行分配分配(PA-F)：

獲取需求和供應約束對應的解對偶變數和。

[5] 應用列生成演算法，為當前用戶類型生成更優的分配模板(PG)：

當時，則將新生成的模式序列添加到模式序列空間中，並轉到[4]處執行，否則，演算法執行結束。

由於應用了對偶演算法思路以及列生成的求解演算法，Pattern-HCG演算法能夠兼顧演算法快速收斂和高精度流量分配結果的優點，同時能夠一定程度的優化用戶層面的各種投放限制和體驗，體現了互聯網廣告投放「在合適的時間對合適的用戶投放合適的廣告」的本質追求，非常適合應用於各類大型廣告業務分配系統中。

結束語

在實時競價、程序化交易廣告和個性化推薦廣告蓬勃發展的今天，品牌合約廣告以其獨特的價值定位、高溢價的流量屬性以及有利於媒體方平台保持良好調性等特徵依然是互聯網廣告中重要的產品類型之一。本文從售賣階段訂單流量分配的角度，分析了品牌合約廣告售賣分配演算法的演進過程，可以看到隨著各類演算法對售賣分配過程核心問題理解的不斷加深，品牌廣告的售賣也不斷的往優化訂單投放效果和用戶觀看體驗等方向發展，是品牌合約廣告在效果優化上的嘗試和創新，值得我們在實際業務場景中引用借鑒。

[1]: https://en.wikipedia.org/wiki/Bipartite_graph

[2]: P. Chen, W. Ma, S. Manalapu, C. Nagarajan, S. Vassilvitskii, E. Vee, M. Yu, and J. Zien. Ad serving using a compact allocation plan. Proceedings of the 13th ACM Conference on Electronic Commerce. 2012, 1(212): 319-336.

[3]: V. Bharadwaj, P. Chen, W. Ma, C. Nagarajan, J. Tomlin, S. Vassilvitskii, E. Vee, and J. Yang. Shale: an efficient algorithm for allocation of guaranteed display advertising. In KDD, 2012.

[4]: https://en.wikipedia.org/wiki/Frequency_capping

[5]: S. Ali Hojjat, John Turner, Suleyman Cetintas, Jian Yang: Delivering Guaranteed Display Ads under Reach and Frequency Requirements. AAAI 2014: 2278-2284

[6]: S. Ali Hojjat, John Turner, Suleyman Cetintas, Jian Yang: A Unified Framework for the Scheduling of Guaranteed Targeted Display Advertising Under Reach and Frequency Requirements. Operations Research 65(2): 289-313 (2017)

[7]: https://en.wikipedia.org/wiki/Column_generationeration

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！