Adwords问题与算法简介课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Adwords问题与算法简介,廖海仁,2011.2.24,Adwords问题与算法简介廖海仁,1,问 题,什么是Adwords问题？,Adwords算法如何解决Adwords问题？,Adwords与Adsense的区别与联系？,什么是竞价排名？,Google与Baidu广告模式的区别？,Adwords对行为定向广告的借鉴意义？,问 题什么是Adwords问题？,2,常见媒体的赚钱方式?,Newspaper(报纸),Magazine(杂志),Radio(广播),TV(电视),Web(网络),常见媒体的赚钱方式?Newspaper(报纸),3,常见媒体的赚钱方式,Newspaper / Magazine,Subscription(订阅) + Advertising(广告）,Radio / TV,Advertising(广告）,Web,主要是Advertising(广告），有什么特别之处？,常见媒体的赚钱方式Newspaper / Magazine,4,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.,(网络的最独特之处是它能利用用户的信息）,Web的独特之处The Web offers an oppo,5,关于广告显示的一些基本观察,广告的位置对点击率有重大影响,第一个位置有比其他位置有高得多的点击率,点击率对于查询的词汇有依赖,比如汽车广告，与“汽车”关键词匹配的广告点击率很高,相对于传统杂志，特别杂志对广告有很大影响，比如在汽车杂志上投放汽车广告比在一般杂志上效果要好得多,在门户网站首页上显示的广告效率相对较低,关于广告显示的一些基本观察广告的位置对点击率有重大影响,6,On-Line and Off-Line Algorithm,Off-line Algorithm(离线算法),所有算法需要的数据预先准备好，算法可以以任何顺序处理数 据，最后得出结果,On-line Algorithm(在线算法),流数据挖掘，我们只能存储一定量的流，极端情况，每一流元素到达时，都需要产生结果。（搜索关键词相关广告算法就是这种算法）,On-Line and Off-Line Algorithm,7,The Competitive Ratio (竞争比),竞争分析是用来分析在线算法的一种方法，其中，在线算法的性能通过与最优的离线算法的性能相比较。,一个在线算法是“有竞争性的”，如果其竞争比有界。,竞争比是所有输入所取得结果的下限,The Competitive Ratio (竞争比)竞争分,8,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 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 (目标是最大化收益，同时尊重每一位广告主的预算),Adwords问题定义A set of bids by ad,9,The Maximal Matching Problem(最大匹配问题),Given a bipartite graph, A matching is a 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(最大匹配）,The Maximal Matching Problem(最,10,二分图与完全匹配,二分图与完全匹配,11,最大匹配问题的贪心算法,算法：考虑以某一顺序给的边(x, y)。如果x, 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个,最大匹配问题的贪心算法算法：考虑以某一顺序给的边(x, y),12,关于贪心算法的一个结论,最大匹配问题的贪心算法的竞争比是1/2,定义：,Mo : 最大匹配,Mg : 贪心匹配,L: 在Mo而不在Mg的左节点集合,R: 联结任一L集合的右节点集合,证明：,1）|Mo| = |Mg| + |L| ,因为在左边的节点中，只有L中的节点能匹配Mo但不在Mg中,2）|L| = |R| , 因为在Mo中，所有L中的节点都匹配上了,3）|R| =|Mo|/2, 但是由以上观察可知， 竞争比不大于1/2，所以竞争比=1/2,关于贪心算法的一个结论最大匹配问题的贪心算法的竞争比是1/2,13,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问题的简化a) There is one a,14,Adwords问题解决史,(1990) R.M. Karp, U.V. Vazirani, 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/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问题解决史(1990) R.M. Karp,15,实际Adwords与模型的差别,关键词实际使用“宽匹配”，而不是精确匹配,广告主有不同的日广告预算,广告主在不同时间进来,一次搜索可匹配多个广告,广告主只在用户点击了广告之后付费。实际会考虑广告的质量，而不完全是竞价(广告质量= 竞价*点击率),、,模型使用first-price auction, 实际上使用second-price auction. 每次点击价格=（下一名出价 x 下一名关键词质量度)/ 当前关键词质量度 + $0.01。second-price auction对广告主的欺诈更不敏感,实际Adwords与模型的差别关键词实际使用“宽匹配”,16,Adwords Vs Adsense,Adwords是针对广告商的，而AdSense是针对发布商的 。,Adwords是花钱的，Adsense是赚钱的。,AdWords匹配的是用户输入的关键词，AdSense则是匹配网站的内容。,Adwords基本投放在搜索引擎上，而Adsense的投放则是嵌入到广告联盟的网站中。,其背后的算法基础都是一个通用匹配问题，Google还将Adwords竞价匹配Email,Adwords Vs AdsenseAdwords是针对广告,17,一些启示,一个难题的解决可以先将其化为简单的情形,一个难题的解决非一日之功,他山之石，可以攻玉,媒体关联与行为定向的广告是值得关注的,一些启示一个难题的解决可以先将其化为简单的情形,18,Thanks!,Thanks!,19,