搜索
当机器学习邂逅行为经济学--浅谈计算广告中的机器学习问题刘铁岩高级研究员/主任研究员微软亚洲研究院8/31/2013Tie-YanLiu@MSRA1蓬勃发展的互联网产业8/31/2013Tie-YanLiu@MSRA2在线广告8/31/2013Tie-YanLiu@MSRA3展示广告搜索广告约750亿元/年年增长率40~50%电子商务8/31/2013Tie-YanLiu@MSRA4C2C电子商务B2C电子商务约10万亿元/年增长率20~30%社交网络8/31/2013Tie-YanLiu@MSRA5微博微信网民覆盖率高;变现手段有待加强互联网产业催生“大数据+机器学习”搜索日志，点击记录，交易记录，竞价数据，Check-in数据回帖、转帖…点击率预测，转换率预测，广告机制优化，产品推荐，LBS推荐社交圈挖掘…互联网产业伴生着海量数据互联网产业包含众多机器学习任务大规模机器学习8/31/2013Tie-YanLiu@MSRA6举例：搜索广告中的机器学习8/31/2013Tie-YanLiu@MSRA7网络搜索的“免费午餐”88/31/2013Tie-YanLiu@MSRA提交查询词，点击广告相应用户搜索请求，显示查询结果和广告搜索引擎网络用户广告主广告平台创建广告，竞拍关键词通过拍卖过程决定广告的排序和收费搜索广告的台前-幕后Tie-YanLiu@MSRA8/31/20139=4fdc0a28050c-9BCACF0210B560E9TitleAdDescriptionDisplayURLLandingpageURLLandingPageAdCopy用户所见所得广告主的推广计划搜索广告的算法框架8/31/2013Tie-YanLiu@MSRA10广告筛选排序广告数据库查询词定价点击预测拍卖机制点击预测核心技术模块：机器学习用于广告点击率预测过滤排序收费点击率𝑝𝑖=𝑃(𝑐𝑖=1|𝑥𝑖)查询词广告上下文点击标签特征抽取i…𝑥1𝑖𝑥2𝑖𝑥3𝑖⋮𝑥𝑑𝑖…⋯𝑐𝑖⋯机器学习点击率预测模型历史8/31/2013Tie-YanLiu@MSRA11机器学习用于广告点击率预测•将查询词、用户、广告表示成特征向量•用Logistic函数定义点击概率•通过（正则化的）最大似然技术学习参数向量𝒘:8/31/2013Tie-YanLiu@MSRA12𝑝≡𝑃𝑐=1𝑥=11+exp(−𝑗=1𝑤𝑗𝑥𝑗)𝒘=argmax𝒘(𝑖=1𝑛log𝑃𝑐𝑖𝑥𝑖+log(𝑃(𝒘)))机器学习用于广告机制优化𝑏2𝑏1𝑏3广告主点击率竞价𝑝1𝑝2𝑝3拍卖机制排序函数𝑓𝑖𝑝,𝑏•例如：𝑓𝑖𝑝,𝑏=𝑝𝑖𝑏𝑖.收费函数𝑔𝑖(𝑝,𝑏)•例如：𝑔𝑖𝑝,𝑏=𝑝𝑖+1×𝑏𝑖+1𝑝𝑖.广义二价拍卖机制（GSP）8/31/2013Tie-YanLiu@MSRA13机器学习用于广告机制优化•RankLogistic[Zhuetal.SIGIR2009]•训练数据：•历史拍卖数据(包含查询词、竞价、点击数据）•经验利润:•替代目标函数：8/31/2013Tie-YanLiu@MSRA14机器学习应用能否水到渠成？•统计机器学习•互联网产业中的学习问题“冰冷”的物理世界数据分布与模型无关独立同分布采样学习泛化学习机器博弈环境“有血有肉”的人数据分布与模型有关学习影响学习机器现实情况：当把学到的模型投入产品，人的行为会受模型影响，数据分布也会发生变化。理想假设：学到的模型不会影响物理世界，独立同分布采样保障学习过程的泛化能力8/31/2013Tie-YanLiu@MSRA15如何突围？•机器学习过程中需考虑人的行为经济学(心理学+经济学)•感性-人有情感、有心理需求•通过心理建模和心理暗示，从“预测人的行为”到“引导人的行为”•理性-人会趋利避害、试图最大化自己的效用•通过对用户行为建模（描述人如何对模型/机制的改变作出博弈反应），学到在用户行为改变后仍然表现优异的模型/机制8/31/2013Tie-YanLiu@MSRA16利用心理学理解和引导用户点击行为8/31/2013Tie-YanLiu@MSRA17点击率预测中的常用特征•内容及上下文–What•用户和查询词的信息•广告本身的质量•查询词和广告的相关性•季节、工作日/周末、上班/休息时间•地域信息•历史点击–How•其他用户在历史上如何对广告进行点击8/31/2013Tie-YanLiu@MSRA18信息检索的手段统计的手段What↛Why解释：•对于常见的查询词，广告的相关性很接近，区分度不高。•用户来搜索引擎是为了搜信息，而不是搜广告。广告是被推送给用户的，他们没有义务仔细查看广告内容。以相关性特征为例：常用特征BM25作为分类器AUC仅有0.55(几乎接近随机猜测)(Dataset:15Madimpression,~2Mqueries)8/31/2013Tie-YanLiu@MSRA19How↛Why解释：•用户之间存在很大差异：即便对于同一支广告，他们也会表现出个性不同、随时间变化的选择。•在当今个性化的年代，即便别人点击了某支广告，特立独行的我也不见得会人云亦云！对同一查询词和同一个广告，不同的用户所表现出的点击率差别巨大。历史点击数据反映的是不同用户点击率的均值，由于方差很大，它的预测能力有限。CTRrangeCTRrange79.98%20.02%0.00%10.00%20.00%30.00%40.00%50.00%60.00%70.00%80.00%90.00%[0%,15%)[15%,100%]percentageofusersofdifferentCTRRangeCTRrange73.26%24.73%0.00%10.00%20.00%30.00%40.00%50.00%60.00%70.00%80.00%90.00%[0%,15%)[15%,100%]percentageofusersofdifferentCTRRangeCTRrange8/31/2013Tie-YanLiu@MSRA20Why-用户的心理需求的影响8/31/2013Tie-YanLiu@MSRA21Query:nikeFreeNikeCouponsDownloadAndPrintNikeCoupons(100%Free)Nike-SalePricesLatestFashionsandStylesonSale.BuyNikeFast!AKADEMABaseballOutletPRO,ROOKIE,FASTPITCH,APPARELBATS,MITT&GLOVES$7.99-199.99Query:perfumePerfume.comofficialsite10,000+brandnameperfumesandcolognes-upto80%offretail!LuxuryEnglishPerfumeShoponlineforluxuryperfumesformen,women&thehome.!VersacePerfumeTheScentofYou.DiscoverVersacePerfume!折扣、免费权威、可信、折扣0.080.0050.0030.1660.0050Query:HPDriversDownloadHPDriversDownload(Recommended)DownloadHPDrivers.DownloadHPDriversinSeconds.HPDriversDownloadFreeDownload:HPDriversUpdate.Download&InstallHPDriversNowHPDriversDownloads(Recommended)HPPrinterDrivers.HPDriversDownloadCenter.快速、便捷0.4840.1670.1038/31/2013Tie-YanLiu@MSRA22需求模式覆盖的广告比例CTR的变化“coupon”2.2%+47.5%“x%off”4.1%+19.7%“official”2.6%+25.0%“returnguarantee”1.9%+31.4%Why-用户的心理需求的影响用户心理需求的层级结构8/31/2013Tie-YanLiu@MSRA23TopQualityTopBrandsJustforyouFirstClassUltimateExperienceUniqueSpecialtyVIPAdvanceyourcareerAchieveyoursYouridealMomentsofyoursYourdream365DaysReturnOfficialsiteCustomerReviews100%Guaranteed20,000+PCs&LaptopsCall888-888-8888HotelsinChicagoVisa,Amex,PaypalAcceptedFinditNearbySameDayShippingSavemoneyBestpriceCoupon20%Discount30%offFreeShipping生理需求安全需求社交需求尊重需求自我实现需求马斯洛需求层次理论迭代常见模式挖掘过滤人工标注标签传播基于不确定性的主动学习候选模式更新的候选模式最不确定的候选模式广告数据库、日志数据标注的候选模式足够确定的候选模式预处理模式数据库不断更新心理需求𝑝𝑘𝐶(𝑝𝑘)挖掘用户心理需求[Wangetal.KDD2013]8/31/2013Tie-YanLiu@MSRA24层次化聚类投影心理模式的层级结构用户对应的心理需求投影广告对应的心理需求历史点击数据模式数据库8/31/2013Tie-YanLiu@MSRA25挖掘用户心理需求[Wangetal.KDD2013]用户和广告的心理匹配利用心理需求建模进行点击率预测8/31/2013Tie-YanLiu@MSRA260%1%2%3%4%5%6%HF-RFHF-DPFHF-DPLFHF-RF-DPFHF-RF-DPLFRelativegainoverHFMethodRelativegaininRIGRelativegaininCTR实现了4-5%的点击率提升对应上亿美元的收益通过动态改变广告引导用户行为NikeShoeGalleryLatestFashionsandStylesonSale.Versatilechoices.Fastshipment.NikeShoesOnSaleLatestFashionsandStylesonSale.Unbelievablediscount.Upto70%discountNikeShoes–GuaranteedQualityLatestFashionsandStylesonSale.Qualityguarantee.Freereturnwithin7days.NikeShoe–YouNike,YourLifeLatestFashionsandStylesonSale.Bestchoiceforexercises!Improveyourhealthiness,improveyoulifequality!屌丝8/31/2013Tie-YanLiu@MSRA27原始的广告词广告主网页不同用户不同的动态广告通过对人的行为建模学习最优拍卖机制8/31/2013Tie-YanLiu@MSRA28传统机器学习框架定义目标函数通过在大量历史数据上优化目标函数来学习机制的参数将学到的机制应用到未来的测试数据中当数据服从独立同分布假设，且训练样本足够多，所学模型在测试集上可实现有效泛化。8/31/2013Tie-YanLiu@MSRA29•当一个新的经济机制/模型（例如：广告拍卖机制）被应用到实际中以后，它所产生的影响会逐渐被人