计算广告中主要模块、策略及其场景(上篇)

514 阅读42分钟
原文链接: mp.weixin.qq.com

本文是我最近学习的一个总结,之前的文章多是和功能特别是广告主界面有关,而本篇文章则是和策略有关。在文章会讲述计算广告(主要是DSP)中的主要模块、用到的策略及其场景。希望大家能和我一样,在了解广告业务的同时,还能对策略的设计有一定了解,总结出一些通用的方法。

本文分三个部分,功能和策略,主讲功能型产品和策略型产品的区别;架构综述,主讲广告系统的流程、模块和技术架构;算法和场景,主讲各个模块和场景中用到的算法。

功能和策略

先下个狭隘的定义,因为找不到比功能/策略更好的词来描述,我在本文中把以UI/UE/人机视觉交互等主要交付物是具体产品形态的产品经理,狭隘的称之为功能产品经理;把以策略/计算逻辑等等主要交付物不是具体产品形态的产品经理,狭隘的称之为策略产品经理。

功能和策略不是非黑即白

一定要注意,本文中的所谓功能和策略产品经理是狭隘的,只是为了方便大家理解和对比。狭隘在于两点:一是对功能和策略的定义太狭隘,所谓视觉交互只是功能的一部分,所谓策略也不只是计算逻辑/算法等等,但为了便于理解就狭隘定义了;二是对产品工作理解太狭隘,实际上策略和功能与活动、文案等都是满足需求和解决问题。方案,产品工作中都会综合运用各种手段去满足需求,关键是满足需求,而非或功能或策略的手段。

因为策略具有无直观产品形态、达到某个目的、受多个因素影响、需根据因素变化随时调整等特点,所以在发现问题-解决问题的产品经理基本工作流程,策略的实际内容与功能略有不同。

发现问题:功能型面对的是场景相对聚焦的需求,重要的是抽象,把需求抽象成问题,把解决方案抽象成功能,抽象出来的多是实体或对象;策略型面对的是更多样更小众更有统计意义的需求,场景更丰富,抽象粒度比功能小,抽象出来的多是变量。

解决方案:功能型产出的是收敛的解决方案,把需求调研和分析得到的结果收敛成较通用的方案,例如微信的注册登录适用于每个用户,每个用户体验到的交互也是一致的。功能型产品通过路程、原型来表达产品实现效果。策略型产出的是发散的解决方案,把需求调研和分析得到的结果发散出多种场景和变量,例如CTR预估中考虑来自广告、用户、场景等多方面的因素。策略型产品通过逻辑描述和效果示例表达产品实现效果。

开发跟进:功能型在跟进开发中,更关注开发结果而非开发过程,过程顶多关心是否可实现和实现原理,面对开发结果是验收的性质。策略型在跟进开发中,更多参与过程,也可以说整个过程就是不断评估测试效果再与RD一起发现各要素中的问题。当然,两者都是要达到目标效果才能上线。

上线回归:功能型因为需求聚焦、方案收敛,能更快地达到理想态,关掉该feature的产品循环。而策略型很有可能会出现永无止境的产品循环,因为策略型需求简单但场景复杂,而且受到很多因素影响,甚至人力都不一定能穷尽。策略要有较强的数据敏感度,拥抱不确定性。

总结一下,功能型产品针对一个相对聚焦的需求,抽象出能够满足80%用户的解决方案,而策略型产品针对一个受复杂因素影响的需求,策略需求比功能需求更长尾。强调一点,在实际运用中,有时把功能和策略结合起来会用更好的效果,例如iPhone调节亮度中包含了手动调节功能和自动调节策略,不要自我设限,目标是解决问题,而不是用什么方法。

架构综述

简单架构

简单架构

广告系统主要解决一个问题:在给定展示场景、用户的情况下,返回收益最大化的广告。上图是一个最简单的DSP广告系统架构,1是收到一个广告展示请求,8是发出针对此次请求的出价、广告创意等。其中,Router、排序模块和检索模块是广告系统的核心,特征计算系统、计费系统和投放系统是用以辅助核心模块的。

Router:对外提供HTTP服务,接收请求后,依次与特征计算系统、检索模块、排序模块交互,最后返回出价和广告等,是枢纽。

检索模块:解决相关性问题,要检索出与用户相关性较高的广告,相关性较低的会影响用户体验和广告效果。检索分两步,首先是定向匹配,根据广告主对广告设定的定向条件,过滤出符合本次请求特点的广告;然后是逐层召回,按多种定向策略或是相关性计算选择与本次请求最相关的若干个广告。

排序模块:解决收益最大化问题,约束下最大化DSP利润。排序也可分两步,粗排和精排,粗排用到的特征比精排少。由于检索出来的候选广告集较大,精排涉及到CTR预估和出价较复杂,通过粗排可做到快速扩率,选出前若干个进入精排,以节省计算时间和成本。

特征计算系统:实时计算曝光场景(媒体、广告位、上下文、设备等)、用户的特征,并向其他模块提供实时查询功能。

计费系统:实时处理曝光后媒体返回过来的曝光数据,以及其他点击、转化等数据,并计算广告费用、剩余预算等,也要包含反作弊。

投放系统:供广告主使用,给广告设置定向条件、创意等,是广告主直接操作的界面。

复杂架构

复杂架构

复杂架构相对于简单架构而言,把系统中涉及到的具体模块,都展示出来,并且区分了离线和在线。组成部分包括分布式计算平台、广告投放机、流计算平台、数据高速公路。其中分布式计算平台是离线数据,流计算平台是实时数据,分布式计算平台会把输出的行为定向、算法模型等通过海量内存管理系统(例如Redis)暂存在内存中,方便在竞价过程中快速调用,以满足DSP在30ms内完成出价,整个竞价过程在100ms以内。

分布式计算平台:采用分布式技术(例如Hadoop),它输出的数据、算法模型一方面提供给广告投放机进行出价决策,另一方面提供给ETL,以数据仓库为基础向产品运营等人提供数据报表的支持,以便于商业决策。

广告投放机:就是简单架构中的router、检索模块和排序模块,是DSP收到请求和返回出价广告等的主逻辑,此处还包含了收益管理模块。广告排序得到的结果是局部最优,收益管理则是用分布式计算平台中计算好的分配规划来生成分配方案,以达到全局最优。

流计算平台:是对实时数据(短时间内发生的用户日志和广告日志等数据)的处理,包括反作弊、实时点击反馈、计费、实时受众定向。反作弊是根据实时用户行为识别作弊流量,并不纳入计费。实时点击反馈会生成实时点击率特征,和离线特征一起参与到基于CTR模型的广告排序中。实时受众定向会把实时数据加工成实时用户标签,用以广告检索。计费是实时计算广告费用,把预算即将耗尽的广告及时告知给实时索引以下线此广告。实时数据对广告检索、排序等效果提升很明显,例如前几分钟给用户推了此广告,而用户有负反馈(点击“不再看”),那就可以不再向此用户推这个广告。

数据流转

上图中可以看到两条处理线,一条是广告竞价请求(投放日志)的处理,另一条是广告曝光、点击等监测数据(跟踪日志)的处理。具体可看我在图上的说明。

总结如下:1.广告跟踪日志和投放日志接入数据高速公路,由数据高速公路把数据运到分布式计算平台和流计算平台。2.分布式计算平台周期性以批处理的方式加工数据,得到数据和模型,存到内存中方便调用。3.流计算平台以流处理的方式加工最近一小段时间的数据,得到数据也存到内存中方便调用。

竞价核心处理流程

接下来看下竞价核心的处理流程,分适配器(输入器)、处理器、渲染器(输出器)。

          竞价核心处理流程

一般来说一个DSP会对接多个ADX,因此请求会先到适配器,使用适配器设计模式,不同ADX平台接口会采用不同的适配器处理。然后填充Action数据输入到处理器中。处理器中使用过滤器的设计模式,增加新业务时根据业务需要增加过滤器即可,因此整体的处理框架相对稳定,且具备十分强大的业务灵活性和高性能扩充性。渲染器也是用适配器设计模式,Action根据不同ADX平台接口适配,最后输出给ADX。

          处理器

重点看下处理器,根据上图处理器中包含索引匹配、广告过滤、出价、出价过滤、决定胜出、曝光点击地址生成、Bid/UnBid日志等。索引匹配是指根据媒体条件索引出匹配的广告,广告过滤指根据广告条件过滤掉不合适的广告。出价、出价过滤和决定胜出就是精排里的内容,粗排这里没说明。

算法和场景

本部分中会重点讲解主要模块用到的算法策略和相关场景,包括检索、粗排、CTR预估平台、CTR预估特征和模型、出价和预算。其中CTR预估平台、CTR预估特征和模型、出价是精排的部分。

广告检索

广告检索就是解决相关性问题,要检索出与用户相关性较高的广告,相关性较低的会影响用户体验和广告效果。检索分两步,定向匹配和逐层召回。

定向匹配

定向匹配要考虑广告本身限制,也要考虑此次请求的用户与广告之间的匹配。广告本身限制包括广告设定的总/每日预算、投放日期、投放时间段、黑白名单、频次控制等等。而用户与广告间的匹配可通过倒排索引实现。

  定向匹配流程图

一个定向请求包括userid和targetid,根据userid去取用户标签,根据targetid取广告的定向包,把定向包解析成DNF的形式(建立倒排索引),与用户标签进行匹配。

一般采用DNF(析取范式)的形式存储广告的定向条件,例如DNF1:(30岁 男性)∪(25岁 女性) DNF2:(非男性)∪(广东 女性)∪(北京 喜欢美食 女性)。每个DNF可分解为一个或多个合取范式(CNF),例如DNF1=C1∪C2,C1=(30岁 男性)。每个CNF可分解为一个或多个条件的交,例如C1=A1∩A2,A1=30岁,A2=男性。每个条件可用一个赋值集来表示,例如A1=30岁,表示为age∈{30}。PS:一般年龄不会精确到几岁,而是设计成25-30年龄段的格式。

而且其中有两个特点,一是当某次广告请求满足某个CNF时,则包含此CNF的所有广告均满足条件,因此对CNF建立倒排索引,并加上CNF→AD的复制索引即可;二是设广告请求中的定向条件个数为n,而m表示某CNF中赋值集条件数,若n<m,则此CNF不满足该次请求的条件。

此外,还要向广告主提供定向的方法,包括地域定向、人口属性定向、行为定向、上下文定向、重定向、lookalike等等。这里还比较考验用户标签的设计,标签类型可以用人口属性、用户分类、商业属性、内容标签、行为标签等,其中除了最基础以外,其他的都会用到标签建模。因为绝大部分标签都来源于数据挖掘而非直接的事实标签,所以给每个标签制定合理的计算标准,也要划分标签权重,标签权重=时间衰减×权重×行为权重。

对某种定向方法的评估可以从质和量两个角度出发。质是指定向的效果,该定向的流量eCPM、点击率、转化率等核心指标是否高于平均值。量是指定向的规模,该定向的流量占整体广告库存流量的比重,从召回率和准确率上看覆盖程度,从广告主使用率看广告主使用意向。

逐层召回

由于通过定向匹配过滤出的广告量级有时仍然较大,还会增加根据相关性设计的逐层召回,即根据相关性水平把广告分层,然后从高到低逐层召回,直到足够的广告参与粗排。

思路就是在检索阶段引入某种评价函数,并以此函数的评价结果结果作为相关性分数。评价函数设计有两个要求,合理性,与最终排序时使用的评价函数相近;高效性,在检索阶段实现快速评价算法。一般使用线性函数,变量为各标签或关键词,且各权重为正。

而具体选择什么变量作为相关性因素,则要根据场景、业务特点等进行自我调整,更是要结合对最终排序影响较大的变量。

以美团为例,美团中有推荐广告、搜索广告、站外广告等多种广告类型,有餐饮、外卖、酒店、婚纱摄影等多种业务类型。因此美团会考虑多种相关性因素:查询匹配模式、距离、星级评价等。例如针对Query匹配模式,广告召回时会优先使用Query精确匹配模式召回,其次选择模糊匹配模式,最后才尝试采用语义匹配模式。针对距离因素,广告召回会优先召回距离3公里内的商户,其次选择5公里内的商户,最后尝试全城召回。

此外,美团也会考虑到不同业务的特点。例如距离的设置上,对于餐饮类流量,系统会优先召回3公里内的商户,而对于距离相对不敏感的婚纱摄影类流量,系统则会放宽限制,优先召回10公里内的商户,或者直接采用全城召回策略。

粗排

粗排是指用少量基础特征,快速过滤候选广告,选出topN进入精排。仍然以美团为例(美团资料较多),美团DSP对接了多个站外ADX,有很多站外媒体流量,美团考虑到了流量因素(媒体、用户数据)和非流量因素(LBS、天气等),也考虑到不同流量所覆盖的特征不同,如有的流量包含大量丰富的用户画像,而有的流量无用户画像,但有标识性较为明显的媒体特征,如P2P、母婴类媒体等,因此对于不同流量,会使用不同的粗排策略,以更好地应用流量特征。

美团对于不同场景下的广告粗排会使用不同模型,最后汇总打分,汇总使用LR模型,不同广告行业权重不同。广告粗排定向场景包括基于用户画像、基于天气特征、基于关键词特征、基于上下文、基于重定向等等。下面会对基于用户画像、基于天气特征、基于关键词特征做描述,注意在各个场景下中的数据准备、离线建模和在线使用。

基于用户画像

基于用户画像核心是标签体系设计和数据挖掘生成标签。

美团现有用户标签体系为树状结构,包括商户分类兴趣体系、自然属性、社会属性、心理认知、自定义标签等五大类。用户画像工程每日例行运行一次,离线处理各数据源并合并产出设备ID粒度的标准化用户标签,然后导入Redis缓存,以供线上加载使用。

虽然这里用到的美团用户标签体系是已经有的,但还是简单讲下用户标签体系的建模。兴趣体系是挖掘型,应用于搜索推荐广告等大型算法场景,是用户在某些分类下所有标签的累加值。自然属性、社会属性是统计、聚类型标签,可把用户填写的资料作为样本,用户行为作为特征,预估无资料的用户。心理认知是挖掘、统计型标签,例如消费水平要用到rfm模型(f消费频次 m消费金额),用户价值则要根据行为时间、消费频率、消费金额等划分。

策略目的:把用户标签中的兴趣体系和商户分类体系关联起来,而广告又都来源于这些商户,就得到用户标签与广告的关联打分并用于粗排。

数据准备:抽取一段时间的用户广告行为数据,点击、转化、收藏等用户行为有不同的行为权重,可把转化等同于多次点击(升采样),然后使用Spark的ML库进行频繁集挖掘。

频繁集挖掘:美团中使用了频繁集挖掘方案,因为用户标签和商户分类类似,规则收益可能好于模型;其次,频繁集可挖掘出规则考虑不到的关联关系;最后,可解释性较强,人工干预方便。

离线建模:由于广告商户分类分三级,每一条点击记录都拆分成多份,让每一级的分类都能和用户标签关联,保证每个层级都不会遗漏。通过Spark的ML库找出大量频繁集以后,剔除掉仅包含广告分类或用户标签的。并限制用户标签在频繁项中的数据,不超过两个,以保证覆盖较多用户。然后对广告分类与兴趣标签的关系打分,广告分类A与兴趣标签B的打分为  ,并考虑到广告展示量对点击的影响,最后得到下表。

打分表

共生次数来源于用户广告行为,得分=共生次数/该二级分类下广告展现次数,可筛选出置顶标签下关联度较高的广告二级分类。得到全部频繁集及相应打分后,可线下进入人工筛选,提出不符合认知的,最终结果作为离线模型产出,写入数据库。

在线使用:每天定时加载一次离线结果到内存中,等某次请求的检索召回完成后,对于有用户画像的请求根据离线模型产出,对广告进行打分和排序。

整体应用框架

FLOW分流,是指在请求进来之后会划分一定百分比的流量作为实验流量,用于用户定向实验。会分析一段时间的累计实验结果,与base分流额作对比,以检测用户定向策略带来的效果提升,并反馈给频繁集模型,以干预调整离线产出模型。

基于天气

在美团O2O业务中,天气情况对用户和业务都会有影响,例如天气会对外卖产生很大影响。而不同行业受到的影响不同,有些行业对天气敏感,例如餐饮、运动等,而有些行业对天气不敏感,例如亲子、结婚等,有些是因为转化不发生在当下。因此对不同广告分类分别训练,每个行业训练一个模型。

策略目的:每个行业分别训练一个离线模型,在线加载模型对广告分类和天气特征的关系进行打分。

数据准备:天气基础数据包括温度、雨量、雪量、天气现象(大雨、雾霾等)、风力等级等。线下模型训练要使用历史天气数据,线上模型加载要使用当前天气数据,但两者的特征要一致,否则会影响模型在线的效果。美团配送团队每日会提供未来72小时的天气数据,同时保存了稳定的历史数据,可直接使用。然后确定更新时间,因为天气情况在短时间(一小时)内较稳定,而且第三方媒体对DSP的响应时间有严格限制,如果每次广告请求都去请求天气数据,会对性能造成较大影响,所以以小时粒度和城市粒度来保存天气。

Gentle AdaBoost模型:在模型上,选择AdaBoost的改进版Gentle AdaBoost。AdaBoost模型可使用若干简单的弱分类器训练出一个强大的分类器,且较少出现过拟合现象。AdaBoost、GBDT、XGBoost都是Boost(提升)一族的算法,可将弱学习器提升为强学习器。且线上检索端不可太复杂,选用了AdaBoost常用的树桩模型(即深度为1的决策树)。在树桩模型中,Gentle AdaBoost的效果好于传统离散AdaBoost。

             

Gentle AdaBoost

数据处理:要把准备好的数据(温度、湿度、降水量、降雪量、天气情况等)处理成适合决策树分类的特征。例如温度,作为连续变量处理,对于特征为温度的决策树,训练合适的分割点(分桶),将温度归类到合适的叶子节点;对于仅有几个取值(正常、一般恶劣、非常恶劣等)天气情况,当做离散值对待,进行one-hot编码,散列到有限的几个数值上(如1、2、3)。若离散值较多,也可以连续值对待。

离线建模:以转化为目标,搜集一段时间的历史点击数据,对数据进行特征化处理,最终训练出合适的离线模型,每个行业训练一个模型。去掉了Gentle AdaBoost最后的感知器模型,直接使用回归函数的和作为打分。而且,在每次迭代过程中,我们会保留当前错误率,当迭代达到一定次数,而错误率仍大于给定阈值时,则直接舍弃对该行业的训练,即在天气场景定向中,不对该行业的广告打分,阈值可动态配置。另外,考虑到线上加载迭代模型会牺牲性能,我们将迭代轮次控制在100次以内。最终结果会存在Tair缓存中,其中key为一级及二级行业,value即为AdaBoost模型的多轮迭代结果,同时保留了最后一轮迭代的错误率。

天气粗排逻辑

在线使用:广告检索端要从Tair读取离线模型,来完成广告打分。因为AdaBoost迭代模型的特点,在线上加载较为耗时,有三个方面可以优化。模型缓存,对某条广告打分后,将其对应的二级分类及相应模型加入缓存,后续同分类可直接使用缓存模型。打分缓存,在指定小时,指定城市内,同二级分类的广告打分一致,可对分类+城市的打分缓存处理,每个整点更新一次。牺牲部分广告打分换取性能提升,使用动态配置的阈值来控制每次检索请求中模型迭代的轮次。举个例子,阈值设为200次,在整点时刻,前五个召回广告的行业各不相同,且使用的模型分别迭代80、90、60、60、30次结束,则本次请求中我们只对前三个广告打分(80+90+60<200),并将广告打分进行缓存。后续召回广告,其二级分类若能命中缓存,则打分,否则不打分。在第二次广告请求过来时,同样沿用这个策略,对已经缓存的广告打分直接加载,否则迭代模型进行打分,直到达到迭代阈值200为止。同时,通过打分缓存机制,可以保证前面牺牲掉的广告行业被逐步打分。使用该优化策略,可以完全确保上线后的性能,通过调整迭代轮次的阈值,控制打分与性能的折中关系。

在本案例中,实际情况性能和打分之间的矛盾提现的淋漓尽致,要在理解策略和算法的特点之后,结合工程上的流程和约束,寻找优秀的解决方案。

基于关键词

基于关键词特征的方案,是指通过对用户近期搜索词的分析,识别出用户感兴趣的店铺及分类,以便于在站外为用户投放相关广告。

策略目的:构建搜索词和店铺分类的关系。

数据准备:用户近期搜索词,由于关键词特征对时效性要求较高,所以除了离线数据以外,实时数据也要参与进来。

TF-IDF模型:此模型常用于文章主题提取等,即文章和词之间的相关程度,而文章-词模型与词-店铺模型非常相似,因此TF-IDF模型也可用于计算词-店铺分类的关联程度。

用于文章主题提取的TF-IDF模型

离线建模:以用户搜索词为“潮汕火锅”为例,计算“美食/火锅”的商家分类与该关键词的相似程度,具体公式如下:

c1 = 搜索“潮汕火锅”后的全部点击数,

c2 = 搜索“潮汕火锅”后点击“美食/火锅”类目店铺的全部点击数,

c3 = 搜索词总数

c4 = 搜索点击“美食/火锅”类目的词总数

由此计算出店铺分类与关键词的关系,取topN(根据存储大小及不同店铺对同一词的TF-IDF差距拟定)个店铺分类。单店及商圈计算方法与此类似,它们的计算值会同时与店铺分类的TF-IDF进行比较,不作区分。(此处有一点需注意:如果用户搜索“中山公园 火锅”,可以预见店铺分类与商圈会同等重要,则最终产出两条独立打分规则,分别挂在店铺分类和商圈下面)

使用Spark来构建离线模型,提取用户的搜索词和搜索后点击的店铺及店铺分类,运用上述方案来计算每个搜索词的关联店铺及店铺分类,设置阈值,保留分数较大的分类结果。分词用的是点评分词系统,同时保存原始词和切分后基础词的TF-IDF结果。结果也存在Tair中,以检索词为key,关联店铺分类和店铺的TF-IDF打分作为value进行保存。

实时流计算:因为关键词的时效性,除了离线以外,也用实时流计算处理用户行为,并把最后的结果保存在Tair集群。首先通过Kafka订阅用户行为实时流,以五分钟为时间片处理用户行为,查找用户ID和搜索词,如果搜索词过长,则进行分词,接着从Tair中查找出与该搜索词相关的店铺及店铺分类和打分(离线模型给出)。然后在Tair中查找该用户ID是否有历史结果,若有,则读出,对之前的打分进行衰减(衰减方案见下文),并与当前新的打分进行合并;否则,将新的数据及时间戳写入Tair。该方案的流程图如下:

     

此方案核心是新老数据的合并,如果新数据包含老数据中的分类&商圈,则用新数据中的权重;若未包含,则对老数据中的分类&商圈权重衰减,若衰减后小于阈值,则提出此分类&商圈。衰减方案是根据时间衰减,使用牛顿冷却定律,默认半衰期为72小时(不同的店铺分类给予不同的半衰期),使用牛顿冷却定律,参数计算公式为:0.5 = 1 × e-α*时间间隔 ,解出α,并带入下面公式得到实际权重为:  其中,w为老权重,w'为新权重。

在线使用:检索端接收到广告请求,根据当前获取的用户ID,从Tair中读取用户偏好的店铺分类,与召回的广告进行匹配,当广告分类与召回广告匹配成功,则顺便将Tair读出的分数进行时间衰减后,作为该广告的关键词打分。检索端采用与实时流同样的时间衰减方案,以保证一致性。示例:用户A在早上8:30有火锅类搜索行为,Spark Streaming处理后进入Tair,假设此时最新时间戳为8:30,而该用户在11:00搜索亲子类商铺,Spark Streaming处理该条记录后,之前的火锅权重需要衰减,同时时间戳更新为11:00,假设此时立即有广告检索请求命中该用户,则此时用户火锅类偏好权重为11:00时权重;假设下午16:00有ADX请求命中该用户,则用户火锅类权重需要根据16:00到11:00的时间间隔继续衰减。因为只有在此用户广告请求时才会计算权重

在此案例中针对关键词时效性强的特点,综合运用了离线计算和在线流计算两种方案,并考虑广告竞价流程,直接在检索召回阶段顺便读出。此外,对tf-idf模型的用法,也有了更深刻的认识,基于上下文的定向应该也可以用这模型。

定向汇总

此阶段是把用户画像、天气、关键词、上下文、重定向等不同场景下的打分汇总起来。美团对于不同场景下的广告粗排会使用不同模型,最后汇总打分,汇总使用LR模型,不同广告行业权重不同。分不同广告行业,以点击为样本,转化为模型,以各个场景下的前期打分为特征,进行混合打分权重的离线建模。

公式如下:

其中θ是向量, 其中x0,x1......,xn 是各个场景定向下的具体打分,打分分布在[0,1]之间。

冷启动时,对每个场景打分给予一个默认权重,积累一定量数据后,使用离线模型训练出各个广告行业下的θ向量,并在引擎端加载使用。引擎端加载各个场景的广告打分,并根据广告行业加载打分权重,最终完成每个广告与当前的流量综合打分。

总结

从ABtest来看,场景化排序机制对点击率和转化率的提升都很明显。之后还可丰富各类场景特征、引入更多场景、尝试不同模型等方法去提升粗排效果。

此次介绍了美团基于场景化的粗排机制,可很明显感受到,在不同场景中,在当前架构、数据、流程等局限条件下,如何综合运用数据处理、特征工程、离线建模、实时流计算、缓存优化等手段以达到策略目的。从场景的拆分汇总到不同场景的不同策略,每一点都值得学习。

CTR预估特征和模型

本节中会讲特征计算系统和模型。特征计算系统为各个模型(主要是CTR预估)提供标准化的特征。模型则会讲解针对于CTR预估的LR、GBDT、FFM、PNN四大模型。

样本中的信息在训练是也可以学习到,但是高维度稀疏下对样本量的要求也很大,就要从特征表达上去突破。在CTR预估中,LR one-hot之后导致特征高维稀疏,FM使用隐向量的内积来建模组合特征,FFM在此基础上引入field的概念,针对不同的field上使用不同隐向量。而DNN输入往往是密集的,所以单纯的DNN不能用于特征高纬稀疏的CTR预估。如何表达特征而且还能不缺失样本中的信息,一直督促算法的发展。

此外,在实际情况下,还会综合考虑ROI、场景特征特点、上线优化瓶颈、latency、资源消耗、性能等因素以选择合适的模型。

特征计算系统

特征计算系统用以实时计算场景(媒体、上下文等)、广告和用户的特征,并提供实时查询功能。

1.特征挖掘

特征有三个来源:场景、广告和用户。人工设计特征需要结合业务领域知识,分析实际业务数据分布特点,寻找与点击率变化相关的属性。特征挖掘可从三个基本思路出发,扩展维度、维度及维度的组合、特征时效性。

扩展维度,指Tina就爱特征集合中未包含的属性维度,例如在广告基本属性基础之上,加入创意中的图像/文本上可利用的信息;或考虑到层级关系,广告/广告主/广告行业越往上泛化性能越好,越往下越稀疏,但有更强个性化信息和精度。

基于维度及维度的组合,统计广告行为相关的统计量,例如用户在过去一段时间对某一类广告的点击率。

上面提到的特征大部分属于静态特征,即历史上相对稳定的属性,可以通过业务DB获取同步到特征库,或者从流量日志中离线挖掘得到,例如:广告主,所属行业,用户的基础画像等。

而特征时效性,就是指挖掘用户动态特征,动态特征实时在变化,例如实时挖掘用户浏览/点击行为,历史信息和实时信息相互补充,也可以提升模型性能。粗排中的关键词场景就是个很好的动态特征案例。

2.特征计算流程

     

特征计算流程

从上图中可以看到,特征挖掘分实时和离线两种方式,实现逻辑基本一致,但是计算设施和时效性不同。从特征库输出的会用于离线的模型训练和在线的预测,其中的特征预处理实现逻辑也基本一致,因为训练后的模型参数生成预估模型,用以预估服务。

离线方式中数据存储在HDFS等分布式存储上,利用Hadoop/Spark等计算框架来处理海量数据。可以进行较多的实验和迭代,尝试不同的样本采样、样本权重、特征处理方法、特征组合方法等,最终得到一个最优的方法,在离线评估得到好的结果后,最终将确定的方案在线上使用。

实时数据处理可以采用Storm/SparkStreaming等流式计算引擎,模型训练则基于parameter server架构现online-learning,更快的更新模型,形成快速反馈的数据闭环,使得模型对于数据分布的变化响应更及时。

模型预测即为线上预估服务,在线请求经过一定的预处理构造出特征数据,而有些广告请求本身不包含的特征数据需要从外部系统获取,通过关联的方式补全,之后特征处理方式基本与训练时相同。要注意时间短,对查找性能要求非常高,所以一般在线需要查询的特征存储在redis缓存中。

3.数据清洗

数据清洗在实时和离线中都要进行,主要任务是数据类型检查、特殊字符清理、异常值过滤、缺失值处理四类。

数据类型检查,是指检查字段和值的数据类型是否一致,例如某个数值型字段出现了字符串类型的值,很明显这就是异常值,需要处理掉。

特殊字符清理,是指处理日志中的特殊字符,数据字段分隔符标准化。

异常值过滤,或是数据范围不合理,一般通过业务规则判断,或者通过统计量分析。常用统计量包括最大值,最小值。如果数据分布服从正态分布,则测量值如果与平均值的偏差超过3个标准差,则认为是异常。

缺失值处理中,缺失值一般处理为统一填充特殊值或者平均数、中位数、众数等统计量。也可以通过预测模型利用不存在缺失值的属性来预测缺失值,例如性别就可用预测模型预测。

4.特征预处理

 

特征预处理逻辑

特征类型可分为连续型特征和离散型特征,连续型特征有无限值,离散型有有限的值。特征千奇八怪,要经过预处理才能输入到模型中,不同模型对输入特征的要求略有差异。

归一化,不同变量往往量纲不同,不同维度之间的取值范围差异很大,归一化可以消除量纲对最终结果的影响,使不同变量具有可比性,取值大的特征不再占有优势。同时归一化后加快了梯度下降求最优解的速度。归一化方式有线性归一化(映射到[0,1]范围)、z-score标准化(均值为0,方差为1的数据集)、非线性归一化(用log、指数函数等数学函数)。

数据平滑,主要起对数据修正作用,例如拉普拉斯平滑,防止某个维度值没有在样本中出现过而出现0概率问题。具体平滑算法可以根据业务场景选择。

离散化,是对连续型特征离散化,连续特征理论上无穷多个,离散化能减少算法的时间和空间开销。离散化方法可分为无监督和有监督。无监督包括等宽(值域等分为K个区间,前提数值要均匀分布)、等频率(每个区间的对象数目相等)、基于聚类(例如k-means聚类,需人工置顶区间数)。有监督即考虑label分类信息下的离散化过程,可使用MDLP。

二值化,即one-hot编码。二值特征,主要是0/1特征,即特征只取两种值:0或者1,例如广告id特征:目前的id是否是某个特定广告id。连续值处理为二值特征方法:先将连续值离散化,再将离散化后的特征切分为N个二元特征(one-hot encoding),每个特征代表是否在这个区间内。二值化同时也给LR这样的线性模型引入了非线性。

二值化示例,例如有运动特征:["足球","篮球","羽毛球","乒乓球"](这里N=4):

足球  =>  1000

篮球  =>  0100

羽毛球  =>  0010

乒乓球  =>  0001

5.特征选择

one-hot之后很容易导致特征高维稀疏,从而出现维数灾难问题,通过特征选择能够大大缓解。特征选择方法是最优特征子集搜索策略和评价标准的组合,与学习算法结合考虑。

特征选择方法有过滤式特征选择(Filter)、封装式特征选择(Wrapper)、嵌入式特征选择(Embedded)。

过滤式特征选择(Filter)一般使用评价准则来增强特征与类别的相关性,,削减特征之间的相关性,通常选择和类别相关度大的特征或者特征子集。过滤式特征选择的评价标准分为四种,即距离度量、信息度量、关联度度量以及一致性度量。目前我们有基于单特征AUC,基于信息增益的评价工具等。优点:算法的通用性强;省去了分类器的训练步骤,算法复杂性低,因而适用于大规模数据集;可以快速去除大量不相关的特征,作为特征的预筛选器非常合适。缺点:由于算法的评价标准独立于特定的学习算法,所选的特征子集在分类准确率方面通常低于Wrapper方法。

封装式特征选择(Wrapper)是利用学习算法的目标函数(通常是预测效果评分)来评价特征子集的优劣。因此,对于一个待评价的特征子集,Wrapper方法需要训练一个分类器,根据分类器的性能对该特征子集进行评价。可以基于模型的AUC来判断。优点:相对于Filter方法,Wrapper方法找到的特征子集分类性能通常更好。缺点:Wrapper方法选出的特征通用性不强,当改变学习算法时,需要针对该学习算法重新进行特征选择;由于每次对子集的评价都要进行分类器的训练和测试,所以算法计算复杂度很高,尤其对于大规模数据集来说,算法的执行时间很长。

在嵌入式特征选择(Embedded)中,特征选择算法本身作为组成部分嵌入到学习算法里。例如GBDT,深度学习,在模型训练过程中自动对特征进行筛选。另外一个标准的嵌入类方法是正则的方式,L1正则中,最后系数为0的特征说明对模型贡献很小,我们保留系数不为0的特征即可,这样就达到了特征选择的目的。

6.特征工程自动化

特征工程自动化是指引入更复杂的模型来解决特征总数增多的问题,通过模型自身自动捕获特征或者特征组合的能力来减少人工特征工程的部分工作。相当于在CTR预估模型中就包含了特征工程自动化的过程,例如GBDT+LR,GBDT的路径可直接作为LR输入特征使用,GBDT用来提取特征,弥补LR模型在非线性上的不足,具体的可到模型阶段讲解。

7.特征质量控制

寻找到了恰当特征之后,需要对特征的数据质量进行监控,及时发现特征层面的问题,保障模型训练效果。而且由于我们广告数据流很复杂,一个广告从发出请求到最终产生曝光/点击并落地日志数据经过了多个环节,可设计DataCheck系统检查线上广告请求(预测)与落地日志(训练)用到的特征是否一致,以及各个特征的分布是否稳定。

线上线下数据流

如上图所示,从线上真实业务环境copy广告请求流量到sample server,按规则抽样后将完整请求及特征数据写入HBASE中,包括query信息以及订单信息。sample server和ctr server在特征处理实现上保持一致。线下环境,基于storm实现针对曝光日志的实时监控,从全量曝光日志中抽取请求id与Hbase中匹配的记录,检测某个特征纬度值是否一致,并同时统计关键特征纬度分布。离线MR程序会统计全量日志中的各特征值分布。特征的一致性以及分布统计会定时发送report,异常波动达到设置阈值则会触发告警,提醒相关人员介入。

LR模型

     

Z是线性边界表现形式,x是特征工程得到的特征向量(onehot后的特征),w是每个特征的权重值。

预测CTR采用二项逻辑回归,则类别表示为点击1,不点击0,条件概率分布函数则表示:

 

逻辑回归的损失函数构成的模型,可能有些权重很大,有些权重很小,导致过拟合,使得模型的复杂度提高,泛化能力差。通过正则化方法来解决,可采用L2范数正则化,损失函数如下

C是正则项系数,它的值越大,说明对模型的复杂度惩罚越大,对拟合数据的损失惩罚小,就不会过分拟合数据,在训练数据上的偏差较大,在未知数据上的方差较小,但是可能出现欠拟合现象;如果它的值很小,说明比较注重对训练数据的拟合,在训练数据上的偏差会小,但是可能会导致过拟合。

损失函数的梯度表示:

     

求对数似然函数I(w)的极大值问题一般会转为求极小值来解,乘以一个负的系数后,变成负对数似然函数。这个函数是个凸函数,可用梯度下降法、共轭梯度法、拟牛顿法、BFGS等算法求解。

LR模型求解得到的参数,作为离线模型的参数以快照形式提供给在线模型,在线模型加载参数快照,结合此次请求的特征值,根据CTR预估公式即可计算出预估的CTR值。

LR模型简单,可加很多很多特征,而且容易debug,能根据模型和结果容易定位到是哪些特征出了问题,并且可以马上采取补救措施,例如人工修改模型权重,以达到增强或者减弱某些特征对结果的影响。还有非常多的优化算法可选择,还有些算法可以有效的产生稀疏模型并使得效果不损失,这对上线非常有利,也有利于减少线上响应时间。缺点则只是个线性模型,不是对所有的数据都能很有效,不同的业务其数据分布都不同,有些业务的数据可能还是需要非线性的模型来学习。

下篇将讲解CTR预估GBDT、FFM、PNN模型、CTR预估平台、出价、预算等,敬请期待

参考文献

《计算广告》刘鹏

《定向广告系统结构》陈肖雅

https://zhuanlan.zhihu.com/p/50441627

《大型广告系统架构 — 检索模块》公众号:架构丛谈

《DSP系统技术架构参考【技术类】》吴俊

https://www.jianshu.com/p/7774114e083a

《美团O2O广告营销中的机器学习技术》公众号:美团技术团队

《美团点评联盟广告的场景化定向排序机制》公众号:美团技术团队

《OMG广告点击率预估之特征工程》公众号:腾讯AMS广平技术黑板报

《在线广告DSP平台实时竞价算法的研究与实现》 韩静