本來打算寫文章介紹一下業(yè)界內(nèi)廣告搜索引擎的業(yè)務及架構(gòu)的,但是覺得應該先介紹一下整個搜索廣告的大背景的,所以周末學習了一下斯坦福大學的Introduction to Computational Advertising課程,下文主要內(nèi)容都是翻譯自此課程的幻燈片,由于我目前只對搜索廣告有所了解,所以只翻譯了搜索廣告相關的一部分內(nèi)容,原文中的很多內(nèi)容沒有涉及到,例如展示廣告,定向廣告,推薦系統(tǒng)等。

什么是計算廣告(Computational Advertising)：。

計算廣告是計算機科學中出現(xiàn)的一個相對較新的子科學領域,利用算法來給用戶展示[通常是在瀏覽器中]出最佳的廣告。

它集合了下面的技術于一身：。

信息檢索 (Information retrieval)。

大規(guī)模搜索與文本分析(Large scale search and text analysis)。

統(tǒng)計建模(Statistical modeling)。

機器學習 (Machine learning)。

微觀經(jīng)濟學 (Microeconomics)。

博弈論、拍賣理論與機制設計 (Game theory, auction theory, mechanism design)。

分類(Classification)。

優(yōu)化(Optimization)。

推薦系統(tǒng) (Recommender systems)。

計算廣告的核心挑戰(zhàn)：。

在一個給定場景下的給定用戶和合適的廣告之間找到一個最佳的匹配(Find the "best match" between a given user in a given context and a suitable advertisement.)。

如果把廣告看作一種信息,那么找到一個“最佳廣告”就是一個信息檢索問題,這個問題附帶有多個可能互相矛盾的效用函數(shù)。

為什么需要“計算”廣告?。

1)把傳統(tǒng)廣告學和計算機的計算能力相結(jié)合。

2)從算法的角度來思考舊的挑戰(zhàn)。

傳統(tǒng)廣告與計算廣告的特點對比：。

傳統(tǒng)廣告：。

相對而言平臺較小--雜志、廣告牌、報紙、傳單、電視等。

每個平臺花費巨資(幾百萬的電視廣告費用)。

不可能個性化。

只能由聰明的廣告人來決定在哪里投放。

很難度量投資回報率(ROI)。

計算廣告：。

億級別的投放機會。

億級別的創(chuàng)意形式。

完全個性化。

每次投放而言花費很小。

更容易度量。

約翰*沃納梅克,著名的百貨商店之父曾經(jīng)說過：。

我在廣告上的投資有一半是無用的,但是問題是我不知道是哪一半。

計算廣告的分類：。

根據(jù)廣告主的計費方式,可以分為。

千次展現(xiàn)付費 CPM(cost per thousand impressions) 主要用于品牌曝光,例如淘寶的鉆展業(yè)務。

每次點擊扣費 CPC(cost per click) 通常用于文本廣告,例如百度鳳巢,Google Adwords。

成交/行為付費 CPT/CPA(cost per transaction/action) 例如淘寶客業(yè)務。

根據(jù)展現(xiàn)形式分為:圖片廣告[Graphical Ads]、文本廣告[Textual Ads]、視頻等。

根據(jù)不同的產(chǎn)品形式分為。

搜索廣告(Sponsored Search),例如百度鳳巢,Google Adwords。

上下文廣告[Contexual Ads],例如Google Adsense。

展示廣告[Display ads],例如淘寶鉆展業(yè)務線。

定向廣告[Targeting Ads],例如Google Adsense。

在互聯(lián)網(wǎng)中,搜索廣告是最主要的文本廣告的形式。

互聯(lián)網(wǎng)廣告的意義：。

廣告支撐起了互聯(lián)網(wǎng)上一個巨大的生態(tài)系統(tǒng)：。

1.內(nèi)容提供商通過廣告賺錢,養(yǎng)活了 宏觀/微觀的內(nèi)容提供商 [就是各種大小網(wǎng)站]。

2.精準觸達/定向使得長尾生意成為可能。

3.廣告主的收入使得大批“免費”的服務成為可能：Facebook, Google, Twitter,Yahoo。

如果沒有廣告,互聯(lián)網(wǎng)就不可能像現(xiàn)在這么發(fā)展迅速、規(guī)模宏大。

廣告給消費者提供了直接和間接的巨大價值。

計算廣告的參與方：。

1.流量提供方(Publishers)。

2.廣告主(Advertisers)。

3.瀏覽者/用戶(Users)。

4.廣告平臺/廣告網(wǎng)絡(Match maker/Ad network)。

這些參與者有各自不同的訴求：流量提供者渴望每次展現(xiàn)/搜索的高收益,廣告主渴望高投資回報率(ROI)和流量,用戶希望高相關性,廣告網(wǎng)絡渴望收益與市場份額。

而廣告的選擇,就是要兼顧四個參與者的收益,達到最優(yōu)狀態(tài),需要權衡長期和短期的商業(yè)目標。

計算廣告對性能的要求很高：。

億級別：。

搜索廣告中有數(shù)億級別的廣告。

每個小時有億級別的搜索。

萬億級別頁面展現(xiàn)次數(shù)。

億級的用戶。

毫秒級別：。

請求是在用戶“等待”過程中完成的,必須在100ms內(nèi)返回錢：。

每個請求都需要消耗CPU資源。

數(shù)據(jù)通常放在內(nèi)存中 [需要大量內(nèi)存,而內(nèi)存比硬盤貴]。

每次請求的耗費必須比收益要低。

過低的點擊率(ctr)使得上面的挑戰(zhàn)更加困難。

搜索廣告：。

什么是搜索廣告(sponsored search)：。

搜索廣告是由搜索關鍵詞驅(qū)動的廣告。

廣告主選擇一個“競價詞”,當用戶觸發(fā)某個搜索請求時,廣告主的廣告得以展現(xiàn)。

業(yè)界的系統(tǒng)：Google AdWords, 百度鳳巢,淘寶搜索直通車。

在上文中我們提到的計算廣告中有4個參與方,在搜索廣告中,流量提供方是搜索結(jié)果頁 SERP(search results page),通常流量提供方和廣告平臺是同一個(Google,Bing),當然也可以不一樣(微軟給雅虎提供廣告搜索)。

在搜索廣告中三個參與者之間有如下的交互行為：。

廣告主：。

1.提交廣告,購買相關的競價詞。

2.為了獲得好的展示位置而競價。

3.為獲得的點擊付費。

瀏覽者：給搜索引擎提交查詢串,表達一定的意圖。

搜索引擎：。

1.根據(jù)用戶的查詢串在web頁面語料庫和廣告語料庫中分別進行檢索。

2.把自然搜索結(jié)果和廣告搜索結(jié)果結(jié)合到一起,展示在搜索結(jié)果頁 SERP上。

搜索廣告中存在的三個子問題。

從搜索引擎的角度來看,搜索廣告中存在三個子問題：。

1.廣告檢索。

2.給拿到的廣告排序。

3.根據(jù)點擊收費。

以上三個順序是搜索廣告事件發(fā)生的順序,這里面1和2屬于信息檢索問題,而2和3又屬于微觀經(jīng)濟學問題。

文章一開頭提到了計算廣告中涉及到了博弈論,拍賣理論,機制設計,到底在哪里用到了呢?想了解這些疑問就得接著往下看。

對于目前的搜索廣告來說,都被設計成了拍賣的機制。

搜索引擎拍賣的是每個流量中可能的廣告位,廣告主提交對購買的關鍵詞的每次點擊的最高出價,廣告主是不知道其他人的出價信息的。

雖然每個流量中一般會有多個廣告位置,但是廣告主只出一個價格。

最終搜索引擎根據(jù)廣告主競價和廣告的點擊率CTR來對廣告進行排序,決定最終的展示位置。

‖。

點擊扣費時,目前普遍采用的是Google發(fā)明的廣義第二價格扣費GSP(General Second Price),有兩種策略：。

競價排序：根據(jù)廣告的出價倒序排列,位于第i個的廣告支付第i+1個廣告的競價。

根據(jù)廣告平臺的收益排序：根據(jù)期望最大收益ecpm來排序。

ecpm=bidprice*ctr。

被點擊的廣告主i付的費用為。

price=bidprice(i+1)*(ctr(i+1)/ctr(i))。

由于bidprice(i)*ctr(i)>bidprice(i+1)*ctr(i+1),可以從上述公式看到廣告主實際扣費肯定小于最高出價。

在廣告搜索引擎中,不能直接拿著用戶的查詢串在倒排索引中進行廣告檢索的,因為這樣可能導致搜出來的廣告深度不夠,而且查詢多種多樣,在搜索引擎有限的資源下,不可能對所有查詢建立倒排索引,所以需要經(jīng)過查詢改寫來改寫出歸一化后的多個搜索詞,用這些搜索詞去檢索廣告。

查詢改寫(Query Rewrite)。

把用戶查詢(Query)改寫成競價詞(Bidword)的過程。

總的來說有離線(offline)改寫和在線改寫(online)兩類。

離線改寫：。

在離線的時候利用相對在線而言更多的數(shù)據(jù)來處理用戶的查詢,生成一個query->bidword的映射關系表,缺點是只能給那些高頻詞進行離線處理。

這里有兩個問題：我們應該改寫哪些查詢--我們需要市場深度的查詢上。

我們應該改寫成什么樣的查詢--那些市場深度足夠的查詢上。

在線改寫：。

對于離線不能處理的少數(shù)請求需要我們進行在線改寫,在線改寫相對離線而言,資源受限(內(nèi)存限制,時間限制),需要在很短的時間(數(shù)ms)內(nèi)做分析。

廣告選擇(Ad Selection)。

給定一個查詢,搜索引擎可以展示兩類廣告：。

精確匹配EM(Exact match): 廣告主對特定的查詢競價。

高級匹配AM(Advanced match)或廣泛匹配(Broad match): 廣告主并不對特定的詞進行競價,但是這個查詢被認為是廣告主感興趣的。

搜索廣告中的流量具有長尾效應,非常多的長尾流量查詢在搜索廣告中沒有對應的廣告,高級匹配主要是為了解決這相當一部分流量沒有被競價的問題,廣告主不關心競價詞,他們只關心轉(zhuǎn)化--賣掉商品。

如何覆蓋到相關的流量呢,從引擎的角度出發(fā),高級匹配比精確匹配更有挑戰(zhàn)性。

兩階段廣告選擇。

在廣告搜索引擎中,廣告語料庫中的廣告數(shù)量巨大,高達百萬之多,而實際展示的過程中,只有極少數(shù)量的廣告能夠展示出來,目前業(yè)界普遍采用兩階段廣告選擇來解決性能問題。

廣告檢索過程中,整個廣告的選擇分為兩部分：。

廣告檢索(Ad Retrieval):從整個廣告語料庫里面選出一個最可能的候選集合。

此過程是粗選階段,我們用來排序的目標函數(shù)(例如評估相關性)可能和最終排序的函數(shù)(例如ecpm)不同。

廣告重排序(Ad Reordering)：利用更多的數(shù)據(jù)來對第一階段返回的有限的候選廣告集合進行更為精細,更為復雜的計算。

這個階段必須綜合考慮競價和相關性分數(shù)(例如ecpm)。

對于廣告重排序階段,目前有兩種主流的方法,以賽馬為例：。

反應式(Reactive)：選定一匹馬,根據(jù)它的歷史成績來預測未來的表現(xiàn)。

預估式(Predictive)：根據(jù)體重,腿長等特征為賽馬建模,找到這些特征在預測比賽名次終的重要程度,然后基于這些特征來給見過、未見過的賽馬預測成績。

當我們擁有對某賽馬的足夠信息的時候,就使用這些信息(反應性),否則使用模型(預測性)。