網際網路廣告系統綜述六模型

聲明：

1）該博文是整理自網上很大牛和專家所無私奉獻的資料的。具體引用的資料請看參考文獻。具體的版本聲明也參考原文獻

2）本文僅供學術交流，非商用。是以每一部分具體的參考資料并沒有詳細對應，更有些部分本來就是直接從其他部落格複制過來的。如果某部分不小心侵犯了大家的利益，還望海涵，并聯系老衲删除或修改，直到相關人士滿意為止。

3）本人才疏學淺，整理總結的時候難免出錯，還望各位前輩不吝指正，謝謝。

4）閱讀本文需要網際網路廣告業的基礎（如果沒有也沒關系了，沒有就看看，當做跟同學們吹牛的本錢）。

5）此屬于第一版本，若有錯誤，還需繼續修正與增删。還望大家多多指點。請直接回帖，本人來想辦法處理。

經過幾個博文的啰啰嗦嗦，又是業務又是定向又是系統架構的，給各位的感覺都是在描述一些外圍的東西，真正核心的東西還沒說到。對于心急得如幹柴烈火的熱血青年來說，似乎一直在各種前戲，一直沒感受到提搶上陣的快感。

就算這麼急，這還是得說——在廣告算法領域，如果說ctr預估是包子餡的話，前面那些東西就是包子皮，直接吃包子餡，不見得是很正确的吃法。

下面就說說大家喜聞樂見的模型吧。

1.1準确估計ctr的意義

得從前面的算分排序那一節說起了。

對于一些大型媒體行業平台，當時就說了ctr的估算要求比較準确，這ctr估高了，會把出價不高同時使用者也不喜歡的廣告的分算得比較高，這樣的廣告就排在了前面，這樣廣告平台既收不到錢，也讨不到使用者喜歡；但ctr估低了，出價一般高但是使用者比較喜歡的廣告的分算得比較低，沒機會投出去，使用者就會總是看到不喜歡的廣告，對媒體來說，這個最終也會導緻使用者的流失，照樣賠了夫人又折兵。

對于廣告生态圈中的DSP來說，同樣DSP需要評估流量品質，如果發現一個流量的品質很高，就開高價去竟争這個流量；如果流量品質低，就開低價去竟争。如果評估得太高，出很高的價錢拿到了品質很低的流量，那就達不到廣告主的要求，會虧錢；如果評估得太低，一直拿不到流量，沒辦法賺錢。評估流量品質，說到底了是預估一個流量的ctr。

說到這份上，總該明白一個問題了吧——估準ctr非常重要。這個就是廣告算法工程師的工作的重中之重。

用另一個方式了解ctr，就是一個使用者點選某一個廣告的機率，點選的機率大，意味着越喜歡這個廣告，使用者越喜歡的廣告，廣告的品質自然可以認為是比較高的。

怎麼算是估準了呢？舉個例子，假如1萬個人對同一個廣告預估了1w個ctr的值，ctr的值當然有高有低了，如果這1w個人點選這個廣告總共100次的話，同樣也希望這1w個值的累加大緻是100，這樣才算估準了。但是，但是要注意的是，在這1w個值裡面，那100個點選的人估算的值要明顯比不點選的人要高，這就叫分開了，這才算是估得比較好的，如果人人都是大緻0.01的話，也可以算是比較好的預估（因為跟真實的很接近），但是就沒那麼具備區分能力了，在有些業務下面，就不容易發揮更多的用處。

要估準ctr的意義說完了，就開始談談模型了。

1.2為啥要模型

預估一個人對一個廣告的ctr，不可能是一個廣告算法工程師在那裡看着，來一個廣告請求就估計一下，給個決定，這樣人累死，估計得也亂七八糟，還效率不高，一天撐死了估計個幾十萬個請求，不得了了。

隻能用機器來估，但是機器是很笨的，隻能進行簡單的規則運算，這些規則還必須提前指定。如果人工指定這些規則，如30歲使用者點選匹克籃球的廣告機率是多少，男性的使用者點選匹克籃球的廣告的機率是多少，年齡和性别在總的ctr預估裡面占多少比重等等，需要大量的先驗知識，而且還不能根據實際情況變化，往往有問題。而且規則往往是有組合的。這個方法比用人估計好很多了，但還是很原始。

這時候數學家們就來勁了，直接看和簡單規則不行，複雜規則可以啊，而且複雜的規則可以用函數來拟合啊，而且上面的那些規則都可以用統計方法得到，用函數把他們組合起來也可以啊。

數學方法就這樣引進來了。

有兩個相關的方面，一個是統計方法；另一個就是拟合一個函數去組合規則，這個函數就是模型。

用數學的方式來表示對點選率的預估，做的工作可以用下面的圖來描述。

統計方法怎麼用呢？如可以統計過去投放過的記錄中，30歲的使用者點選匹克籃球的廣告的點選率是多少，這個資料直接就能根據投放日志統計出來；再統計男性的使用者點選匹克籃球的廣告的點選率是多少，這樣前面的兩個東西就得到了。

但是知道這兩個點選率，可以認為是兩個規則；但這還不夠，還需要知道這兩個點選率在評估這個人點選匹克籃球的廣告的機率中分别起什麼作用，這就是規則的組合。這兩個點選率加起來不行，相減也是不行的，權重累加可能是一種辦法，但是這樣行嗎？還有怎麼權重呢？用一個函數去組合這些規則就是很好的解決方案。為了描述的友善，我們用數學的方法來描述這兩個規則，把這兩個點選率（也就是規則）稱為特征，用一個向量x=(x1,x2)來統一表示，其中x1表示30歲的使用者對匹克籃球的廣告的點選率，x2男性的使用者對匹克籃球的廣告的點選率。

問題就轉變成了利用一個函數把向量x轉變成使用者對匹克廣告的ctr了。這個函數就是模型，用數學的方法來描述就是完成上面的圖中函數f的形式，這個函數f的形式确定了，就有了ctr=f(x)。

可以看到的是，利用模型是避免了人工規則擴充的困難，也使得每個ctr的計算變得可以用機器經過一些計算就可以完成，進而達到網際網路線上服務的标準。

在傳統領域也有些廣告主利用先驗知識做ctr預估的，就像是派傳單，也要先看看哪個路人更容易接才派出去的；又比如化妝品促銷活動，活動大使們肯定是找街上的一些女生來參加他們的活動，隻有女生才更可能樂意參加他們的活動，這些都是一些ctr預估活動在起着作用，但是這個是人用了自己強大的大腦和先驗知識來完成的，網際網路線上服務要求并發高，務必要估得多而且快。想象一下行人密集得像地鐵裡面一樣，而且都是百米沖刺的速度從派傳單小哥或者活動大使面前經過，他們還怎麼做生意？

是以模型加上人和廣告對的向量表示，才能完成網際網路的高并發與高速度的需要。

1.3用什麼模型

上面說到了那個函數f就是模型，由于它的工作很複雜，那麼形式應該是很複雜的，但是太複雜的模型不利于擴充，就用簡單的形式來。經過工業界長期的工作，認為下面的形式是比較有效的。

其中x是上面的那個x，w也是一個向量，表示的是x的每個特征的權重。這個w每取一個值，對相同的user和ad對就能得到一個預估的ctr，在f的形式已經确定的情況下w也可以稱為是模型，因為它能根據x的取值，也就是特征的取值來決定ctr，也就是，f的形式主要是由w來确定的。

那麼w這個向量的每個特征取值就變得很重要了，這個w的每個特征的值也可以由人工指定，但是上面說過了，需要大量的先驗知識，而且特征會特别多，如上面還有地域，職業，學校什麼的，可以搞到成千上萬的特征，人工指定沒辦法做到周全。是以這個權重的是要用一些方法來讓機器自己學習到的，這個過程稱為訓練，這個訓練過程還不能隻根據一個記錄user和ad對來訓練，要根據很多對來訓練。每個展示記錄就是一個對，根據曆史的一段時間内的展示記錄，能有很多的資料對可以進行訓練。

說到了訓練要用很多資料，但是這樣說不夠數學化，機器也做不了。隻有把訓練描述成一個數學問題的形式，機器才能接受。

很多年前最優化課程的老師說過，所有的問題都可以轉化成一個最優化問題，當時聽不懂也不知道為啥，現在才明白，計算機時代都隻能這麼來的，問題就是怎麼建構那個最優化問題，就是幾乎所有的算法工程師的工作，各種大牛們發表的paper都可以總結成在建構什麼樣的問題和怎麼解這個問題。

現在有待解決的事情就是把權重向量w的每個特征的計算出來，擁有的條件是一大堆的x和這個x對應的使用者的回報：點選或者不點選。

1.3模型求解

上面描述了函數f的形式，以及權重向量w的意義，模型求解的意思就是把權重向量w的每個特征的計算出來，能依賴東西隻有一大堆的x和這個x對應的使用者的回報。

數學家們也對這樣的問題有了很好的辦法。且看怎麼建構一個最優化問題。

數學家認為總體的曆史展示與點選資料符合一個伯努利分布，訓練過程稱為是拟合這個分布的過程。一次廣告的展示是否被點選（每次展示被點選的機率可能不一樣）是一個伯努利試驗，使用者點選這個廣告表示伯努利試驗成功，否則表示伯努利試驗失敗；對多個使用者展示多個廣告的過程是一個伯努利過程，每次伯努利試驗成功的機率就是上面的f(user,ad)的值。為了友善描述，改變一下f的寫法，用下面的方式表示

其中y=1表示這個展示被點選了，y=0表示這個展示沒有被點選。

到這個時候，就要出動極大似然估計了。極大似然估計的意思是已經出現的情況，發生的機率是最大的。怎麼了解呢？三個人去打靶，打中的機率分别是p1、p2、p3。用二進制的方式表示是否打中，如010表示中間那個人打中，那麼可能會發生8種情況：000,001,010,011,100,101,110,111。這8種情況發生的機率分别是(1-p1)*(1-p2)*(1-p3),(1-p1)*(1-p2)*(p3), (1-p1)*(p2)*(1-p3), (1-p1)*(p2)*(p3), (p1)*(1-p2)*(1-p3), (p1)*(1-p2)*(p3),(p1)*(p2)*(1-p3), (p1)*(p2)*(p3)。假如這8個機率中p1*(1-p2)*(1-p3)最大，讓人去預估打靶的結果，各位都應該認為是100這種情況，因為最符合常識的。

極大似然就是把這種情況反過來用了，意思是：打靶的結果是100這樣的情況，但是p1、p2、p3還在估計中，那麼無論p1、p2、p3估計出來什麼值，都要保證p1*(1-p2)*(1-p3)最大。

那麼在上面這種情況下，很自然地用極大似然建構最優化問題了。用似然函數表示上面的那個伯努利試驗過程，得到整個伯努利試驗的似然函數（也就是事情發生的聯合機率）

下面的那個式子是對數似然，是為了友善計算加上的。

回到打靶的那個說法，要保證已經發生的事件那個機率最大，在這裡就變成讓似然函數取得最大值了，這樣最優化問題的優化目标就有了，就是求似然函數的最大值，剛好每個x對應的h(x)都帶着w，那麼就可以把w當成要求解的變量。

就這樣，優化目标有了，要求解的變量有了，整個最優化問題就建立了。

有人可能會注意到有可能同一個x（特征完全相同）的情況下可能會出現兩個不同的點選結果（一次點選，一次不點選），這個情況就類似抛硬币一樣，假如這個硬币正面向上的機率是0.6，抛出去，依然會有若幹次會反面朝上。

這個會不會影響模型的建構呢？這時候就該統計分布的知識出馬了，注意極大似然的目标依然是進行分布的拟合，算的依然是機率，一個事件的發生是按照機率來判斷的，極大似然估計計算的依據其實是機率，而不是某一次伯努利試驗是否成功，是以對于模型的建構來說是沒有問題的。哪怕這個問題推到極緻，所有x都一樣，那麼得到的結果就是h(x)剛好接近總體點選率，這依然是一個好的模型，隻是，可能用其他方法也能得到同樣的結果罷了。

拟合分布跟計算一個分類器（判别模型的決策面）不一樣，對于一些建構分類決策面的模型來說，如果同一個向量同時落在決策面的兩邊，有可能會讓模型的訓練變得有問題。這個問題等具體想清楚了，再來解釋。

剩下的就是求解的方法了，這個就是最優化的知識了，具體可以看其他博文。

這整個問題就是logisticregression的問題建構和求解過程。有關logistic regression，很多大神都刷了無數博文了，就不多獻醜了。

1.3.1正則化

正則化是一個機器學習通用的技術，目的是讓w的每一個特征都不能太大，同時保證整個w所有特征都的絕對值都不特别大，總的來說就是避免産生特别不好的模型。

加完L2正則的優化目标如下

加完L1正則的優化目标如下

其中L2和L1是兩種不同的正則化技術，差別具體可以看其他博文。

1.3.2求解工具

這個是多出來的東西，因為解上面的最優化問題可以有通用的解法SGD和BFGS。

但是前面的博文說過，找一個工具是很重要的，我們用過的比較好的工具就是vw。

Vw這個工具有幾個優點如下

1、Vw這個工具可以前期先用SGD跑出一個接近最優解的解，再用BFGS進行微調，得到盡可能的最優解。

2、vw可以直接在Hadoop叢集上進行并行訓練，避免了很多資料轉移的工作。

3、vw非常快，幾億的訓練樣本一般一個小時以内就完成，網絡開銷也不大，因為傳輸的東西很少。

1.3.3線上學習

線上學習就是把模型線上上實時更新，投放了一個廣告，就馬上得到一個樣本，利用這個樣本去更新模型（SGD的方式）。

這樣的話，模型是線上上訓練的，是以也叫線上學習。

1.4模型架構

從模型視角看，系統架構是下面的樣子的。

1.5優點

除了logisticregression，還有很多其他的模型可以選擇的，如random forest、gbdt。這些模型應用起來可能會有一定的效果提升，但是相比logistic regression來說，還是沒有具備那麼高的擴充性。

下面列些優點看看。

和邏輯回歸算法本身的很多特點有關的，例如：

1、變量範圍是[-∞ ,+∞]；同時和其他“廣義線性回歸”相比，值域是[0,1]，是以形式上類似一個機率函數，适合分類問題；

2、可擴充性好，适合海量的特征；訓練工具多樣、可選

3、online learning，能夠進行增量學習；

4、線性模型，解釋性強。

這些優點都讓logisticregression在做ctr預估的時候特别有優勢，尤其是可擴充性，可以簡單地增加特征，不需要太多的工作。

1.6評估

評估模型效果的方法有很多，如：

1. AUC，從排序的角度評估模型預估效果；

2. MAE（Mean Absolute Error）/MSE（Mean Squared Error），從準确率的角度評估模型預估效果；

3．OE比，就是預估的平均ctr與真實的ctr的比值，越接近1越準

緻謝

多位網際網路部落客如@Rickjin等。

多位同僚的指點。

參考文獻

[1] Computational Advertising:The LinkedIn Way. Deepak Agarwal, LinkedIn Corporation CIKM

[2] Ad ClickPrediction: a Viewfrom the Trenches. H. Brendan McMahan, Gary Holt et al，Google的論文

[3] http://www.flickering.cn/uncategorized/2014/10/%E8%BD%AC%E5%8C%96%E7%8E%87%E9%A2%84%E4%BC%B0-2%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92%E6%8A%80%E6%9C%AF/騰訊的廣點通的技術部落格《邏輯回歸技術》

文章來源：http://blog.csdn.net/mytestmy/article/details/40932241