近年來，線上廣告在整個廣告行業的比重越來越高。線上廣告中實時競價的廣告由于其良好的轉化效果，占有的比重逐年升高。DSP（Demand-Side Platform）[1]作為需求方平台，通過廣告交易平台（AdExchange）[2]對每次曝光進行競價嘗試。對于AdExchange的每次競價請求，DSP根據Cookie Mapping [3]或者裝置資訊，嘗試把正在浏覽媒體網站、App的使用者映射到DSP能夠識别的使用者，然後根據DSP從使用者曆史行為中挖掘的使用者畫像，進行流量篩選、點選率/轉化率預估等，緻力于ROI [4]的最大化。
美團點評的使用者量越來越大，積累了大量的使用者在站内的行為資訊，我們基于這些行為構造了精準的使用者畫像，并在此基礎上針對美團App和網站的使用者搭建了美團DSP平台，緻力于擷取站外優質的流量，為公司帶來效益。本文從政策角度描述一下在搭建DSP過程中的考慮、權衡及對未來的思考。
- 在DSP實時競價過程中，政策端都在哪些步驟起作用；
- 對每一個步驟的嘗試和優化方向做出詳細介紹；
- 總結DSP如何通過AB測試、使用者行為回報收集、模型疊代、指導出價/排序等步驟來打通整個DSP實時競價廣告閉環。
美團DSP在一次完整的競價展示過程中可能涉及到兩個大的步驟： 1. 對AdExchange的競價請求實時競價； 2. 競價成功之後使用者點選進入二跳頁、浏覽、點選、最後轉化。
我們分别看一下這兩個步驟中政策的支援。
圖1 競價廣告示意圖
圖1給出了每一次競價廣告的粗略示意圖，競價Gateway在收到競價請求之後，會識别出美團點評使用者的流量，根據網站曆史CTR、網站品類屬性等因素進行簡單的流量過濾，把流量分發到後端的AdServer。AdServer作為後端廣告的總控子產品，首先向RecServer（定向召回服務）擷取站外展示廣告召回結果，然後根據擷取的廣告結果向PredictorServer（CTR/點選價值預測服務）請求每個廣告的站外點選率和點選價值。最後AdServer根據擷取的點選價值*v*和*ctr*，根據\(v*ctr^t\)進行排序，進而挑選出top的廣告進行展示。
圖2 二跳頁廣告流程圖
圖2給出了競價成功後，使用者從站外展示的廣告點選後，所經曆的流程示意圖。使用者點選站外廣告後，到達二跳頁Gateway，二跳頁Gateway向AdServer請求廣告清單。AdServer從RecServer擷取站内二跳頁廣告召回結果，然後根據擷取的廣告結果向PredictorServer請求每個廣告的二跳頁點選率并進行排序。排序後的結果傳回給二跳頁Gateway進行廣告填充。
在上述兩個步驟中，美團DSP政策端的支援由RecServer和PredictorServer提供，在圖1和圖2分别用紅色的箭頭和AdServer互動。其中RecServer主要負責站外廣告和二跳頁的廣告召回政策，而PredictorServer主要負責站外流量的CTR預估，點選價值預估和二跳頁内的CTR預估。整個政策的閉環如下圖：
圖3 政策閉環圖
接下來詳細介紹下美團DSP的召回、CTR預估、點選價值預估相關的政策。
從上一小節的介紹可以看到，定向召回服務分别在實時競價過程中提供了站外廣告的召回服務，在競價完成之後提供了二跳頁的廣告召回服務。站外召回和站内二跳頁召回沒有本質的差別，比較常見的做法是二跳頁會根據使用者點選商品的品類進行品類過濾。下面我們具體看一下目前定向召回相關的具體政策。
基于實時行為召回
通過實時日志流平台準确的跟蹤使用者的實時點選浏覽/收藏/購買行為，對于相應的使用者重新投放使用者近一段時間内發生過浏覽/收藏/購買行為的商品。需要注意的是這個政策需要考慮召回機率按時間進行衰減，使用者的實時行為能夠比較強反映使用者的近期興趣，距離目前時間比較長的使用者行為對于使用者近期興趣的定向偏弱。
基于位置召回
O2O的業務特點與傳統的電商有明顯的差別，傳統電商是線上上達成交易意向，然後通過快遞送貨的方式完成交易。O2O業務絕大部分消費者是線上上買入電子券，然後要到店進行消費，是以使用者的位置資訊在廣告召回中起着舉足輕重的作用。我們在基于位置的廣告召回中嘗試了以下三種政策：
1. 實時地理位置召回
根據使用者所在的實時地理位置召回距離比較近的廣告。 * 對于移動端的廣告流量，可以比較準确的獲得使用者的實時地理位置，進而進行比較精準的投放； * 對于PC端的流量，地理位置是通過使用者通路的IP位址進行推算的，是以地理位置是有偏移的，但是考慮到PC端浏覽廣告的流量使用者位置一般都比較固定，比如使用者一般是在上班或者在家休息，我們仍然使用了這個政策。
2. 實時商圈熱單召回
根據使用者所在的實時地理位置推斷出使用者目前所在商圈，給使用者投放目前商圈的熱門消費單。商圈的範圍一般在幾公裡範圍之内，對于使用者到店消費是一個合理的距離範圍，是以我們離線挖掘出每一個商圈的熱門消費單，作為使用者召回的候選。
可以看到政策1和政策2是不需要userid的，是以這兩個政策也是我們在識别不到userid的時候一個比較好的冷啟動召回政策。
3. 偏好商圈熱單召回
通過離線分析使用者曆史的浏覽/點選/購買行為，分析出使用者的曆史商圈偏好，召回使用者偏好的商圈消費熱單作為廣告候選集。這個政策需要使用者的userid，僅對于能夠識别并能映射到userid的使用者适用。
基于協同過濾召回
基于協同過濾的召回政策我們融合了user-based和item-based兩種。
基于item-based的協同過濾，我們首先通過使用者的購買行為計算item之間的相似度，比如通過計算發現item A和item B之間的相似度比較高，我們把item A作為候選推薦給購買item B的使用者，作為item B的使用者的召回候選集之一；同樣也把item B作為候選推薦給購買item A的使用者，作為購買item A的使用者的召回候選集之一。因為item-based協同過濾的特征，這一部分召回基本能夠把熱門爆款單都拉到候選集中。
基于user-based的協同過濾，我們同樣需要先計算使用者之間的相似度。計算使用者相似度時，除了考慮使用者購買的商品，還可以把使用者所消費過的商家及商家所在的商圈作為相似度權重考慮進來。這麼做是因為，很多商品是在全國多個城市都可以購買的，如果隻采用使用者購買的商品來計算相似度，可能把兩個不同城市使用者的相似度計算的比較高，加入商家和商圈的權重，可以大大降低這種情況的可能性。
基于矩陣分解的場景化召回
對于O2O消費的某些場景，比如美食和外賣，使用者是否發生購買與使用者目前所處的場景有很大關系，這裡的場景包含時間、地點、季節、天氣等。舉個例子來說，工作日的中午，如果還在下雨，這個時候外賣的購買機率一般是比其他商品高的。
基于此，我們開發了基于矩陣分解的場景化召回政策。我們采用了FM模型來進行模組化，模組化的特征包括季節、時間（工作日/周末，一天之内的時段）、地點、天氣等。這個政策的目的是希望召回使用者實時的基于場景化的需求。
上文提到在實時競價階段，AdServer會跟PredictorServer請求每個廣告的站外點選率和點選價值，最後AdServer根據擷取的點選價值*v*和*ctr*，根據\(v*ctr^t\)進行站外廣告排序，挑選top的廣告。最終的報價公式如下： \[a*\sum_{i=1}^k v_i * ctr{_i^t}+b\tag{1}\]
*k*是本次競價要展示的廣告數，t,a,*b*都是根據實際流量情況進行調整。其中*t*為擠壓因子，為了控制*ctr*在排序和報價中起作用的比重，*t*越大，*ctr*在排序和報價中的比重越高；a,*b*需要根據DSP需要擷取的流量和需要達到的ROI之間的權衡進行調整，a,*b*越大，出價越高，擷取的流量越多，成本越高，ROI就減少。
公式1中CTR直接作為一個引子進行出價計算，是以這裡的CTR必須是一個真實的點選率。因為在站外廣告點選日志中，正樣本是非常稀疏的，為了保證模型的準确度，我們一般都會采用負樣本抽樣。這樣模型估計出來的CTR相對大小是沒有問題的，可以作為排序依據，但是用來計算出價的時候，必須把負樣本采樣過程還原回去，我們在下面的小節中詳細解釋。
站外CTR預估
該模型目标是，對于RecServer召回的廣告，預測出廣告的相對點選率和真實點選率，相對點選率用于排序， 真實點選率用于流量報價。對于每個流量，AdExchange會下發給多個DSP，報價最高的DSP會勝出，擷取在這個流量上展示廣告的機會。為了能夠引入更多的優質流量，減少流量成本，提高ROI、CTR預估模型需要充分考慮站點、廣告、使用者等次元的資訊。
廣告的點選與轉化主要與使用者、廣告、媒體（user，ad，publisher）這三個因素相關。我們的特征也主要從這三個方向去建構，并衍生出一些特征[5]。
特征選擇
1. 使用者特征
使用者浏覽，購買的品類，使用者畫像，浏覽器，作業系統等特征。
2. 廣告特征
- 廣告deal的屬性特征，如商家、品類、價格、創意類型等特征。
- 廣告deal的統計特征，如曆史CTR、CVR、PV、UV、訂單量、評分等。
3. 媒體特征
網站類别，網站域名，廣告位，尺寸等特征。
4. 比對特征（主要是使用者與廣告次元的比對）
- 使用者浏覽、購買的品類與廣告品類的match， 商家的match。
- 使用者浏覽廣告的不同時間粒度的頻次特征，比如使用者浏覽目前廣告的次數、使用者上次點選廣告距離目前的時間差。
5. 組合特征
在LR+人工特征的實作過程中，需要人工構造一些組合特征，比如，網站+廣告、使用者消費水準+價格、廣告主+廣告品類等，對于FM和FFM能都自動進行特征的組合。
6. 環境特征
廣告的效果往往與使用者所處的外部環境相關。比如 時段、工作日/節假日、移動端的經緯度等。
特征處理
最後再看我們具體如何構模組化型。
1. 模型選擇
由于站外的站點數量巨大、廣告位較多、廣告的品類較多，造成訓練樣本的特征數較大，需要選擇合适的模型來處理，這裡我們選用了LR+人工特征的方式，確定訓練的性能。
2. 特征降維
點選率模型需要考慮使用者次元的資料，由于美團的使用者量巨大，如果直接用使用者id作為特征會造成特征數急劇增大，而且one-hot encoding後的樣本會非常稀疏，進而影響模型的性能和效果。是以我們這裡采用了使用者的行為和畫像資料來表征一個使用者，進而降低使用者次元的大小。
3. 負樣本選擇
- 對于站外廣告，有很多廣告位比較靠近頁面的下方，沒有被使用者看到，這樣的廣告作為負樣本是不合理的。我們在負樣本選擇的時候需要考慮廣告的位置資訊，由于我們作為DSP無法擷取廣告是否真實被使用者看到的資訊。這裡通過适當減少點選率較低的展位負樣本數量，來減輕不合理的負樣本的情況。
- 對于二跳頁廣告，隻取點選的位置之前的負樣本，而未點選的則隻取top20的廣告作為負樣本。
4. 負樣本采樣
由于廣告點選的正負樣本分布極其不均，站外廣告的點選率普遍較低，絕大多數樣本是負樣本，為了保證模型對正樣本的召回，需要對負樣本按照一定比例抽樣。
5. 真實CTR校準
由于負樣本抽樣後，會造成點選率偏高的假象，需要将預測值還原成真實的值。調整的公式如下：
\[q=\frac{p}{\left(p+\frac{1-p}{w} \right)} \tag{2}\]
q: 調整後的實際點選率。 p: 負樣本抽樣下預估的點選率。 w: 負樣本抽樣的比例。
二跳頁CTR預估
當使用者點選了廣告後，會跳轉到廣告中間頁，因為站外流量轉化非常不容易，是以對于吸引進來的流量，我們希望通過比較精細化的排序給使用者投放盡可能感興趣的廣告。
由于進入二跳頁的流量大概比站外流量少兩個數量級，我們可以使用比較複雜的模型，同時因為使用比較多的使用者/廣告特征，是以這裡我們選擇了效果比較好的FFM[6]模型（詳情可以參考之前的部落格文章《深入FFM原理與實踐》）。
特征和樣本處理方面的流程基本類似CTR預估子產品中的樣本處理流程。差别在于廣告在展示清單中的位置，對廣告的點選機率和下單機率是有非常大影響的，排名越靠前的廣告，越容易被點選和下單，這就是position bias的含義。在抽取特征和訓練模型的時候，就需要很好去除這種position bias。
我們在兩個地方做這種處理： * 在計算廣告的曆史CTR和曆史CVR的時候，首先要計算出每個位置的曆史平均點選率ctr_p，和曆史平均下單率cvr_p，然後再計算i廣告的每次點選和下單的時候，都根據這個item被展示的位置，計算為ctr_0/ctr_p及cvr_0/ctr_p。 * 在産生訓練樣本的時候，把展示位置作為特征放在樣本裡面，并且在使用模型的時候，把展示位置特征統一置為0。
上文提到廣告是根據\(v*ctr^t\)進行排序，并通過公式1進行報價。這裡面的*v*就是點選價值（點選價值是指使用者發生一次點選之後會帶來的轉化價值）。
廣告業務的根本在于提高展示廣告的eCPM[7]，eCPM的公式可以寫為\(v*ctr*1000\)，準确的預估點選價值是為了準确預估目前流量對于每一個廣告的eCPM。劉鵬在《計算廣告》[8]中提到，隻要準确的估計出點選價值，通過點選價值計算和CTR計算得到的eCPM進行報價，就始終會有利潤，這是因為AdExchange是按照廣義第二出價進行收費的。
在實際投放過程中，出價公式可以随着業務目标的不同進行适當的調整，比如我們的出價公式中包含了擠壓因子*t*，和*a *，*b*兩個參數。出價越高帶回來的流量越大，可能帶來品質參差不齊的流量，一般在一段時間之内會引起CTR的降低，這樣會帶來CPC點選成本的提高，是以ROI會降低。反之出價比較低的情況下，帶來的流量越少，經過比較細緻的流量過濾，CTR能長期保持在一個較高的水準，點選成本CPC比較低，ROI就會比較高。
美團DSP在點選價值預估上經曆了兩個階段： * 第一階段是站外廣告的落地頁是廣告的詳情頁面時，廣告的點選價值預估比較簡單，隻需要預估出站外流量到達廣告詳情頁之後的CVR即可。正負樣本的選擇也比較簡單，采集轉化樣本為正樣本，采集浏覽未轉化樣本作為負樣本。我們也進行了适當的負樣本采樣和真實CVR校準，這裡采用的方法跟上一節類似，不再贅述。 * 模型方面，在控制特征複雜度的基礎上，我們選擇了效果不錯的二次模型FFM，複雜度和性能都能夠滿足線上的性能。 * 特征方面，我們使用了站外實時特征+部分離線挖掘特征，由于FFM預測複雜度是(k*n*n)，*k*是隐向量長度，*n*是特征的個數，特征的選擇上需要挑選貢獻度比較大的特征。
- 第一階段投放之後，經過統計，詳情頁的使用者流失率非常高，為了降低流失率，我們開發了廣告二跳頁，在二跳頁裡面，使用者在站外點選的廣告排在第一位，剩下的是根據我們的召回政策和排序政策決定的。根據公式1，點選價值是由二跳頁的*k*個廣告共同決定的。但是在站外廣告排序和報價的過程中，我們無法擷取中間頁的召回結果，是以在實際情況中是無法适用的。目前我們的政策是直接對目前使用者和目前商品的特征建立一個回歸模型，使用使用者在二跳頁上成交的金額作為label進行訓練，模型分别嘗試了GBDT和FM，最終采用了效果稍好些的GBDT模型。
離線評估
業内常用的量化名額是AUC，就是ROC曲線下的面積。AUC數值越大，模型的分别能力越強。
Facebook提出了NE（Normalized Entropy）[9]來衡量模型，NE越小，模型越好。
\[NE=\frac{-\frac{1}{N} \sum_{i=1}^n \left(\frac{1+y_i}{2}\log(p_i)+\frac{1-y_i}{2}\log(1-p_i) \right)}{-(p*\log(p)+(1-p)*\log(1-p) )} \tag{3}\] > N：訓練的樣本的數量。 yi：第i個樣本的lable，點選為+1， 未點選為-1。 pi：第i個樣本預估的點選率。 P：所有樣本的實際點選率。
離線我們主要使用的是AUC和NE的評估方法。
線上AB測試
通過線上ABtest，確定每次上線的效果都是正向的，多次疊代後，站外CTR提升30%，廣告二跳頁CTR提升13%，二跳頁CVR提升10%。
線上監控
1. 線上AUC監控
線上預估的CTR和CVR，建立小時級流程，計算每個小時的線上AUC。發現AUC異常的情況，會報警，確定模型線上應用是正常的。
2. 線上預估均值監控
線上預估的值會計算出平均值，確定均值在合理的範圍之内。均值過高會導緻報價偏高，擷取流量的成本增加。均值過低，造成報價偏低，擷取的流量就偏少，對于估值異常的情況能及時響應。
本文介紹了美團DSP在站外投放過程中的政策實踐。很多細節都是在業務摸索過程中摸索出來的。後續有些工作還可以更細緻深入下去：
1. 流量篩選
流量篩選目前還是比較粗暴的根據網站曆史的CTR等直接進行過濾，後續會基于使用者的站内外的行為，對流量進行精細化的篩選，提升有效流量，提高轉換。
2. 動态調整報價
- 在DSP的報價環節，點選率預估模型會對每一個流量預估出一個CTR，為了适應adx市場的需要，會加上指數和系數項進行調整。但是通過這種報價方式擷取的流量，由于外部競争環境的變化，流量天然在不同時段的差異，經常會出現CPC不穩定。該報價的系數對于所有的媒體都是一緻的，而一般的優質媒體都是有底價的，且不同媒體的底價不一緻，造成該報價方式無法适用所有的媒體，出現部分優質媒體無法擷取足夠的流量。
- 我們的目标是在CPC一定的情況下，在優質媒體、優質時段盡可能多的擷取流量，這裡我們需要根據實時的回報和期望穩定的CPC來動态調整線上的報價[10]。進而在競價環境、時段、媒體變化時，CPC保持穩定，進一步保證我們的收益最大化（同樣的營銷費用，擷取的流量最多）。
3. 位置召回
基于位置的召回政策中，我們對使用者的商圈屬性沒有作區分，比較粗粒度的統一召回，這樣其實容易把使用者目前時間/位置真正有興趣的商品拍的比較靠後；比較好的辦法是通過精準的使用者畫像和使用者消費時間/位置上下文挖掘，根據使用者競價時的位置和時間，分析出使用者轉化率高的商圈，進而進行更加精準的投放。
在業務上，美團DSP會逐漸接入市場上主流的AdExchange和自有媒體的流量。技術上，會持續探索機器學習、深度學習在DSP業務上的應用，進而提升美團DSP的效果。
- https://en.wikipedia.org/wiki/Demand-side_platform
- https://en.wikipedia.org/wiki/Ad_exchange
- https://developers.google.com/ad-exchange/rtb/cookie-guide?hl=en
- https://en.wikipedia.org/wiki/Return_on_investment
- http://www.xiutx.cn/archives/263
- https://www.csie.ntu.edu.tw/~cjlin/libffm/
- http://baike.baidu.com/view/1666309.htm
- http://book.douban.com/subject/26596778/
- http://www.herbrich.me/papers/adclicksfacebook.pdf
- https://en.wikipedia.org/wiki/PID_controller
鴻傑，美團平台與酒旅事業群使用者增長政策負責人，曾就職于阿裡，2015年加入美團點評。主要緻力于通過機器學習提升美團點評平台的活躍使用者數，作為技術負責人，主導了站外管道投放、站内新客營運等項目的算法工作，提升營銷效率，有效降低營銷成本。
李樂，美團點評美團平台與酒旅事業群使用者增長組DSP業務基礎召回和裝置下載下傳的負責人，2014年7月從浙江大學碩士畢業後加入美團。負責過CPS搜尋廣告、新客營運、DSP基礎召回、DSP裝置下載下傳等業務，緻力于推動全網裝置的精準觸達。
** 因團隊業務急劇發展，誠招廣告算法工程師，級别不限，歡迎郵件wuhongjie#meituan.com咨詢。**