计算广告-刘鹏

微博：@北冥乘海生2021/5/91互联网广告概述2021/5/92广告的作用什么是广告(Advertising)？广告是由已确定的出资人通过各种媒介进行的有关产品(商品、服务和观点)的，通常是有偿的、有组织的、综合的、劝服性的非人员的信息传播活动。广告的主体出资人(sponsor)即广告主(advertiser)，媒介(medium)，受众(audience)广告的本质是借助某种有广泛受众的媒介的力量，完成较低成本的用户接触(reach)2021/5/93关于互联网广告在线广告支撑了整个互联网行业的大半壁江山。不了解互联网广告，就不可能深入了解互联网。互联网广告是迄今为止，大数据领域唯一形成规模化营收的应用。互联网广告是结合了计算技术、心理学、经济学、营销学等的综合应用。2021/5/94美国互联网广告增长趋势2021/5/95中国互联网广告增长趋势2021/5/96品牌广告(Brand

Awareness)创造独特良好的品牌或产品形象,目的在于提升较长时期内的离线转化率/programs/view/t7vIISf65cI2021/5/97效果广告(Direct

Response)有短期内明确用户转化行为诉求的广告。用户转化行为例如：购买,注册,投票,捐款等.2021/5/98

Interactive

Advertising

Bureau在线广告供给方的行业协会，推动数字化市场营销行业的发展制定市场效果衡量标准和在线广告创意的标准会员:Google,Yahoo,Microsoft,Facebook等AmericanAssociationofAdvertisingAgencies主要的协议是关于广告代理费用的收取约定(17.65%)，以避免恶意竞争主要集中在创意和客户服务，在线业务是一部分会员：Ogilvy

&

Mather,JWT,McCann等,Dentsu等非4A会员的大公司但也被列为4A公司AssociationofNationalAdvertisers主要代表广告需求方的利益(也有媒体和代理会员)会员：AT&T,P&G,NBA等广告行业协会2021/5/99互联网广告

产品与市场2021/5/910概念：变现、广告与销售潜在用户有较明确需求者媒体价值2021/5/911媒体概念的差异化2021/5/912在线广告类型条幅广告(Banner)文字广告(Textual)邮件营销(EDM)

2021/5/913在线广告类型视频广告(video)富媒体广告

(RichMedia)2021/5/914在线广告简史搜索广告上下文广告CPM定向广告CPD广告精准定向广告广告网络广告交易市场线下广告竞价合约2021/5/915什么是流量变现？站内流量RPM水平的不断提升典型产品：搜索广告、导航广告、门户品牌广告、社交网站信息流广告什么是数据变现？获取站外流量，通过对用户行为的理解，提升其RPM水平从而获得差价是流量变现的护城河，不断吸引广告主的关键典型产品：AdNetwork(网盟),DSP，DMP流量变现vs数据变现2021/5/916广告网络(网盟，AdNetwork)承接媒体剩余流量，同时接入长尾广告主，在流量与媒体之间撮合变现的产品百度联盟、阿里妈妈、Adsense自助交易终端(AutoTradingDesk)服务于广告主，在各种不同类型的广告网络和媒体上一站式采买流量的产品广告交易市场(AdExchange)承接媒体剩余流量，并以实时竞价的方式进行广告交易的产品淘宝Tanx，GoogleAdx,百度BES数据变现产品形式2021/5/917需求方平台(DemandSidePlatform,DSP)代表广告主，按照灵活的人群划分，以实时竞价的方式从AdExchange里采买流量的产品MediaV聚效、Invitemedia、好耶Winmax、品友网站分析(WebAnalytics,WA)帮助网站主分析站内流量来源和效果的工具GA、百度统计、量子统计、聚合分析数据管理平台(DataManagementPlatform,DMP)收集广告主或媒体端数据，在确保用户隐私的前提下加工成标签，在广告市场上售卖是WA产品的自然延伸数据变现产品形式2021/5/918互联网广告市场供给方(Supply)需求方(Demand)2021/5/919

相关公司产品布局

产品类型搜索营销聚优广告发布系统广告交易平台BES广告网络DSPATD网站分析/DMP广告安全In-app移动广告联盟App统计2021/5/920计算广告基础知识2021/5/921互联网广告技术特点技术和计算导向数字媒体的特点使在线广告可以按人群投放广告决策和交易朝着计算驱动的方向发展可衡量性广告的点击是效果的直接收集途径98至今，Banner点击率从10%降至0.1%标准化技术投放和精准定向促进了在线广告标准化

在标准化方面做了很多贡献2021/5/922广告有效性模型曝光(exposure)关注(attention)理解(comprehension)信息接受(messageacceptance)保持(retention)购买(purchase)阶段主要原则1.1.主要取决于广告位的天然属性2.1不要干扰或打断用户的任务2.2明确揭示推荐的原因2.3符合用户兴趣或需求3.1广告在用户能理解的兴趣范围3.2与关注程度相匹配的理解门槛4.1广告商/广告认可度

(+/-)4.2广告位认可度

(+/-)5.1艺术性带来的记忆效果6.1在用户的价格敏感接受范围内选择解释态度2021/5/923一些广告策略的效果曝光(exposure)关注(attention)理解(comprehension)信息接受(messageacceptance)保持(retention)购买(purchase)幽默

(2+,3-)性感

(2+,4?)折扣

(2+,6+)艺术

(3-,

5+)仿背景(2.1+):1.仿网页文字链2.尽量靠近网页色调简单(2,3.2+):1.留白吸引用户关注2.减少同时表达的诉求大标识(2+):1.显著大于背景字体2.logo尽量显著传统广告策略分析在线广告创意原则2021/5/924计算广告核心挑战广告中的计算问题给定用户

u,上下文环境c,找到最合适的广告创意

a.从优化角度来看特征提取：受众定向微观优化：eCPM估计宏观优化：竞价市场机制受限优化：在线分配强化学习：探索与利用个性化重定向：推荐技术从系统角度来看整体框架：广告服务器候选查询：实时索引特征存储：No-sql技术离线学习：Hadoop在线学习：流计算交易市场：实时竞价2021/5/925在线广告技术课题大规模(Scale)百万量级的页面，十亿量级的用户，需要被分析处理高并发在线投放系统(例:Rightmedia每天处理百亿次广告交易)Latency的严格要求(例:adexchange要求竞价在100ms内返回)动态性(Dynamics)用户的关注和购物兴趣非常快速地变化丰富的查询信息(Richquery)需要把用户和上下文中多样的信号一起用于检索广告候选探索与发现(Explore&exploit)用户反馈数据局限于在以往投放中出现过的(a,u,c)组合，需要主动探索未观察到的领域，以提高模型正确性2021/5/926搜索、广告与推荐的比较搜索搜索广告显示广告推荐首要准则相关性(relevence)投资回报率(ROI)用户兴趣其他需求各垂直领域独立定义质量，安全性(Safety)多样性(diversity),新鲜度(freshness)索引规模~十亿级~百万级--千万级~百万级~百万级--亿级个性化较少的个性化需求~亿级用户规模上的个性化检索信号较为集中较为丰富Downstream优化不适用`适用2021/5/927投资回报率-ROI投入广告资源的成本，在多数情形下是线下合同约定的在DSP产品中，投入的成本是可以优化的回报Return=

点击率点击价值(payoff) eCPM2021/5/928在线广告计费模式不同的eCPM分解对应不同的市场形态CPM结算:固定eCPM，供给方风险最小需求方的市场部门承担eCPM估计的任务CPC结算:动态CTR,固定clickvalue供给方估计点击率，需求方估计点击价值，对效果广告较为合理CPS/CPA/ROI结算:供给方负责估计eCPM并没有看上去上去那么美好…CPT/CPD结算:中国特色的结算方法2021/5/929在线广告系统数据高速公路内部及外部TB级数据实时收集处理高并发投送系统十毫秒级别的实时决策百亿次/天的广告投放系统受众定向平台灵活的海量数据挖掘平台前沿机器学习算法的分布式架构流式计算平台日志的准实时挖掘和反馈反作弊与计价2021/5/930在线广告系统模块2021/5/931用开源工具搭建广告系统AvroHbaseS4ChuhwaPigBigTableGFSChubbyZooKeeperHiveOozieElephant-birdStormScribe2021/5/932跨语言服务搭建工具-跨语言服务快速搭建(c++,java,python,ruby,c#

…)用struct定义语言无关的通信数据结构:struct

KV

{1:optionali32key=10;2:optional

stringvalue=“x”}用service定义RPC服务接口:serviceKVCache{voidset(1:i32key,2:stringvalue);stringget(1:32key);voiddelete(1:i32key);}将上述声明放在IDL文件(比如service.thrift)中,用thrift–r–gencppservice.thrift生成服务框架代码能实现结构体和接口的Backwardcompatible类似工具：Hadoop子项目Avro，Google开发的ProtoBuf2021/5/933合约广告2021/5/934广告位售卖–CPD售卖供给方：广告排期系统

帮助媒体自动执行多个合同的排期不提供受众定向，可以将广告素材直接插入页面需求方：代理商帮助广告商策划和执行排期用经验和人工满足广告商质和量的需求典型场景品牌条幅广告2021/5/935担保式投送–CPM售卖担保式投送(GuaranteedDelivery,GD)基于合约的广告机制，未完成约定量要向广告商补偿多采用千次展示付费(CostperMille,CPM)方式结算广告投放机(Adserver)CPM方式要求广告投送由服务器端完成决策受众定向、流量预测是广告投放的基础典型场景视频广告、机顶盒广告2021/5/936简化的流量配送模型供给节点(SupplyNodes,定向标签的最细组合)需求节点(DemandNodes,订单要求的定向标签组合)假设：节点内部的流量差异可以忽略2021/5/937拉格朗日方法原问题(Primaryproblem)拉格朗日(Lagrangian)对偶问题(Dual

problem)等式约束下的几何意义见右KKT条件为保证此方法有效的条件凸优化情形下满足KKT条件，但注意一些非凸优化也满足对偶函数(Dual

function)2021/5/938在线随机分配算法

(withFreedisposal)对每个a,初始化对偶变量βa为0当展示i在线到达时,将其分配给a’以最大化μia

−βa令xia’=1.

如果a’已经得到Ca’次展示,令i’为使得此值最小的展示,令xia’=0在对偶问题中,令zi=μia’

−βa’,并按照一定规则更新βa’,

不同更新规则对应了不同的算法对偶问题：原问题：2021/5/939βa更新策略策略算法有效性Greedy对每个a,βa是分配给a的前Ca个高权重展示中最低的权重,也即a接受一个新的展示需要抛弃的权重1/2competitiveUniformWeighting对每个a,βa是分配给a的前Ca个高权重展示的权重的算术平均.如果分配给a的展示少于Ca个,βa是这些展示总权重与Ca的比.1/2competitiveExponentialWeighting对每个a,βa是分配给a的前Ca个高权重展示的权重的指数加权。即：设μ1

≤μ2≤

…≤μCa，则：当Ca对每个a都充分大时为(1−1/e)competitive2021/5/940流量预测指导下的在线分配目的利于历史数据为在线分配提供指导在线决策时避免存储xia(compactallocationplan)HWM(HighWaterMark)算法离线计划：令每个人群维度组合k的剩余supply等于预测量rk

=sk按照分配优先级对每个a，解下式得到其servingrateαa

:对Γ(a)中的每个k,令rk

=rk–min{rk,skαa}在线分配对在线到来的某个impression,A={a1,a2,…,a|A|}为按照分配优先级排序的所有满足要求的广告按照A中的每个广告的servingrate随机分配其展示机会2021/5/941核心业务：GD,无法分配的流量转接到NGD(non-guaranteeddelivery,即Rightmediaexchange)进行变现GD市场广告主数量为几千，年收入为Billion量级其他点评：采用compactallocationplan完成线上决策提供下列受众定向地域、人口属性、行为(较为粗浅，常用的仅有几十个分类)合约式销售中，品牌广告主对曝光有独占要求2021/5/942担保式投送系统框架2021/5/943受众定向2021/5/944中国互联网用户桌面2021/5/945受众售卖vs广告位售卖2021/5/946A(d)U(ser)C(txt)上的标签体系受众定向即为AUC打标签的过程上下文标签可以认为是即时受众标签标签的两大主要作用建立面向广告主的流量售卖体系为各估计模块(如CTR预测)提供原始特征2021/5/947常见受众定向方式曝光(exposure)关注(attention)理解(comprehension)信息接受(messageacceptance)保持(retention)购买(purchase)阶段定向方式上下文(2.1,3.1)重定向(2.2,2.3,3.1)行为(2.3,3.1)地域(2.3,4.1)人口属性(2.3,3.1,6.1)网站/频道(2.3,3.1,4.2)效果作用阶段Hyper-local

(2.3,4.1)Look-alike(2.3,3.1,4.1,6.1)(见DSP部分)2021/5/948上下文定向(Contextualtargeting)根据用户正在浏览的页面和其他信息投送广告举例GoogleAdsense早期产品2021/5/949上下文定向主要技术举例频道/URL定向，操作系统定向按关键词、主题、分类等进行定向与行为定向相比，架构有较大区别常用方法用规则将页面归类到一些频道或主题分类提取页面中的关键词提取页面入链锚文本中的关键词提取页面流量来源中的搜索关键词用主题模型将页面内容映射到语义空间的一组主题上2021/5/950半在线(Near-line)抓取系统用在线cache系统存储url->特征表以提供实时访问不预先加载任何cache内容，对cache中不存在的url,立刻返回空特征,同时触发相应的页面爬虫和特征提取设置cache系统合适的失效时间以完成特征自动更新2021/5/951页面主题分析-TopicModel问题:发现一组文档中抽象的主题(topics)常用模型图表示PLSILDA(LatentDirichletallocation)GaP(Gamma-Poisson)p(w|•),p(z|•):Multinomialp(π|•),p(θ|•):Dirichletp(z|•):Gammap(w|•):Poisson2021/5/952经验贝叶斯–EmpiricalBayes如下图模型,如何确定hyperparameter?EB解:当为指数族分布，为其共轭先验时，可用EM求解,其中E-step为Bayesianinference过程,由得到后验参数,而M-step为:2021/5/953从经验贝叶斯看LDALDA可以视为PLSI的经验贝叶斯版本由于PLSI不是指数族分布，而是其混合分布，因此其贝叶斯版本不能使用前面的EM算法Deterministicinference:可用变分近似，假设z和θ的后验分布独立迭代求解过程与EM非常相似，称为VBEM在大多数问题上无法保证收敛到局部最优Probabilisticinference:可用Gibbs-sampling(Markov-chainMonte-Carlo,MCMC,的一种)，以概率1收敛到局部最优值CollapsedGibbs-sampling:2021/5/954Topicmodel的并行化EM及VBEM的并行化E-step(mapper):可以方便地并行计算M-step(reducer):累加E-step各部分统计量后更新模型将更新后的模型分发到新的E-step各个计算服务器上AD-LDA:Gibbs

Sampling的并行化Mapper:在部分data上分别进行GibbssamplingReducer:全局Update文档的Topicmodel抽取可以认为是一个大量(而非海量)数据运算，采用类MPI架构的分布式计算架构(例如spark)会比map/reduce效率更高2021/5/955行为定向(Behaviortargeting)根据用户历史上网记录和其他数据总结出用户兴趣，根据此投放广告举例YahooBT(BehaviorialTargeting)2021/5/956受众定向标签体系举例YahooBT标签体系：Finance-BankAccounts,CreditCards,Investiment,Insurance,Loans,RealEstate,...Service-Local,Wireless,Gas&Electric,...Travel-Europe,Americas,Air,Lodging,Rail,...Tech-Hardware,Software,Consumer,Mobile,...Entertainment-Games,Movies,Television,Gambling,...Autos-Econ/Mid/Luxury,Salon/Coupe/SUV,...FMCG-Personalcare,...Retail-Apparel,Gifts,Home,......Other-Health,Parenting,Moving,...2021/5/957Bluekai标签体系类别描述数据来源规模(用户数)Intent最近输入词表现出某种产品或服务需求的用户BluekaiIntent160+MMB2B职业上接近某种需求的用户Bizo12+MMPastPurchase根据以往消费习惯判断可能购买某产品的用户Addthis,Alliant65+MMGeo/Demo地理上或人口属性上接近某标签的用户Bizo,Datalogix,ExpediaInterest/LifeStyle可能喜欢某种商品，或某种生活风格的用户Forbes,i360,IXI103+MMEstimatedFinancial根据对用户财务状况的估计做的分类V122021/5/958

核心业务：主要提供面向publisher的数据加工服务直接运营adnetwork，并帮助广告主进行campaign管理和优化其他点评：较早提出受众定向(audiencetargeting)的概念数据标签不像bluekai那样在市场上公开出售,仅供委托他们优化campaign的广告商使用使用标签impression创造的营收按照一定比例跟publisher分成2021/5/959行为定向数据来源用户标识除上下文和地域外各种定向的基础，需要长期积累和不断建设可以通过多家第三方ID绑定不断优化用户行为业界公认有效行为数据（按有效性排序）交易，预交易，搜索广告点击，广告点击，搜索，搜索点击，网页浏览，分享，广告浏览需去除网络热点话题带来的偏差越靠近demand的行为对转化越有贡献越主动的行为越有效2021/5/960行为定向数据来源广告商(Demand)数据简单的cookie植入可以用于retargeting。对接广告商种子人群可以做look-alike，提高覆盖率。用户属性和精确地理位置非媒体广告网络很难获取，需通过第三方数据对接。移动互联和HTML5为获得地理位置提供了便利性。社交网络朋友关系为用户兴趣和属性的平滑提供了机会实名社交网络的人口属性信息相对准确2021/5/961行为定向计算过程t(i)(u)：用户u在标签i上的强度2021/5/962行为定向其他问题Sessionlog将各种行为日志整理成以用户ID为key的形式，完成作弊和无效行为标注，作为各数据处理模块的输入源可以将targeting变成局部计算，大大方便整个流程Long-term行为定向两种多日累积方式滑动窗方式(f为long-term标签,下标为日期)

时间衰减方式(空间复杂度低，仅需昨天的f和今天的t)

2021/5/963受众定向评测–Reach/CTR曲线2021/5/964竞价广告2021/5/965竞价广告–CPC售卖2021/5/966位置拍卖市场位置拍卖(Positionauctions)将对象

a={1,2,…A}

排放到位置s={1,2,…,S}对象a的出价(bid)为ba

,而其对位置s的计价为uas=vaxs,(x1>x2>…>xS)将va视为点击价值，xs视为点击率，该模型可近似描述广告系统竞价问题(对显示广告，S=1)对称纳什均衡(SymmetricNashequilibrium)(vs–ps)xs>=(vs–pt)xt,其中pt=bs+1寻找收入最大化且稳定的纳什均衡状态是竞价系统设计的关键2021/5/967定价机制VCG(Vickrey–Clarke–Groves)机制某对象的收费应等于给他人带来的价值损害整体市场是truth-telling的

广义第二高价(Generalizedsecondpricing)机制ps=rs+1/μs+1=μs+1bs+1/μs+1与VCG机制相比，会收取广告主更多的费用整体市场不是truth-telling的

简单易行，为在线广告系统广泛采用

2021/5/968广告检索广告投放条件过滤可以视为布尔表达式检索问题布尔表达式检索的一些概念DocDNF:(age∈{3}^state∈{NY})∨(state∈{CA}^gender∉{M})Conjunction:age∈{3}^state∈{NY},state∈{CA}^gender∉{M}.同一属性在某Conjunction里只出现一次Assignment:age∈{3},state∈{NY},state∈{CA},…sizeof[Conjunction]:conjunction包含非∉的Assignment个数基本思想某查询满足conjunction，也就满足包含此conjunction的doc.维护两层倒排关系:Conjunction->DocId,Assignment->ConjunctionId如果sizeof(Conjunction)大于sizeof(query)，则无需考虑2021/5/969布尔表达式检索广告投放条件过滤可以视为布尔表达式检索问题布尔表达式检索的一些概念DocDNF:(age∈{3}^state∈{NY})∨(state∈{CA}^gender∉{M})Conjunction:age∈{3}^state∈{NY},state∈{CA}^gender∉{M}.同一属性在某Conjunction里只出现一次Assignment:age∈{3},state∈{NY},state∈{CA},…sizeof[Conjunction]:conjunction包含非∉的Assignment个数基本思想某查询满足conjunction，也就满足包含此conjunction的doc.维护两层倒排关系:Conjunction->DocId,Assignment->ConjunctionId如果sizeof(Conjunction)大于sizeof(query)，则无需考虑2021/5/970布尔表达式检索–

index算法建立第一层Index遍历文档DNF的Conjunction，如果为新的，则分配一个新ID(从0递增)，否则用之前分配的ConjunctionID；文档分配DocID（从0递增)；写入conjunction到doc的倒排关系，形成第一层Index对于上步出现的新Conjunction，建立第二层Index：将Conjunction切成Assignment流，Term为(属性,值)，例:age∈{3;4}切成两个Term:(age,3),

(age,4)；state∉{CA;NY}也切成两个Term:(state,CA),

(state,NY)，∉和∈体现在倒排链表上计算Conjunction的size，将size体现在Term中，最终的Term的组成是(sizeof[Conjunction],属性,值)对于size为0的Conjunction，添加一个特殊的Term：Z，∈写入倒排关系,Term->(ConjunctionID,∈|∉)+2021/5/971布尔表达式检索–

index示例doc1=(age∈{3}^state∈{NY})∨(state∈{CA}^gender∈{M})=c1∨c4doc2=(age∈{3}^state∈{F})∨(state∉{CA;NY})=c2∨c6doc3=(age∈{3}^gender∈{M}^state∉{CA})∨(state∈{CA}^gender∈{F})=c3∨c7doc4=(age∈{3;4})∨(state∈{CA}^gender∈{M})=c5∨c4doc5=(state∉{CA;NY})∨(age∈{3;4})=c6∨c5doc7=(age∈{3}^state∈{NY})∨(state∈{CA}^gender∈{F})=c1∨c7doc6=(state∉{CA;NY})∨(age∈{3}^state∈{NY})∨(state∈{CA}^gender∈{M})=c6∨c1∨c4第一层倒排:(conjunction->doc)c1->doc-1,doc-6,doc-7c2->doc-2c3->doc-3c4->doc-1,doc-4,doc-7c5->doc-4,doc-5c6->doc-2,doc-5,doc-7c7->doc-3,doc-6第二层倒排:(assignment->conjunction)0

(state,

NY)

[(c6,

∉)(c8,

∉)](state,

CA)

[(c6,

∉)]

Z

[(c6,

∈)]1

(age,

3)

[(c5,

∈)](age,

4)

[(c5,

∈)]2

(age,

3)

[(c1,

∈),

(c2,

∈),

(c3,

∈)](state,

NY)

[(c1,

∈)]

(gender,

F)

[(c2,

∈),

(c7,

∈)]

(gender,

M)

[(c3,

∈),

(c4,

∈)](state,

CA)

[(c3,

∉),

(c4,

∈),

(c7,

∈)]2021/5/972长Query情况下的相关性检索根据(u,a)广告检索时(考虑上下文定向情形)Query有可能比较长,且子Term都是Should传统搜索引擎需要将所有出现过以上Term的文档都取出来，然后计算相关性并找到Top-N，在长Query和大文档集时查询速度被巨大的计算量所限制一种可行的思路在查找候选DOC的过程中做一个近似的评估，切掉那些理论上不需要再考虑的文档，只对进候选的文档进行相关性计算，比Top-N最小堆最小值大的插入当相关性函数为线性时，存在有效的剪枝算法2021/5/973Weight-And(WAND)检索算法文档和Query相似度:Term贡献上界ub:文档相关性上界UB:检索算法概要step-1:按doclist最前面的docID对terms排序step-2:迭代terms，并累加UB直至大于堆顶，设此时到达第n-1个term，如果terms[0].doc和terms[n-1].doc一样，逼出一个doc至最小堆；如果不一样，在前n个term挑选一个skip到terms[n-1].doc，跳转至step-1.2021/5/974基于WAND的上下文定向检索相关性SearchWANDExactduplicate0.0%0.8%Nearduplicate7.1%9.5%Veryrelated44.4%64.5%Weaklyrelated24.0%18.0%Unrelated21.1%8.0%内容类别SearchWANDPolitics0.44%0.39%Business0.74%1.02%Entertainment0.97%1.32%Crime0.57%1.20%Sport1.65%2.27%Health0.47%0.57%Science0.52%0.35%SocialIssues0.28%0.43%Lifestyle0.17%0.24%Unrest0.33%0.39%Disaster0.10%0.16%Overall0.49%0.68%实验为上下文内容推荐，目的是同时检测算法是否倾向于给出“Duplicate”的结果编辑相关性评测(左)&

线上测试CTR对比(右)2021/5/975流量预测可以视为query为a,对(u,c)进行检索的反向retrieval问题由于(u,c)

联合空间规模过大，需要对u,c分别处理例：上下文页面(c)索引c,#impressionc,pc(eCPM)预测过程：给定a,首先通过c的索引找出所有符合条件c的集合对每个c估计e(a,c)，并根据pc(eCPM)得到a在c上胜出的百分比p(a,c),并将a的流量累加p(a,c)ⅹ#impressionc上下文页面该页面流量该页面eCPM分布2021/5/976点击率预测点击预测概率模型:Regression比Ranking合适一些广告的实际排序是根据eCPM，因此需要尽可能准确估计CTR，而不仅仅是各候选的CTR排序正确新广告的cold-start利用广告层级结构(creative,solution,campaign,advertiser)，以及广告标签对新广告点击率做估计捕获点击率的动态特性动态特征:快速调整特征在线学习:快速调整模型2021/5/977逻辑回归(LogisticRegression)LogisticRegression模型logistic函数(sigmoid函数一种)视角1：Logisticregression

为Generalizedlinearmodel

在Binomialerror情形的特例视角2：Logisticregression为Maximumentropymodel在类数目等于2情形的特例n维特征权重矢量(参数)

n维特征矢量2021/5/978逻辑回归优化方法–L-BFGSBFGS(Broyden,Fletcher,Goldfarb,andShanno)Quasi-Newton方法的一种，思路为用函数值和特征的变化量来近似Hession矩阵，以保证正定性，并减少计算量BFGS方法Hession计算公式(空间复杂度为O(n2))：L(imitedmemory)-BFGS将nⅹn的Hession阵用右图方式

加以近似(Bk为Hession近似)空间复杂度降为将O(nⅹk),在特

征量大时比BFGS实用可以非常容易地用map/reduce实现分布式求解：mapper求部分数据上的梯度，reducer求和并更新参数2021/5/979ADMM方法AlternatingDirectionMethodofMultipliers形式AugmentedLagrangian及迭代解法ScaledForm:()2021/5/980逻辑回归的ADMM分布式解法样本划分的逻辑回归ADMM问题分布式迭代解2021/5/981动态特征-多层次点击反馈在标签组合维度上聚合点击反馈统计作为CTR预测的特征优势:工程架构扩展性强(与在线学习相比)对新(a,u,c)组合有较强back-off能力缺点:在线特征的存储量大，更新要求高组合维度举例:cookie(u)

andcreative(a)gender(u)andtopic(c)location(u)andadvertiser(a)Category(a)andcategory(u)cookie(u)creative(a)gender(u)2021/5/982归一化点击率特征-COEC有效展示可以通过Eyetracking测算工程上可以使用ExpectedClick(EC)来近似有效展示EC的计算实测法：实际随机流量测算Bias模型法：只使用与广告决策无关的bias特征训练的CTR模型：EC

=

pbias(a,u,c)归一化点击率是同样有效的展示么？2021/5/983在线广告常见bias特征广告位位置搜索广告：North1,North2,…,East1,East2,…显示广告：相对页面的(x,y)广告位尺寸广告位类型门户首页,频道首页,内容页,客户端,…创意类型图片,flash,富媒体,…操作系统和浏览器日期和时间2021/5/984点击反馈的平滑问题:在数据稀疏的情况下较稳健地估计CTR或COEC经验贝叶斯方案点击产生概率模型(Binomial分布,其中为点击率):视

为随机变量,采用Beta分布共轭先验进行regularization:生成模型图示意:2021/5/985经验贝叶斯解E-step:M-step:点击率的平滑通常在每个维度组合上分别进行物理意义：数据不足时，更依赖于相应维度组合的点击率先验值维度组合内的点击率分散程度对先验值的作用有影响思考：对COEC的平滑可以采用什么模型？2021/5/986评测指标–PR曲线PRcurve2021/5/987评测指标–AUCROCcurveAUC2021/5/988探索与利用(E&E)问题为长尾的(a,u,

c)组合创造合适的展示机会以积累统计量，从而更准确地估计其CTR提升整体的广告收入，即需要严格控制探索的量和有效性方法思路通常描述为Multi-armBandit(MAB)问题有限个arms(或称收益提供者)a,每个有确定有限的期望收益E(rt,a)在每个时刻t,我们必须从arms中选择一个,最终目标是优化整体收益基本方法为ε–greedy:将ε比例的小部分流量用于随机探索广告问题中的主要挑战海量的组合空间需要被探索各个arm的期望收益是动态变化的2021/5/989E&E算法-UCB方法思路在时间t,通过以往的观测值以及某种概率模型,计算每个arm的期望收益的upperconfidencebound(UCB)，并选择UCB最大的arm我们不可能一直选择非最优的arm,原因是我们选择的此arm次数越多,其UCB就越接近于其期望收益具体UCB策略β-UCB策略:依一个很大的概率,我们选择非最优arms的次数存在着一个上界,该上界与总的选择次数无关UCB-tuned策略:我们已选择的次数越多,就越可以自信地抛弃不太有前途(但仍有可能最优)的arm.2021/5/990E&E算法–ContextualBandit问题描述对每次展示，每个arm(广告)a有一个对应的特征矢量x(u,a)用此特征矢量代替arm本身进行Bandit决策LinUCBDisjointlinearmodel:参数()的岭回归(Ridgeregression)解:{Da}#特征维度ⅹ#样本数为观测样本，ca为回报(广告中是点击)矢量特征空间内的UCB策略:2021/5/991AdNetwork系统架构示意2021/5/992搜索广告特点广告网络的特殊形式用户定向标签f(u):远远弱于上下文影响，一般可以忽略Session内的短时用户搜索行为作用很重要上下文定向标签f(c):关键词典型位置竞价模式分为北，南，东三个广告区块根据各位置的referencectr决定

各位置在竞价系统中的位次referencectr可以通过ε流量较准

确测定出NorthSouthEast2021/5/993查询词扩展(QueryExpansion)基于推荐的方法挖掘(session,query)矩阵找到相关query,可类比(user,item)矩阵利用的是搜索数据基于语义的方法用topicmodel或概念化的方法中找语义相关query利用的是其他文档数据基于收益的方法根据实际eCPM统计得到变现能力最好的相关query利用的是广告数据2021/5/994用户相关的搜索广告决策结果个性化对于搜索广告作用有限上下文信息(c)太强,个人兴趣可以忽略搜索页上的结果需要保证主题上某种一致性广告展示条数是可以深度个性化的约一半的用户无法明确区分广告与搜索结果在平均广告条数的约束下，可以对每个用户的广告条数进行个性化，以最大化营收又一个约束优化问题！可以根据同一session内的行为调整广告结果2021/5/995短时用户行为反馈短时用户行为狭义:用户在一个session内的行为广义:用户在短时间(一般为一刀两天)内的行为短时用户行为反馈短时受众定向:根据短时行为为用户打上的标签短时点击反馈:根据短时广告交互计算的动态特征短时用户行为计算需要准实时(分钟级)对用户行为进行加工，不适合在Hadoop上进行可以利用流式计算(streamcomputing)平台,如S4,Storm等2021/5/996流式计算平台-

StormTopologyTasks大规模实时数据处理框架,自动完成数据分发和可靠性管理,开发者只需要关注处理逻辑.数据流基本在网络和内存进行计算逻辑类似Map/Reduce,区别在调度数据而非调度计算2021/5/997广告购买平台(TradingDesk)产品目标:Allowsadvertisersbuyaudienceacrosspublishersandadnetworks关键特征:连接到不同媒体和广告网络，为广告商提供universalmarketplace非实时竞价campaign的ROI优化能力经常由代理公司孵化出来2021/5/998非RTB流量的ROI优化目标:给定总预算，在多广告网络中采买并优化ROI(例:SEM)若干关键问题:在合适的流量segment上投放广告SEM中的选词显示广告网络中的标签组合选择在每个投放上合理地出价以优化ROI与RTB不同，采买方无法控制每次展示的出价u,c的取值未知，需要在各流量分割上估计其分布并合理出价对每个segment的量以及Marketprice进行预估，以完成整体的优化2021/5/999

核心业务：为搜索广告主提供大量关键词情形下的ROI优化服务，并收取固定比例的提成核心技术为PortfolioOptimization目前正在向显示广告领域扩张其他点评：核心竞争力除了算法还来自于长时间数据积累被Adobe收购的原因是Omniture的数据，现改名AdobeAdlens2021/5/9100在线广告市场结构示意DSP1Media1Media2Media3Adnet1Adnet2AdxDSP2Agency1ATDAdvertiserSSPAgency12021/5/9101广告实时交易2021/5/9102实时竞价多方参与的过程分为cookiemapping和adcall两阶段主要技术点：Adx与DSP之间的用户身份同步(cookiemapping)DSP数量较多时的服务和带宽成本优化2021/5/9103广告交易平台关键特征:用实时竞价(RTB)方式连接广告和

(上下文，用户)按照展示上的竞价收取广告主费用类比:实时竞价股票实时交易广告交易市场证券交易所需求方平台券商代表:

GoogleAdx,Rightmedia,AdECN,Tanx2021/5/9104

核心业务：提供媒体网络和广告主网络之间的交易平台提供托管和RTB两种交易模式其他点评：在很长一短时间内并没有RTB模式目前是北美最大的广告交易平台，每天100亿次展示，有相当部分流量来自yahoo的remnant流量与Doubleclick的公开市场模式有一些不同与DMP合作以提高定向精准性和市场流动性2021/5/9105AdExchange系统架构示意2021/5/9106CookieMapping三个核心问题：谁发起？在哪里发起？谁存mapping表？2021/5/9107需求方平台

(DemandSidePlatform,DSP)定义:以实时竞价的方式、从广告交易市场上购买广告资源，并优化广告效果的产品关键特征:广告主自定义的人群划分跨媒体流量采购通过ROI估计来支持RTB代表:InviteMedia,MediaMath2021/5/9108DSP系统架构示意2021/5/9109

核心业务：传统业务是提供比较透明的Adx采买功能，并收取固定比例的佣金正在提供越来越深入的采买ROI优化服务其他点评：随着Google的DFA,Adx,InviteMedia的整合，可以减少cookiemapping带来的损失新版的Invitemedia将会改称doubleclickbidmanager,并提供更多的优化功能2021/5/9110重定向(Retargeting)2021/5/9111重定向的分类网站重定向(Siteretargeting)根据用户在广告主网站上的行为进行重定向搜索重定向(Searchretargeting)根据用户与广告主相关的搜索行为进行重定向个性化重定向(Personalizedretargeting)根据用户在广告主网站上关注的具体产品和购买阶段，推送商品粒度的广告不再推送已购买产品，而是推荐相关产品对广告主而言，可以视为一个站外推荐引擎2021/5/9112

核心业务：基于站外推荐的个性化重定向系统动态创意技术与广告主商品库的准实时feed接口其他点评：并不是完全采用RTB购买流量，而是有相当部分采用优选CPM购买方式在广告主端完全采用CPC结算方式不会将cross-site数据用于推荐全球有~600人，2012年营收将有数亿美元的规模2021/5/9113

核心业务：主要提供搜索重定向功能，服务于品牌广告商其他点评：按照固定CPM与广告主结算，并购买较低价CPM实现套利目前主要采用非RTB采买方式，刚收购了一家小的RTB技术公司全球有~150人，商业模式决定了目前主要是销售驱动2021/5/9114新客推荐(Look-alike)问题:对于中小电商，仅对老用户定向营销远远不够对于某些类型的广告商，大多数用户无法通过重定向渠道捕捉，例如银行新客推荐:由广告商提供一部分种子用户，DSP通过网络行为的相似性为其找到潜在用户是一种广告商自定义标签，可视为扩展重定向在同样reach水平下，效果应好于通用标签2021/5/9115电商网站浏览行为客户购买搜索关键词分析用户具体行为，匹配针对性广告展示延续广告对搜索该关键词用户贴标签展示对应广告展示对应广告网站重定向搜索重定向站外推荐电商网站提供用户购物阶段数据同一用户，访问搜狐匹配与关键词对应标签定制化定向功能新客推荐分析行为相似性找到潜在用户展示对应广告客户提供种子用户3124200-300%ROI↑50-100%ROI↑2021/5/9116从电商角度看推荐站内推荐站外推荐新客推荐pv:…,search:…,adc:…,share:…pv:…,search:…,adc:…,share:…看起来很相似！2021/5/9117广告流量交易方式实时竞价(RTBD)优选(Preferred)网络优化(