1、大數(shù)據(jù)存儲與應(yīng)用Web廣告課程主頁：/?page_id=397陳一帥chenyishuai內(nèi)容背景算法匹配Adwords問題實(shí)現(xiàn)背景背景分類的分類直投式廣告顯示式廣告廣告信息平臺51同城，趕集網(wǎng)二手，租房，。用戶搜索，返回廣告廣告和用戶搜索的匹配基于feature，類似搜索引擎問題：如何排序？沒有PageRankMost-recent first?可能會被作假。稍微改動一點(diǎn)。用LSH解決根據(jù)點(diǎn)擊歷史，找出最有吸引力的Item挺難的。顯示式廣告新聞/媒體網(wǎng)站上的廣告按Impression付費(fèi)CPM：Cost per thousand impressions和電視/雜志廣告類似問題讀者和廣告的匹配

2、每次觀看，只值幾分錢改進(jìn)網(wǎng)站內(nèi)容專門化，提高廣告和讀者的匹配程度。汽車網(wǎng)上，放汽車廣告，價格就提上來了。搜索廣告的問題按點(diǎn)擊付費(fèi)Overture發(fā)明，付費(fèi)排名（百度）google Adwords改進(jìn)（搜索結(jié)果和廣告分開）模式：廣告主Bid搜索關(guān)鍵字搜“癌癥”，過來一次訪問多少錢用戶Search queries，提供廣告廣告主預(yù)算（Budget）每個月200元問題如何展示廣告，把廣告主的預(yù)算花光。例算法算法Off-line算法完全知道輸入，計算最優(yōu)策略O(shè)n-line算法執(zhí)行算法時，不知道所有的輸入類似Stream例：找伴侶買滑板還是租滑板？Adwords是一個On-line問題來一個query，

3、要決定怎么給它顯示廣告后面來什么query，不知道Online算法性能評估相對于Offline的性能折扣競爭率 Competitive Ratio （CR）最差情況下的性能折扣再差，不會比這差配對找朋友完美配對（Offline）每個節(jié)點(diǎn)都在另一邊找到對象配對數(shù)：4最大配對在可能的情況下，最大配對數(shù)Online Greedy配對男生Greedy 1 - a 2 - b 3 - d3對小伙姑娘Online Greedy配對女生Greedy a - 1 b - 3還有比這更差的嗎？如果沒有，CR = 1/2小伙姑娘證明CR = G: girls in Mopt but not in Mgreedy|

4、Mopt| = |Mgreedy| + |G|B: Boys who G likesB肯定已被占了B在Mgreedy里|B| = |G|Mopt|=|Mgreedy| + |G| = |Mgreedy| + |B| = 2|Mopt|CR = 1/2廣告一個更復(fù)雜的配對問題問題描述問題: 依據(jù)關(guān)鍵字，選擇廣告主在線算法復(fù)雜：廣告主出價不同: 愛的程度不同廣告主有預(yù)算（Budget）：每個月200元一個關(guān)鍵字，可以選多個排序影響點(diǎn)擊率點(diǎn)了，才能掙錢目標(biāo)花光廣告主預(yù)算廣告主關(guān)鍵字Bid難題1: CTR收入 = Bid Click Through Rate （CTR），按收入排序問題：如何預(yù)測CTR

5、？CTR和算法的互相影響：給它的排序有關(guān)CTR預(yù)測機(jī)器學(xué)習(xí)問題新Bid冷啟動老Bid測量，預(yù)測調(diào)整最壞情況Bid/Budget：廣告主A：沙發(fā)：1元廣告主B：沙發(fā)：1元；凳子：1元預(yù)算都是2元查詢：先來2個沙發(fā)，再來2個凳子。Greedy Online算法：“沙發(fā)”全給B，賺2元，把B的預(yù)算花光“凳子”來時，B已經(jīng)沒錢了。Offline算法：知道后面還有2個凳子，不能花B的錢。沙發(fā)，顯示廣告主A的廣告，賺2元凳子，顯示廣告主B的廣告，賺2元CR多少？前例：Greedy Online算法，賺2元Offline算法：賺4元性能折扣：2/4 = 1/2還有比1/2更低的嗎？沒有了。證明和前面的一樣。

6、CR = 1/2證明CR = 3/4A1，A2兩個廣告主，budget都是B，最優(yōu)算法能夠把A1，A2的錢都花光。求最差性能性能最差點(diǎn)，出在一個廣告主的錢被花光時如果還有錢的話，還能繼續(xù)花，性能增加（錢花得越多，性能越高）假設(shè)A2的錢被花光了，A1的錢還剩x最優(yōu)非最優(yōu)，本應(yīng)給A1的，給了A2證明 y = x有兩種可能第一種可能A1給A2的查詢 = x非最優(yōu)，本應(yīng)給A1的x，給了A2，結(jié)果剩x證明 y = x第二種可能：A1給A2的查詢 B/2考慮這些查詢中的最后一個，稱它為qq分給了A2，意味著：此時，A1的錢一定不比A2多= B/2 的A1查詢給了A2，意味著：A2至少已花了B/2，所以，它

7、剩下的錢一定不超過B/2A1的錢，一定也不超過B/2： x = B/2x+y = B，所以 x = y 最差結(jié)果（CR）x：剩的錢數(shù)x越大，性能越差前面證明了 x N查詢：到達(dá)N輪，每輪B個查詢，這些查詢相同B個q1，B個q2，。，B個qN第一輪B個q1，第1N個廣告主都想要第二輪的B個q2，第2N個廣告主想要。第i輪的B個qi，第iN個廣告主想要最優(yōu)分配第i輪，給第i個廣告主，正好把錢花完。共賺NB最壞情形Balance卻會把第一輪的B個查詢，均勻分到N個用戶把第二輪的B個，均勻分到N-1個用戶。當(dāng) B = 時， AN的錢花完歐拉輪后，AN的錢花完收入=CR =Balance算法的問題沒有考慮出價兩個廣告主A1有110元，對q出價：1元A2有100元，對q出價：10元10個q查詢Balance算法：全給A1，賺10元最優(yōu)算法：全給A2，賺100元改進(jìn)廣告主i，出價xi，總錢數(shù)bi，已花錢