大数据存储与应用Web广告课件

1、大数据存储与应用Web广告课程主页：/?page_id=397陈一帅chenyishuai内容背景算法匹配Adwords问题实现背景背景分类的分类直投式广告显示式广告广告信息平台51同城，赶集网二手，租房，。用户搜索，返回广告广告和用户搜索的匹配基于feature，类似搜索引擎问题：如何排序？没有PageRankMost-recent first?可能会被作假。稍微改动一点。用LSH解决根据点击历史，找出最有吸引力的Item挺难的。显示式广告新闻/媒体网站上的广告按Impression付费CPM：Cost per thousand impressions和电视/杂志广告类似问题读者和广告的匹配

2、每次观看，只值几分钱改进网站内容专门化，提高广告和读者的匹配程度。汽车网上，放汽车广告，价格就提上来了。搜索广告的问题按点击付费Overture发明，付费排名（百度）google Adwords改进（搜索结果和广告分开）模式：广告主Bid搜索关键字搜“癌症”，过来一次访问多少钱用户Search queries，提供广告广告主预算（Budget）每个月200元问题如何展示广告，把广告主的预算花光。例算法算法Off-line算法完全知道输入，计算最优策略On-line算法执行算法时，不知道所有的输入类似Stream例：找伴侣买滑板还是租滑板？Adwords是一个On-line问题来一个query，

3、要决定怎么给它显示广告后面来什么query，不知道Online算法性能评估相对于Offline的性能折扣竞争率 Competitive Ratio （CR）最差情况下的性能折扣再差，不会比这差配对找朋友完美配对（Offline）每个节点都在另一边找到对象配对数：4最大配对在可能的情况下，最大配对数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广告一个更复杂的配对问题问题描述问题: 依据关键字，选择广告主在线算法复杂：广告主出价不同: 爱的程度不同广告主有预算（Budget）：每个月200元一个关键字，可以选多个排序影响点击率点了，才能挣钱目标花光广告主预算广告主关键字Bid难题1: CTR收入 = Bid Click Through Rate （CTR），按收入排序问题：如何预测CTR

5、？CTR和算法的互相影响：给它的排序有关CTR预测机器学习问题新Bid冷启动老Bid测量，预测调整最坏情况Bid/Budget：广告主A：沙发：1元广告主B：沙发：1元；凳子：1元预算都是2元查询：先来2个沙发，再来2个凳子。Greedy Online算法：“沙发”全给B，赚2元，把B的预算花光“凳子”来时，B已经没钱了。Offline算法：知道后面还有2个凳子，不能花B的钱。沙发，显示广告主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，最优算法能够把A1，A2的钱都花光。求最差性能性能最差点，出在一个广告主的钱被花光时如果还有钱的话，还能继续花，性能增加（钱花得越多，性能越高）假设A2的钱被花光了，A1的钱还剩x最优非最优，本应给A1的，给了A2证明 y = x有两种可能第一种可能A1给A2的查询 = x非最优，本应给A1的x，给了A2，结果剩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 最差结果（CR）x：剩的钱数x越大，性能越差前面证明了 x N查询：到达N轮，每轮B个查询，这些查询相同B个q1，B个q2，。，B个qN第一轮B个q1，第1N个广告主都想要第二轮的B个q2，第2N个广告主想要。第i轮的B个qi，第iN个广告主想要最优分配第i轮，给第i个广告主，正好把钱花完。共赚NB最坏情形Balance却会把第一轮的B个查询，均匀分到N个用户把第二轮的B个，均匀分到N-1个用户。当 B = 时， AN的钱花完欧拉轮后，AN的钱花完收入=CR =Balance算法的问题没有考虑出价两个广告主A1有110元，对q出价：1元A2有100元，对q出价：10元10个q查询Balance算法：全给A1，赚10元最优算法：全给A2，赚100元改进广告主i，出价xi，总钱数bi，已花钱