DSP基础算法与模型研究
DSP基礎(chǔ)算法與模型研究
（轉(zhuǎn)載請保留原文鏈接?http://www.techinads.com/archives/41?authored by 江申_Johnson）
美國有一家很優(yōu)秀的DSP公司--M6D（m6d.com），這個公司只是個startup公司，卻已經(jīng)在KDD之類的頂級會議發(fā)表的7-8篇優(yōu)秀的文章。最近我研究了一下他們的DSP算法，和大家分享一下我的理解，希望以一個實例讓大家對DSP中的基礎(chǔ)算法和模型有一個初步的了解。寫得不對的地方，還請大家及時指正。
這篇文章假設(shè)大家對DSP及RTB生態(tài)圈各種三個字母縮寫的概念有初步的理解。
一、整體流程
首先，我們先來看一下M6D的DSP工作的整個流程：
?
?
?
?
?
?
?
二、核心算法
第2步（Audience Selection）和第5步(Bidding)是最核心的兩步，其中audience selection是離線計算過程，因為可以在exchange發(fā)送請求前離線慢慢算好，而bidding的過程需要在100ms內(nèi)在線快速算好。下面分開介紹這兩步中的算法和模型，最后介紹如何對算法效果進行評估。
Audicence Selection:
m6d的Audience Selection算法需要對每個compaign都訓(xùn)練以下兩個模型（對每個compaign獨立訓(xùn)練模型是因為廣告主隱私保護，從一個廣告主網(wǎng)站上采集的數(shù)據(jù)不能用來優(yōu)化另外一個廣告主的模型，例如不能利用京東上訪問過電視購買頁面的用戶數(shù)據(jù)，來給蘇寧電器優(yōu)化模型，被京東知道了，他們的生意你以后就沒得做了。另外一個原因是分每個compaign單獨訓(xùn)練模型在訓(xùn)練數(shù)據(jù)充足的時候可能有更優(yōu)的效果。當然隱私的原因是主要原因）：
?
之所以要分為兩個模型，個人認為主要是性能考慮，如果把所有的用戶都用high-level model來預(yù)測，那么在特征抽取和預(yù)測上都會消耗大量的計算量。而low-level模型因為特征只有URL，特征抽取邏輯簡單，計算量小很多，另外對于一個compaign的Low-level Model來說，非0權(quán)重的特征數(shù)目有限，只需要把這些非0權(quán)重的url對應(yīng)的用戶拿出來計算預(yù)估值就可以了（相當于一個簡單檢索過程），不需要對所有的用戶來計算預(yù)估值。
之后，每個compaign就會根據(jù)每個用戶通過audience selection model預(yù)估的轉(zhuǎn)化概率p(c|u)選出目標用戶，m6d的經(jīng)驗數(shù)據(jù)是不超過百分之一的用戶會成為某個compaign的目標用戶。然后這些目標用戶會根據(jù)不同的轉(zhuǎn)化概率閾值劃分到不同的segments中。例如p(c|u)>0.01放到一個segment中，0.01>= p(c|u) > 0.001放到另外一個segment中。論文中沒有說到一個用戶是否可以放到兩個或以上的segment中，但我覺得應(yīng)該是可以的。每個compaign有大約10到50個segments左右。劃分segments的作用一是方便賬戶管理員對每個segment設(shè)置基礎(chǔ)出價，另外在后面介紹的bidding算法中將屬于同一個segment的用戶做無差別對待，相當于同屬一個類，可以緩解某些用戶數(shù)據(jù)稀疏的問題，后面會詳細介紹。
以上就是m6d的audience selection算法，值得注意的是，上述步驟是offline的，也即是預(yù)處理的，在exchange的請求到來前就已經(jīng)對每個compaign都算好了。有的地方把根據(jù)廣告主的一些少量已知轉(zhuǎn)化用戶找到更多潛在用戶的模型叫做Look-alike Model, 我理解這里的audience selection model也應(yīng)該算是look-alike model。
Bidding?
當exchange發(fā)送請求時，DSP會接受到當前用戶的cookie和一些最基本的用戶信息，以及當前廣告位的信息。DSP則需要找到這個用戶所屬的所有segments，而這些segments可能會對應(yīng)多個compaign。那么應(yīng)該出哪個compaign的廣告呢？這里有一個內(nèi)部競價的過程。
m6d是這么做的，首先要把一些不合適出廣告的compaign根據(jù)規(guī)則過去掉。主要的規(guī)則有，如果一個用戶之前已經(jīng)被展現(xiàn)了這個compaign的廣告數(shù)達到一定的個數(shù)了，那么就不要再浪費廣告費了（這個次數(shù)限制通常叫frequency cap）。另外一個主要規(guī)則是，如果一個compaign已經(jīng)達到了它的每日，或者每周，或者每月預(yù)算限制了，那么也不再為它投放廣告了。對于剩下的compaign候選，DSP會對他們都根據(jù)算法計算出最合適的出價，然后簡單地選取出價最高的那個（出價反映了當前用戶對該compaign的價值）。細心的朋友會發(fā)現(xiàn)這里是一個貪心的算法，有優(yōu)化的空間，這個我們最后一起來總結(jié)。
下面介紹下對于某一個compaign, 如何計算對當前展現(xiàn)機會的出價。
前面的audience selection部分，我們已經(jīng)對每個用戶劃分了segments，然后賬戶管理員又對每個segment給出了基礎(chǔ)出價（base price），當時這個出價考慮的是這個用戶和這個compaign的適合程度，并沒有考慮當前廣告位是否適合這個compaign投廣告，是否適合這個用戶。因此m6d的算法，以基礎(chǔ)出價為基準，根據(jù)當前廣告位計算出一個調(diào)整因子?Φ?，最后的出價就是?baseprice?Φ?。因此我們?nèi)康墓ぷ骶褪且嬎氵@個?Φ?。
如果上過劉鵬老師的計算廣告學(xué)課的同學(xué)肯定會知道，在廣義二階競價模型里，排序是應(yīng)該按照 ecpm=轉(zhuǎn)化概率*轉(zhuǎn)化價值 來排序的。ecpm可以認為是一個展現(xiàn)的價值，它等于一個轉(zhuǎn)化的價值*一個展現(xiàn)變?yōu)橐粋€轉(zhuǎn)化的概率。其實我想說的就是，對于同一個compaign來說，如果我們知道一個展現(xiàn)的轉(zhuǎn)化率是另外一個展現(xiàn)的2倍，那么前面那個展現(xiàn)的出價應(yīng)該是后面那個展現(xiàn)的出價的2倍。
按照上面的邏輯，既然我們?yōu)閟egments出了一個平均價格base price，當僅當一個展現(xiàn)的轉(zhuǎn)化率是這個segments中用戶的平均轉(zhuǎn)化率的?Φ?倍，我們應(yīng)該為這個展現(xiàn)出?baseprice?Φ?的出價。所以
Φ=p(c|u,i)Ej[p(c|u,j)]
其中，u指的是用戶，i是當前的廣告位(inventory)，c指的是轉(zhuǎn)化。分母計算的是在所有廣告位（用j指代）上的平均轉(zhuǎn)化率。這個分母要計算起來很復(fù)雜，我們要遍歷所有的廣告位(inventory)。但我們知道：
p(c|u)=Ej[p(c|u,j)]=∑jp(c|u,j)p(j)
因此有
Φ=p(c|u,i)p(c|u)
所以m6d的bidding算法的最核心部分，就是為每個compaign都建立兩個模型來分別預(yù)估p(c|u,i)和p(c|u)。考慮到每個compaign的轉(zhuǎn)化數(shù)據(jù)很少，這2個模型的訓(xùn)練數(shù)據(jù)很少，要訓(xùn)練這兩個模型太難了。因此m6d將同一個segment中的用戶不做區(qū)分，從而可以把上式變?yōu)?/p>
Φ=p(c|s,i)p(c|s)
其中，s是segment。這樣就只需要訓(xùn)練p(c|s,i)和p(c|s)。因為s的個數(shù)遠小于u的個數(shù)，這2個模型的特征空間顯著變小了，模型更容易得到更好的結(jié)果。事實上，m6d也對i的部分做了類似的trick，它把類似的廣告位聚合到一起，給予一個相同的inventory id。目的和把u變?yōu)閟是類似的。m6d的inventories的規(guī)模是5000個左右，每個compaign的segment的個數(shù)是10到50個左右。
以上就是m6d對bidding的建模過程了，剩下的工作就是如何訓(xùn)練得到這兩個模型。
p(c|s,i)模型:??要得到這個模型的訓(xùn)練數(shù)據(jù)，還有一個冷啟動的過程。必須事先對這些segments在這些inventories上投放，然后把那些最終帶來轉(zhuǎn)化的展現(xiàn)標記為正例，沒有最終帶來轉(zhuǎn)化的展現(xiàn)標記為負例。m6d認為一次轉(zhuǎn)化是由之前7天內(nèi)該用戶見到的最后一次展現(xiàn)帶來的。這個模型的特征只有兩類，一類就是segment id, 另外一類就是inventory id。也就是說，每一個樣本只有兩個非0的特征，一個是segment id對應(yīng)的那個特征，另外一個是inventory id對應(yīng)的那個特征。m6d沒有組合segment和inventory特征，這樣做的結(jié)果是：不管對于哪個segment，某個特定的inventory對最后預(yù)估值的貢獻都是一樣的。這個假設(shè)可以認為在大多數(shù)情況下是合理的。而且如果真要把這些組合特征加入模型，特征空間一下子又大了不少，對于少得可憐的訓(xùn)練數(shù)據(jù)來說，很容易就過擬合了。
p(c|s)模型：和p(c|s,i)模型基本一樣，區(qū)別就是特征只有segment id。
這兩個模型的正例比例都非常低，因此進行了采樣（sampling）和修正（recalibration）。這是一種很常見的處理方式，不了解的朋友可以Google這篇文章：《Logistic regression in rare events》。
考慮了廣告位（inventory）和不考慮廣告位對轉(zhuǎn)化率的預(yù)估由有多大的影響呢？以下的圖展示了區(qū)別：
考慮廣告位信息后，AUC提升了0.0346，還是非常明顯的。這個Lift也是一種評估指標，后面會詳細解釋。這里可以看到Lift指標也明顯提升了。
具體看個例子。對于一個hotel廣告主的一個compaign，不同的廣告位預(yù)估出來的?Φ?值也很不相同，旅游類的預(yù)估值最高，社會媒體的最低。說明這個模型還是有一定區(qū)分度的。
評估
1. 模型評估
通常我們用AUC來評估模型的排序能力，但是AUC有一個問題是它無差別地考察了一個列表中所有位置的排序合理性，而對于我們的audience selection模型，轉(zhuǎn)化率預(yù)估模型，我們更看重是否把最靠譜的拍在了前面，換句話說，是更看重這個列表中，前面的位置的排序合理性。因此m6d用了Lift指標。Lift@5% 指標衡量了在前5%的結(jié)果中，正例的比例比在隨機情況下正例出現(xiàn)的比例高了多少。具體的Lift定義可以看：http://en.wikipedia.org/wiki/Lift_(data_mining)
2. 業(yè)務(wù)目標評估
對于DSP的投放效果，m6d主要會看兩個業(yè)務(wù)指標，一個是轉(zhuǎn)化率（PVSVR）, 即轉(zhuǎn)化數(shù)除以展現(xiàn)數(shù)（即CTR*CVR）；另外一個是CPA, 即獲得每一個轉(zhuǎn)化，平均花了多少錢。
m6d的廣告主大多喜歡按CPM方式購買展現(xiàn)，找n家DSP來同時投放，給一樣的CPM，然后看誰的轉(zhuǎn)化率高。因此轉(zhuǎn)化率是DSP賴以生存的指標之一。
轉(zhuǎn)化率是和價格無關(guān)的，而如果一家DSP雖然轉(zhuǎn)化率低10%，但是每個展現(xiàn)的價格（cpm）比別人低50%，那么對于廣告主來說，還是會選擇它的。因為它的CPA更低了，即獲取一個轉(zhuǎn)化，廣告主需要付出的成本更低了。
所以，DSP的轉(zhuǎn)化率是和利潤掛鉤的，要么把技術(shù)做得很好提高轉(zhuǎn)化率，這樣在保持CPA不變的情況下，向廣告主收取更高的CPM，從而賺更多的錢。否則就只能比別人賣得更便宜了，甚至虧本了。當然，聰明的DSP會在早期先砸VC的錢虧本吸引廣告主來投放，投放是可以累積數(shù)據(jù)的，有了數(shù)據(jù)下次就可以把轉(zhuǎn)化率做得更好，從而再把錢賺回來。
也有廣告主是按每個點擊付費的（CPC），有的廣告主是給一筆固定的投放預(yù)算，但其實最后都是類似的，廣告主最終會去換算成CPA來進行比較。（只重視展現(xiàn)量的廣告主除外）
三、延伸討論
上面的篇幅研究了m6d的DSP的算法和模型，我覺得有些地方可能可以有不同的做法（不一定更優(yōu)），寫出來和大家探討一下：
1. bidding中的轉(zhuǎn)化率模型
前面的audience selection model (look-alike model)對每個compaign分別建模還有可能是因為在每個compaign訓(xùn)練數(shù)據(jù)充分的情況下可能取得更好的預(yù)估效果。而后面的兩個轉(zhuǎn)化率模型將每個compaign分別建模就一定是因為privacy的原因了，因為每個compaign的這2個模型的訓(xùn)練數(shù)據(jù)太少了，而且m6d用的是轉(zhuǎn)化作為正樣本，還不是點擊作為正樣本，那正例就更少了。所以m6d不得不將u替換成s來建模，將相似廣告位（inventory）用同一個inventory id表示，來拼命減少特征空間，在少得可憐的數(shù)據(jù)下，犧牲bias來換取低variance從而抑制過擬合，提高模型泛化能力。
如果沒有那么高的privacy要求，是可以對所有compaign的數(shù)據(jù)一起來訓(xùn)練一個的統(tǒng)一模型的。事實上，我了解到國內(nèi)大多數(shù)公司都是這么做的。再考慮到國內(nèi)的廣告主對點擊也比較看重，所以更通常一點的建模方式是：對所有compaign建立一個CTR模型（預(yù)估點擊率=點擊/展現(xiàn)）p(click|u,i,a),這里的a指一個compaign，和一個CVR模型（轉(zhuǎn)化/點擊）p(conversion|u,i,a)。這樣訓(xùn)練數(shù)據(jù)就更豐富了，也可以直接對每個用戶來預(yù)估，不需要對整個segment來預(yù)估。當然，這樣的一個結(jié)果是在某個廣告主網(wǎng)站上的點擊和轉(zhuǎn)化數(shù)據(jù)，可能對另外一個廣告主的點擊和轉(zhuǎn)化預(yù)估起到正向的作用。在不明顯有偏向性的算法設(shè)計下，可能會使大多數(shù)廣告主的預(yù)估都有一些提升（尤其是那些數(shù)據(jù)很少的小廣告主）。
2. 內(nèi)部競價機制
m6d的算法在內(nèi)部競價時是選擇bid最高的compaign。這是一種明顯的貪心算法，在考慮到每個廣告主有預(yù)算限制的情況下，不一定是最優(yōu)的。舉個例子，廣告主A要的用戶是對喬丹感興趣的用戶，因為他是賣喬丹的運動鞋的，但是他們是小公司，出不起太高的價來打廣告；廣告主B是的要的用戶是對籃球感興趣的用戶。這個時候來了一個經(jīng)常上新浪體育喬丹個人頁面的用戶，廣告主A經(jīng)過bidding算法后出了封頂價3塊錢，廣告主B很有錢，基礎(chǔ)出價就是4塊錢，bidding算法調(diào)整后比如是4.5塊。那么廣告主B的廣告會在內(nèi)部勝出。當事實上對籃球感興趣的用戶很多，廣告主B完全可以在其他流量上買到足夠多的展現(xiàn)而達到當日預(yù)算限額，而對喬丹感興趣的用戶的展現(xiàn)可能1天就2,3個，廣告主A這次買不到，可能當日預(yù)算一點都花不出去。
這個優(yōu)化在系統(tǒng)進化早期可能效果不明顯，當平臺成熟了，量上去了，可能會有作用。?
3. 考慮外部競爭
m6d的出價算法是基于價值的出價算法，沒有考慮競爭對手出價。也就是說，我覺得這個展現(xiàn)值多少錢，我就出多少錢，不管其他人的出價是多少。這樣有可能會出現(xiàn)出價嚴重偏離市場價的情況，就好比在北京買房子，郊區(qū)一個老破房子，你可能覺得只值2000塊一平，但是市場上都已經(jīng)出到20000了，不調(diào)整出價根本就買不到房子了。
因此專門有一個技術(shù)叫Bid Landscape Forecasting, 用來預(yù)測其他競爭對手的出價情況，實際應(yīng)用中它要預(yù)測的是bid與能購買到流量的一個函數(shù)關(guān)系，也就是出多少錢能買到多少流量的這么一個曲線，從而根據(jù)自己的需求來調(diào)整自己的出價。詳細可以Google這篇文章《Bid Landscape Forecasting in Online Ad Exchange Marketplace》。
M6d的算法里有一部分是賬戶管理員對segment打一個base price，我相信這個base price應(yīng)該會考慮到市場競爭的情況。
4. 流量預(yù)測、預(yù)算控制
對于廣告主來說，關(guān)心的是兩個東西，一個是質(zhì)，一個是量。質(zhì)的意思是投放的廣告要投在那些可能對這個廣告感興趣的人身上，量的意思是，得找到并投放足夠多的這樣的廣告。寶潔公司對于那種每天只能覆蓋1,2個人的廣告compaign是不會感興趣的，即使這2個人的轉(zhuǎn)化率都是100%。
但是因為RTB是要實時決定你是否去競爭這個展現(xiàn)，DSP需要對后續(xù)可能出現(xiàn)的展現(xiàn)有一個預(yù)判。打個比方來說，假設(shè)你去相親，有多少女生會來你是不知道的，但是你總共有約會5個女朋友的機會。接下來每個女生依次和你見面，你要馬上決定是否和她約會。這個時候如果你對女生的整體質(zhì)量有一個估計，或者對總共有多少女生會來有一個估計，就會做出更明智的選擇。
這個其實也是Bid Landscape Forecasting的一部分，因為它是要預(yù)測bid與能購買到流量的一個函數(shù)關(guān)系。能購買的流量一方面和競爭有關(guān)，另外一部分和流量的質(zhì)量和數(shù)目有關(guān)系。
5. 點擊率、轉(zhuǎn)化率
m6d是直接對轉(zhuǎn)化建模的，而不是分為點擊率和點擊后的轉(zhuǎn)化率來建模的（有一些compaign,對廣告主頁面的點擊就被認為是轉(zhuǎn)化，對這些compaign兩種方式?jīng)]有區(qū)別）。點擊數(shù)據(jù)對于m6d來說就沒有作用了。如果有很多點擊數(shù)據(jù)，分開建模可能會有更好的效果，因為能把點擊數(shù)據(jù)利用上了。
參考文獻：
[1] Bid Optimizing and Inventory Scoring in Targeted Online Advertising
[2] Design Principles of Massive, Robust Prediction Systems
[3] Bid Landscape forecasting in Online Ad Exchange Marketplance
與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖總結(jié)
以上是生活随笔為你收集整理的DSP基础算法与模型研究的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
