本來(lái)打算寫文章介紹一下業(yè)界內(nèi)廣告搜索引擎的業(yè)務(wù)及架構(gòu)的，但是覺(jué)得應(yīng)該先介紹一下整個(gè)搜索廣告的大背景的，所以周末學(xué)習(xí)了一下斯坦福大學(xué)的introduction to computational advertising課程，下文主要內(nèi)容都是翻譯自此課程的幻燈片，由于我目前只對(duì)搜索廣告有所了解，所以只翻譯了搜索廣告相關(guān)的一部分內(nèi)容，原文中的很多內(nèi)容沒(méi)有涉及到，例如展示廣告，定向廣告，推薦系統(tǒng)等。
什么是計(jì)算廣告(computational advertising)：
計(jì)算廣告是計(jì)算機(jī)科學(xué)中出現(xiàn)的一個(gè)相對(duì)較新的子科學(xué)領(lǐng)域，利用算法來(lái)給用戶展示[通常是在瀏覽器中]出最佳的廣告。它集合了下面的技術(shù)于一身：
信息檢索 (information retrieval)
大規(guī)模搜索與文本分析(large scale search and text analysis)
統(tǒng)計(jì)建模(statistical modeling)
機(jī)器學(xué)習(xí) (machine learning)
微觀經(jīng)濟(jì)學(xué) (microeconomics)
博弈論、拍賣理論與機(jī)制設(shè)計(jì) (game theory, auction theory, mechanism design)
分類(classification)
優(yōu)化(optimization)
推薦系統(tǒng) (recommender systems)
計(jì)算廣告的核心挑戰(zhàn)：
在一個(gè)給定場(chǎng)景下的給定用戶和合適的廣告之間找到一個(gè)最佳的匹配(find the best match between a given user in a given context and a suitable advertisement.)
如果把廣告看作一種信息，那么找到一個(gè)“最佳廣告”就是一個(gè)信息檢索問(wèn)題，這個(gè)問(wèn)題附帶有多個(gè)可能互相矛盾的效用函數(shù)。
為什么需要“計(jì)算”廣告?
1)把傳統(tǒng)廣告學(xué)和計(jì)算機(jī)的計(jì)算能力相結(jié)合
2)從算法的角度來(lái)思考舊的挑戰(zhàn)
傳統(tǒng)廣告與計(jì)算廣告的特點(diǎn)對(duì)比：
傳統(tǒng)廣告：
相對(duì)而言平臺(tái)較小--雜志、廣告牌、報(bào)紙、傳單、電視等
每個(gè)平臺(tái)花費(fèi)巨資(幾百萬(wàn)的電視廣告費(fèi)用)
不可能個(gè)性化
只能由聰明的廣告人來(lái)決定在哪里投放
很難度量投資回報(bào)率(roi)
計(jì)算廣告：
億級(jí)別的投放機(jī)會(huì)
億級(jí)別的創(chuàng)意形式
完全個(gè)性化
每次投放而言花費(fèi)很小
更容易度量
約翰*沃納梅克，著名的百貨商店之父曾經(jīng)說(shuō)過(guò)：
我在廣告上的投資有一半是無(wú)用的，但是問(wèn)題是我不知道是哪一半。
計(jì)算廣告的分類：
根據(jù)廣告主的計(jì)費(fèi)方式，可以分為
千次展現(xiàn)付費(fèi) cpm(cost per thousand impressions) 主要用于品牌曝光,例如淘寶的鉆展業(yè)務(wù)
每次點(diǎn)擊扣費(fèi) cpc(cost per click) 通常用于文本廣告,例如百度鳳巢，google adwords
成交/行為付費(fèi) cpt/cpa(cost per transaction/action) 例如淘寶客業(yè)務(wù)
根據(jù)展現(xiàn)形式分為:圖片廣告[graphical ads]、文本廣告[textual ads]、視頻等。
根據(jù)不同的產(chǎn)品形式分為
搜索廣告(sponsored search)，例如百度鳳巢，google adwords
上下文廣告[contexual ads]，例如google adsense
展示廣告[display ads]，例如淘寶鉆展業(yè)務(wù)線
定向廣告[targeting ads]，例如google adsense
在互聯(lián)網(wǎng)中，搜索廣告是最主要的文本廣告的形式。
互聯(lián)網(wǎng)廣告的意義：
廣告支撐起了互聯(lián)網(wǎng)上一個(gè)巨大的生態(tài)系統(tǒng)：
1.內(nèi)容提供商通過(guò)廣告賺錢，養(yǎng)活了 宏觀/微觀的內(nèi)容提供商 [就是各種大小網(wǎng)站]
2.精準(zhǔn)觸達(dá)/定向使得長(zhǎng)尾生意成為可能
3.廣告主的收入使得大批“免費(fèi)”的服務(wù)成為可能：facebook, google, twitter,yahoo
如果沒(méi)有廣告，互聯(lián)網(wǎng)就不可能像現(xiàn)在這么發(fā)展迅速、規(guī)模宏大。廣告給消費(fèi)者提供了直接和間接的巨大價(jià)值。
計(jì)算廣告的參與方：
1.流量提供方(publishers)
2.廣告主(advertisers)
3.瀏覽者/用戶(users)
4.廣告平臺(tái)/廣告網(wǎng)絡(luò)(match maker/ad network)
這些參與者有各自不同的訴求：流量提供者渴望每次展現(xiàn)/搜索的高收益，廣告主渴望高投資回報(bào)率(roi)和流量，用戶希望高相關(guān)性，廣告網(wǎng)絡(luò)渴望收益與市場(chǎng)份額。而廣告的選擇，就是要兼顧四個(gè)參與者的收益，達(dá)到最優(yōu)狀態(tài),需要權(quán)衡長(zhǎng)期和短期的商業(yè)目標(biāo)。
計(jì)算廣告對(duì)性能的要求很高：
億級(jí)別：
搜索廣告中有數(shù)億級(jí)別的廣告
每個(gè)小時(shí)有億級(jí)別的搜索
萬(wàn)億級(jí)別頁(yè)面展現(xiàn)次數(shù)
億級(jí)的用戶
毫秒級(jí)別：
請(qǐng)求是在用戶“等待”過(guò)程中完成的，必須在100ms內(nèi)返回錢：
每個(gè)請(qǐng)求都需要消耗cpu資源
數(shù)據(jù)通常放在內(nèi)存中 [需要大量?jī)?nèi)存，而內(nèi)存比硬盤貴]
每次請(qǐng)求的耗費(fèi)必須比收益要低
過(guò)低的點(diǎn)擊率(ctr)使得上面的挑戰(zhàn)更加困難
搜索廣告：
什么是搜索廣告(sponsored search)：
搜索廣告是由搜索關(guān)鍵詞驅(qū)動(dòng)的廣告。廣告主選擇一個(gè)“競(jìng)價(jià)詞”，當(dāng)用戶觸發(fā)某個(gè)搜索請(qǐng)求時(shí)，廣告主的廣告得以展現(xiàn)。
業(yè)界的系統(tǒng)：google adwords, 百度鳳巢，淘寶搜索直通車
在上文中我們提到的計(jì)算廣告中有4個(gè)參與方，在搜索廣告中，流量提供方是搜索結(jié)果頁(yè) serp(search results page)，通常流量提供方和廣告平臺(tái)是同一個(gè)(google，bing)，當(dāng)然也可以不一樣(微軟給雅虎提供廣告搜索)。
在搜索廣告中三個(gè)參與者之間有如下的交互行為：
廣告主：
1.提交廣告，購(gòu)買相關(guān)的競(jìng)價(jià)詞
2.為了獲得好的展示位置而競(jìng)價(jià)
3.為獲得的點(diǎn)擊付費(fèi)
瀏覽者：給搜索引擎提交查詢串，表達(dá)一定的意圖
搜索引擎：
1.根據(jù)用戶的查詢串在web頁(yè)面語(yǔ)料庫(kù)和廣告語(yǔ)料庫(kù)中分別進(jìn)行檢索
2.把自然搜索結(jié)果和廣告搜索結(jié)果結(jié)合到一起，展示在搜索結(jié)果頁(yè) serp上
搜索廣告中存在的三個(gè)子問(wèn)題
從搜索引擎的角度來(lái)看，搜索廣告中存在三個(gè)子問(wèn)題：
1.廣告檢索
2.給拿到的廣告排序
3.根據(jù)點(diǎn)擊收費(fèi)
以上三個(gè)順序是搜索廣告事件發(fā)生的順序,這里面1和2屬于信息檢索問(wèn)題，而2和3又屬于微觀經(jīng)濟(jì)學(xué)問(wèn)題。
文章一開頭提到了計(jì)算廣告中涉及到了博弈論，拍賣理論，機(jī)制設(shè)計(jì)，到底在哪里用到了呢?想了解這些疑問(wèn)就得接著往下看。
對(duì)于目前的搜索廣告來(lái)說(shuō)，都被設(shè)計(jì)成了拍賣的機(jī)制。搜索引擎拍賣的是每個(gè)流量中可能的廣告位，廣告主提交對(duì)購(gòu)買的關(guān)鍵詞的每次點(diǎn)擊的最高出價(jià)，廣告主是不知道其他人的出價(jià)信息的。雖然每個(gè)流量中一般會(huì)有多個(gè)廣告位置，但是廣告主只出一個(gè)價(jià)格。最終搜索引擎根據(jù)廣告主競(jìng)價(jià)和廣告的點(diǎn)擊率ctr來(lái)對(duì)廣告進(jìn)行排序，決定最終的展示位置?！?br>點(diǎn)擊扣費(fèi)時(shí)，目前普遍采用的是google發(fā)明的廣義第二價(jià)格扣費(fèi)gsp(general second price)，有兩種策略：
競(jìng)價(jià)排序：根據(jù)廣告的出價(jià)倒序排列，位于第i個(gè)的廣告支付第i+1個(gè)廣告的競(jìng)價(jià)
根據(jù)廣告平臺(tái)的收益排序：根據(jù)期望最大收益ecpm來(lái)排序
ecpm=bidprice*ctr
被點(diǎn)擊的廣告主i付的費(fèi)用為
price=bidprice(i+1)*(ctr(i+1)/ctr(i))
由于bidprice(i)*ctr(i)>bidprice(i+1)*ctr(i+1),可以從上述公式看到廣告主實(shí)際扣費(fèi)肯定小于最高出價(jià)
在廣告搜索引擎中，不能直接拿著用戶的查詢串在倒排索引中進(jìn)行廣告檢索的，因?yàn)檫@樣可能導(dǎo)致搜出來(lái)的廣告深度不夠，而且查詢多種多樣，在搜索引擎有限的資源下，不可能對(duì)所有查詢建立倒排索引，所以需要經(jīng)過(guò)查詢改寫來(lái)改寫出歸一化后的多個(gè)搜索詞，用這些搜索詞去檢索廣告。
查詢改寫(query rewrite)
把用戶查詢(query)改寫成競(jìng)價(jià)詞(bidword)的過(guò)程。總的來(lái)說(shuō)有離線(offline)改寫和在線改寫(online)兩類。
離線改寫：
在離線的時(shí)候利用相對(duì)在線而言更多的數(shù)據(jù)來(lái)處理用戶的查詢，生成一個(gè)query->bidword的映射關(guān)系表，缺點(diǎn)是只能給那些高頻詞進(jìn)行離線處理。這里有兩個(gè)問(wèn)題：我們應(yīng)該改寫哪些查詢--我們需要市場(chǎng)深度的查詢上。我們應(yīng)該改寫成什么樣的查詢--那些市場(chǎng)深度足夠的查詢上。
在線改寫：
對(duì)于離線不能處理的少數(shù)請(qǐng)求需要我們進(jìn)行在線改寫，在線改寫相對(duì)離線而言，資源受限(內(nèi)存限制，時(shí)間限制)，需要在很短的時(shí)間(數(shù)ms)內(nèi)做分析。
廣告選擇(ad selection)
給定一個(gè)查詢，搜索引擎可以展示兩類廣告：
精確匹配em(exact match): 廣告主對(duì)特定的查詢競(jìng)價(jià)
高級(jí)匹配am(advanced match)或廣泛匹配(broad match): 廣告主并不對(duì)特定的詞進(jìn)行競(jìng)價(jià)，但是這個(gè)查詢被認(rèn)為是廣告主感興趣的。
搜索廣告中的流量具有長(zhǎng)尾效應(yīng)，非常多的長(zhǎng)尾流量查詢?cè)谒阉鲝V告中沒(méi)有對(duì)應(yīng)的廣告，高級(jí)匹配主要是為了解決這相當(dāng)一部分流量沒(méi)有被競(jìng)價(jià)的問(wèn)題，廣告主不關(guān)心競(jìng)價(jià)詞，他們只關(guān)心轉(zhuǎn)化--賣掉商品。如何覆蓋到相關(guān)的流量呢，從引擎的角度出發(fā)，高級(jí)匹配比精確匹配更有挑戰(zhàn)性。
兩階段廣告選擇
在廣告搜索引擎中，廣告語(yǔ)料庫(kù)中的廣告數(shù)量巨大，高達(dá)百萬(wàn)之多，而實(shí)際展示的過(guò)程中，只有極少數(shù)量的廣告能夠展示出來(lái)，目前業(yè)界普遍采用兩階段廣告選擇來(lái)解決性能問(wèn)題。
廣告檢索過(guò)程中，整個(gè)廣告的選擇分為兩部分：
廣告檢索(ad retrieval):從整個(gè)廣告語(yǔ)料庫(kù)里面選出一個(gè)最可能的候選集合。此過(guò)程是粗選階段，我們用來(lái)排序的目標(biāo)函數(shù)(例如評(píng)估相關(guān)性)可能和最終排序的函數(shù)(例如ecpm)不同。
廣告重排序(ad reordering)：利用更多的數(shù)據(jù)來(lái)對(duì)第一階段返回的有限的候選廣告集合進(jìn)行更為精細(xì)，更為復(fù)雜的計(jì)算。這個(gè)階段必須綜合考慮競(jìng)價(jià)和相關(guān)性分?jǐn)?shù)(例如ecpm)。
對(duì)于廣告重排序階段，目前有兩種主流的方法，以賽馬為例：
反應(yīng)式(reactive)：選定一匹馬，根據(jù)它的歷史成績(jī)來(lái)預(yù)測(cè)未來(lái)的表現(xiàn)
預(yù)估式(predictive)：根據(jù)體重，腿長(zhǎng)等特征為賽馬建模，找到這些特征在預(yù)測(cè)比賽名次終的重要程度，然后基于這些特征來(lái)給見(jiàn)過(guò)、未見(jiàn)過(guò)的賽馬預(yù)測(cè)成績(jī)。
當(dāng)我們擁有對(duì)某賽馬的足夠信息的時(shí)候，就使用這些信息(反應(yīng)性)，否則使用模型(預(yù)測(cè)性)。