計算廣告@合約廣告
合約廣告主要分為廣告位合約和展示量合約。
廣告位合約
實際上是將線下的模式搬到了線上，指的是廣告主與媒體約定在某一時間段內，在某些廣告位上固定投放該廣告主的廣告，相應的結算方式是 CPT(Cost Per Time)（也就是按照展示時間結算），這種模式下售賣給廣告主的是廣告位。
這種合約對供給方和需求方的技術的要求都不高。供給方即媒體往往會使用一種在合同確定以後自動的執行合同的廣告管理工具：廣告排期系統。廣告排期系統能夠幫助媒體自動執行多個合同的排期，可以將廣告素材直接插入頁面，且對於圖片等靜態資源，會放到 CDN 上進行加速。
需求方即廣告主往往會通過代理商（agency）進行媒介採買（也就是廣告位採買），代理商幫助廣告主策劃和執行排期，而對於廣告的質和量，是根據代理公司人員對媒體廣告位的歷史經驗以及對廣告主業務的了解通過人工優化的方式來滿足。這樣的代理公司的代表有我們前面一講提到的 4A 公司。
展示量合約
展示量合約廣告指的是約定某種受眾條件下的展示量，然後按照事先約定好的單位展示量價格來結算，這種結算方式是 CPM(Cost Per Mille)（也就是每一千次展示的付費）。這種方式也叫擔保式投放(Guarantee Delivery, GD)，意思就是先廣告主擔保其提出的廣告展示量會被滿足。這種模式下售賣給廣告主的是廣告位+人群。
這種合約主要是為了在受眾定向的基礎上提高單位流量的變現能力，可是面向的任然是原來的品牌廣告主。廣告主按廣告位採買時，比較容易預估到自己能夠拿到的流量，可是按照人群定向的方式採買，流量有諸多不確定的因素，因此，需求方希望在合約中加入對量的保證，才能放心購買。而假如約定的量未完成，則需要向廣告商補償。實際中的展示量合約往往是以一些曝光量很大的廣告位為基礎，再切分人群售賣，最典型的例子就是視頻網站的鐵片位置或者門戶網站首頁的廣告位。
展示量合約這種模式的出現實際上已經反映了互聯網廣告計算驅動的本質：分析得到用戶和上下文的屬，並且由伺服器端根據這些屬性以及廣告庫情況動態決定廣告候選。這一商業模式的出現，需要有一系列技術手段的支持，這些技術手段主要包括受眾定向、流量預測、在線分配等。下面主要介紹流量預測和在線分配，受眾定向見計算廣告@系統架構。
- 流量預測
流量預測(traffic forecasting) 簡單來說就是預測某個標籤的人群訪問某個站點的量。流量預測其目的有多種，典型的有售前指導，在線流量分配，出價指導，前面兩個是合約廣告中的內容，而後面一個是競價廣告中的內容。
1. 售前指導指的是在展示合約廣告系統中，由於要約定曝光總數，事先儘可能準確地預測個人群標籤的流量非常重要。因為如果流量低估，會出現資源售賣量不足的情形；而如果流量嚴重高估，則會出現一部分合約不能達成的狀況。
2. 在線流量分配指的是在展示量合約廣告系統中，由於合約之間在人群的選擇上會有很多的交集，因此一次的曝光往往會滿足多個合約的要求，這時候就需要在多個合約之間進行分配，目的是達到整體滿足所有合約的目的。這也是下面要詳細探討的在線流量分配的問題。
3. 出價指導是競價廣告中的內容，在競價廣告中，沒有了量的保證，廣告主往往需要根據自己預計的出價先了解一下可能獲得多少流量，以判斷自己的出價是否合理。與前面在合約廣告中的應用不同，這裡還多了出價這一因素。
- 在線分配
在合約廣告系統中主要討論在線分配（Online Allocation）問題，在線分配問題指的是在通過對每一次廣告展示進行實時在線決策，從而達到在滿足某些量的約束的前提下，優化廣告產品整體收益的過程。在線分配是廣告中比較關鍵的演算法框架之一，適用於許多量約束下的效果優化問題，而這實際上是廣告業務非常本質的需求。
問題模型
在線匹配可看作是一個二部圖匹配問題，如上圖，左邊是代表廣告庫存的供給節點（集合記為 I），右邊代表廣告合約的需求節點（集合記為 A）。供給節點標籤能夠滿足需求節點的要求時，就在相應的兩個節點之間建立一條連接邊，所有邊的連接記為集合 E。在線分配技術並不僅僅適用於展示量合約中的擔保投放（GD）問題，還適用於 AdWords 問題，展示廣告問題等。下面主要介紹 GD 問題和 AdWords 問題。
- GD問題
前面已經提到了GD的概念，在這裡如果不考慮合約未完成的懲罰，收益一定是常數。那麼 GD 的優化問題可以表示為（s為供應節點的流量）
- Adwords問題
AdWords 問題，也被稱為有預算約束的出價問題，是競價廣告領域內的問題。簡單來說，這個問題討論的是在按照 CPC 方式結算的廣告環境下，給定廣告主的預算，整體化市場營收問題。需要注意的是，競價廣告中已經沒有了量的約束，廣告主給的約束是其預算費用。因此可以將這個問題表示為如下的優化問題（q為出價，d為預算）
上面的兩個最優化問題均是線性規劃問題，未知量是供給節點的流量和供給節點分配給需求節點的流量的比例。但是對於供給節點，常常利用歷史流量去估計它的值，因此上面的優化問題變成了僅僅需要求解流量分配比例的問題。下面解決這個問題的幾種思路。
- 直接求解
對於這類線性規劃問題，可以通過內點法或單純形法直接進行求解，但是在大型的廣告合約系統中，供給節點和需求節點的數目都很大，因此邊 |E| 的數目也會非常大（百萬級以上),這樣會使得對應的分配問題變得過於複雜而無法直接有效求解。令 n 為變數的個數，則內點的時間複雜度為 n 的多項式級別，單純形法的時間複雜度為 O(n^2), 這樣直接求解的解參數正比於 |E| 的數量，規模有可能過於龐大，無法進行實時的在線分配。因此有必要探索更新效率更高的的在線分配方案。
- 對偶求解
通過拉格朗日對偶可將原問題裝化為對偶問題，但是對偶問題的變數數目仍然正比於約束的數目（供給約束和需求約束），前者的變數的量級為十萬甚至百萬千萬，但後者的量級在數千級別。
為了減少所需求解的變數，這篇文獻Optimal Online Assignment with Forecasts提出了一個方法：只保留需求約束對應的對偶變數，然後通過數學變換恢復出供給約束對應的對偶變數和分配率。具體的演算法過程可參考上面提到的文獻。
上面的方法在求解對偶問題時代價仍然比較高，因此在an efficient algorithm for allocation of guaranteed display advertising提出了 SHALE 演算法，優化了求解對偶變數的步驟，採用了原始對偶方法迭代進行求解，求解出對偶變數後，通過數學變換恢復出供給約束對應的對偶變數和分配率跟上面的方法一致。
- 啟發式分配方案 HWM
上面根據歷史流量數據來求解的分配方案原理上可行，但是在實際的工程應用中仍然顯得有些複雜，比如離線仍然要消耗大量的時間求解對偶解。因此，人們希望實現一種快速演算法，保持前述方法的緊湊分配的特性，效果上也能夠近似最優。前述方法中通過合同節點的對偶變數即可恢復最優解，受其討論啟發，可以發現，只要大體確定好每個合同在分配中的相對優先順序以及分配時得到某次展示的概率，就可以構造出一種直覺上可行的在線分配方案。
Ad serving using a compact allocation plan提出的 HWM（High Water Mark） 演算法便是這樣一種方案，雖然在數學上並不完全嚴謹，但是由於根據歷史數據來指定的分配方案本身就具有相當程度的近似，因此其實際效果也不錯，而工程上的便利性則是這個演算法的一大優點。
HWM 分配演算法
離線階段
1. 令每個人群維度組合k的剩餘supply(r_k)等於預測量(s_k)：r_k = s_k.2. 對於每個合約j，按照分配優先順序對每個a：解得serving rate alpha_j, 若無解則 alpha_j = 1.3. 對於與a相鄰的每個supply，令r_k = r_k - min{r_k, s_k * alpha_j}註：通過可滿足各合約的供給節點總流量的升序排列進而得到分配優先順序在線階段1. 對在線到來的每個impression, A = {alpha_1, alpha_2, ..., alpha_|A|}為所有滿足要求的廣告的serving_rate.
2. 按照A中的每個廣告的serving rate隨機分配其展示機會。
廣告平台的常用工具
Offline
1. HBASE（列存儲的NOSQL資料庫，類似的有BigTable，HyperTable，Cassandra）2. Pig: 一種腳本語言3. Elephant-bird：將二進位文件轉為 pig 可處理的文本文件4. Hive: 一種腳本語言5. mahout: 分散式機器學習Online1. ZooKeeper/Chubby: 分散式環境下解決一致性問題2. Avro/Thrift: 分散式環境下跨語言的通信問題3. S4/Storm: 流式計算平台
4. Chuhwa/Scribe/Flume: data highway： 分散式日誌收集工具，並送到其他平台
推薦閱讀：
