互联网广告算法和系统实践
前言
这两年在招聘过程中,有很多的同学问我“大互联网公司的广告部门是做什么的?”,或者“互联网广告算法都包括哪些?”。有些时候,一些同学还会问的更加细致,比如“DSP的报价算法是怎么设计的?”、“不同公司的搜索广告算法一样吗?”、“海量数据下的模型训练系统是怎么搭建的?”。更有一些焦急的找工作的同学直接了当的问我“我学的专业能否进入广告部门?”。
在解答同学们的问题之余,我开始构思写这个入门短书,本书的定位非常明确,就是力求用简单明了的语言,给入门级的同学介绍一下互联网广告算法的体系。在本书中,有很多的地方没有详细的展开,这是留给同学们去自学的地方,大家可以根据书中的内容,自己去深入挖掘。比如,对于逻辑回归的详细推导,大家可以去找一下相关的书籍和博客;对于ctr prediction的工程优化,大家可以去google上面找找相关论文,扩展一下视野。
本书注重实践,写了一些实践的例子,有些实践是一个方向的深入阐述,有些实践是经验的总结。
希望这本短书能够帮到大家。与人分享,不亦乐乎。
第一部分 互联网广告简介
1.1 广告简介
在今天,如果你问一个人:“什么是广告?”回答可能五花八门,因为现在的广告形式日新月异,已经发生了巨大的变化,渗透到了几乎生活的每一个角落。我们现在在电视上、电影放映前、地铁里、商场里、车站牌上、洗手间里……广告无处不在。以至于有些人预测了一幅未来的人类社会场景:随着显示硬件技术和联网技术的极大发展,所有的公共区域,甚至墙上都布满了显示和输入设备,每个人都可以随意的在街角的一块墙上输入自己的身份,然后登陆完成自己的所有操作,同时也收到了来自各种源的定向广告内容。当然,这只是一种带有科幻色彩的想象,目前的广告形式和广告渠道并没有达到这种大一统的阶段。
William F.Arens在
广告是由已确定的出资人通过各种媒介进行的有关产品(商品、服务和观点)的、有偿的、有组织的、综合的、劝服性的非人员的信息传播活动。
这个定义到现在也不过时,在这个定义里,我们看到了传统广告业务包括了三方角色,分别是:广告主(Advertiser)、媒体(Media)、普通受众(Audience)。这三方的诉求和利益各不相同,共同构成了一个博弈的生态系统。充分理解这个生态系统的构成,对于后面理解广告系统的算法设计、目标设计、平衡之道,具有重要意义。
既然谈到了广告,那么,在这里简单说一下广告的历史。目前认为最早的广告是古希腊的《寻奴》,这是一则寻人启事,描述了一个在逃的奴隶,并悬赏一枚硬币抓捕。古罗马也有早期广告的痕迹,庞贝古城的废墟里面就发现了关于商业信息和政治信息展示物。在古埃及和古阿拉伯,也都有用纸莎草来制作销售信息和贴墙海报的历史。
真正意义的现代广告,随着印刷术在15世纪的广泛应用出现在欧洲。英国出现了世界广告史上第一个纸质的广告——宣传教会图书。随着纸质媒体的发展,广告业务迅速发展,到了1843年,第一家广告代理公司由Volney Palmer创立,专门贩卖广告版面,却并不提供内容。在1869年,Georage P Rowell编写了广告史上第一部报纸索引
面的服务,是第一个具备现代广告公司基本特征的公司。在大热的美剧《疯狂广告人》里面,描述了美国上世纪60年代,处于黄金时期的传统广告业。剧中展现了令人叹为观止的广告创意和灵感,有些即便放在今天也是经典。
时至今日,中国互联网广告产业已经有了千亿的规模,产品形式丰富多样,每天影响着几亿中国网民,是实实在在的“大产业”。而且,互联网广告可以用算法进行优化,投放效果可以量化评估,这些都是传统广告行业不可比拟的。
1.2 互联网广告简史
在20世纪末的美国,大型互联网公司开始崛起,美国在线(AOL)、雅虎(Yahoo!)开始逐渐成为科技之星,Amazon还只是个网上的小书店。AOL和Yahoo!的巨大的流量(刚开始也只是百万级的pv)并没有转换成巨大的收入。这时,这些互联网公司开始尝试在页面中插入条幅(banner)广告创意,并向广告主收取费用,这种条幅广告就是显示广告(Display Advertising)的最初雏形。显示广告的售卖方式是按照所谓的合约广告(Agreement-based Advertising)方式进行的,合约广告是指:采用合同约束的方式,让某一广告位在某一段时间被特定广告主所独占。这个时候的广告并没有今天这么复杂的在线计算,甚至就是没有什么计算,只是工程师把HTML的代码嵌入到网站的某个
位置而已。这种简单的售卖方式,非常符合普通的广告售卖认知,但是却无法提升互联网广告的地位。很快,对于不同的人群做不同的广告创意投放开始出现了,这是一个重要的转折点,标志着互联网广告从单纯的位置、时间售卖,进入到算法驱动的时代。这种定向广告(Targetd Advertising),通过受众定向技术(Audience Targeting)分析用户的属性(User Profile)标签(性别、年龄……),通过广告投放服务(Ad Server),将原来静态的广告HTML代码转变为根据算法实时变换广告HTML代码,返回给浏览者。
一开始的广告投放,网站作为媒体方,需要跟广告主保证一定的投放量(页面展示或者时长),这种担保式的投放(Guaranteed Delivery)开始逐渐成为最流行的方式,此时的计费方式,主要以CPM(Cost per Mille)为主,即千次展现付费。
我们可以看出,担保式的投放是一个面对广告主的包销式的售卖,这种方式是不能达到“每次流量的利益最大化”的。在Overture公司(原名GoTo公司)的开创下,竞价广告(Auction-based Advertising)应运而生,开创了互联网广告崭新的一片天地。后来,Overture公司被雅虎收购。竞价广告随着Google公司的腾飞而发扬光大的。Google公司在2002年发布了第一个广告推送产品:Adwords Select,并革命性的采用了广义二阶价格拍卖(GSP),取代了Overture公司的广义一阶价格拍卖(GFP),成为后来互联网广告的定价(Pricing)基石。关于定价的详细理论,我们后面还会讨论。
Google的最主要的收入来自于搜索广告(Search Ad),而这种搜索广告的形式,其实就是根据用户的搜索词进行定向,然后投放相关的广告。Google公司并没有满足于搜索广告,而是继续把目光投向了其它的网站的流量,利用自身的技术优势,开始大量分析其它网站的网页内容,并根据网页的内容给用户提供广告,这就产生了上下文广告(Contextual Advertising)。上下文广告是根据网页的上下文内容进行的定向,这种定向方式是假定用户的兴趣点跟当前的网页内容是相关的。在定向广告以后的发展历史里,将会产生根据用户历史行为进行定向的技术(Behavior Targeting),那时,对用户历史行为的挖掘和分析将获得极大的发展。
随着互联网广告的演进,有一些需求方(Demand Side)对流量的定制化需求越来越高,甚至想自己去控制竞价流量,这样就产生了一种新的竞价模式:实时竞价(Real Time Bidding)。这种竞价方式改变了预先由广告主出价的模式,改为每次请求的时候,实时出价。随着互联网广告市场的媒体流量的聚合,一些聚合的流量联盟采用实时竞价的方式来变现自己的流量,这样就产生了一个新的互联网广告产品:广告交易平台(Ad Exchange)。说到广告交易平台,总要提起股票交易大厅的概念来作类比,也就是说,广告交易平台是一个交易平台,处于中间的角色,一方面接入了流量,另一方面接入了竞价的广告主;这种角色配置跟股票交易大厅的情况很类似。广告交易平台所聚合的中小流量,很多都不可能单独满足一个广告主的精细的定制化需求,比如:一个小型网站,作为流量的提供方(Supply Side),没有技术力量去做
人群分析等工作,就可以接入广告交易平台,由需求方来按照自己的挑选流量的标准去竞价,价高者得。这样既避免了小网站变现难的尴尬,也给广告主更多更自主的选择。上面所说的需求方组成的平台,叫做需求方平台(Demand Side Platform,DSP),提供方组成的平台叫做提供方平台(Supply Side Platform)。DSP可以是广告主自己,也可以是一些专门的技术公司,这是因为RTB技术是很专业、很复杂的技术,需要较强的技术力量。这方面的内容在后面还会详细讲到。
平行于售卖方式进化历史的另一个历史,是计费方式的历史。CPC(Cost per Click)是按照点击付费的方式,这种方式能够让一些中小网站媒体获得了可以变现的方式,即:不用跟大网站一样去费力的向大品牌广告主兜售自己的流量——大品牌广告主更倾向于大网站的充沛流量和影响力——而是可以把自己的流量加入到某些网络联盟里面,借助联盟的力量为自己变现,只要获得了点击就可以有收入。而CPS(Cost per Sale)模式则是更加有利于广告主的一种计费方式,这种方式只有在发生了销售的情况下,广告主才付费,这样的定价方式,可以让广告主基本达到一种“无忧”的投放状态,即不担心投资回报率的问题。但是,另一方面,CPM、CPC和CPS这些计费方式,无法相互取代,因为广告主的诉求是不一样的。有些广告主要求大面积、稳定的曝光,这时候,可能CPM会比较适合。有些广告主只是想把流量引入到自己的网站,这时候,CPC可能比较合适。有些广告主只想在成交的时候才付费,那么,CPS比较合适。关于计费方式,后面还要讨论。
目前在中国,最大的三家互联网公司BAT(Baidu、Alibaba、Tencent)已经掌控了超过90%的互联网在线广告市场收入。这三家企业分别是搜索、电子商务、即时通讯这几个方向的领军企业,在广告产品形式方面各有特点,但是背后的算法、引擎架构、存储方案都有相同或者想通的地方,这些将在后面详细介绍。
1.3 互联网广告类型
互联网广告从诞生之日起,就没有停止过形式创新的步伐,从最初的条幅广告开始,随之技术的进步,不断的丰富广告展示内容和方法。下面就对这些类型做一个简单的介绍。
(一)条幅广告(Banner Ad)
起源最早的互联网广告形式,一直到目前都活跃在各种网站上。这种广告一般具有固定的尺寸,内容用图片或者Flash等方式展现,有很多是动态的创意素材。
(二)邮件直接营销广告(Email Direct Marketing, EDM) 通过电子邮件的方式进行宣传的方式,这种方式要对客户的兴趣有一定的了解,否则极易沦为垃圾邮件,被扔进黑名单。
(三)富媒体广告(Rich Media Ad)
顾名思义,这种广告是内容展现力很强的一种广告形式,一般是采取中断式、侵入式、遮挡式的方式,想浏览者推送品牌性很强、创意很丰富的广告。这种广告甚至有时候允许用户交互。
(四)视频广告(Video Ad)
视频广告的形式比较多样,片头广告、片尾广告、暂停阶段的广告、正常播放中间的插片广告,等等。
(五)文字链广告(Textual Ad)
顾名思义,就是以文字内容为主的广告,文字一般配有链接,会引导到广告主的网站或者活动页。由于文字链广告占用篇幅少,而且可以跟上下文进行配合,所以应用场景很多,在搜索广告当中是主流形式。
(六)社交广告(Social Ad)
随着社交网络(Social Network)的兴起,在社交场景下,跟场景结合推出的广告,取得了很好的效果。随着国内社交产品的迅猛发展,尤其是微信等平台级产品的出现,使得国内的社交广告形式发生了巨大的变化。商家跟粉丝之间可以用微信平台进行互动,这种私密性是前所未有的,一些商家也看到了里面的广告商机,开始进驻微信等SNS平台进行营销,取得了惊人的效果,一些商家甚至利用这种社交工具进行定制化营销,为自己的粉丝定制商品。社交广告以后的发展空间是非常大的,也许会涌现出更加先进的广告推广方式。
(七)移动端广告(Mobile Ad)
严格来说,移动设备上面的广告跟PC端的广告没有本质区别,后台的算法也基本一致,只是由于载体换成了移动设备,所以单独把这种广告列出来。移动端广告的发展速度很快,并且在产品形式上有很大的创新空间,相信很快就会有新颖的移动广告出现。
1.4 有效性模型
广告的有效性模型,前人已经有了很好的成果,我们在这里就直接拿来用了。下图是广告有效性模型的图,有时候也称为广告效果过程图:
图1 广告有效性模型示意图
这个模型把整个广告推广过程分为三个大阶段:选择、解释和态度,又分为六个小阶段:曝光、关注、理解、信息接受、保持和购买。
“曝光”这个阶段,主要在于“位置”,这个跟开饭店很像,地段很重要。广告位的位置差异往往是巨大的,大型网站的首页的广告位CPT可以卖到一天上百万,而小网站的不显眼位置可能根本无法通过传统方式卖出,只能加入流量联盟,走Exchange的方式变现。
“关注”这个阶段,需要广告创意本身吸引人,并且借助算法的力量做到定向精准投放,才能够让浏览者更加关注。
“理解”指的是广告本身所传递的信息能否被浏览者理解,尤其是在当今快节奏的社会里面,让用户迅速的理解广告想传达的意思是一件不简单的事情。有些优秀的创意不但能够能够一下子抓住眼球,让人“关注”,而且设计巧妙,让浏览者一下子就知道这是什么品牌,什么活动,什么噱头。利用当下实事进行借位宣传也是普遍采取的方式,比如网络热点事件,网络流行词汇,等等。
“信息接受”是很难的,不同的人,观念不一样,很难让看到广告的人都能接受这些创意内容。比如一个特价活动的广告,有些用户更关心品质,所以有可能就对特价活动兴致缺缺。对于“信息接受”,除了研究人群行为,还要借助心理学方面的一些理论才能更好的优化创意。
“保持”的意思是指广告主要追求中长期的转化,让潜在消费者更关注品牌的核心价值,从而牢记在心是非常重要的。
“购买”其实就是最终的决策阶段,能否给用户提供更多更好的选择非常关键,在这方面,各个行业打动消费者的点不一样,比如对于电
商而言,创意上面的信息再花俏,如果不能促使用户在一段时间内购买,也是比较失败的。
总体而言,一个好的创意,不但能够吸引人(提升CTR),而且能够抓住人(提升ROI),这样的创意是比较优秀的。
1.5 计费模式
下面,先来看看有哪些互联网广告计费模式。 (一)CPM(Cost per Mille)
这里的Mille是拉丁文“千次”的意思,CPM即指按照千次展现计费。我们可以看到,这种方式就是按照展现计费,至于展现之后有什么样的效果,广告平台是不保证的。也就是说,在CPM计费方式下,广告平台只需要把广告投放出去,让广告主的广告获得足够的曝光,至于后续有多少人来点击?点击之后是否跳到了广告主自己的页面?跳到了广告主的页面之后,浏览者是否浏览了核心内容?浏览了内容之后是否有成交?……这些问题,广告系统一概不管。
所以,CPM的计费方式非常适合于品牌广告,因为品牌广告不仅仅注重当下的成交,更注重长远的品牌增值,注重品牌所影响的人群范围,注重知名度。
(二)CPT(Cost per Time)
顾名思义,这是按照单位时间计费的方式。一般来说,是针对大广告主的推广活动,以独占时间段的方式进行推广和计费。跟CPM类似,就是广告系统不负责对投资回报率进行预估和管理,仅仅是遵守时间的限制而已。显而易见,这种方式也是适合于大广告主为了增加曝光度的行为。
(三)CPC(Cost per Click)
CPC最早产生于搜索广告,目前是应用最广的计费方式。顾名思义,就是按照千次点击计费。CPC的计费方式下,一方面广告系统要负责对点击率进行预估,给出尽可能准确的预估分数;另一方面广告主可以参与竞价,变相的控制自己的推广流量。我们可以看到,在CPC方式下,广告系统和广告主的能动性都得到了一定的发挥,而在前面的CPM和CPT方式下,广告主基本是设定了一个宏观的值(投放总预算、总次数或者总时长)然后就撒手不管了。对于广告系统来说,CPC下需要做的CTR预估(CTR Prediction)是一个非常重要的计算广告学分支,是当今研究的热点,这部分在后面有详细讨论。
在CPC下,广告系统关注点击率,却仍然不关注广告的实际成交情况,成交风险仍然是广告主自己承担。
(四)CPS(Cost per Sale)
CPS方式下,广告系统终于开始关注转化率了!因为CPS计费的核心就是按照成交计费,所以广告系统对于ROI指标要进行预估。CPS下,广告系统完全站在了广告主这一边。
我们来总结一下各种计费方式,从广告主的角度来看,不同的计费方式对自己来说风险是不一样的,按照风险从大到小,各种计费方式的排列是:CPM/CPT,CPC,CPS。从流量提供方的角度来看,风险同样存在分别,从大到小分别是:CPS,CPC,CPM/CPT。大家可以看到,流量提供方和广告主方的风险级别几乎是反向的,也就是说,在CPM/CPT下面,流量提供方不用承担太多的预估计算的风险,而在CPS下,广告主可以不用担心自己的投放费用打水漂。所以,采取什么样的计费方式,就要照顾到各方的利益,综合来看。CPC的方式能够照顾到流量提供方和广告主的控制权,所以目前被广泛接受;CPM/CPT受大的品牌广告主的青睐;CPS在一些特殊的推广渠道(阿里巴巴推出的“淘客”产品)有自己的用武之地。
在移动互联网和社交产品急速发展的今天,有一些新的收费方式也在酝酿和发展当中。比如,按照收藏量来计费的方式。在一些APP(APP指的是在iOS和Android等平台下的应用程序)当中,曾经尝试过按照浏览者是否“收藏”了该商品(或者是店铺,或者是品牌)来收费。一些游戏的广告主是按照游戏的安装或者激活来付费。未来,计费模式肯定会有更大的创新。
我们谈了这么多的计费方式,那么广告系统对于自己的收益指标是拿什么来评估呢?对于定量表示若干次展现的期望收益(CPM)值,有一个专有名词eCPM(expected CPM)来表示。这个概念是广告系统当中最经常被提起的收益评估指标。
1.6 机制设计
机制设计是经济学中的一个重要研究课题。在经济学中,机制设计所讨论的问题是:在给定一个社会目标或者经济目标,以及自由选择、自愿交换的分散化决策条件下,能否并且怎样设计一个经济机制(包括制约条件、资源配置等),使得参与者的个人利益和设计者既定的目标一致。互联网广告的参与者包括广告平台、广告主和广告受众。广告机制设计研究的是,如何针对不同广告受众,将广告平台上有限的展现位置分配给不同的广告,以达到某种既定的利益目标。这个目标在不同公司甚至不同广告业务线不尽相同,有可能是实现广告平台的利益最大化,也有可能是实现广告平台、广告主和广告受众三赢,由广告平台选择。
互联网广告的计费方式有CPM、CPT、CPC、CPS等等。其中,CPC方式的覆盖范围最广,搜索广告和定向广告大部分是以CPC方式进行收费。CPC方式所涉及的竞价方式,也最为丰富。因此本章以CPC广告为例,介绍其中涉及的机制设计知识。
1.6.1 广告位拍卖
搜索广告的竞价机制可以抽象为一种广告位拍卖机制。在搜索广告平台上,广告主会为自己的广告选择一些相关的关键字,并在这些关键
字下出具不同的竞价。这样,对于一个给定的关键字,可以关联上若干条不同的广告,每条广告有不同的竞价,这些广告在广告系统中形成了一个竞拍关系,竞拍的目标是一次关键字命中后,系统中空出的若干条广告位。形式化而言,假设有平台提供
,n个广告,另外广告
,m个广告位,这里m 目的是从A中选取m条广告,依次放置到S中。如果广告被点击了,广告系统需要的广告主收取一定的费用。对于通常的广告系统,即使是同一次广告展现,不同的展现位置收到的用户关注度也会不同。例如,百度的搜索广告中,广告的展现形式是自上而下的排列若干条广告,这种展现形式中,排第一位的广告天然会有更高的点击率。因此,对于广告主而言,每次关键字拍卖竞争的不仅是是否获得展现机会,还包括在S中的排序位置。 不难看出,广告位的拍卖过程大致可以分为两个步骤,广告排序和广告扣费。广告排序解决当关键字命中后,展现哪些广告的问题。广告扣费则关心当广告被点击后,向广告主收取多少费用的问题。互联网广告的不同发展时期,不同的公司,使用的广告排序方式和广告扣费方式有所不同。在后面的三节中,我们会讨论三种比较常见的排序方法和扣费机制。这里,我们先讨论一些拍卖理论中评价拍卖策略优劣的通用指标。 拍卖理论中,竞拍各方通过相互博弈,竞争待分配的资源,形成最终交易。在竞拍过程中,如果存在一点,博弈各方如果改变竞价策略就会导致利益损失。这一点,就被称为纳什均衡点。存在纳什均衡点,表 示该拍卖策略存在一种稳定状态,在这个状态下,博弈双方如果做出策略改变,就会导致利益损失,因为各方都趋于保持该状态。在互联网关键字拍卖中,广告主可能会频繁的修改自己的出价。因此,关键字拍卖的博弈过程是一种无限重复的博弈,这种博弈过程会有很多不同的纳什均衡点。过多的均衡点不便于分析拍卖策略的效果,于是有人提出一种本地无嫉妒均衡(locally envy-free equilibria),又称对称纳什均衡。本地无嫉妒均衡是指,排在第k位的广告主,如果增大出价排到第k-1位,不会增加其收益。 与纳什均衡相关联的一个概念是占优策略,占优策略是指无论竞争对手采取什么策略,都能使本方获得最大利益的策略。与纳什均衡不同的是,占用策略不考虑其他竞争者的策略,都能保证自己利益最大。 此外,关键字拍卖希望广告主按照自己的真实估价出价,并通过调整扣费方式来激励用户按照真实估价出价。如果竞拍方按照真实估价出价,能够保证其获得最大利益,则该竞价策略称为激励相容。 1.6.2 广义一阶价格(GFP) 世界上首例互联网广告诞生于1994年,与现在主流的计费方式不同,早期的互联网广告大部分采取按照展现收费的方式。在那段互联网广告的原始时代,既没有自动投放系统,也没有自动计费系统。广告主通过线下签订商业合同的方式,从互联网媒体那里购买从一定流量。一 般来说,每笔交易涉及的流量大约只有几千次展现。即便如此,广告的花费却比如今的广告贵很多,通常广告主一个月大约要花费几千美金。更糟糕的是,这种线下交易的方式,通常操作起来流程相当复杂,广告主往往需要等待很长时间才能看见自己的广告生效。 1997年,Overture公司(已被Yahoo!收购)提出了一套全新的广告售卖机制,就是所谓的竞价排名机制。广告主选择跟自己商品相关的关键字,并对它竞价。用户输入关键字时,搜索引擎按照竞价由高到低的顺序,自上而下的展现相关广告。这样展现的原因是,通常情况下,越靠上的广告位越能吸引用户的注意,因而商机越好。与早期的互联网广告不同,在Overture的商业模式中,广告展现并不扣费,只有当用户点击了某个广告,才会扣除广告主竞买这个关键字的价格。按照这样的商业模式,Overture开发的广告投放系统,在当年一炮走红,成为Yahoo!和MSN等知名搜索引擎的广告提供商。 Overture的拍卖策略就是所谓的广义一阶价格拍卖,这里的一阶价格是指广告主本身的出价。广告的排序方式采取按照竞价降序排列,然后选取排序较高的前几个广告用于展现。在广义一阶价格模式的扣费方法是,如果广告发生点击了,便会按照广告主的竞拍出价,进行扣费。 但是Overture的成功背后却隐藏着巨大的危机。因为理论上来说,广义一阶价格排序不存在纳什均衡点。所以当Overture支持快速改价功能后,于是市场上出现了竞价机器人,帮助广告主在不丢失自己想要广告位的情况下,不断尝试降低竞价。比如说,现在有三个广告位售卖,a、b和c三个广告主分别出价¥6,¥4和¥1。如果,b使用竞价机 器不断调价,那么为了保住他第二名的广告位,竞价机器人最终只要给出¥1.01就可以了。同理,如果a也使用竞价机器人,那么a为了保住第一名的广告位,只要给出¥1.02即可。因此,竞价机器人的出现,导致广告系统的收益大大降低。此外,竞价机器人的频繁改价,也极大的加重的广告系统的负载。 1.6.3 广义二阶价格(GSP) Google意识到,竞价机器人的出现实际是广义一阶价格模式激励了广告主不断调低竞价,以便降低自己的广告成本。于是,Google提出了自己的计费机制,该机制被称为广义二阶价格。对应第i位的广告,如果发生点击,那么广义二阶价格扣费是,收取第i位广告主,第i+1位广告竞价加上一个货币最小值。在上一段的例子中,广告主a和b发生点击的收费分别是¥4.01和¥1.01。在广义二阶价格中,广告主降低其竞价,在其展现位置不变的情况下,不会降低收费。因此,杜绝了竞价机器人对广告系统的恶劣影响。此外,因为下家没有降低竞价的行为,其结果导致上家需要付出更多的点击费用。如果人人皆如此,广告系统的实际收益反而会比广义一阶价格更多。 对于广义二阶价格,存在所谓本地无嫉妒均衡,举例说明 图2 广告位和点击率 图3 广告和点击价值 假设A、B、C三条广告竞争1、2两个广告位,其中1、2的点击率以及A、B、C的每次点击价值如上表。那么(4,1,0.5)是一个均衡报价。因为,任意一方如果加价是的排名升高,都会导致利益降低。 形式化的,对于值为置的点击率为 ,n个广告,每条广告的点击价 ,另外广告平台提供 ,每个位置当前竞价为 。对于任意的广告位i上获得位置的广告j有 则称,当前状况为均衡报价。需要注意的是,广义二阶价格的均衡点不唯一。并且,广义二阶价格不是一个激励相容的机制。广告主如果按照真实点击价值报价,并不一定是最优的选择。例如: ,每个位 图4 广告位和点击率 图5 广告和点击价值 按照上表,此时如果按照真实点击价值报价为(5,2,1),而如果A降低报价为1.5,他将获得更大的利益。因此,广义二阶价格不是一个激励相容的机制。 尽管如此,由于广义二阶价格简单易行。当前国内各大互联网广告公司如百度、淘宝等,使用的关键词竞拍模式都是基于广义二阶价格拍卖。在真实的系统中,不会将广告简单的按照竞价扣费,扣费也不是简单的按照下家加一的方式进行。因为在CPC的广告场景下,需要考虑广告的点击率因素,即使是竞价很高的广告,如果点击率很低也不会给广告系统带来多大的收益,因此不应该给这类广告分配展现。因此,对于每条广告i,广告系统会首先预估广告i在当前展现场景下的点击率,结合其竞价,然后计算其每千次展现的期望收益为 (原则上,计算,所以就简化为 ,但是不乘常数项1000不影响后面的),然后将广告集合按照ecpm排序, 选取排序靠前的若干条广告用于展现。在计费时,如果第i个广告被点击了,那么从广告主处扣除的费用为: 这里i+1表示排名在i后面一位的广告。上式可见,广告的点击率越高,那么当它被点击事,从广告主处扣除的费用就越少。而广告平台采取这种方式扣费,可以激励用户优化广告质量提高广告点击率,从而也提高了整个广告系统的用户体验。 1.6.4 VCG机制 VCG(Vickrey-Clarke-Groves)机制是一种目标为最大化社会价值的竞价机制,在互联网中有一定的应用,facebook和bing曾经使用过VCG机制。假设有价为置的点击率为 ,n个广告,每条广告的竞 ,每个位 ,另外广告平台提供 。VCG机制假设用户按照真实估价报 价,那么每条广告的真实价值便是V。那么当广告i不参与关键字拍卖时,排在i后面的广告主i+1,i+2,?,m可以获得的预期总收益为 而由于的参与,这些广告获得的价值为 通常情况下因为只有m个广告位,所以 。那么,如果被 点击了,那么它要付出的代价是他给社会上的其他个体带来的利益损失 与GSP相比,VCG有一些理论上的优势: 第一,VCG是一个激励相容的机制,在VCG机制下,按照真实估价出价是最有选择。 第二,VCG机制最大化社会价值,对广告主来说是一个很好的机制。 第三,VCG存在纳什均衡,且均衡点唯一。 尽管如此,工业界使用VCG机制的并不多,原因在于VCG虽然有很好的理论性质却也有很多缺点: 第一,VCG计算困难,且难以向广告主解释。 第二,在相同竞价情况下VCG机制的扣费会低于GSP机制,因此鲜有广告系统愿意降低收入使用VCG机制。 1.7 技术课题 1.7.1 优化目标 互联网广告算法要解决的核心问题是什么?雅虎研究院的Andrei Broder在2008年首次提出了计算广告学(Computational Advertising)的概念。他给出了一个并不十分严谨的表述:找到用户、上下文和合适的广告之间的最佳匹配。 我们不必对Andrei Broder的定义咬文嚼字的进行分析,这个定义只是对下面展开描述的一个铺垫。我们对于互联网广告要解决的核心任务做了一个新的归纳,如下: 互联网广告算法的核心问题,是根据用户、环境、广告的全部有效信息,找到最合适的投放策略和模型,兼顾浏览者、广告主、广告平台的最大利益,并不断调整。 上面的归纳也不是一个严格的定义,只是本书的一家之言。首先,我们可以看到,互联网广告算法和策略的核心是维护一个多方博弈的生态圈,不是一方独大的局面。同时,不同的广告产品形式,不同的广告平台,侧重点是不一样的。其次,互联网广告算法和策略要利用的信息来自用户、环境(上下文,或者称情境)、广告,我们分别用U(user)、C(context)、A(ad)来表示,那么我们可以把算法的目标函数简单表示为: 从这里我们只能看出,这个函数F跟U、C、A都有关,但是具体的内容并不清楚。对于广告主来说,由于投放广告更多的考虑是投资回 报率的问题,即ROI(Return On Investment),所以,对于广告主的F是: 所以,对于广告主的核心利益,目标变成了对上述F的最优化问题。这里有一个需要注意的地方,对于第1次到第N次的展现(i=1…N),总体的ROI最优化并不等于每一次的展现ROI最优化之和,但是,由于广告系统是每次展示就要立刻计算的,所以,一般来说都是在每次展示的时候立刻计算ROI,虽然这种方式跟全局优化的目标未必一致,但是也已经成为了业界的通用做法。 对于浏览者来说,核心利益是ROI吗?我们举个例子,看看在电子商k务平台上面,浏览者跟广告的关系。我们平时在淘宝购物的时候,如果看到广告,感兴趣的话,会去点击,如果商品是我们需要的,可能会下单购买。在整个点击广告、购买商品的过程中,广告主投放广告花了多少钱,这些钱带回来多少成交,我们这些普通的浏览者并不关心;而这个广告产品有没有用,定向的准不准确,创意好不好看……这些才是浏览者在意的。所以,从这个例子可以看出,浏览者更注重广告对自己的吸引大不大,而这种吸引可以部分的反应在CTR这个指标上。所以,对于浏览者来说,F是: 现在,我们再来看看对于平台来说(广告系统方面)核心利益是不是又有所区别呢?广告系统的目的是帮助广告主推广商品,同时能够盈 利,所以,广告系统有一个非常重要的核心目标,就是收入,我们用RPM来表达这个指标: 上面的公式里,CTR(Click Through Rate)是点击率,PPC(Pay per Click)是点击收费,上面的公式的意思就是RPM等于点击率和PPC的线性叠加,有些时候还有一些Discount(折扣)方面的业务因子。 虽然广告主、浏览者、广告平台各自的核心利益并不完全一样,但是,一旦竞价模式、计费规则等定下来,大家都是遵守同一规则来参与的,当生态系统发生了变化的时候,规则和算法也应该进行相应的调整。 1.7.2 搜索引擎技术 从功能上来看,广告系统搜索引擎十分相似。实际上,广告系统的确包含了大部分的搜索引擎功能:倒排索引、搜索词分析、排序……。但是,这两个系统还是有很大区别的,比如广告系统有计费模块,有广告主实时更改价格的子系统,等等。 广告系统的创意库数据量有时候十分巨大,数以亿计,甚至数以十亿计,所以,广告系统对于检索性能的要求一点也不比搜索引擎低。实际上,检索性能一直是广告系统所追求的目标之一。一个优秀的广告系统,一次完整的查询和排序计算过程,一般在几十毫秒之内完成。 跟通用搜索引擎不同的是,广告系统可能没有典型的爬虫(Crawler)模块。这是因为广告系统的广告内容一般来说都是公司内部的资源,所以可以通过规范化的步骤获取,而不用Crawler来抓取。 1.7.3 存储技术和实时计算技术 广告系统在离线部分,需要存储大量的用户历史行为信息、用户属性、商品标签……等等信息,信息量很大,可以达到T级别,需要有一个适合大规模读写的存储系统。现在的大规模存储技术发展很快,大量有特点的开源系统被大公司采用。 另一方面,广告系统对实时计算方面的需求增长很快,有很多方面需要有实时计算的系统,比如:用户行为分析的实时计算、点击率预估的特征更新计算……这些系统的介绍将放在最后一部分。 1.7.4 推荐技术 推荐(Recommendation)方法在互联网广告系统中应用很广,我们经常在购物网站上面看到“购买过这个商品的人还购买了”、“跟你有同样爱好的人还喜欢”等等标题的广告位,类似的标题就是说明在这个位置应用了推荐技术。推荐技术能够很好的解决“人与人”或者“商 品与商品”的关系问题,提供一套非常成熟稳定的映射结果。推荐方面的内容将在后面详细介绍。读者也可以看一下这方面的论文。 1.7.5 点击率预估 点击率预估(CTR Prediction)是互联网广告算法当中非常重要的一个方向。在前面讲优化目标的时候,我们可以看到CTR这个指标是非常重要的,也是排序(Ranking)当中的核心参数之一。点击率预估涉及到模型方法、特征的选取和评估、实时系统的架构……等等诸多问题,这方面的内容也会在后面详细介绍。 1.7.6 广告主工具 对于广告主,广告系统会提供推广工具和统计工具来帮助广告主进行广告营销。一般情况下,大型的广告系统会对广告主推荐一些投放方法,比如:对特定搜索词竞价,对特定人群维度竞价……等等。 举个例子,对于搜索广告,广告系统所推荐的搜索词,是经过相关性计算,并且综合了覆盖率等其它因素之后,推荐给广告主的。广告系统提供的这些搜索词,避免了广告主对于搜索广告投放“闭门造车”, 大大减少了广告主对市场的调研开销,使得中小广告主也能够准确的选择投放渠道,并达到满意的效果。 1.8 系统架构简介 一个典型的广告投放系统,大概包括如下几个主要的组成部分,分别介绍一下。 前端引擎:这部分是接收网页(或者移动设备)发过来的广告请求,并经过初步处理(判断请求合法性,等等)之后向后端传递,并在拿到后端返回的结果之后,进行拼装并返回给请求者。这部分是在线部分(online)。 检索引擎:这部分是根据检索关键字,对事先存好的倒排索引进行检索,取出关键字对应的索引内容。这部分的主要关注点就是效率和性能。这部分是在线部分(online)。 实时点击率预估服务:这部分是对广告打分,这个分数将极大的影响广告的最终展现。如果广告系统比较简单,对广告的打分是一维的分数(即一个广告一个分数),那么这个服务其实也可以做成一个静态的数据存储服务。而现在真正的大型广告系统,都是实时计算二维的联合分数,比如搜索广告会实时计算 广告主操作消息更新服务:广告主是有权利随时更改自己的广告竞价的,这就需要一个实时更新的服务来将新价格更新到索引里去。其实,广告主随时更改的,不仅限于广告的价格,还有广告的投放地域、投放人群、投放时间、价格折扣,等等各种参数。所以,更新服务的压力是非常大的,除了要保证更新消息的及时性,同时还要保证更新息的完整性和安全性。这部分是在线部分(online)。 用户行为数据收集和更新系统:系统收集的行为数据,经过一些处理(初步的反作弊、过滤)生成结构化的中间层数据,再供后续模块调用。这里需要说明的是,行为数据既可以被离线(offline)的算法模块调用,也可以被在线(online)的算法和业务模块调用。一般来说,用户行为数据收集和更新系统是实时或者准实时的将行为数据导入存储系统的,这是为了迅速更新用户特征,更准确的计算点击率。这部分是在线部分(online)。 特征提取和行为分析:这部分都是利用“用户行为数据收集和更新系统”的数据,进行特征提取、用户行为分析等离线操作,一般是用Hadoop平台来完成这样的海量数据的处理。对Hadoop不了解的同学,可以去搜索一下Hadoop的基本原理和程序设计。这部分是离线部分(offline)。 反作弊系统:这部分是用来发现和处理作弊信息,包括异常的访问、无效的点击等等。反作弊的机制比较复杂,有实时的反作弊模块,也有周期性运行的模块,有人工规则,也有模型判定。这部分既有离线部分(offline)也有在线部分(online)。 广告主后台:这部分是给广告主管理自己所有的投放活动的系统。一般来说,广告主典型的行为包括:建立投放计划,增加投放创意,出价,设定投放参数,阅读报表(包括实时和非实时),等等。这部分既有离线部分(offline)也有在线部分(online)。 存储系统:广告系统很多的存储任务都是 计算系统:广告系统的离线计算包括各种数据挖掘任务,比如人群属性(User Profile)的挖掘,意图(User Intention)的挖掘;也包括很多特征提取的任务,比如:给Ctr Prediction用的User Feature;还有一些模型训练的任务,等等。计算资源也一直是衡量一个大公司硬实力的核心指标之一。一般采取Hadoop来做数据挖掘和特征提取等计算,采取MPI等架构来做模型训练等任务。当然,每个大公司的架构选型都不太一样。 第二部分 搜索广告 2.1 搜索广告架构 搜索广告是指,在搜索过程中,搜索引擎推送给我们的互联网广告。例如,每当我们打开百度搜索引擎,输入查询,在得到搜索结果的同时,页面的右侧和搜索结果的上方,会有一些推广链接。这些推广链接,就是我们常说的搜索广告。搜索引擎通过这些推广链接获取了巨额的收益,参考Google财报,Google主站2011年的总收益约是261亿美元,其中绝大部分收入来自于搜索广告。从某种意义上说,是搜索广告养活了搜索引擎,也为终端用户的搜索服务买了单。 那么,从搜索引擎收到查询,到最后展出广告,都发生了哪些事情呢? 一般来说,当用户输入一个查询后,广告系统会经过:广告检索、广告排序、流量分配,三个模块为用户提供广告。 广告检索模块,是以当前的查询关键字为基础,辅以用户自身的信息,从数以千万乃至上亿的广告大集合中,粗选出一些比较合适的广告,交给后续的广告排序模块进行排序。广告检索模块,又可以分为广告索引和广告匹配两个子模块。广告索引模块,将广告建成 广告排序模块,计算检索到广告的质量分数,并以此进行排序。搜索广告一般是按照点击计费,也就是说,展现出去了,如果用户没点,搜索引擎是不收广告主钱的;如果用户点了,广告系统才会收费。那具体一次点击收多少钱呢?因此,在广告排序模块中,最为重要的莫过于CTR预估模型。CTR预估模型会从用户的信息、关键字、广告本身中抽取有用特征。再调用机器学习模型,预估出用户对广告的CTR。 流量分配模块,根据广告的排序分数,决定当前情况给用户出哪些广告。广告系统会对每次流量出的广告数量和广告质量做一些限制。流量分配模块,就是根据这些限制,实时的展现广告。 2.2 广告检索 搜索广告需要按照用户的关键字,选出相关的广告。在实际的系统中,一般会设置粗选和精选两个步骤。粗选是用信息检索的方法,选取和查询关键字相关的一批广告。精选则是要精确的预估广告的点击率,进行排序。本章将会介绍信息检索的相关技术,后续的章节将会介绍CTR预估相关的算法。一般来说,广告检索需要经过三个步骤,广告分析,关键字分析和相关性匹配。广告分析是指,对广告进行处理,获取广告相关的信息,如作用地域、作用年龄段、作用人群等,并按照与广告相关的竞价词将广告组织成倒排索引的形式。关键字分析则是根据用户的输入,判断是否应该出广告,如果有必要出广告,那么应该出什么 类型的广告。相关性匹配则是根据关键字分析的结果,去广告索引库中检索广告,并按照一定的相关性算法选取相关性大的广告交给后续的精选环节。本章的接下来部分将会分别介绍广告分析、关键字分析和相关性匹配设计的内容和涉及的算法。 2.2.1 广告分析 一般来说,广告分析有两个目的,第一个目的是将广告组织成倒排索引的形式。所谓倒排索引,是这样一种key-value格式,key是一个竞价词,value是一个广告id的链表。在检索广告时,广告系统就是用竞价词作为key,找出与该竞价词相关的若干广告。广告分析的第二个目的,是从广告中抽取特征,如广告是否地区相关,属于什么类型广告等等。这些信息,可以在相关性匹配阶段提供辅助信息,过滤不相关的广告。 在广告主建立广告时,会选择与其相关的竞价词,并提供广告在每个竞价词下的竞价。一种简单的方式是按照广告主提供的竞价词建立索引,如果广告主买了某个竞价词,则广告会被挂到该竞价词的value链下。但是,广告主的想象力通常比较有限,这种简单的索引建立方式会导致索引向某些常见词严重倾斜。随着广告系统中广告主和广告的增加,这种倾斜状况会越来越严重。大型的广告系统会提供一些技术和产品解决此类问题,比较常见的方法包括竞价词生成和模糊匹配。 竞价词生成是指广告系统通过分析广告主的landing page,帮助广告主选取竞价词。这样可以引导广告主选择一些竞争不那么激烈的词,保证索引中广告链长度均匀。竞价词生成会抓取landing page中的文字,并对其做命名实体识别,抽取其中可能的商品词、型号词等,作为竞价词推荐给广告主。 模糊匹配是指用户选择一个通投出价,按照这个出价,广告系统自己选择跟广告相关的竞价词。一般的选择方式是,根据用户已卖的关键词,推出跟这些关键词和广告标题相关的竞价词。并按照一定的探测逻辑,尝试在这些竞价词下出广告。 经过这些处理以后,广告最终建立成索引。广告系统还会根据自己业务线的具体需要抽取相应的信息做相关性条件。最终,这些数据被传到后续的相关性匹配环节中。 2.2.2 查询分析 用户在搜索引擎上输入的关键字,用词的长短可能不完全相同。做查询分析时,对长串和短串的处理方式是不同的。一般的广告系统都会对长串和短串做区分处理。一般来说,长串的语义信息明确,如果确有广告主买了这个长串做竞价词,那么按照该词出广告,往往可以获得更高的转化。但是缺点是,每个长串在广告系统的展现量往往不足,而长串的总量又会很大,往往对广告系统的存储造成很大压力。而短串一般 都是一些用户会频繁输入的词,每条短串下的广告展现量会丰富,给算法分析提供很高的便利。但是缺点是,短串的语义信息可能不明确,需要一些方法来帮助明确用户的意图。 对于长串,语义信息一般比较丰富,但是分词后会有多个词语,所以从长串中提取关键的词汇更加重要。例如,用户输入“海底捞火锅”,包含两个词“海底捞”和“火锅”,此时需要区分到底是“海底捞”更重要还是“火锅”更重要。一般来说,认为“海底捞”这类的品牌词更加重要,所以如果有两条广告分别是关于“海底捞旗舰店”和“小肥羊火锅”,此时更应该出前者相关的广告。 而对于短串,分词后一般只有一个词语,有些情况下,还可能是多义词。例如,用户输入“土豆”,他可能是想知道土豆网的链接地址,也可能真的是想找蔬菜土豆的信息。这个时候,就需要对“土豆”一次做消歧。消歧的方法一般是两种,一种是根据用户的个性化信息,如用户的年龄、性别、学历、工作等,推算用户更有可能指的是哪一个“土豆”。另一种方法,是根据搜索的上下文信息,如果用户在输入“土豆”前查找的是“优酷”,那此时更有可能指的是土豆网。而如果用户在输入“土豆”前查找的是“地三鲜”,那此时更有可能指的是蔬菜土豆。 此外,在查询分析阶段,一项最重要的指标是扩大召回。查询扩展是扩大召回的一个可靠方法,通过分析用户输入的关键词,得到与其语意相近的相关词,用这些相关词下的广告扩充广告候选集。用来做查询扩展的技术包括,用topic model、用语意字典扩充、事先构造本体扩充以及通过query-ad链接分析查询相似度做关键字聚类的方法等等。 2.2.3 相关性匹配 广告的相关性匹配可以分成精确匹配和模糊匹配两种模式。精确匹配是指只有当关键字中严格的包含某个竞价词时,才触发的广告。在匹配时,首先从关键字中提取出能匹配成功的竞价词,然后在以竞价词为key的广告索引库中提取广告即可。 在搜索广告中,用户输入的关键字如果很短,那么往往不能匹配上足够多的竞价词,从而使得召回降低。为了解决这个问题,广告系统往往会使用模糊匹配,扩充竞价词,已获得更多的广告。模糊匹配获得的竞价词,及其相关的广告,由于不是精确获得,需要对不同竞价词区分对待,此时需要有一些算法精确计算关键字同竞价词之间的相似度。除了文本的相似度以外,在模糊匹配时,还会考虑搜索上下文,以及用户本身的个性化信息等,作为辅助更加精准的向用户投放广告。 2.3 广告排序 在前面的章节介绍了主流广告系统的排序逻辑。通常,广告系统会按照ECPM(Effective Cost Per Mille,指的是每一千次展现可以获得的广告收入)降序排列广告候选集,然后将排序靠前的广告展现出来。这里,ECPM=广告竞拍价*广告CTR*1000,其中,广告竞拍价由广告主提供,而广告CTR则需要广告系统利用机器学习的方法,进行准确 的预估。而广告CTR预估的精度,将直接影响广告系统的收入。因此,在各大互联网广告公司中,都会深入研究广告CTR预估的方法,从而最大化其收益。 业界用于CTR预估的方法大致可以分成两大类,基于点击模型的方法和基于机器学习的方法。点击模型的方法在互联网广告出现的早期比较常见,当时的CTR预估多基于简单统计的方法。对于一个展现充分的广告来说,预估其CTR最有效的策略是直接从数据中统计其点击次数和展现次数,直接算出其历史CTR来预测其未来的CTR。但是,在应用中发现,广告的CTR会受到广告展现位置的影响。通常,展现位置靠上的广告天然会赢得更高的CTR。如果直接通过统计的方法计算广告的CTR势必会受到位置因素的影响。利用直接统计的方法,频繁展现在第一位的广告会获得更高的CTR。为了克服位置因素的影响,学术界提出了很多种所谓点击模型。大部分点击模型的思路,是将点击率建模成如下形式, 在上式中, 是日志中统计到的广告CTR,而在学术界会有 ,然后通过上式计算出 很多不同的点击模型来预测 ,作为广告真实的CTR用于未来使用。学术界计算 的方法非常多,考虑的因素往往也很多,比如位置本身、前面位置的广告是否被点击、用户本身的点击偏好等等。 基于点击模型的方法,往往只能对展现充分的广告做出准确的CTR预估。而一般的广告系统中,能获得充分展现的广告往往只占系统中很 小的一部分。而每天上架的大量新广告,往往不能用点击模型来计算CTR。为了解决新广告的CTR预估问题,学术界和工业界都尝试了很多种办法。解决的方法是利用机器学习算法,综合考虑大量特征,预测广告的CTR。当今工业界,最流行的方法便是用逻辑回归模型解决CTR预估问题。本章将会详细介绍基于逻辑回归模型的CTR预估方法。一个中等规模的互联网广告公司每天会接受上亿次访问请求,产生几T规模的访问日志,什么样的机器学习模型能够有效的处理如此海量的数据,并从中挖掘出有用信息,并能实时的给出准确的CTR预估结果。第一节将重点讨论在搜索广告中常用的逻辑回归模型,并分析其在训练和预测阶段的一些性质和优缺点。在机器学习问题中,数据的特征抽取会直接影响后续的模型精度。因此,对于广告CTR预估,特别是搜索广告的CTR预估,抽取哪些特征是一个非常重要的研究课题。第二节将介绍搜索广告中常用的特征处理方法,并给出一些常用的特征分析算法。在互联网广告公司中,算法迭代的速度是非常惊人的,有时甚至几十分钟就可以完成一次模型的更新。但是,未必每次模型更新都会带来效果的提升。因此,在模型发布前,需要经过科学的评估,以确保其能带来效果的提升。第三节将列举一些常用的模型评估方法,首先介绍通常的在线评估策略,然后重点介绍离线评估中常用的评测标准,并分析其背后的数学含义。 2.3.1 辑回归模型 逻辑回归的函数形式为,,这里e是自然对数,x是 输入的特征向量,y是预测目标,w是需要学习的特征权重。以x为一维向量为例,图中给出当w取不同值时,y随着x值变化的函数曲线。逻辑回归的函数曲线为一条S型曲线,随着x从-∞向∞逐渐增大,y值从0向1逐渐增大,并与y轴相交于(0,1/2)点。w控制了y值从0到1的过渡速度,w越小y值过渡的越平缓,w越大y值过渡的越迅速。 图 6 sigmoid函数 逻辑回归可以被用做分类和回归。当用作二分类问题时,假设数据分成0,1两种类别,而逻辑回归的函数结果既是输入x,类别为1的条件概率,即: 另一方面,输入x,类别为0的概率为1-P(Y=1|x),即: 二分类时,取两个类别中条件概率较大者作为输入x的类别。换句话说,当P(Y=1|x)>1/2时,Y取1类别;P(Y=1|x)<1/2时,Y取0类别。可见,逻辑回归的分界面是P(Y=1|x)=1/2时所对应的超平面 。 因为逻辑回归的值域分布为(0,1)而不是整个实数域,所以在用作回归问题时,通常是被用作拟合随机变量的发生概率。在互联网广告中,也是使用逻辑回归来预测发生点击这一事件的概率,即点击率CTR。在广告的CTR预估中,x是表示广告的特征,通常为处理过后的0,1特征,维度极高,一般为上亿级别。广告系统利用一段时间的广告点击日志作为训练数据,离线训练得到特征权重w,并用在线算法和实时数据不断微调w。最后得到的特征权重w,被用于实时计算广告的CTR。 在广告系统中,通常采用极大似然估计法来学习特征权重w,对于给定的训练样本集 ,这里如果样本i 被点击了,那么取1;否则取0。训练样本集T的似然函数为: 这里的样本, 。上式其实是一个条件判断公式,对于=1为1,似然函数只取;而对于=0的样本, 为 1,似然函数只取1-。似然函数是一个连乘积的形式,在求导过程中不容易计算,所以大部分极大似然估计法通常最大化的是似然函数的对数,对数似然函数为: 需要注意的是,不论是似然函数还是对数似然函数,都是关于特征权重w的一个函数,极大似然估计法的目的,就是需要通过各种优化方法找到使得对数似然函数最大化的特征权重。在优化方法的学术术语中,逻辑回归的求解属于无约束的优化问题,且目标函数负对数似然函数恰好是凸函数,并且在可行域上连续可微。不了解优化的读者可能不理解上面一句话的意思,简单的说,就是逻辑回归的似然函数恰好满足很好的性质,很多种经典的优化方法都可以被用于求解特征权重w。常用的方法包括,梯度下降法、随机梯度下降法、牛顿法和拟牛顿法。下面以梯度下降法为例,继续介绍如何求解逻辑回归的特征权重w。 对于无约束优化问题,梯度下降法的核心思想是,对于一个给定的特征权重值 ,我们需要找到一个方向,保证特征权重值往这个方向走 。这样,进过不停的迭代,让特征 一点,能得到似然函数值更大的 权重值收敛在最优特征权重。这里,我们需要找的方向就是负对数似然函数的梯度方向,即对于 来说,其需要找的方向为: 这里,用f(w)表示负对数似然函数。需要注意的是,是一个维度与x,w相同的向量,而不是一个标量。 而w的迭代公式如下: 其中,为第k步的迭代步长,步长的选择是梯度下降法里最为纠结的研究课题,步长设定的过大,容易造成迭代过程在最优特征权重附近来回振荡而不收敛,设定太小的步长又会使求解的过程太慢。这里我们就不再赘述步长选择问题。 在实际广告系统中,特征向量的x维度极高,至少在亿量级,有些系统甚至上百亿千亿。如此高维的特征向量,极易造成模型过拟合,从而影响模型的泛化能力。因此,需要用正则化的方法防止模型过拟合,其中最常用的正则化方法是L2正则和L1正则,两种正则化后的负对数似然函数如下: 上式中的NLL是负对数似然函数,是一个正则项权重,L2正则项即w中每一维权重值的平方和,而L2正则项是w中每一维权重值的绝对值和。L2正则,可以防止得到单维绝对值过高的w,从而防止模型过拟合。L1则更加激进,不仅可以防止出现单维绝对值过高,还能使得大量特征的权重为0,从而起到特征选择的作用,因此,L1正则方法在互联网广告CTR预估中被广泛的应用。 在实际的广告系统中,用户的兴趣习惯可能会在某个时间点发现突然的漂移。例如,淘宝的双十一促销、情人节玫瑰的热销等。这些漂移要求模型能够针对新数据的反馈,迅速改变模型权重,以适应现实环境的变化。在机器学习领域,这种针对流数据,不断改变模型的问题被称为在线学习。逻辑回归的极大似然估计天然具有在线学习的基因,因为对数似然函数具有样本可加性,样本集的对数似然函数是每一个样本的对数似然函数之和。对于逻辑回归问题,一种常用的在线学习算法是随机梯度下降算法,其思想是对于一条给定的样本(x,y),其负对数似然函数为: 对于该样本的NLL,可以计算其梯度方向为: 随机梯度下降法的思路是,对每一条新到来的新样本(x,y),计算出其梯度方向g,然后选择一定的步长参考如下公式,更新模型权重。 可以看出,随机梯度下降法和梯度下降法并没有本质的区别,只是在计算梯度的顺序上有所不同。不仅是在线学习,即使是离线训练模型时,也可以使用随机梯度下降方法,反复的顺序或者随机从样本集中抽取样本,计算梯度,更新模型权重,直到模型权重收敛时停止。当数据冗余比较大时,随机梯度下降法具有比梯度下降法更快的收敛速度。此外,对于存在局部最优解的学习问题,随机梯度下降法更容易从局部极 值点逃逸。因此,在广告系统学习实际模型时,普遍使用随机梯度下降法代替梯度下降法进行训练。 2.3.2 特征处理方式 特征处理是介于具体广告业务和底层机器学习算法之间的一层。我们现在已经有了一个比较不错的机器学习模型,能够帮我们综合各种信息,拟合出广告的CTR。同时,我们又有了一系列预测CTR的先验知识,比如广告中的字和查询关键字匹配越多CTR越高。特征处理的任务就是将人的先验知识,表示成机器学习算法能够接受的方式。 对于搜索广告而言,大部分是以文字链的形式出现,其CTR预估的粒度也通常是以<关键字,广告>对的粒度进行预估,常用的特征通常包括以下几类: 广告和查询关键字的相似度,这类特征用于衡量广告和查询关键字的关联,一些自然语言处理常用的计算相似度方法都可以作为特征,包括,广告和查询关键字的共现词个数,广告和查询关键字的cosine距离、KL距离、编辑距离等。有些复杂的广告系统,也会使用比较复杂的语义相似度作为特征。 广告本身的特征,如广告的历史CTR、历史展现、广告对于商品的价格、广告的字数、广告所包含的词语等。 查询本身的特征,如查询关键字历史的广告CTR、历史展现、查询所包含的词语等。 相似广告的特征,比如与当前广告相似的广告的历史CTR等特征,以及其与当前广告的相似度。 相似查询的特征,比如与当前查询相似的查询的历史CTR等特征,以及其与当前查询的相似度。 广告的树形结构信息,通常的广告系统是一棵广告主—广告账户—广告计划—广告组—广告创意的树形结构,那么倘若待预估广告创意的展现不足,而同广告主的其他广告创意的展现充足。那么,同一个广告主的其他广告创意的CTR往往能对预估当前广告创意的CTR提供很大的帮助。因此,这条广告树形结构的每一点都可以作为特征加入到回归模型中。 以上的信息,还是属于原始信息的范畴。对于逻辑回归来说,还是很难从直接使用这些原始信息建模。在工业界,很少直接将连续值作为特征喂给逻辑回归模型,而是将连续特征离散化成一系列0、1特征,交给逻辑回归模型。离散化的方法通常有两种,等距划分和等频划分。等距划分是根据连续特征X的值域范围,等间距的分为n段,产生 ,n个0、1特征,当X的取值属于第i段时,则 为1,否则 为0。等频划分是按照特征在训练样本中的出现频率,将其分成频率相同的几段,这种方式可以保证 在训练样本中出现的频率相同, 对于一些分布不均匀的信息,如广告的展现量等,通常效果较好。 2.3.3 算法评估 在工业环境下,一个CTR预估模型效果是否好,最终的检验方法是看其应用于广告系统中时,是否能带来稳定的收入提升。大型互联网企业,会建立一套分流机制,从生产系统中切出一部分小流量,用于实验算法。只有在小流量上,算法能保证,CTR、PPC、RPM等指标符合要求,才会考虑将算法发布到全流量上。 然而,小流量实验毕竟也会涉及线上效果和收入的变化。为了保证算法确实有可能提升线上效果,通常在小流量实验前,算法还需要经过一些离线指标的验证。搜索广告的CTR预估是以<关键字,广告>对的粒度进行预估,这样的对在测试集上能够获得的展现往往很少。这样,就无法使用传统的误差平方和等指标,衡量预估的CTR和真实CTR之间的差异。解决的方案是使用AUC来衡量CTR预估的精度。AUC的英文全称为Area Under Curve,意思是曲线下面积。这里的曲线指的是ROC曲线,ROC全称为Receiver Operating Characteristics,经常被用于模式识别领域,用于衡量分类器的精度。ROC是二维平面上的曲线,平面的横坐标是false positive rate(FPR)假阳性率,即反例样本中被误分为正例的比例,纵坐标是true positive rate(TPR)真阳性率,即正例样本中被准确的分为正例的比例。分类器在测试集上的表现可以表现为一个TPR和FPR点对。调节分类器的参数,可以使得分类器在ROC曲线上形成一条从(0,0)到(1,1)的曲线。AUC便是计算分 类器在ROC曲线下的面积之和。当ROC曲线是一条从(0,0)到(1,1)的直线时,表明分类器的分类为随机分类,此时的AUC为0.5。 在广告系统中,并不是通过得到ROC曲线,再求其面积得到AUC的。互联网广告系统计算AUC的方法源自AUC的一个有趣的性质,AUC等价于正样本的score大于负样本的score的概率。有了这个性质,我们就可以通过求得这个概率,计算得到AUC。求得这个概率的方法是通过统计测试集中所有的正样本负样本对,并计算其中正样本score大于负样本score的概率,如果正负样本的score值相同,则按照0.5个正样本score大于负样本score对计算。在互联网广告计算AUC时,以被点击的样本为正样本,没有被点击的样本为负样本,预估模型计算出的CTR为score值进行计算。 穷举所有正负样本对的方法有时候计算开销会比较大,因为,如果假设正样本个数为M,负样本个数为N,则计算AUC的开销是M*N。可以通过排序的办法,减少计算AUC的时间复杂度,具体做法是,将样本按照score的大小从高向低排序,score第一大的样本获得一个n=M+N的rank值,第二大的样本获得的rank值为n-1,以此类推。那么,对于rank为r的正样本i,能组成的正样本score大于负样本score的样本对个数为r-排在i后的正样本个数。由此,AUC可以按照如下方式进行计算, 这里需要特别注意的是,如果i个样本的score值相同,那么他们的rank值也相同,假设比他们score大的样本有j个,则这i个样本的rank值为n-j-(i-1)/2,以此类推。 2.4 广告主推荐工具 2.4.1 投放要素 前面讲了搜索广告的架构和广告排序方面的知识。那么,一个广告主是如何将自己的广告投放出去的呢?系统为广告主提供了哪些推荐的候选竞价词?这一章就来讲讲广告主推荐工具方面的事情。 首先,广告主要注册一个推广账户。一般来说,一个推广账户(Account)包含多个推广计划(Campaign),一个推广计划又包含多个推广的单元(Group),设置Group的时候主要需要竞价词(Bidword)和广告创意(Creative),如下图所示。 图7 投放层级关系 在这里,一个广告主对应一个账户(Account)很好理解。一个账户下面对应多个推广计划(Campaign)的用意是广告主可以根据实际情况创建多个侧重点不同的推广活动,举个例子:一个店铺对于夏天的新款服装单独组建一个Campaign,既便于对新款推广的管理,也便于对新款推广效果的分析。一个Campaign对应多个Group,这里的Group已经是很细节的单元了,一般来说对应的是一个单独的商品,对这个单独商品可以设置竞价词(Bidword)还有价格(Bidprice)等等。虽然一个Group一般对应一个商品,但是Group下面的Creative可以有多个,目的是为了让广告主比较不同创意的效果,从而最终筛选出好的创意。 对于Group来说,除了Bidword和Creative这两个最基本的要素,还有其它需要完善的需求和策略,如下图所示。