計(jì)算機(jī)廣告學(xué)3

搜索與競(jìng)價(jià)廣告1搜索與競(jìng)價(jià)廣告2搜索廣告示例分為北(North)、東(East)、南(South)三個(gè)區(qū)域廣告一般帶有底色位置次序?yàn)椋篘orth1,North2,…,East1,East2,East3,

…南區(qū)或重復(fù)北區(qū)、或重復(fù)東區(qū)3位置拍賣市場(chǎng)位置拍賣(Positionauctions)將對(duì)象

a={1,2,…A}

排放到位置s={1,2,…,S}對(duì)象a的出價(jià)(bid)為ba

,而其對(duì)位置s的計(jì)價(jià)為uas=vaxs,(x1>x2>…>xS)將va視為點(diǎn)擊價(jià)值，xs視為點(diǎn)擊率，該模型可近似描述廣告系統(tǒng)競(jìng)價(jià)問題(對(duì)顯示廣告，S=1)對(duì)稱納什均衡(SymmetricNashequilibrium)(vs–ps)xs>=(vs–pt)xt,其中pt=bs+1尋找收入最大化且穩(wěn)定的納什均衡狀態(tài)是競(jìng)價(jià)系統(tǒng)設(shè)計(jì)的關(guān)鍵4機(jī)制設(shè)計(jì)-定價(jià)廣義第二高價(jià)(Generalizedsecondpricing)機(jī)制與VCG機(jī)制相比，會(huì)收取廣告主更多的費(fèi)用整體市場(chǎng)不是truth-telling的

簡(jiǎn)單易行，為在線廣告系統(tǒng)廣泛采用CPM情形下：

ps=

bs+1+1CPC情形下：ps=rs+1/μs+1=μs+1bs+1/μs+1VCG(Vickrey–Clarke–Groves)機(jī)制某對(duì)象的收費(fèi)等于給他人帶來(lái)的價(jià)值損害：整體市場(chǎng)是truth-telling的

5機(jī)制設(shè)計(jì)其他方法市場(chǎng)保留價(jià)(MarketReservePrice,MRP)即“底價(jià)”，出價(jià)高于MRP才能參與競(jìng)價(jià)計(jì)費(fèi)如果小于底價(jià)，按底價(jià)計(jì)費(fèi)可以根據(jù)不同競(jìng)價(jià)標(biāo)的設(shè)置不同的底價(jià)價(jià)格擠壓

κ為正數(shù)：當(dāng)其充分大時(shí)，只根據(jù)點(diǎn)擊率排序；當(dāng)其接近0時(shí)，只根據(jù)點(diǎn)擊單價(jià)排序

6整體計(jì)價(jià)過程7搜索廣告概貌優(yōu)化目標(biāo)：關(guān)鍵特點(diǎn)：搜索廣告的變現(xiàn)能力即eCPM遠(yuǎn)高于一般顯示廣告搜索廣告的受眾定向標(biāo)簽，即是上下文的搜索查詢搜索廣告樣式與自然結(jié)果的展示形式非常接近，有原生廣告的意味從搜索廣告發(fā)展起來(lái)的競(jìng)價(jià)交易模式，已經(jīng)逐漸發(fā)展成為互聯(lián)網(wǎng)廣告最主流的交易模式8搜索廣告產(chǎn)品新形式①、②：原生化探索③、④：弱相關(guān)廣告形式9搜索廣告系統(tǒng)架構(gòu)10搜索廣告產(chǎn)品策略搜索廣告決策過程：

查詢擴(kuò)展檢索排序

放置定價(jià)關(guān)鍵產(chǎn)品策略：查詢擴(kuò)展、廣告排序、廣告放置

11查詢擴(kuò)展精確匹配英語(yǔ)培訓(xùn)

{英語(yǔ)培訓(xùn),培訓(xùn)英語(yǔ)}短語(yǔ)匹配英語(yǔ)培訓(xùn)

{英語(yǔ)培訓(xùn)暑期班,哪個(gè)英語(yǔ)培訓(xùn)機(jī)構(gòu)好,英語(yǔ)的培訓(xùn),英語(yǔ)相關(guān)培訓(xùn),培訓(xùn)英語(yǔ),英文培訓(xùn),…}等廣泛匹配英語(yǔ)培訓(xùn)

{外語(yǔ)學(xué)習(xí)班,四級(jí)證書,…}否定匹配12廣告放置廣告放置(AdPlacement)問題廣告候選完成排序以后，需要分別確定北區(qū)和東區(qū)的廣告條數(shù)用戶體驗(yàn)指標(biāo)北區(qū)廣告的平均條數(shù)，即NorthFootPrint(NFP)或AverageServingNumber(ASN)廣告放置策略優(yōu)化13查詢擴(kuò)展精確匹配英語(yǔ)培訓(xùn)

{英語(yǔ)培訓(xùn),培訓(xùn)英語(yǔ)}短語(yǔ)匹配英語(yǔ)培訓(xùn)

{英語(yǔ)培訓(xùn)暑期班,哪個(gè)英語(yǔ)培訓(xùn)機(jī)構(gòu)好,英語(yǔ)的培訓(xùn),英語(yǔ)相關(guān)培訓(xùn),培訓(xùn)英語(yǔ),英文培訓(xùn),…}等廣泛匹配英語(yǔ)培訓(xùn)

{外語(yǔ)學(xué)習(xí)班,四級(jí)證書,…}否定匹配14產(chǎn)品概況：Google推出的關(guān)鍵詞競(jìng)價(jià)廣告產(chǎn)品其他點(diǎn)評(píng)：最早按CPM售賣，銷售不理想后來(lái)采用了Overture的CPC售賣，并創(chuàng)造性地引入點(diǎn)擊率概念表達(dá)廣告相關(guān)性，取得了非常高的營(yíng)收2013年?duì)I收374億美元15產(chǎn)品概況：淘寶專門服務(wù)于賣家的廣告產(chǎn)品，在搜索結(jié)果等頁(yè)面上展示競(jìng)價(jià)廣告其他點(diǎn)評(píng)：按CPC售賣，同樣是按照eCPM排名廣告主集中在電商行業(yè)，同時(shí)用戶意圖比通用搜索引擎更強(qiáng)烈與廣告主是共生關(guān)系16競(jìng)價(jià)廣告網(wǎng)絡(luò)聚合媒體剩余流量，以人群為標(biāo)的物進(jìn)行競(jìng)價(jià)售賣17廣告網(wǎng)絡(luò)廣告示例18廣告網(wǎng)絡(luò)概貌優(yōu)化目標(biāo)：關(guān)鍵特點(diǎn)：競(jìng)價(jià)方式不向廣告主做量的約定，而是根據(jù)變現(xiàn)能力，即eCPM，來(lái)決定每次展示分配給哪個(gè)廣告主。按人群售賣，淡化媒體和廣告位的概念無(wú)需再滿足廣告主品牌獨(dú)占的要求采用分成結(jié)算，運(yùn)營(yíng)方的現(xiàn)金流狀況大為改善19廣告網(wǎng)絡(luò)系統(tǒng)架構(gòu)20廣告網(wǎng)絡(luò)產(chǎn)品策略廣告網(wǎng)絡(luò)展示決策過程：

檢索排序

定價(jià)關(guān)鍵產(chǎn)品策略：廣告檢索、廣告排序

21倒排索引文檔集D1=“谷歌地圖之父跳槽Facebook”

D2=“谷歌地圖創(chuàng)始人拉斯離開谷歌加盟Facebook”D3=“谷歌地圖創(chuàng)始人跳槽Facebook與Wave項(xiàng)目取消有關(guān)”D4=“谷歌地圖創(chuàng)始人拉斯加盟社交網(wǎng)站Facebook”關(guān)鍵詞(term)：{谷歌，地圖，之父，跳槽，F(xiàn)acebook，…}倒排鏈：谷歌{D1,D2,D3,D4}，地圖{D1,D2,D3,D4}，之父{D1,D3,D4}，跳槽{D1,D3}，F(xiàn)acebook

{D1,D2,D3,D4}，…22廣告檢索廣告投放條件過濾可以視為布爾表達(dá)式檢索問題布爾表達(dá)式檢索的一些概念DocDNF:(age∈{3}^state∈{NY})∨(state∈{CA}^gender?{M})Conjunction:age∈{3}^state∈{NY},state∈{CA}^gender?{M}.同一屬性在某Conjunction里只出現(xiàn)一次Assignment:age∈{3},state∈{NY},state∈{CA},…sizeof[Conjunction]:conjunction包含非?的Assignment個(gè)數(shù)基本思想某查詢滿足conjunction，也就滿足包含此conjunction的doc.維護(hù)兩層倒排關(guān)系:Conjunction->DocId,Assignment->ConjunctionId如果sizeof(Conjunction)大于sizeof(query)，則無(wú)需考慮23布爾表達(dá)式檢索–

index算法建立第一層Index遍歷文檔DNF的Conjunction，如果為新的，則分配一個(gè)新ID(從0遞增)，否則用之前分配的ConjunctionID；文檔分配DocID（從0遞增)；寫入conjunction到doc的倒排關(guān)系，形成第一層Index對(duì)于上步出現(xiàn)的新Conjunction，建立第二層Index：將Conjunction切成Assignment流，Term為(屬性,值)，例:age∈{3;4}切成兩個(gè)Term:(age,3),

(age,4)；state?{CA;NY}也切成兩個(gè)Term:(state,CA),

(state,NY)，?和∈體現(xiàn)在倒排鏈表上計(jì)算Conjunction的size，將size體現(xiàn)在Term中，最終的Term的組成是(sizeof[Conjunction],屬性,值)對(duì)于size為0的Conjunction，添加一個(gè)特殊的Term：Z，∈寫入倒排關(guān)系,Term->(ConjunctionID,∈|?)+24布爾表達(dá)式檢索–

index示例廣告集合：Conjunctions：倒排索引：25相關(guān)性檢索根據(jù)(u,a)廣告檢索時(shí)(考慮上下文定向情形)Query有可能比較長(zhǎng),且子Term都是Should搜索引擎方案：Term之間取或關(guān)系，然后計(jì)算相關(guān)性并找到Top-N，在長(zhǎng)Query和大文檔集時(shí)查詢速度被巨大的計(jì)算量所限制相關(guān)性檢索在查找候選過程中做近似的評(píng)估，切掉那些理論上不需要再考慮的文檔，只對(duì)進(jìn)候選的文檔進(jìn)行相關(guān)性計(jì)算，比Top-N最小堆最小值大的插入當(dāng)相關(guān)性函數(shù)為線性時(shí)，存在有效的剪枝算法26Weight-And(WAND)檢索算法文檔和Query相似度:Term貢獻(xiàn)上界ut，文檔相關(guān)性上界Ua算法概要step-1:按doclist最前面的docID對(duì)terms排序step-2:迭代terms，并累加UB直至大于堆頂，設(shè)此時(shí)到達(dá)第n-1個(gè)term，如果terms[0].doc和terms[n-1].doc一樣，逼出一個(gè)doc至最小堆；如果不一樣，在前n個(gè)term挑選一個(gè)skip到terms[n-1].doc，跳轉(zhuǎn)至step-1.27點(diǎn)擊率預(yù)測(cè)問題點(diǎn)擊率預(yù)測(cè)，在(a,u,c)組合與點(diǎn)擊間建立關(guān)系：Regression比Ranking合適一些廣告的實(shí)際排序是根據(jù)eCPM，因此需要盡可能準(zhǔn)確估計(jì)CTR，而不僅僅是各候選的CTR排序正確新廣告的cold-start捕獲點(diǎn)擊率的動(dòng)態(tài)特性28邏輯回歸(LogisticRegression)參數(shù)特征LogisticRegression模型

視角1：Generalizedlinearmodel

在Binomialerror情形的特例視角2：Maximumentropymodel在類數(shù)目為2時(shí)的特例29優(yōu)化方法–L-BFGSBFGS(Broyden,Fletcher,Goldfarb,andShanno)Quasi-Newton方法的一種，思路為用函數(shù)值和特征的變化量來(lái)近似Hession矩陣，以保證正定性，并減少計(jì)算量BFGS方法Hession計(jì)算公式(空間復(fù)雜度為O(n2))：L(imitedmemory)-BFGS將Hession逆用右圖方式加以近似空間復(fù)雜度降為將O(nⅹk),30優(yōu)化方法–Trust-RegionBFGS(Broyden,Fletcher,Goldfarb,andShanno)Quasi-Newton方法的一種，思路為用函數(shù)值和特征的變化量來(lái)近似Hession矩陣，以保證正定性，并減少計(jì)算量BFGS方法Hession計(jì)算公式(空間復(fù)雜度為O(n2))：L(imitedmemory)-BFGS將Hession逆用右圖方式加以近似空間復(fù)雜度降為將O(nⅹk),31動(dòng)態(tài)特征-多層次點(diǎn)擊反饋在標(biāo)簽組合維度上聚合點(diǎn)擊反饋統(tǒng)計(jì)作為CTR預(yù)測(cè)的特征優(yōu)勢(shì):工程架構(gòu)擴(kuò)展性強(qiáng)(與在線學(xué)習(xí)相比)對(duì)新(a,u,c)組合有較強(qiáng)back-off能力缺點(diǎn):在線特征的存儲(chǔ)量大，更新要求高組合維度舉例:cookie(u)andcreative(a)gender(u)andtopic(c)category(a)andcategory(u)creative(a),gender(u)32歸一化點(diǎn)擊率-COEC有效展示可以通過Eyetracking測(cè)算工程上可以使用ExpectedClick(EC)來(lái)近似有效展示EC的計(jì)算實(shí)測(cè)法：實(shí)際隨機(jī)流量測(cè)算Bias模型法：只使用與廣告決策無(wú)關(guān)的bias特征訓(xùn)練的CTR模型：

EC

=

pbias(a,u,c)歸一化點(diǎn)擊率是同樣有效的展示么？33在線廣告常見bias特征廣告位位置搜索廣告：North1,North2,…,East1,East2,…顯示廣告：相對(duì)頁(yè)面的(x,y)廣告位尺寸廣告位類型門戶首頁(yè),頻道首頁(yè),內(nèi)容頁(yè),客戶端,…操作系統(tǒng)和瀏覽器廣告投放延遲日期和時(shí)間34點(diǎn)擊反饋的平滑問題:在數(shù)據(jù)稀疏的情況下較穩(wěn)健地估計(jì)CTR或COEC經(jīng)驗(yàn)貝葉斯方案點(diǎn)擊產(chǎn)生概率模型：視μ為隨機(jī)變量,采用Beta分布共軛先驗(yàn)進(jìn)行正則化：35經(jīng)驗(yàn)貝葉斯解E-step:M-step:點(diǎn)擊率的平滑通常在每個(gè)維度組合上分別進(jìn)行物理意義：數(shù)據(jù)不足時(shí)，更依賴于相應(yīng)維度組合的點(diǎn)擊率先驗(yàn)值維度組合內(nèi)的點(diǎn)擊率分散程度對(duì)先驗(yàn)值的作用有影響思考：對(duì)COEC的平滑可以采用什么模型？36點(diǎn)擊率模型的校準(zhǔn)正負(fù)樣本不均衡帶來(lái)的估計(jì)誤差LogisticRegression的校準(zhǔn)37探索與利用(E&E)問題為長(zhǎng)尾的(a,u,c)創(chuàng)造展示機(jī)會(huì)以積累統(tǒng)計(jì)量，從而更準(zhǔn)確估計(jì)CTR提升整體的廣告收入，即需要嚴(yán)格控制探索的量和有效性方法思路通常描述為Multi-armBandit(MAB)問題有限個(gè)arms(或稱收益提供者)a,每個(gè)有確定有限的期望收益E(rt,a)在每個(gè)時(shí)刻t,我們必須從arms中選擇一個(gè),最終目標(biāo)是優(yōu)化整體收益基本方法為ε–greedy:將ε比例的小部分流量用于隨機(jī)探索廣告問題中的主要挑戰(zhàn)海量的組合空間需要被探索各個(gè)arm的期望收益是動(dòng)態(tài)變化的38E&E算法–ContextualBandit問題描述對(duì)每次展示，每個(gè)arm(廣告)a有一個(gè)對(duì)應(yīng)的特征矢量x(u,a)用此特征矢量代替arm本身進(jìn)行Bandit決策LinUCBDisjointlinearmodel:參數(shù)的嶺回歸(Ridgeregression)解:{Da}#特征維度ⅹ#樣本數(shù)為觀測(cè)樣本，ca為回報(bào)(廣告中是點(diǎn)擊)矢量特征空間內(nèi)的UCB策略:39評(píng)測(cè)指標(biāo)–PR曲線(左)與ROC曲線(右)AUC40短時(shí)用戶行為反饋短時(shí)用戶行為狹義:用戶在一個(gè)session內(nèi)的行為廣義:用戶在短時(shí)間(一般為一刀兩天)內(nèi)的行為短時(shí)用戶行為反