Adwords问题与算法简介

1、Adwords问题与算法简介,廖海仁 2011.2.24,问 题,什么是Adwords问题？ Adwords算法如何解决Adwords问题？ Adwords与Adsense的区别与联系？ 什么是竞价排名？ Google与Baidu广告模式的区别？ Adwords对行为定向广告的借鉴意义？,常见媒体的赚钱方式?,Newspaper(报纸) Magazine(杂志) Radio(广播) TV(电视) Web(网络),常见媒体的赚钱方式,Newspaper / Magazine Subscription(订阅) + Advertising(广告） Radio / TV Advertising(广告）

2、 Web 主要是Advertising(广告），有什么特别之处？,Web的独特之处,The Web offers an opportunity to tailor display ads in a way that hardcopy media cannot: it is possible to use information about the user to determine which ad they should be shown. (网络的最独特之处是它能利用用户的信息）,关于广告显示的一些基本观察,广告的位置对点击率有重大影响 第一个位置有比其他位置有高得多的点击率 点击率对于查

3、询的词汇有依赖 比如汽车广告，与“汽车”关键词匹配的广告点击率很高 相对于传统杂志，特别杂志对广告有很大影响，比如在汽车杂志上投放汽车广告比在一般杂志上效果要好得多 在门户网站首页上显示的广告效率相对较低,On-Line and Off-Line Algorithm,Off-line Algorithm(离线算法) 所有算法需要的数据预先准备好，算法可以以任何顺序处理数 据，最后得出结果 On-line Algorithm(在线算法) 流数据挖掘，我们只能存储一定量的流，极端情况，每一流元素到达时，都需要产生结果。（搜索关键词相关广告算法就是这种算法）,The Competitive Rati

4、o (竞争比),竞争分析是用来分析在线算法的一种方法，其中，在线算法的性能通过与最优的离线算法的性能相比较。 一个在线算法是“有竞争性的”，如果其竞争比有界。 竞争比是所有输入所取得结果的下限,Adwords问题定义,A set of bids by advertisers for search queries （对于每一搜索查询有一个广告主出价集合） A click-through rate for each advertiser-query pair (对每一查询的每一广告有不同的点击率） A budget for each advertiser （每一广告主有固定的预算） A limit

5、 on the number of ads to be displayed with each search query (每一次搜索显示的广告数量有限） The objective is to maximize the total revenue at the end of the day while respecting the daily budgets of the bidders (目标是最大化收益，同时尊重每一位广告主的预算),The Maximal Matching Problem(最大匹配问题),Given a bipartite graph, A matching is a

6、subset of the edges such that no node is an end of two or more edges(匹配） A matching is said to be perfect if every node appears in the matching（完全匹配） A matching that is as large as any other matching for the graph in question is said to be maximal(最大匹配）,二分图与完全匹配,最大匹配问题的贪心算法,算法：考虑以某一顺序给的边(x, y)。如果x,

7、y都还没有在已选的匹配中，将此边加入到匹配中; 否认，忽略(x, y)。 比如前面的二分图，以字符顺序排列，表示为 (1, a), (1, c), (2, b), (3, b), (3, d), (4, a) 贪心匹配为: (1, a), (2, b), (3, d) 贪心匹配并非最大匹配（最大匹配边数为4） 如果二分图排序为(1，a), (3, b) 则只能匹配2个,关于贪心算法的一个结论,最大匹配问题的贪心算法的竞争比是1/2 定义：Mo : 最大匹配 Mg : 贪心匹配 L: 在Mo而不在Mg的左节点集合 R: 联结任一L集合的右节点集合 证明： 1）|Mo| =|Mo|/2, 但是由以

8、上观察可知， 竞争比不大于1/2，所以竞争比=1/2,Adwords问题的简化,a) There is one ad shown for each query b) All advertisers have the same budget（b) c) All click-through rates are the same d) All bids are either 0 or 1. Alternatively, we may assume that the value of each ad is the same,Adwords问题解决史,(1990) R.M. Karp, U.V. Vaz

9、irani, and V.V. Vazirani. An optimal algorithm for online bipartite matching. 提出一个竞争比为1-1/e的随机算法RANKING（针对二分图匹配问题），并且证明没有一个随机在线算法的竞争比能超过此值。 (2000) Bala Kayaanasundaram and Kirk Pruhs. An optimal deterministic algorithm for online b-matching. 提出一个竞争比趋向于1-1/e的确定性算法BALANCE（针对b匹配问题），并且证明确定性算法竞争比的下限为1-1/

10、e。（基本思路：将关键词匹配给剩下余额最多的广告主） (2005) Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani (Google). Adwords and generalized on-line matching. 证明对于b-matching问题，没有随机性算法的竞争比能超过1-1/e(对于大的b),并得到一个最优的竞争比为1-1/e的算法。解决了一般化的在线匹配问题。,实际Adwords与模型的差别,关键词实际使用“宽匹配”，而不是精确匹配 广告主有不同的日广告预算 广告主在不同时间进来 一次搜索可匹配多个广告 广告主只在用户点击了广告之后付费。实际会考虑广告的质量，而不完全是竞价(广告质量= 竞价*点击率) 、 模型使用first-price auction, 实际上使用second-price auction. 每次点击价格=（下一名出价 x 下一名关键词质量度)/ 当前关键词质量度 + $0.01。second-price auction对广告主的欺诈更不敏感,Adwords Vs Adsense,Adwords是针对广告商的，而AdSense是针对发布商的 。 Adwords是花钱的，Adsense是赚钱的。 AdWords匹配的是用户输入的关键词，AdSense则