Adwords问题与算法简介

Adwords问题与算法简介廖海仁2011.2.24问题什么是Adwords问题？Adwords算法如何解决Adwords问题？Adwords与Adsense的区别与联系？什么是竞价排名？Google与Baidu广告模式的区别？Adwords对行为定向广告的借鉴意义？常见媒体的赚钱方式?Newspaper(报纸)Magazine(杂志)Radio(广播)TV(电视)Web(网络)常见媒体的赚钱方式Newspaper/MagazineSubscription(订阅)+Advertising(广告）Radio/TVAdvertising(广告）Web主要是Advertising(广告），有什么特别之处？Web的独特之处TheWeboffersanopportunitytotailordisplayadsinawaythathardcopymediacannot:itispossibletouseinformationabouttheusertodeterminewhichadtheyshouldbeshown.(网络的最独特之处是它能利用用户的信息）关于广告显示的一些基本观察广告的位置对点击率有重大影响第一个位置有比其他位置有高得多的点击率点击率对于查询的词汇有依赖比如汽车广告，与“汽车”关键词匹配的广告点击率很高相对于传统杂志，特别杂志对广告有很大影响，比如在《汽车》杂志上投放汽车广告比在一般杂志上效果要好得多在门户网站首页上显示的广告效率相对较低On-LineandOff-LineAlgorithmOff-lineAlgorithm(离线算法)所有算法需要的数据预先准备好，算法可以以任何顺序处理数据，最后得出结果On-lineAlgorithm(在线算法)流数据挖掘，我们只能存储一定量的流，极端情况，每一流元素到达时，都需要产生结果。（搜索关键词相关广告算法就是这种算法）TheCompetitiveRatio(竞争比)竞争分析是用来分析在线算法的一种方法，其中，在线算法的性能通过与最优的离线算法的性能相比较。一个在线算法是“有竞争性的”，如果其竞争比有界。竞争比是所有输入所取得结果的下限Adwords问题定义Asetofbidsbyadvertisersforsearchqueries（对于每一搜索查询有一个广告主出价集合）Aclick-throughrateforeachadvertiser-querypair(对每一查询的每一广告有不同的点击率）Abudgetforeachadvertiser（每一广告主有固定的预算）Alimitonthenumberofadstobedisplayedwitheachsearchquery(每一次搜索显示的广告数量有限）Theobjectiveistomaximizethetotalrevenueattheendofthedaywhilerespectingthedailybudgetsofthebidders(目标是最大化收益，同时尊重每一位广告主的预算)TheMaximalMatchingProblem(最大匹配问题)Givenabipartitegraph,Amatchingisasubsetoftheedgessuchthatnonodeisanendoftwoormoreedges(匹配）Amatchingissaidtobeperfectifeverynodeappearsinthematching（完全匹配）Amatchingthatisaslargeasanyothermatchingforthegraphinquestionissaidtobemaximal(最大匹配）二分图与完全匹配最大匹配问题的贪心算法算法：考虑以某一顺序给的边(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个关于贪心算法的一个结论最大匹配问题的贪心算法的竞争比是1/2定义：Mo:最大匹配Mg:贪心匹配L:在Mo而不在Mg的左节点集合R:联结任一L集合的右节点集合证明：1）|Mo|=|Mg|+|L|,因为在左边的节点中，只有L中的节点能匹配Mo但不在Mg中2）|L|=|R|,因为在Mo中，所有L中的节点都匹配上了3）|R|=|Mg|,R中每一节点在Mg中有匹配右上可知，|Mg|=|Mo|/2,但是由以上观察可知，竞争比不大于1/2，所以竞争比=1/2Adwords问题的简化a)Thereisoneadshownforeachqueryb)Alladvertisershavethesamebudget（b)c)Allclick-throughratesarethesamed)Allbidsareeither0or1.Alternatively,wemayassumethatthevalueofeachadisthesameAdwords问题解决史(1990)R.M.Karp,U.V.Vazirani,andV.V.Vazirani.Anoptimalalgorithmforonlinebipartitematching.提出一个竞争比为1-1/e的随机算法RANKING（针对二分图匹配问题），并且证明没有一个随机在线算法的竞争比能超过此值。(2000)BalaKayaanasundaramandKirkPruhs.Anoptimaldeterministicalgorithmforonlineb-matching.提出一个竞争比趋向于1-1/e的确定性算法BALANCE（针对b匹配问题），并且证明确定性算法竞争比的下限为1-1/e。（基本思路：将关键词匹配给剩下余额最多的广告主）(2005)AranyakMehta,AminSaberi,UmeshV.Vazirani,andVijayV.Vazirani(Google).Adwordsandgeneralizedon-linematching.证明对于b-matching问题，没有随机性算法的竞争比能超过1-1/e(对于大的b),并得到一个最优的竞争比为1-1/e的算法。解决了一般化的在线匹配问题。实际Adwords与模型的差别关键词实际使用“宽匹配”，而不是精确匹配广告主有不同的日广告预算广告主在不同时间进来一次搜索可匹配多个广告广告主只在用户点击了广告之后付费。实际会考虑广告的质量，而不完全是竞价(广告质量=竞价*点击率)、模型使用first-priceauction,实际上使用second-priceauction.每次点击价格=（下一名出价x下一名关键词质量度)/当前关键词质量度+$0.01。second-priceauction对广告主的欺诈更不敏感AdwordsVsAdsenseAdwords是针对广告商的，而AdSense是针对发布商的。Adwords是花钱的，Adsense是赚钱的。AdWords匹配的是用户输入的关键词，AdSense则是匹配网站的内容。Adwords基本投放在搜索引擎上，而Adsense的投放则是嵌入到广告联盟的网站中。其背后的算法基础都是一个通用匹配问题，Google还将Adwords竞价匹配Email一些启示一个难题的解决可以先将其化为简单的情形一个难题的解决非一日之功他山之石，可以攻玉媒体关联与行为定向的广告是值得关注的Thanks!