ML學習分享系列(2)_計算廣告小窺[中]

原作：面包包包包包包

修改：寒小陽 && 龍心塵

時間：2016年2月

出處：http://blog.csdn.net/Breada/article/details/50697030

http://blog.csdn.net/han_xiaoyang/article/details/50697074

聲明：版權所有，轉載請聯系作者并注明出處

1. 引言

提筆寫這篇部落格，我的内心是惶恐的。原因很簡單，作為一個資曆尚淺的研究所學生，是沒有資格對計算廣告這樣一個偉大的行業、領域和學科來評頭論足的。之是以這麼做，一是總結自己已掌握的知識，二是降低同學們的學習成本。本人能力有限，更缺乏實踐經驗，文章内容多為書籍和論文的讀後感，若有不當或者錯誤之處，還望各位同學指出，我定悉心求教。在此，向編寫《計算廣告》的劉鵬和王超兩位老師緻謝，向各位paper作者緻謝。

[關于ML學分計劃]

• 由寒小陽和龍心塵發起，一個互幫互助的機器學習知識共享平台。
• 我們是一群對機器學習感興趣的小夥伴，對于神奇的機器學習經常有“一探究竟”的沖動，卻因為孤身一人學習的寂寞、亦或繁忙考試工作之餘的小小拖延症，而沒有持續這份對知識的渴求和熱情。
• 由于深感類似情況的小夥伴之多，我們希望建立一個“ML學分計劃”——機器學習的學習和分享計劃——來幫助我們一起更高效地學習、更集中地整理分享我們的知識和經驗。因為我們也深信”證明自己真的透徹了解一個知識，最好的方法，是給一個不熟悉這個内容的人，講清楚這個内容“。

[關于原作@面包包包包包包]

• 海澱區明光村計算機職業技術學院，研二學生。
• 關注計算廣告點選率預估和競價算法，關注機器學習和深度學習，初學者。
• 機器學習QQ群：初學者373038809，行業同學和研究者472059892。

(上)(中)(下)全文目錄

1. 引言

2. 廣告=>網際網路廣告

   ：“您好，了解一下”

3. 網際網路廣告=>計算廣告

   ：指哪兒打哪兒！

4. 計算廣告四君子

   ：誰在弄潮？

5. 計算廣告關鍵技術

   ：這孫子怎麼什麼都知道？

6. 廣告系統架構

   ：要啥自行車，這裡有寶馬。

7. 手把手系列之教你搭建一個最小廣告系統

   ：mieSys

5. 計算廣告關鍵技術：這孫子怎麼什麼都知道？

一句話解釋關鍵技術：沒聲音，再好的戲也出不來。

廣告作為一項商業活動，是需要資本來滋養的。作為整個産業鍊的金主，隻有廣告主花錢做廣告，使資金流動起來，整個廣告行業才能正常運轉。所謂關鍵技術，就是那些能讓廣告主覺得“這錢花的值”，讓媒體網站覺得“這錢掙的快”的技術。具體都有哪些呢？下面我們一一來表。

5.1 合約廣告關鍵技術：閱聽人定向

計算廣告發展到合約廣告階段，媒體網站依靠閱聽人定向技術給使用者打标簽，在實作了媒體網站廣告位的時分複用的同時，還提高了廣告主的投入産出比，極大的激發了廣告主在網際網路上做廣告的積極性。是以，閱聽人定向是合約廣告中的關鍵技術。

我們知道，隻要描述物體的次元足夠高，那麼世間萬物都是獨一無二的。在廣告系統中，标簽就是描述使用者的次元。媒體網站為了精準的刻畫使用者，标簽的種類和數量自然也不會少。為了更加直覺地了解閱聽人定向技術，我們從使用者、上下文和廣告三個方面讨論打标簽的思路和一般方法。

• 使用者标簽：主要用性别、年齡、收入、地理位置、教育程度和使用者行為等标簽來刻畫使用者，進而回答 “你是誰” 的問題。
• 上下文标簽：主要用網頁的地域、主題和頻道等标簽來刻畫使用者目前所處的媒體網站環境，進而回答“ 你在看啥 ”的問題。
• 廣告标簽：主要用廣告主、廣告創意、廣告計劃和廣告關鍵詞等标簽來刻畫廣告的相關内容，将廣告内容與使用者和上下文進行比對後，進而回答“ 你該看啥 ”的問題。

5.1.1 使用者标簽關鍵技術

對一個使用者來說，性别是不會輕易變的，但是使用者的喜好和興趣卻是時刻都在變化的。根據标簽屬性的變化頻率，我們這裡私自将使用者标簽分為靜态和動态兩類。靜态标簽主要指年齡、性别、地理位置、收入和教育程度等這種不變或者很長時間之内都不變的标簽，行話叫“人口屬性”；動态标簽則是指使用者的浏覽、搜尋和點選等能夠反映使用者短時喜好和興趣的行為标簽，行話叫“行為定向(BT:Behaviroal Targeting)”。下面我們針對靜态和動态這兩類标簽分别讨論。

一句話解釋靜态标簽和動态标簽的關系：價格圍繞價值上下波動。

• 靜态标簽(人口屬性)

在《計算廣告小窺[上]》中，我們曾簡要地提到過一種閱聽人定向的方法：

通過對點選日志的分析，媒體網站發現點選過女性護膚品的使用者又點選過媒體網站上其他女性品牌。在“女性使用者對女性品牌可能更感興趣”的合理假設下，判斷這些使用者的性别為女，男性使用者同理。

現在我們可以更加清楚的認識到，上述媒體網站所打的标簽是靜态标簽中的“性别”，使用的是基于規則的方法，即：

滿足了某種條件，就是某種人

。這種基于規則的方法簡單并且易于實作，但也存在着緻命的缺點：基于規則的方法對資料非常敏感，若資料本身存在噪音(如誤點選)，那麼标簽的品質也将大打折扣。這可如何是好？簡單的不行，那就來點複雜的嘛——用機器學習模型來實作(自帶音效：當當當當，當當~~)。

假設我們已經知道一部分使用者的真實性别，那麼就可以用機器學習中有監督的二分類模型來預測使用者性别。首先，我們需要對原始資料進行清洗，合理地處理缺失值和奇異值，并劃分訓練集、交叉驗證集和測試集；其次，要在業務的指導下做特征工程，利用統計或模型的方法構造特征，并進行特征選擇和特征組合；然後，我們要選擇合适的模型(如SVM等)，設定合适的評價标準并進行模型的訓練；最後，通過模型調參和模型融合，獲得性别預測模型。

• 動态标簽(行為定向)

一句話解釋行為定向：唐伯虎喜歡如花多一些，還是鳳姐多一些？

“如果一定要比較一下，那唐伯虎是喜歡如花多一些，還是鳳姐多一些？”這個看似荒謬的問題，正是行為定向要解決的。如果唐伯虎是異性戀，那他應該是喜歡鳳姐多一些的，否則是如花。這也就告訴我們，在行為定向中，判斷的标準至關重要。下面我們借助一個例子來分析該使用者的動态标簽究竟是什麼。

有資料顯示，某使用者在過去的三個月時間中，點選廣告的标簽和次數如下表所示：

标準	單反愛好者	跑鞋愛好者	飲料愛好者	護膚品愛好者	…
點選	25	4	2	1	…

對上述資料進行分析，我們可以輕而易舉的得到答案：該使用者的标簽應該是“單反愛好者”，因為他的點選行為集中在這個标簽上。但是，這個答案是我們以使用者的點選行為作為标準得來的，如果以使用者的浏覽和搜尋行為做标準，答案也是“單反愛好者”嗎？我們再來看一下相關資料。

标準	單反愛好者	跑鞋愛好者	飲料愛好者	護膚品愛好者	…
浏覽	15	2	…

标準	單反愛好者	跑鞋愛好者	飲料愛好者	護膚品愛好者	…
搜尋	7	16	5	3	…

是不是出問題了？以點選和浏覽為标準，該使用者标簽應該是“單反愛好者”，但是以搜尋為标準，标簽應該是“跑鞋愛好者”。如果該使用者的标簽隻能有一個，那該選哪一個呢？為了解決這個問題，我們從數學角度分析一下好了。嘿嘿，數學噢，前方高能預警！我會盡量讓這個過程變得簡單，大家跟上我的思路哈。

Step1. 泊松分布

一句話解釋泊松分布:猜猜我在哪兒~~~

我們先來介紹下泊松分布。啊啊啊啊！一上來就是數學，我不聽我不聽我不聽，泊松分布是什麼鬼？咳咳，那，那就先不丢公式了，咱們看圖解決問題好了，下面是泊松分布繪出的曲線圖，實際工程中要解決的問題就是找到圖中的最高點，如下圖：

這個肉眼找最高點的過程不要太簡單了！！！我們可以看到：

圖中最高點的縱坐标大約為0.36，而對應的橫坐标是1

。OK，你就算會用泊松分布了哦！那個，感興趣的同學們，可以一起來看看對應上圖的泊松分布的公式。

pt(h)=λhte−λth!

公式相對于圖，是有那麼點點複雜啦。不過，我們隻需知道

λt 影響泊松分布的形狀，一個 λt 對應一個泊松分布就可以了

。這個場景下要做的事情就是找到對應泊松分布圖像的最高點。

Step2. 一個結論

一句話解釋這個結論：一個蘿蔔一個坑。

我們先說一個結論：

在一個标準下，所有使用者占有的标簽，在所有标簽上的機率分布是滿足泊松分布的。

對于這個結論，有興趣的同學可以參見Stanford 《Introduction to Computational Advertising》講義Page-81，我們在這裡就直接拿來用了。而所謂“标準”，就對應泊松分布公式中的 λt ，在我們這裡的場景下與使用者行為有關。

這張圖的橫軸代表使用者擁有的标簽數目，縱軸代表興趣标簽數目為x的使用者數目，比方說有1個标簽的使用者有500人，有3個标簽的人有5000人。從這張圖中我們可以很清楚的看到，使用者在所有标簽上的分布是滿足泊松分布的。但是這裡有一個問題，大量使用者所呈現出的這種泊松分布，和單獨使用者的興趣标簽之間有關聯嗎？我們說，關聯不大，因為一個是随機過程，一個是随機事件，想要得到每個使用者的興趣标簽，其實是一個複雜的任務。下面我們從統計和投票的角度入手，來看一種使用者打标簽的方法。

Step3. 最佳标準

一句話解釋最佳标準：盲人摸象

“盲人摸象”比喻以偏概全，現在我們想要知道大象全貌，把每個人摸到的拼起來便是了。在廣告系統中，搜尋、點選和浏覽三種行為資料都隻能從一個側面反映使用者的行為，要想完整的刻畫一個使用者，我們需要将這三種行為融合起來之後找到一個最佳标準。提到融合，較為常用的方法是投票，我們可以寫出下列公式：

λt=∑i=1nωi∗ti ，where t∈(搜尋，點選，浏覽)

簡單解釋一下： ti 是标準，分别代表了搜尋、點選和浏覽行為； ωi 是标準的權重，即該标準對于完整描述使用者行為的貢獻。我們用機器學習中的廣義線性模型對該問題進行模組化，模型訓練完成後可得各标準的權重 ωi ，進而預測出最佳标準 λt 。

Step4. 最終求解

通過廣義線性模型，我們找到了最佳标準 λt 。現在，我們根據該 λt 畫出相應泊松分布，如下圖：

回顧Step2中的結論：

在一個标準下，使用者在所有标簽上的機率分布是滿足泊松分布的。

現在最佳标準下的泊松分布我們已經畫了出來，該使用者在所有标簽中的機率分布也應該符合這個分布的。還是老步驟，我們找最高點所對應的标簽，即标簽5，是以該使用者的動态标簽是标簽5，問題完美解決。

在學習了泊松分布和機器學習之後，媒體網站終于完成了使用者标簽的工作，看着那圓圓的餅圖，流下了激動了淚水，哽咽着說“嗯..終于..終于可以賣錢了..”沒錯，流量可以變現了，網際網路廣告一腳踏進合約廣告時代。但是僅僅知道“你是誰”，粒度還是太粗，賣不了好價錢。“要是知道你正在幹嘛就好了”媒體網站嘴裡嘟囔着，突然腦海中靈光一閃，大叫一聲：(圖檔來自網絡)

5.1.2 上下文标簽關鍵技術

一句話解釋上下文标簽的做法：吃的是URL，擠的是标簽。

“我當然知道他在幹嘛！我有日志啊！我有他正在通路頁面的URL！啊哈哈哈哈哈！”有了使用者标簽的經驗，媒體網站處理起上下文标簽來就顯得輕車熟路了，總共分兩步：第一，根據使用者目前頁面的URL，抓取使用者目前浏覽的頁面内容；第二，提取頁面内容的關鍵詞，作為目前頁面的标簽。

通過URL獲得頁面内容是一個典型的爬蟲應用，與搜尋引擎的爬蟲不同的是，廣告系統的爬蟲隻抓取使用者請求的頁面，而非全網頁面。鑒于上述原因，廣告系統使用“半線上抓取系統”，該系統有三個特點。第一，僅對使用者發起請求的頁面進行抓取，節省了時間和成本；第二，将

{URL:标簽}

存儲下來，當其他使用者發起相同頁面請求時，直接傳回标簽結果，避免重複抓取。第三，考慮到某些頻道頁面内容可能會更新(例如”舊浪體育”)，還可設定合适時間，周期地更新已存頁面的标簽。

在抓取到頁面之後，如何提取标簽也有幾種常見方法。最簡單的是利用規則，在URL層面上人為做映射，例如

sports.oldna.com

對應的頁面标簽就是”舊浪體育”。若使用者是通過搜尋發起的頁面通路，還可以根據搜尋詞作為頁面标簽。當然，在廣告系統使用範圍較廣的方法還是機器學習中的

主題模型

，得到頁面内容在幾個主題上的分布，進而判斷頁面标簽。例如，

sports.oldna.com

頁面内容在”體育”、”财經”和”遊戲”三個主題上的機率分布分别為：

體育	财經	遊戲
0.85	0.10	0.05

我們可以很容易的看出

sports.oldna.com

的标簽是”體育”。這裡值得注意的是，如果想要加工出”體育”、”财經”和”遊戲”這種可解釋的标簽，通常需要采用有監督的主題模型。

能用的資料都用了，能打的标簽也都打了，知道了“你是誰”和“你在看什麼”之後，媒體網站這才感覺踏實了些。下面的工作就簡單了許多，把标簽賣給廣告主就可以了，也算是一勞永逸，深藏功與名。至于使用者會看到什麼，那是廣告主的地界，就不管媒體網站什麼事兒了。

5.1.3 廣告标簽關鍵技術

普通的廣告标簽就是廣告本身的屬性，如所屬廣告主、廣告大小、廣告類别和目标人群等，當廣告和使用者兩兩比對時，該廣告就會展示給使用者。但是，這裡我們想說的廣告标簽是在程式化交易中的“個性化标簽”。在《計算廣告小窺[上]》中我們提到：“程式化交易是廣告主為實作個性化營銷舉行的海天盛筵。”品嘗過個性化營銷的甜頭之後，廣告主就想：“既然這些人是回頭客，那各方面表現和這些回頭客很像的人，有沒有可能也是我的回頭客呢？世界那麼大，我得去找找這種人。”

• look-alike

一句話解釋look-alike：比葫蘆畫瓢。

這個技術的名字還挺洋氣呢，英文的，“看起來像”？說白了就是比葫蘆畫瓢，找到那些看起來像回頭客的新使用者，行話叫“新客推薦”。這裡一定要注意了，千萬不能翻譯成“看起來像”，那樣顯得逼格不夠，就叫英文的，look-alike~

關于look-alike的具體實作，市面上沒有統一的做法，畢竟我們正在經曆。這樣一來我的心也放下了，因為即便我下面都是胡扯也不一定是錯的。

look-alike的核心是按着回頭客的樣子去找新使用者。那簡單呀，

看看回頭客的标簽是什麼樣子，對着去找相同的不就行了？

沒錯，這算一種方法，并且是一種基于規則的方法。但是直覺告訴我們這樣做粒度太粗，沒有充分考慮到廣告主因素，同時經驗也告訴我們，基于規則的不如基于模型的效果好，是以我們還可以得出一個基于模型的做法：

将某使用者是否是潛在使用者模組化成一個機器學習中的二分類問題

，利用回頭客資料訓練模型，并在新使用者上做預測，是就是1不是就是0，也挺好了解的。

閱聽人定向關鍵技術我們就介紹到這裡了，現在我們來回顧一下。為了更加精準的刻畫使用者，我們從使用者标簽、上下文标簽和廣告标簽三個方面來介紹閱聽人定向。雖說角度不同，但總的說來，不外乎兩種方法：基于規則和基于模型。在閱聽人定向技術的支援下，網際網路廣告進入合約廣告時代。在經見了線上配置設定的大坑之後，媒體網站發現合約不可保，便使用競價方式售賣流量，指定廣告主。那在競價廣告中，又有什麼關鍵技術呢？請看下一小節：競價廣告關鍵技術：點選率預估。

5.2 競價廣告關鍵技術：點選率預估

郭德碗：聊(bi)了(bi)了這麼久，想必衣食父母也都累了。

于 兼：是有點兒。

郭德碗：能堅持看到這兒的人不多。

于 兼：東西太難。

郭德碗：那就歇了吧，《計算廣告小窺》到此結束！

于 兼：給我回來！像話嘛這個！

郭德碗：還想怎麼着啊？

于 兼：說好的點選率預估呢？大夥都沖這個來的。

郭德碗：真有沖這個來的？

(有！)

郭德碗：怎麼不提錢跟我說呢？

(籲~)

郭德碗：好了，玩笑歸玩笑，驢鞭歸于兼，下面呀，我..

于 兼：您等會兒，那玩意兒歸我幹嘛呀？

郭德碗：嘿嘿嘿。

(籲~)

郭德碗：你們都懂？

(籲~)

郭德碗：仁者見仁，污者見污喲。

(下去吧~)

我知道很多同學是沖着點選率預估來的，是以不能讓你們白來不是，免費送您一小段兒，别跟我提錢哈哈。等最後聊到最小廣告系統，幫我貢獻幾次點選就行，我也好收集一些高品質資料，訓練模型自己玩兒。言歸正傳，下面我們将從“是什麼”、“為什麼”和“怎樣做”三方面來介紹點選率預估。

5.2.1 點選率預估是什麼

• 點選率

一句話解釋點選率：0.1%

既然聊到點選率預估，那我們先來看看什麼叫點選率。點選率這個概念我們是第一次提起，但其實我們早就知道它了。我們在《計算廣告小窺[上]》曾經提到：

“自從廣告上了網際網路，廣告的面貌就煥然一新。造成行業巨變的原因，是因為網際網路廣告的效果可以被衡量。”

如果接着往下說，以什麼标準來衡量呢？沒錯，最常用的衡量标準就是點選率。點選率(CTR:Click-Through Rate)是指的是媒體網站上某個廣告的

點選量/展示量

。之是以使用點選率來衡量廣告效果是有原因的，先來看分母：分母是某廣告的總展示量。在《計算廣告小窺[上]》中我們曰過，廣告展示機會是廣告主通過競價獲得的，展示機會越多，意味着廣告主的出價越高，是以總展示量可以用來表征廣告主的廣告投入。再來看分子：分子是總點選量，而點選行為代表了使用者的注意力，說明使用者渴望進一步了解廣告内容。

是以點選率越高，意味着廣告主在相同投入的情況下，收獲了更多的使用者注意力

，完美诠釋了廣告主做廣告的初衷，是以點選率是廣告主和媒體網站常用來衡量廣告效果的标準。我聽過一個數字，廣告平均點選率為千分之一，也就是每展示1000次廣告才會收獲1次點選，是以點選率預估中資料都是很稀疏的。

• 點選率預估

一句話解釋點選率預估：80%

了解了點選率，我們再來看看什麼叫點選率預估。從字面上了解，點選率預估是預測媒體網站上某個廣告的

點選量/展示量

，然而這樣了解并不是很準确，我先給出我的了解：

點選率預估，是指預測特定使用者點選特定廣告的機率

，例如小明點選某信二手車廣告的機率是80%。

為什麼對媒體網站廣告點選率(0.1%)的預測，會變成了對使用者點選某廣告機率(80%)的預測呢，接着往下看啦。

5.2.2 為什麼要做點選率預估

一句話解釋為什麼要做點選率預估：錢。

在競價廣告階段，廣告主與媒體網站之間以按點選付費(CPC)的方式結算，是以我們可以用下列公式來表征媒體網站在某次廣告活動中的收入：

媒體網站收入 = (點選率 * 展示量) * 單次點選價格 = 點選量 * 單次點選價格

我們知道，

展示量

和

單次點選價格

這兩部分都是廣告主參與競價後才能決定的，與媒體網站無關，是以媒體網站的收入就與

點選率

直接挂鈎。在收益最大化的驅使下，媒體網站有提高點選率的動力。點選率的定義是

點選量/展示量

，

展示量

又是廣告主通過競價決定的，是以媒體網站隻能想方設法提高

點選量

。

對于媒體網站而言，他所擁有的資源就是頁面上幾個固定的廣告位和海量的使用者。為了提高點選量，一種簡單明了的想法就是讓展示的廣告盡可能多的被點選，即“指哪兒打哪兒”。為了實作這個理想，亟需解決兩個問題：首先需要知道使用者感興趣的廣告有哪些，其次需要讓使用者盡可能多的點選這些廣告。

第一個問題叫做“廣告檢索”，是指媒體網站根據使用者的定向标簽或其他方式檢索出符合使用者口味的廣告候選集合。這部分内容是搜尋引擎的核心，在這裡我們就不展開讨論了。我們來看第二個問題，假設我們已經得到了一個符合使用者口味的廣告候選集合，如何能讓使用者更多的點選呢？很簡單，

把使用者最可能點選的廣告放在最顯眼的地方

，為了定量描述

使用者最可能點選的廣告

，這便引出了點選率預估的問題。是以我們說，點選率預估并不是來預估媒體網站上

點選量/展示量

，而是預測某個特定使用者點選某個特定廣告的機率。OK，那預估完幹什麼呢？剛才不是說了嘛，把最可能點選的廣告放在最顯眼的地方呀！

• 最顯眼的地方

一句話解釋最顯眼的地方：你也是柳岩的球迷？

為了較為直覺地描述使用者的注意力分布，我找了一張LinkdIn的使用者注意力熱力分布圖。(圖檔來自網絡)

圖中，顔色越紅代表使用者注意力越集中。可以看到，使用者最關注的是頁面的上半部分，其次是右半部分，最後是下半部分。這種注意力分布基本我們日常的浏覽習慣，即如果能在頁面靠前位置找到我們所需的資訊，一般就不會再關注頁面其他地方。了解了注意力分布，我們來看一下某度搜尋頁面上的廣告位分布。

某度廣告位主要分布在北區、東區和南區三部分，以LinkedIn頁面中的使用者注意力分布來推測，使用者在某度頁面上注意力分布從高到底分别是北區、東區和南區。假設某度共有10個廣告位，那麼将使用者最可能點選的10個廣告按照點選機率由高到低順序分别排在北區、東區和南區。然後還幹嘛？沒有了，萬事俱備，隻欠點選。

不知道您聽明白了沒，我來幫您捋捋。為了提高媒體網站的收益，我們結合業務場景不斷簡化問題，從提高媒體網站點選率入手，到提高總點選量，再到獲得廣告候選集合，預測出了使用者點選廣告的機率。僅僅預測點選機率媒體網站還賺不着錢，是以媒體網站根據點選機率在頁面廣告位上對廣告進行排序。是以為什麼要做點選率預估呢？都是為了錢！都是為了錢！都是為了錢！

5.2.3 點選率預估怎麼做

一句話解釋點選率預估怎麼做：使盡渾身解數，隻為更懂你。

自計算廣告學誕生以來，點選率預估就是一個在學術界和工業界被廣泛研究和實踐的課題。剝去種種具體場景，點選率預估的本質其實還是一個機器學習中的二分類問題。一般來講，媒體網站點選資料的數學分布是非線性的。為了拟合這種非線性關系，學術界側重于模型的研究，工業界側重于特征的構造，雙方優勢互補，已取得了相當豐碩的成果。下面我們将先介紹展示廣告和搜尋廣告這兩種網際網路廣告的主要形式，然後闡述二者在點選率預估問題上的不同之處，最後介紹一些點選率預估的方法。

• 展示廣告

展示廣告(Display Advertising)是一種以“圖檔+文字”的方式進行廣告宣傳的網際網路廣告形式。從廣告觸發方式來看，展示廣告是媒體網站根據使用者

曆史行為

所做的推薦，對使用者而言廣告是被動接收的，如下圖。

• 搜尋廣告

搜尋廣告(Sponsored Search)是一種以“标題+超連結”的方式進行廣告宣傳的網際網路廣告形式。從廣告觸發方式來看，搜尋廣告是媒體網站針對使用者

目前檢索

所做的廣告比對，廣告是使用者主動發起的，如下圖。

根據上面我們對展示和搜尋廣告的描述，我們可以對兩種廣告形式的點選率預估有一個淺顯并直覺的認識：展示廣告的點選率預估可以看作是一個推薦問題，根據曆史記錄推測使用者對哪些廣告更感興趣；搜尋廣告的點選率預估可以看作是一個檢索問題，根據使用者目前的查詢來做廣告比對。前者推薦後者檢索，問題性質的不同也決定了點選率預估所采用方式的不同。

• 點選率預估方法

有關展示廣告和搜尋廣告的實作算法和應用細節都是各家網際網路公司的商業機密，由于場景的不同，各家對點選率的預估也是八仙過海各顯神通。作為一個沒有實戰經驗的小屁孩兒，想要較為流暢地闡述這個話題，還是力不從心，畢竟眼界太窄太年輕。為了保證文章結構的完整，這部分還必須要寫，那麼我就抛開業務場景，僅從機器學習角度來和大家聊一聊我所知道的内容。寫的不好，還請各路大神多多指教，如有不當指出，請嚴厲指出，我定感激不盡！

上面我們提到過，從使用者浏覽網頁到廣告獲得展示，要經過三個階段：使用者定向、廣告檢索和廣告排序。使用者定向和廣告檢索就不多說了，最終在廣告庫中可以找到符合你口味的廣告，即“萬裡挑十”。在廣告排序階段，需要将這十個廣告位放置在頁面上，通常做法有兩種，一個是基于規則，一個是基于機器學習。我們這裡從機器學習的角度入手，但是各位千萬不要忽視了規則的能力。聊到機器學習，主要就是兩方面，特征和模型。下面我就根據我所了解的内容，重點介紹一下線性模型+海量特征的方法，然後簡單介紹一下點選率預估的發展。

• <1>線性模型 + 海量特征

用于點選率預估的資料主要是日志資料，一般會有點選行為(點選為1，沒點為0)、廣告資訊(廣告位、廣告主id、廣告标簽和廣告描述等)、使用者資訊(使用者id和使用者标簽等)、上下文資訊和時間戳等。有了這些原始資料之後，需要對資料進行清洗，然後利用統計或模型的方法構造特征，進而做特征選擇和特征組合，最終特征的數量級大約在10億-100億維。完成了特征工作之後，在模型方面，較為經典的點選率預估模型是線性模型Logistic Regression，由于LR在通過sigmoid之前是一個[0,1]之間的浮點數，利用LR的特點，我們可以将這個浮點數作為使用者點選該廣告的機率，把廣告按照這個機率從高到低放置在相應廣告位上，就完成了廣告排序。

為什麼要造出次元這麼高的特征向量呢？我的了解是這樣的。對于點選資料來說，點選行為與其他特征之間的關系是非線性的，為了拟合這種非線性關系，我們依然可以從特征和模型兩方面入手。通常來說，非線性模型的效果要更好一些，但是效率太低，不适合工業界的現實場景，是以快速簡單的線性模型就成為了模型的首選。那線性模型如何拟合非線性關系呢？這就需要在特征層面做文章，利用特征工程的方法來構造出高階特征，同樣可以實作非線性。這個思路了解起來還是不難的，如下面兩式對比：

特征工程前：y1=w1x1+w3x2+1

特征工程後：y2=w1x21+w2x1+w3x2+w4x1x2+1

• <2>點選率預估的發展

為了構造出次元如此巨大的特征向量，特征工程幾乎占據了70%的項目時間，并且主要是靠努力的程式員人工來實作的。那有沒有自動選擇特征的方式呢？ADKDD’14有一篇Facebook的paper《Practical Lessons from Predicting Clicks on Ads at Facebook》提出了一種使用GBDT自動選擇特征的方法，用每棵樹上的葉子節點來表達特征，比如

{1:2, 2:3}

指的是第一棵樹上第2個節點和第2棵樹上第五個節點，根據每棵樹的節點個數用one-hot表示即可。多說一句，GBDT選特征的方法已經經過實踐驗證，在Kaggle-Criteo點選率預估大賽中，冠軍的解決方案便是GBDT+FFM的方法獲得的。

說到FFM，它是FM的一個變種。FM(Factorization Machine)：因式分解機是最近比較火的一個模型，這個模型可以挖掘出特征間的非線性關系，并且可以在 O(n) 的時間内完成計算，非常吸引人。

最後就是深度學習了，在視訊、圖像和語音領域有較為突出的成果。最新的聽說MSRA出了一個152層的網絡，OMG…國内在廣告領域應用深度學習最早的應該是百度鳳巢，低于10層，經過多輪疊代之後效果初顯。我自己也在探索階段，期待能有好的結果，這裡就不多說了。

點選率預估環節到這裡就結束了，以上内容不知是否和您心意。部分内容可能需要一些機器學習背景，對此感興趣的同學可以加入我們的QQ群(初學者373038809，行業同學和研究者472059892)，我們共同讨論。好累呀，賣個萌再往下面寫吧。(圖檔來自網絡)

5.3 程式化交易關鍵技術：出價政策

在上半部分中，我們曾經介紹過程式化交易中的參與者，除了使用者外，主要還有代表媒體網站利益的SSP、代表廣告主利益的DSP和小三ADX。通俗來講，SSP是管倉庫的，ADX是管傳話的，DSP是管花錢的，現在我們要開始聊程式化交易中的關鍵技術，您覺得我們應該把目光放在誰上面呢？已經講到現在了，我們要收起情懷，統一思想，當然是要重點關注DSP啦！你可能會想，花錢誰不會啊，這要啥技術？沒錯，花錢是沒什麼難的，但對于廣告主而言，花錢做廣告是一種投資，本質和風投股票文玩樓盤高利貸沒什麼差別，追求的就是高的投入産出比，真刀真槍的動起錢來，弄不好會走火入魔的。這錢，您還敢花嗎？

敢啊！

要是不敢我還怎麼寫部落格嘛，哈哈哈哈哈~~~花錢不要緊，隻要能掙就行了呀！那我們就來聊聊如何才能掙的比花的多吧。

5.3.1 出價原則

上面我們提到，廣告主花錢做廣告實際上是一種投資行為，既然是投資，就要對風險進行評估。具體到DSP來說，“投資”是指廣告主投錢給DSP，讓其參與實時競價，期望獲得良好的廣告效果(點選/購買/注冊/下載下傳等)；“風險”是指錢花了，但由于效果太差，沒見着收益。為了規避風險，擷取較高的投入産出比，DSP在出價時需要進行“風險評估”，即預估本次廣告展示機會所能帶來的收益，以此作為出價的參考。在出價時，要注意以下幾點原則，可能并不全面，還請行業内的同學補充。

• 預算限制：廣告主一次就給這麼多，超了算你的。
• 時間限制：到時間花不完就收回去了。
• 花錢為主：都說了是投資，能花了就别留着。
• 見好就上：出價與流量品質成正相關。

這些出價原則了解起來沒什麼難的，但我想要着重說一下第四條

見好就上

，這才是最關鍵的部分。如何定義流量品質，又如何出價呢，好戲馬上開始。

5.3.2 如何定義流量品質？

所謂流量品質，就是在此時此刻此情此景，使用者點選廣告能為廣告主帶來的收益，主要分為兩部分：一是點選率，二是點選價值。點選率的預估就不多說了，和媒體網站上點選率預估是類似的，隻不過在實時的場景下要求會更高一些。點選價值是什麼意思？劉鵬老師在《計算廣告》中這樣解釋道：（有部分修改，括号内容為我的解釋）

點選價值可以分解為到達率、轉化率和轉化單價三個量的乘積。到達率是指實際打開廣告次數與點選次數的比例，這與廣告主網站的頁面你打開延遲關系最大，與媒體的屬性、特别是誤點情況也有一定關系；轉化率指的是到達廣告首頁以後，有多少比例産生了廣告主定義的轉化行為(購買/注冊/下載下傳等)；轉化單價是指廣告主指定的轉化費用(即DSP做一單能掙多少)。

上述三個變量中，到達率和轉化單價都是很好統計的，隻有轉化率的預估是比較困難的。轉化率預估的方法可以參照點選率預估，但是由于轉化資料要比點選資料少得多，除非是在有充足行業資料支援的情況下，否則用機器學習方法模組化有較大困難。實踐中比較可行的辦法基本上都是簡單統計與營運經驗相結合來估算轉化率。

5.3.3 如何出價？

終于進入到了最核心的出價環節。按照“見好就上”的原則，出價與流量品質成正相關。那到底是采用線性政策好，還是非線性政策好呢？我們來仔細分析一下。

• 線性出價政策

我們在CTR預估階段提到過使用者注意力，廣告位這個實體因素對點選率的影響是十分顯著的。我曾看到過一個數字，同樣一個廣告，把它放在第一位所獲得點選率是放在第二位時的兩倍。若采用線性出價政策，DSP在出價時就有必要出兩倍于第二位的價格去參與競價。這個思路很好了解，感興趣的同學可以參照KDD’12的paper《Bid Optimizing and Inventory Scoring in Targeted Online Advertising》。

• 非線性出價政策

非線性政策是我想說的重點，主要是想借着這個機會介紹一下限制條件下的優化問題以及其解法，這對于我們做科研或者工程項目都是很有幫助的，下面我們通過KDD’14《Optimal Real-Time Bidding for Display Advertising》一文來了解一下非線性出價政策的來龍去脈。以下内容是我對這篇paper的個人了解，可能并不到位，既然寫出來就不怕大家笑話啦，有錯就改嘛嘿嘿。

<1>. 文章大意

實時競價的場景中，在預算限制條件下如何設計出價政策是我們關注的焦點。為了實作這一目标，分為三步。第一，将現實問題用數學方法模組化為限制條件下的優化問題，并通過拉格朗日乘子法，求得出價政策的數學表達式；第二，利用品友RTB出價算法大賽的資料拟合出價政策中的參數；第三，驗證結果，發現了一個有意思的結論：相比少量高品質的展示機會，那些大量低品質的展示機會同樣可以具有較好的廣告效果，值得出價。這個發現對于那些預算不夠，同時又想做廣告的小廣告主來說，簡直就是福音。

<2>. 建立模型

在一切開始之前，讓我們先考慮清楚要解決的問題是什麼，簡單來說就一句話：

選擇合适的出價政策，在預算的限制下實作廣告效果最大化

，用數學語言描述就是下面這樣：

b()ORTB=argmaxb()NT∫xθ(x)w(b(θ(x),x),x)px(x)dx

subject to NT∫xb(θ(x),x)w(b(θ(x),x),x)px(x)dx

我靠！這一堆是什麼玩意兒！你TM在逗我？淡定。。看不懂就對了啊哈哈哈哈！下面我來做一下簡化，告訴你這個模型在我眼中長什麼樣。

b()ORTB=argmaxb()一大坨 ！

subject to　 又一大坨 !<B

這下是不是好多了？反正我第一次看到這個模型就長這樣，把積分部分當作一大坨，就很容易看懂了。這個模型一共有兩個公式，我們一一來看。

b()ORTB=argmaxb()一大坨 ！

第一個公式是一個等式，等号左邊是我們想得到的出價政策函數 b()ORTB ，等号右邊是 argmaxb() 跟上一大坨，這裡 argmaxb() 的意思是：當後面一大坨取最大值時，傳回在最大值情況下的那個 b() 。将等号左右兩邊連起來，這個等式所表達的意思就是：當後面一大坨取最大值時，傳回在最大值情況下的那個 b() 作為我們要求的出價政策 b()ORTB 。這個思路是不是有點眼熟？沒錯，在前面合約廣告關鍵技術——閱聽人定向中，講到使用者動态特征時我們對泊松分布的處理方式有些類似。綜上所述，對于這個等式而言，我們要做的工作就一個：求最大值。

subject to　 又一大坨 !<B

第二個公式是一個不等式，subject to是“受限于”的意思。在這裡， 又一大坨 !<B 想要表達的就是一個限制條件，在等式求最大時插上一腳。還記得我們在高中時學過的線性規劃嗎，一樣的道理。

現在我們的任務已經明确了：在限制條件下求等式最大值。那麼這個數學任務和我們的實際問題：

選擇合适的出價政策，在預算的限制下實作廣告效果最大化

是怎麼比對上的呢？這就需要去看那兩大坨了。那一大坨全都是各種符号，我們看不懂，是以需要一張符号對照表，如下圖。為了友善，我再把模型公式再貼一次。

b()ORTB=argmaxb()NT∫xθ(x)w(b(θ(x),x),x)px(x)dx

subject to NT∫xb(θ(x),x)w(b(θ(x),x),x)px(x)dx

有了符号定義和模型，我們開始聊(啃)一聊(啃)這兩大坨吧。先看第一坨，我們從右往左看。

• dx ：x代表一次bid request，是ADX發給DSP的競價請求“辨別XXX,男性，20-25歲，跑鞋愛好者，廣告位為首頁”，即一次廣告展示機會。之是以是 dx 而不是 x ，是因為我們關注的是整個廣告推廣計劃中所有的競價過程，而非某一次競價。
• px(x)：廣告展示機會的機率密度分布，我的了解是在全網所有的競價中，滿足我DSP要求的、或者是我能收到的bid request所占的比例。是以， px(x)∗dx 的實體意義是“我能收到的展示機會”。
• θ(x) ： θ 是赢得此次競價所能帶來的收益(KPI)，本文用CTR來衡量，CTR越高，收益就越高。
• b(θ(x),x) ：對于此次展示機會，在能帶來收益為 θ(x) 的情況下，我所出的價格bid。
• ω(b(θ(x),x),x) ：對于此次展示機會，在能帶來收益為 θ(x) 的情況下，我的出價bid能獲勝的機率是多少。是以， ω(b(θ(x),x),x)∗px(x)∗dx 的實體意義是“對于本次我所收到的這個展示機會來說，在該機會能帶來收益為 θ(x) ，我出價為bid的情況下，我能打敗對手獲得此次展示機會的機率”。
• θ(x) ：依然收益。是以 θ(x)∗ω(b(θ(x),x),x)∗px(x)∗dx 的實體含義是“我出價為bid，赢得這次展示機會後，所能獲得的收益”。
• NT ：一次廣告推廣活動中所有的bid request。

有了上面的解釋，我們可以很容易的得出第一坨的實體意義：對于一次廣告推廣活動中的所有競價，我使用 b() 的出價政策所能獲得的收益。和等式連起來，即：

對于一次廣告推廣活動中的所有競價，我使用 b() 的出價政策所能獲得最大收益時所對應的 b() ，就是我們想要的出價政策。

有了第一坨的經驗，第二坨啃起來就容易多了。前面都不變，隻有到最後把 θ(x) 換成了 b(θ(x),x) ，變為 b(θ(x),x)∗ω(b(θ(x),x),x)∗px(x)∗dx ，其實體意義為：對于這次廣告展示機會，我出價為bid且赢得這次展示機會所花費的預算。是以對于整個廣告推廣活動而言，

所有的出價要小于預算

。就這樣，我們順利的将預算限制寫進了數學模型裡。

好了，分析完兩大坨積分的含義之後，我們合起來解釋一下該模型(ORTB)所表達的實體意義：

在整個廣告推廣活動中，在出價總和小于預算的限制條件下，當廣告收益取得最大值時所對應的那個出價政策，就是我們夢寐以求的出價政策 b()ORTB

。再來對照一下我們的任務：

選擇合适的出價政策，在預算的限制下實作廣告效果最大化

。這下比對了吧！完美！(圖檔來自網絡)

<3>. 模型求解

截止到目前，我們已經得到了模型表達式，由一個等式和一個不等式組成。接下來我們就要開始求解了：求最大值。最大值有什麼好求的？讓導數等于0之後帶入極值點不就完了？你說的對，如果隻有一個等式我們是這麼求的，但問題是我們現在除了一個等式，還有一個不等式，這種情況下怎麼來求最大值呢？用拉格朗日乘子法。

通過拉格朗日乘子法，我們可以将不等式乘一個參數 λ 後和等式寫進一個公式裡(化簡過程已省略)，得到如下結果。

L(b(θ),λ)=∫θθw(b(θ))pθ(θ)−λ∫θb(θ)w(b(θ))pθ(θ)dθ+λBNT  (6)

有了這個公式，我們就可以對它進行求導等于0了，可得如下結果：

θpθ(θ)∂w(b(θ))∂b(θ)−λpθ(θ)[w(b(θ))+b(θ)∂w(b(θ))∂b(θ)]=0  (7)

通過化簡，可得出價函數 b() 與勝率函數 w() 的關系：

λw(b(θ))=[θ−λb(θ)]∂w(b(θ))∂b(θ)  (8)

也就是說，我們想要的出價函數 b() 與勝率函數 w() 有關，那我們就來看看他們之間到底有什麼關系。通過對資料的統計，可以畫出出價函數 b() 與勝率函數 w() 的關系圖像：

從圖像中我們可以看出，出價函數 b() 與勝率函數 w() 的關系是非線性的，并且這個曲線的走勢和 y=xc+x 很像，我們來對比一下，這裡c=3。

沒錯，的确很像。基于此，為了達到消元的目的，作者做了一個出價函數 b() 與勝率函數 w() 之間的假設，仿照着 y=xc+x 得到下面公式：

w(b(θ))=b(θ)c+b(θ)  (9)

将出價函數 b() 與勝率函數 w() 的9式關系帶入到倒數為0的7式中，化簡可得：

bORTB1(θ)=cλ+c2‾‾‾‾‾‾‾√−c  (13)

就這樣，我們得到了我們的出價政策 bORTB() 的表達式(公式13)。我們來看看這個公式裡有什麼。這個公式是由 θ ， c 和λ組成的，其中 c 和λ都是常量，隻有 θ 一個變量。 c 是出價函數b()與勝率函數 w() 之間的系數， λ 是拉格朗日乘子，而 θ 是每次廣告展示的收益，按CTR高低來評判。我們來驗證一下：CTR越高，由該政策算出的出價也就越高，符合我們的預期，大功告成。

我們來梳理一下思路。在模組化環節，我們已經得到了我們所需的模型：一個等式+一個不等式。我們的任務是要求等式的最大值，通常方法直接對等式求導等于0即可，由于我們這裡是一個限制條件下的優化問題，是以需要用到拉格朗日乘子法，将限制條件寫進等式中，構造出一個新的公式(公式6)。對于新的公式，我們就可以用求導等于0了(公式7)。在化簡過程中，我們發現了出價函數 b() 與勝率函數 w() 存在着數學關系(公式8)，為了消元，我們按照實際資料的分布構造出出價函數 b() 與勝率函數 w() 的表達式(公式9)，将公式9帶入公式7，繼續化簡就得到了我們的出價政策： bORTB() ，剩下的工作就是根據資料去拟合 λ 和 c 即可，這裡就不多說了。這裡需要強調的是，這種限制條件下的優化方法在統計與機器學習中是很常見的，例如SVM的推導過程，感興趣的同學可以試一試，其實并不難。

<4>. 結果分析

既然有了公式，那我們就來看看ORTB的出價有什麼特點吧。

我們可以很直覺的看出，我們所得到的出價政策是一個非線性的。橫坐标θ代表了廣告展示計劃的品質，ORTB會對低價值的展示機會出高價，這樣的結果能為我們帶來什麼，誰會去要那些低價值的展示機會呢？我們來看下面這張圖。

在此圖中，我們盯着一條曲線看，比如藍色的(1/32)。随着 λ 增加，收獲的點選量是增加的，意味着 λ 越高，我們的收益越高。對于我們獲得的出價政策而言， λ 越高，我們的出價是越低的，也就意味着這次展示機會的價值是很低的。這樣的結果值得我們深思，我們以為低價值的展示機會是不值錢的，但資料說明，這些看似不值錢的展示所能帶來的回報還算不錯。特别地，在 λ =1e-05時三條曲線的幾乎重合，而紅色代表有錢的廣告主，藍色代表窮廣告主，雖然預算差了16倍，但是獲得的收益是相同的，這個結論對于預算有限的小廣告主而言，是個天大的好消息：雖然我們錢不多，但隻要我們出價合适，依然可以收獲很好的廣告效果，四兩撥千斤，極大的調動了小廣告主參加程式化交易的積極性。

我們知道，“二八原則”是客觀存在的，在廣告主中也不例外，如果能吸引這80%的小廣告主參與程式化交易，玩家一多，需求自然更多。為了滿足金主的需求，勢必會推動相關計算技術的發展，這對于計算廣告的未來而言，是一件好事。

講完了非線性出價政策，程式化交易中的關鍵技術也接近尾聲了。出價政策之是以重要，是因為就是DSP賴以生存的看家本領，沒有這些真本事，DSP是走不了多遠的。

到此，計算廣告關鍵技術就講完了，啥也不說了，給自己鼓個掌吧(圖檔來自網絡)。

曆時大半個月，中間又加上過年，終于把這章給寫完了，沒想到這一章的内容要比上半部分全文都要多。在本篇《計算廣告小窺[中]這孫子怎麼什麼都知道》中，我們從理論的角度探讨了計算廣告各階段的關鍵技術：在合約廣告中，我們讨論了閱聽人定向技術，從使用者、上下文和廣告主三個方面簡單介紹了打标簽的常用思路和方法，為計算廣告實作精準營銷打下了堅實的基礎；在競價廣告中，我們讨論了點選率預估的來龍去脈，感受到了網際網路人的智慧，為媒體網站流量變現提供了直接保障；在程式化交易廣告中，我們通過學術論文了解了當下學術界領先的DSP出價政策，近距離地感受了一下科研的魅力。

曾有人歎息到“我們這一代最聰明的人竟然都在這裡思考着怎樣讓人們去大量的點選廣告，真衰。”我個人不認同這種說法，因為在計算廣告這樣複雜的場景下，相關技術和解決方案的水準必然是頂尖的，稍加修改即可解決其他場景下的疑難雜症，這恰似軍工技術反哺民用，又恰似女生随手甩一個不要了的護膚品給男生，那可都是寶。

受篇幅所限，原定于本篇要完成的第五章和第六章隻好放在《計算廣告小窺[下]廣告系統架構：要啥自行車，這裡有寶馬。》中來寫了。在下篇中，我們将介紹一個通用的廣告系統架構，在領略線上和離線過程的同時，還将見到時下工業界最火熱的技術，譬如Nginx，Hadoop，Spark等在計算廣告領域的位置與應用。

除了廣告系統架構，我還将介紹一個我自己搭的最小廣告系統mieSys，可以先放出來給大家玩一玩，連結是http://115.159.33.50/。使用方法：使用者點選頁面中廣告，等一段時間後重新整理頁面，在頁腳處會顯示使用者的興趣标簽和性别，在第一行五個廣告位中會展示符合使用者口味的廣告。

需要注意的是，由于目前缺少點選資料，CTR模型并不準，為了保證示範效果，暫時隻能用離線代替線上，是以您在點選過後預計要10分鐘(使用者多的話甚至更長)才能看到頁面效果，我後期會進行優化，還望輕拍

，效果圖如下，第一張為預設頁面，第二張為結果頁面。

這個系統是我用大概20天的時間搭成的，目前來說基本的功能都有，但還是太簡單，并且算法沒有優化，我會逐漸的往上面添加子產品和算法，目前思路已有，就差各位為我提供點選資料了[嘿嘿嘿嘿···]。如果您發現mieSys挂了，不是使用者太多就是我在調程式，在系統成熟的時候我會選擇開源，願意與有興趣的同學多交流。哦對了，至于為什麼起名為mieSys，因為我女朋友屬咩，呵呵哒~

好了，我們《計算廣告小窺[下]》再見！