計算廣告關鍵技術：他們怎么什么都知道？
作者|面包包包包包包
修改|寒小陽 && 龍心塵
上一期我們一起探索了計算廣告的基本概念和四種形式(點擊查看《計算廣告小窺(上)》)，本期文章是我們為讀者帶來的【計算廣告小窺】專題的第二個部分。
(上)(中)(下)全文目錄
- 引言
- 廣告=>互聯網廣告：“您好，了解一下”
- 互聯網廣告=>計算廣告：指哪兒打哪兒!
- 計算廣告四君子：誰在弄潮?
- 計算廣告關鍵技術：這孫子怎么什么都知道?
- 廣告系統架構：要啥自行車，這里有寶馬。
- 手把手系列之教你搭建一個最小廣告系統：mieSys
5. 計算廣告關鍵技術：這孫子怎么什么都知道?
一句話解釋關鍵技術：沒聲音，再好的戲也出不來。
廣告作為一項商業活動，是需要資本來滋養的。作為整個產業鏈的金主，只有廣告主花錢做廣告，使資金流動起來，整個廣告行業才能正常運轉。所謂關鍵技術，就是那些能讓廣告主覺得“這錢花的值”，讓媒體網站覺得“這錢掙的快”的技術。具體都有哪些呢?下面我們一一來表。
5.1 合約廣告關鍵技術：受眾定向
計算廣告發展到合約廣告階段，媒體網站依靠受眾定向技術給用戶打標簽，在實現了媒體網站廣告位的時分復用的同時，還提高了廣告主的投入產出比，極大的激發了廣告主在互聯網上做廣告的積極性。因此，受眾定向是合約廣告中的關鍵技術。
我們知道，只要描述物體的維度足夠高，那么世間萬物都是獨一無二的。在廣告系統中，標簽就是描述用戶的維度。媒體網站為了精準的刻畫用戶，標簽的種類和數量自然也不會少。為了更加直觀地了解受眾定向技術，我們從用戶、上下文和廣告三個方面討論打標簽的思路和一般方法。
- 用戶標簽：主要用性別、年齡、收入、地理位置、教育程度和用戶行為等標簽來刻畫用戶，從而回答“你是誰”的問題。
- 上下文標簽：主要用網頁的地域、主題和頻道等標簽來刻畫用戶當前所處的媒體網站環境，從而回答“你在看啥”的問題。
- 廣告標簽：主要用廣告主、廣告創意、廣告計劃和廣告關鍵詞等標簽來刻畫廣告的相關內容，將廣告內容與用戶和上下文進行匹配后，從而回答“你該看啥”的問題。
5.1.1 用戶標簽關鍵技術
對一個用戶來說，性別是不會輕易變的，但是用戶的喜好和興趣卻是時刻都在變化的。根據標簽屬性的變化頻率，我們這里私自將用戶標簽分為靜態和動態兩類。靜態標簽主要指年齡、性別、地理位置、收入和教育程度等這種不變或者很長時間之內都不變的標簽，行話叫“人口屬性”;動態標簽則是指用戶的瀏覽、搜索和點擊等能夠反映用戶短時喜好和興趣的行為標簽，行話叫“行為定向(BT:Behaviroal Targeting)”。下面我們針對靜態和動態這兩類標簽分別討論。
一句話解釋靜態標簽和動態標簽的關系：價格圍繞價值上下波動。
靜態標簽(人口屬性)
在《計算廣告小窺[上]》中，我們曾簡要地提到過一種受眾定向的方法：
通過對點擊日志的分析，媒體網站發現點擊過女性護膚品的用戶又點擊過媒體網站上其他女性品牌。在“女性用戶對女性品牌可能更感興趣”的合理假設下，判斷這些用戶的性別為女，男性用戶同理。
現在我們可以更加清楚的認識到，上述媒體網站所打的標簽是靜態標簽中的“性別”，使用的是基于規則的方法，即：滿足了某種條件，就是某種人。這種基于規則的方法簡單并且易于實現，但也存在著致命的缺點：基于規則的方法對數據非常敏感，若數據本身存在噪音(如誤點擊)，那么標簽的品質也將大打折扣。這可如何是好?簡單的不行，那就來點復雜的嘛——用機器學習模型來實現(自帶音效：當當當當，當當~~)。
假設我們已經知道一部分用戶的真實性別，那么就可以用機器學習中有監督的二分類模型來預測用戶性別。首先，我們需要對原始數據進行清洗，合理地處理缺失值和奇異值，并劃分訓練集、交叉驗證集和測試集;其次，要在業務的指導下做特征工程，利用統計或模型的方法構造特征，并進行特征選擇和特征組合;然后，我們要選擇合適的模型(如SVM等)，設置合適的評價標準并進行模型的訓練;最后，通過模型調參和模型融合，獲得性別預測模型。
動態標簽(行為定向)
一句話解釋行為定向：唐伯虎喜歡如花多一些，還是鳳姐多一些?
“如果一定要比較一下，那唐伯虎是喜歡如花多一些，還是鳳姐多一些?”這個看似荒謬的問題，正是行為定向要解決的。如果唐伯虎是異性戀，那他應該是喜歡鳳姐多一些的，否則是如花。這也就告訴我們，在行為定向中，判斷的標準至關重要。下面我們借助一個例子來分析該用戶的動態標簽究竟是什么。
有數據顯示，某用戶在過去的三個月時間中，點擊廣告的標簽和次數如下表所示：
標準
單反愛好者
跑鞋愛好者
飲料愛好者
護膚品愛好者
…
對上述數據進行分析，我們可以輕而易舉的得到答案：該用戶的標簽應該是“單反愛好者”，因為他的點擊行為集中在這個標簽上。但是，這個答案是我們以用戶的點擊行為作為標準得來的，如果以用戶的瀏覽和搜索行為做標準，答案也是“單反愛好者”嗎?我們再來看一下相關數據。
標準
單反愛好者
跑鞋愛好者
飲料愛好者
護膚品愛好者
…
標準
單反愛好者
跑鞋愛好者
飲料愛好者
護膚品愛好者
…
是不是出問題了?以點擊和瀏覽為標準，該用戶標簽應該是“單反愛好者”，但是以搜索為標準，標簽應該是“跑鞋愛好者”。如果該用戶的標簽只能有一個，那該選哪一個呢?為了解決這個問題，我們從數學角度分析一下好了。嘿嘿，數學噢，前方高能預警!我會盡量讓這個過程變得簡單，大家跟上我的思路哈。
Step1. 泊松分布
一句話解釋泊松分布:猜猜我在哪兒~~~
我們先來介紹下泊松分布。啊啊啊啊!一上來就是數學，我不聽我不聽我不聽，泊松分布是什么鬼?咳咳，那，那就先不丟公式了，咱們看圖解決問題好了，下面是泊松分布繪出的曲線圖，實際工程中要解決的問題就是找到圖中的最高點，如下圖：
這個肉眼找最高點的過程不要太簡單了!!!我們可以看到：圖中最高點的縱坐標大約為0.36，而對應的橫坐標是1。OK，你就算會用泊松分布了哦!那個，感興趣的同學們，可以一起來看看對應上圖的泊松分布的公式。
公式相對于圖，是有那么點點復雜啦。不過，我們只需知道λt影響泊松分布的形狀，一個λt對應一個泊松分布就可以了。這個場景下要做的事情就是找到對應泊松分布圖像的最高點。
Step2. 一個結論
一句話解釋這個結論：一個蘿卜一個坑。
我們先說一個結論：在一個標準下，所有用戶占有的標簽，在所有標簽上的概率分布是滿足泊松分布的。對于這個結論，有興趣的同學可以參見Stanford 《Introduction to Computational Advertising》講義Page-81，我們在這里就直接拿來用了。而所謂“標準”，就對應泊松分布公式中的λt，在我們這里的場景下與用戶行為有關。
這張圖的橫軸代表用戶擁有的標簽數目，縱軸代表興趣標簽數目為x的用戶數目，比方說有1個標簽的用戶有500人，有3個標簽的人有5000人。從這張圖中我們可以很清楚的看到，用戶在所有標簽上的分布是滿足泊松分布的。但是這里有一個問題，大量用戶所呈現出的這種泊松分布，和單獨用戶的興趣標簽之間有關聯嗎?我們說，關聯不大，因為一個是隨機過程，一個是隨機事件，想要得到每個用戶的興趣標簽，其實是一個復雜的任務。下面我們從統計和投票的角度入手，來看一種用戶打標簽的方法。
Step3. 最佳標準
一句話解釋最佳標準：盲人摸象
“盲人摸象”比喻以偏概全，現在我們想要知道大象全貌，把每個人摸到的拼起來便是了。在廣告系統中，搜索、點擊和瀏覽三種行為數據都只能從一個側面反映用戶的行為，要想完整的刻畫一個用戶，我們需要將這三種行為融合起來之后找到一個最佳標準。提到融合，較為常用的方法是投票，我們可以寫出下列公式：
簡單解釋一下：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頁面內容在”體育”、”財經”和”游戲”三個主題上的概率分布分別為：
體育
財經
游戲
我們可以很容易的看出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的用戶注意力熱力分布圖。(圖片來自網絡)
圖中，顏色越紅代表用戶注意力越集中?？梢钥吹剑脩糇铌P注的是頁面的上半部分，其次是右半部分，最后是下半部分。這種注意力分布基本我們日常的瀏覽習慣，即如果能在頁面靠前位置找到我們所需的信息，一般就不會再關注頁面其他地方。了解了注意力分布，我們來看一下某度搜索頁面上的廣告位分布。
某度廣告位主要分布在北區、東區和南區三部分，以LinkedIn頁面中的用戶注意力分布來推測，用戶在某度頁面上注意力分布從高到底分別是北區、東區和南區。假設某度共有10個廣告位，那么將用戶最可能點擊的10個廣告按照點擊概率由高到低順序分別排在北區、東區和南區。然后還干嘛?沒有了，萬事俱備，只欠點擊。
不知道您聽明白了沒，我來幫您捋捋。為了提高媒體網站的收益，我們結合業務場景不斷簡化問題，從提高媒體網站點擊率入手，到提高總點擊量，再到獲得廣告候選集合，預測出了用戶點擊廣告的概率。僅僅預測點擊概率媒體網站還賺不著錢，因此媒體網站根據點擊概率在頁面廣告位上對廣告進行排序。所以為什么要做點擊率預估呢?都是為了錢!都是為了錢!都是為了錢!
5.2.3 點擊率預估怎么做
一句話解釋點擊率預估怎么做：使盡渾身解數，只為更懂你。
自計算廣告學誕生以來，點擊率預估就是一個在學術界和工業界被廣泛研究和實踐的課題。剝去種種具體場景，點擊率預估的本質其實還是一個機器學習中的二分類問題。一般來講，媒體網站點擊數據的數學分布是非線性的。為了擬合這種非線性關系，學術界側重于模型的研究，工業界側重于特征的構造，雙方優勢互補，已取得了相當豐碩的成果。下面我們將先介紹展示廣告和搜索廣告這兩種互聯網廣告的主要形式，然后闡述二者在點擊率預估問題上的不同之處，最后介紹一些點擊率預估的方法。
展示廣告
展示廣告(Display Advertising)是一種以“圖片+文字”的方式進行廣告宣傳的互聯網廣告形式。從廣告觸發方式來看，展示廣告是媒體網站根據用戶歷史行為所做的推薦，對用戶而言廣告是被動接收的，如下圖。
搜索廣告
搜索廣告(Sponsored Search)是一種以“標題+超鏈接”的方式進行廣告宣傳的互聯網廣告形式。從廣告觸發方式來看，搜索廣告是媒體網站針對用戶當前檢索所做的廣告匹配，廣告是用戶主動發起的，如下圖。
根據上面我們對展示和搜索廣告的描述，我們可以對兩種廣告形式的點擊率預估有一個淺顯并直觀的認識：展示廣告的點擊率預估可以看作是一個推薦問題，根據歷史記錄推測用戶對哪些廣告更感興趣;搜索廣告的點擊率預估可以看作是一個檢索問題，根據用戶當前的查詢來做廣告匹配。前者推薦后者檢索，問題性質的不同也決定了點擊率預估所采用方式的不同。
點擊率預估方法
有關展示廣告和搜索廣告的實現算法和應用細節都是各家互聯網公司的商業機密，由于場景的不同，各家對點擊率的預估也是八仙過海各顯神通。作為一個沒有實戰經驗的小屁孩兒，想要較為流暢地闡述這個話題，還是力不從心，畢竟眼界太窄太年輕。為了保證文章結構的完整，這部分還必須要寫，那么我就拋開業務場景，僅從機器學習角度來和大家聊一聊我所知道的內容。寫的不好，還請各路大神多多指教，如有不當指出，請嚴厲指出，我定感激不盡!
上面我們提到過，從用戶瀏覽網頁到廣告獲得展示，要經過三個階段：用戶定向、廣告檢索和廣告排序。用戶定向和廣告檢索就不多說了，最終在廣告庫中可以找到符合你口味的廣告，即“萬里挑十”。在廣告排序階段，需要將這十個廣告位放置在頁面上，通常做法有兩種，一個是基于規則，一個是基于機器學習。我們這里從機器學習的角度入手，但是各位千萬不要忽視了規則的能力。聊到機器學習，主要就是兩方面，特征和模型。下面我就根據我所了解的內容，重點介紹一下線性模型+海量特征的方法，然后簡單介紹一下點擊率預估的發展。
<1>線性模型 + 海量特征
用于點擊率預估的數據主要是日志數據，一般會有點擊行為(點擊為1，沒點為0)、廣告信息(廣告位、廣告主id、廣告標簽和廣告描述等)、用戶信息(用戶id和用戶標簽等)、上下文信息和時間戳等。有了這些原始數據之后，需要對數據進行清洗，然后利用統計或模型的方法構造特征，進而做特征選擇和特征組合，最終特征的數量級大約在10億-100億維。完成了特征工作之后，在模型方面，較為經典的點擊率預估模型是線性模型Logistic Regression，由于LR在通過sigmoid之前是一個[0,1]之間的浮點數，利用LR的特點，我們可以將這個浮點數作為用戶點擊該廣告的概率，把廣告按照這個概率從高到低放置在相應廣告位上，就完成了廣告排序。
為什么要造出維度這么高的特征向量呢?我的理解是這樣的。對于點擊數據來說，點擊行為與其他特征之間的關系是非線性的，為了擬合這種非線性關系，我們依然可以從特征和模型兩方面入手。通常來說，非線性模型的效果要更好一些，但是效率太低，不適合工業界的現實場景，所以快速簡單的線性模型就成為了模型的首選。那線性模型如何擬合非線性關系呢?這就需要在特征層面做文章，利用特征工程的方法來構造出高階特征，同樣可以實現非線性。這個思路理解起來還是不難的，如下面兩式對比：
<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 如何出價?
終于進入到了最核心的出價環節。按照“見好就上”的原則，出價與流量品質成正相關。那到底是采用線性策略好，還是非線性策略好呢?我們來仔細分析一下。
（1）線性出價策略
我們在CTR預估階段提到過用戶注意力，廣告位這個物理因素對點擊率的影響是十分顯著的。我曾看到過一個數字，同樣一個廣告，把它放在第一位所獲得點擊率是放在第二位時的兩倍。若采用線性出價策略，DSP在出價時就有必要出兩倍于第二位的價格去參與競價。這個思路很好理解，感興趣的同學可以參照KDD’12的paper《Bid Optimizing and Inventory Scoring in Targeted Online Advertising》。
（2）非線性出價策略
非線性策略是我想說的重點，主要是想借著這個機會介紹一下限制條件下的優化問題以及其解法，這對于我們做科研或者工程項目都是很有幫助的，下面我們通過KDD’14《Optimal Real-Time Bidding for Display Advertising》一文來了解一下非線性出價策略的來龍去脈。以下內容是我對這篇paper的個人理解，可能并不到位，既然寫出來就不怕大家笑話啦，有錯就改嘛嘿嘿。
<1>. 文章大意
實時競價的場景中，在預算限制條件下如何設計出價策略是我們關注的焦點。為了實現這一目標，分為三步。第一，將現實問題用數學方法建模為限制條件下的優化問題，并通過拉格朗日乘子法，求得出價策略的數學表達式;第二，利用品友RTB出價算法大賽的數據擬合出價策略中的參數;第三，驗證結果，發現了一個有意思的結論：相比少量高品質的展示機會，那些大量低品質的展示機會同樣可以具有較好的廣告效果，值得出價。這個發現對于那些預算不夠，同時又想做廣告的小廣告主來說，簡直就是福音。
<2>. 建立模型
在一切開始之前，讓我們先考慮清楚要解決的問題是什么，簡單來說就一句話：選擇合適的出價策略，在預算的限制下實現廣告效果最大化，用數學語言描述就是下面這樣：
我靠!這一堆是什么玩意兒!你TM在逗我?淡定。。看不懂就對了啊哈哈哈哈!下面我來做一下簡化，告訴你這個模型在我眼中長什么樣。
b()ORTB=argmaxb()一大坨 !
subject to 又一大坨 !
這下是不是好多了?反正我第一次看到這個模型就長這樣，把積分部分當作一大坨，就很容易看懂了。這個模型一共有兩個公式，我們一一來看。
b()ORTB=argmaxb()一大坨 !
第一個公式是一個等式，等號左邊是我們想得到的出價策略函數b()ORTB，等號右邊是argmaxb() 跟上一大坨，這里argmaxb()的意思是：當后面一大坨取最大值時，返回在最大值情況下的那個b()。將等號左右兩邊連起來，這個等式所表達的意思就是：當后面一大坨取最大值時，返回在最大值情況下的那個b()作為我們要求的出價策略b()ORTB。這個思路是不是有點眼熟?沒錯，在前面合約廣告關鍵技術——受眾定向中，講到用戶動態特征時我們對泊松分布的處理方式有些類似。綜上所述，對于這個等式而言，我們要做的工作就一個：求最大值。
subject to 又一大坨 !
第二個公式是一個不等式，subject to是“受限于”的意思。在這里，又一大坨 !
現在我們的任務已經明確了：在限制條件下求等式最大值。那么這個數學任務和我們的實際問題：選擇合適的出價策略，在預算的限制下實現廣告效果最大化是怎么匹配上的呢?這就需要去看那兩大坨了。那一大坨全都是各種符號，我們看不懂，所以需要一張符號對照表，如下圖。為了方便，我再把模型公式再貼一次。
有了符號定義和模型，我們開始聊(啃)一聊(啃)這兩大坨吧。先看第一坨，我們從右往左看。
- 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能獲勝的概率是多少。因此，
的物理意義是“對于本次我所收到的這個展示機會來說，在該機會能帶來收益為θ(x)，我出價為bid的情況下，我能打敗對手獲得此次展示機會的概率”。
的物理含義是“我出價為bid，贏得這次展示機會后，所能獲得的收益”。
- NT：一次廣告推廣活動中所有的bid request。
有了上面的解釋，我們可以很容易的得出第一坨的物理意義：對于一次廣告推廣活動中的所有競價，我使用b()的出價策略所能獲得的收益。和等式連起來，即：對于一次廣告推廣活動中的所有競價，我使用b()的出價策略所能獲得最大收益時所對應的b()，就是我們想要的出價策略。
有了第一坨的經驗，第二坨啃起來就容易多了。前面都不變，只有到最后把
其物理意義為：對于這次廣告展示機會，我出價為bid且贏得這次展示機會所花費的預算。所以對于整個廣告推廣活動而言，所有的出價要小于預算。就這樣，我們順利的將預算限制寫進了數學模型里。
好了，分析完兩大坨積分的含義之后，我們合起來解釋一下該模型(ORTB)所表達的物理意義：在整個廣告推廣活動中，在出價總和小于預算的限制條件下，當廣告收益取得最大值時所對應的那個出價策略，就是我們夢寐以求的出價策略b()ORTB。再來對照一下我們的任務：選擇合適的出價策略，在預算的限制下實現廣告效果最大化。這下匹配了吧!
<3>. 模型求解
截止到目前，我們已經得到了模型表達式，由一個等式和一個不等式組成。接下來我們就要開始求解了：求最大值。最大值有什么好求的?讓導數等于0之后帶入極值點不就完了?你說的對，如果只有一個等式我們是這么求的，但問題是我們現在除了一個等式，還有一個不等式，這種情況下怎么來求最大值呢?用拉格朗日乘子法。
通過拉格朗日乘子法，我們可以將不等式乘一個參數λ后和等式寫進一個公式里(化簡過程已省略)，得到如下結果。
有了這個公式，我們就可以對它進行求導等于0了，可得如下結果：
通過化簡，可得出價函數b()與勝率函數w()的關系：
也就是說，我們想要的出價函數b()與勝率函數w()有關，那我們就來看看他們之間到底有什么關系。通過對數據的統計，可以畫出出價函數b()與勝率函數w()的關系圖像：
從圖像中我們可以看出，出價函數b()與勝率函數w()的關系是非線性的，并且這個曲線的走勢和y=xc+x很像，我們來對比一下，這里c=3。
沒錯，的確很像?；诖耍瑸榱诉_到消元的目的，作者做了一個出價函數b()與勝率函數w()之間的假設，仿照著y=xc+x得到下面公式：
將出價函數b()與勝率函數w()的9式關系帶入到倒數為0的7式中，化簡可得：
就這樣，我們得到了我們的出價策略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，因為我女朋友屬咩，呵呵噠~
【本文是51CTO專欄機構大數據文摘的原創文章，微信公眾號：大數據文摘 id: BigDataDigest】
