大数据存储与应用Web广告-精选.ppt

大数据存储与应用Web广告-精选
内容
背景
算法
匹配
Adwords问题
实现
背景
背景
分类的分类
直投式广告
显示式广告
广告的分类
广告信息平台（直投）
51同城，赶集网，安居客
媒体网站广她们选择的，却是另外的姑娘唯一看上的
Online Greedy配对
女生Greedy
a -> 1
b -> 3
还有比这更差的吗？
如果没有，CR = 1/2
小伙
姑娘
证明CR = ½
G: girls in Mopt but not in Mgreedy
|Mopt| = |Mgreedy| + |G|
B: Boys who G likes
B肯定已被占了
B在Mgreedy里
|B| <= |Mgreedy|
G in Mopt
G中Girl，有一个或多个Boy和她情投意合
|B| >= |G|
|Mopt|=|Mgreedy| + |G| <= |Mgreedy| + |B| <= 2|Mgreedy|
|Mgreedy| > = 2|Mopt|
CR = 1/2
广告
一个更复杂的配对问题
问题描述
问题: 依据关键字，选择广告主
在线算法
复杂：
广告主出价不同: 爱的程度不同
广告主有预算（Budget）：每个月200元
一个关键字，可以选多个
排序影响点击率
点了，才能挣钱
目标
花光广告主预算
广告主
关键字
Bid
难题1: CTR
收入 = Bid × Click Through Rate （CTR），按收入排序
问题：
如何预测CTR？
CTR和算法的互相影响：给它的排序有关
CTR预测
机器学习问题
新Bid
冷启动
老Bid
测量，预测
调整
简化分析
一个query，显示1个广告
广告主Budget相同：B
广告主出价相同：1
CTR相同
类似我们前面分析过的什么问题？
最坏情况
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更低的吗？
没有了。
证明和前面的一样。
CR = 1/2
改进：BALANCE算法 [MSVV]
Mehta, Saberi, Vazirani, and Vazirani
挑钱剩得多的
例：
广告主A：沙发：1元
广告主B：沙发：1元；凳子：1元
预算都是2元
查询：先来2个沙发，再来2个凳子。
结果：
沙发1，(A,B) 钱 (2,2)，给A，挣1元， (A,B) 钱 (1,2)
沙发2，(A,B) 钱 (1,2)，B钱多，给B，挣1元， (A,B) 钱 (1,1)
凳子1，(A,B) 钱 (1,1)，只有B要，给B，挣1元，(A,B) 钱 (1,0)
凳子2，(A,B) 钱 (1,0)，B要，但没钱
挣3元
CR = ¾？
证明CR = 3/4
A1，A2两个广告主，budget都是B，最优算法能够把A1，A2的钱都花光。
求最差性能
性能最差点，出在一个广告主的钱被花光时
如果还有钱的话，还能继续花，性能增加（钱花得越多，性能越高）
假设A2的钱被花光了，A1的钱还剩x
最优
非最优，本应给A1的，给了A2
证明 y >= x
有两种可能
第一种可能
A1给A2的查询 <=B/2
y + x = B
y >= x
非最优，本应给A1的x，给了A2，结果剩x
证明 y >= x
第二种可能：A1给A2的查询 > B/2
考虑这些查询中的最后一个，称它为q
q分给了A2，意味着：此时，A1的钱一定不比A2多
>= B/2 的A1查询给了A2，意味着：A2至少已花了B/2，所以，它剩下的钱一定不超过B/2
A1的钱，一定也不超过B/2： x <= B/2
x+y = B，所以 x <= y
最差结果（CR）
x：剩的钱数
x越大，性能越差
前面证明了 x <= y
x + y = B
最差情况：x = y = B/2
CR = 3/4
多个广告主时
N个广告主
CR = ～
Offline能全花掉的，Online最坏情况时，只能花掉63%
最坏情况是特定的。
类似于前面的两个广告主的情形。
最坏情形
N个广告主，每个有钱B 。B > N
查询：到达