Adwords问题与算法简介.ppt

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 Mo 2 但是由以上观察可知 竞争比不大于1 2 所以竞争比 1 2 Adwords问题的简化 a Thereisoneadshownforeachqueryb Alladvertisershavethesamebudget b c Allclick throughratesarethesamed Allbidsareeither0or1 Alternatively wemayassumethatthevalueofeachadisthesame Adwords问题解决史 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则是匹配网站的内容 Adwor