达观数据：计算广告系统算法与架构综述

前言

我们当今身处一个被广告包围的时代，无论是走在马路上、收看电视剧、或者是玩手机游戏，都能看见形形色色的广告。随着时代和技术的发展，广告的形式呈现出多样化、立体化的趋势，从最早的纸媒广告发展到如今的网页的展示、搜索广告，广告的定位也从原先的“广而告之”发展成大数据时代的“精准营销”，相应地，人们对广告的态度也在悄然变化。这一切都得益于互联网技术的快速发展以及用户数据的爆炸式增长。作为IT从业者，自然想对广告产业背后的产品、技术一探究竟，正如刘鹏博士在其《计算广告》一书中所说的“不论你在做一款用户产品还是商业产品，不深入了解在线 广告，就不太可能全面地了解互联网业务”，因此本文也希望能带领读者从产品、技术以及整个生态的角度深入浅出的了解计算广告。

核心术语

首先，在深入了解计算广告之前， 有必要先对一些核心术语做简单的介绍。

竞价流程

在RTB模式出现之后，我们发现展现的广告越来越精准了，好像网站知道用户是谁、用户在做什么、用户对什么感兴趣，因此，在了解了上述这些核心术语之后，接下来就以网站用户角度，从流程上解析RTB是如何做到精准展示广告的。

有两点需要说明：

技术细节

纵观计算广告的发展会发现，整个市场本质上是计算驱动的，而计算背后最大的推动力正是互联网以及大数据，而大数据的发展动力又来自于硬件和软件。因此接下来，就来剖析下技术细节。

1.架构

一个典型的广告系统架构如下图：

结合上图，广告系统有以下几个重要组成部分：

（1）受众定向平台：这部分一般为离线挖掘，是系统中最具算法挑战的部分，利用数据挖掘、机器学习等技术进行受众定向，点击率预估等工作。具体还可以细分为以下几个模块：

（2）高并发的投送系统：也就是在线的广告投放机（Ad server），主要任务是与各模块交互，将它们串联起来完成在线广告的投放决策。特点是高并发，要做到10ms级别的实时决策，百亿次/天的广告投放系统。具体可细分为以下几个模块：

（3）数据高速公路：联系在线与离线的部分，可以用开源工具实现。作用是准实时地将日志推送到其它平台上，目的一是快速地反馈到线上系统中，二是给BI人员快速看结果。它还可能收集其它平台的日志，比如搜索广告会收集搜索日志。

（4）流式计算平台：主要功能是对在线数据的处理，做到准实时的挖掘和反馈，解决那些离线计算平台无法快速响应的计算问题。具体又可分为：

2. 硬件

在以上介绍的架构图中，都离不开大数据工具的作用，其中大多来自开源社区，正所谓，工欲善其事，必先利其器。可以说，正是由于这些成熟的开源工具有力的保障了数据通信、数据传输、负载分配等底层架构的健康运行，才使得上层的广告算法和策略能快速发展。

（1）Hadoop：一个由Apache基金会所开发的分布式系统基础架构，用户可以轻松地在Hadoop上开发和运行处理海量数据的应用程序，主要优点有：高可靠性、高扩展性、高容错、低成本。Hadoop框架最核心的设计就是：HDFS和MapReduce。

（2）Spark：一个用来实现快速而通用的集群计算的平台，扩展了广泛使用的MapReduce计算模型，Spark的一个重要特点就是能够在内存中计算，因而更快，即使在磁盘上进行的复杂计算，Spark依然比MapReduce更加高效。举例来说，机器学习中很多算法都要迭代训练多次才能达到收敛，例如聚类算法K-Means，每次迭代需要将K个中心点的位置保存下来，以进行下次的更新，传统的MapReduce计算框架在Map阶段和Reduce阶段用硬盘进行数据交换，这就使得整个训练过程效率很低，而Spark的做法则是将数据加载到内存中，直接在内存中更新K个中心点的位置，大大加快了训练过程。Spark支持各种机器学习算法为代表的迭代型计算、流式实时计算、社交网络中常用的图计算、交互式即席查询等。

（3）Lucene：用于全文检索和搜索的开源程式库，提供了一个简单却强大的应用程式接口，但它不是一个完整的全文检索引擎，而是一个全文检索引擎的架构。目前大多数的计算广告采用的是检索加排序模式，为了加快检索的时间，可以对所有广告的关键字建立倒排索引（主键为关键字，值为文档ID），这样在广告召回时，便能快速地从规模巨大的广告库中返回结果。

（4）Storm：广告系统中除了需要离线挖掘数据，同样还需要在线、准实时的处理数据，例如反作弊处理、实时点击反馈、实时查看某地区当前的广告投放情况等，业界常用的工具是Storm。利用Storm可以很容易做到可靠地处理无限的数据流，像Hadoop批量处理大数据一样，主要的特点有：

（5）ZooKeeper：ZooKeeper是一个分布式的，开放源码的分布式应用程序协调服务，是Hadoop和Hbase的重要组件，为分布式应用提供一致性服务。分布式应用程序可以基于 ZooKeeper 实现诸如数据发布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master选举、配置维护等功能。简单来说ZooKeeper=文件系统+监听通知机制。在广告系统中，大量的广告投放机就是通过ZooKeeper进行管理，可以把所有机器的配置全部放到ZooKeeper上的某个目录节点中，所有相关应用程序对这个目录节点进行监听。当需要增加一台新的投放机时，配置信息发生了变化，应用程序就会收到 ZooKeeper 的通知，然后从 ZooKeeper 获取新的配置信息应用到系统中。

3.核心算法

介绍完了上述的硬件架构之后，接下来就要了解一下计算广告背后的核心算法和技术。

CTR（点击率）预估是所有广告系统、推荐系统中非常重要的一个指标，可以反映出一个系统是否做的精准，是各个广告系统的“必争之地“。点击率预估的目的是为了广告排序，排序的依据是eCPM，即点击率*点击单价，然后再根据其他策略进行后续处理。

目前业界的点击率预估方法，是利用系统中已有的大量用户行为日志、根据规则抽取特征、离线训练机器学习模型、将模型上线后对每一个请求计算其点击广告的概率值，值的范围为 [0,1] 。这里既然用到了模型，就不得不提其背后的两个细节。

（1）特征

在实际的广告系统中，其实有非常多的因素会决定广告的点击率，这些因素在模型中即称为特征，主要分为三大类：

在有了用户日志后，就需要根据上述三类特征进行特征工程。特征工程对于机器学习来说非常重要，可以使特征更好地在算法上发挥作用，一般包括特征选择、特征提取、特征构造。

1.1 特征选择：在实际拿到的数据中一般都有非常多的特征，但并非每一个都能拿来训练模型，可能有些特征有用，而另外一些特征就毫无作用，即冗余特征，特征选择的作用就是从已有的特征全集中选择出一部分的特征子集。

进行特征选择有两个重要的原因：

一、维数灾难。若对所有特征不加筛选而一股脑全扔进模型，比如，用户ID和设备ID交叉之后，特征的维度就会非常高，而其实这样的组合特征完全可以只用一个特征来代替，进行特征选择就会大大减少冗余特征，缓解维数灾难问题。

二、去除冗余特征可以减轻模型的学习难度，直观感受就是减少模型的训练时间。常见的特征选择方法主要有三种：过滤式、包裹式、嵌入式。

r 描述的是两个变量间线性相关强弱的程度，绝对值越大表明相关性越强。 r 的取值在-1与+1之间，若 0 ">r>0 ，表明两个变量是正相关，即一个变量的值越大，另一个变量的值也会越大；若 r ，表明两个变量是负相关，即一个变量的值越大另一个变量的值反而会越小。

在上式求解过程中，最初的特征全集中只有对应于非零权重的特征才会出现在最终模型中。这样，L1正则化就起到了特征筛选的作用，其特征选择过程与模型训练过程融为一体，同时完成。

1.2 特征提取：将原始特征转换为一组具有明显物理意义（Gabor、几何特征角点、不变量、纹理LBP HOG）或者统计意义或核的特征，比如通过变换特征取值来减少原始数据中某个特征的取值个数等。常用的方法有：

1.3特征构建：在经过了特征选择之后，确定了需要放入模型的特征后，接下来就要对特征进行处理，对特征进行转换、加工、处理成模型能够识别的格式。根据不同的数据类型，需要采取不同的处理方式：

即求出样本特征 X_{i} 的均值 \mu 和标准差 \sigma ，然后用来代替原特征。这样新的特征值就变成了均值为0，方差为1。

求出样本特征X_{i}的最大值 max 和最小值 min ，然后

用来代替原特征值。不过，这种方法有个问题，若预测集里的特征有小于min，或者大于max的数据，会导致max和min 发生变化，需要重新计算。所以一般实际应用中，最大-最小标准化不如Z-score标准化鲁棒。

一般采用分桶或者分段的方式，即事先指定每个桶的取值范围，然后将特征值划分到桶中，最后用桶的编号作为新的特征值。对于桶的划分又可以分为等频（各个桶中的数量大致相同）、等宽（各个桶的上下界的差值相同）、人工指定。一般来说，等频离散不会像等宽离散出现某些桶中数量极多或者极少。但是等频离散为了保证每个区间的数据一致，很有可能将原本是相同的两个数值却被分进了不同的区间，会对最终模型效果产生一定影响。人工指定则需要根据过去的经验来进行划分大数据计算框架，例如对于反馈点击率，发现过去的点击率集中在1%和2%之间，因此，可以这样划分（python代码）：

其中， tf 反映的是该词在当前文档中的热门程度，但是对于那些几乎每篇文章都会出现的助词来说，如“的”、“了”、“这”等等，就需要给它们降权，从 idf 的计算公式可以看出，包含该词的文档数约多，倒数就越小，从而就可以起到降权的作用。因此最终的乘积就可以认为是该词在整篇文章的重要性。

Word2Vec其实训练了一个语言模型，即通过前n 个字预测下一个字的概率，是一个多分类器，输入一个one hot，然后连接一个全连接层、再连接若干个层，最后接一个Softmax分类器，就可以得到语言模型了，然后将大批量文本输入训练就行了，最后得到第一个全连接层的参数，就是字、词向量表。

Word2vec主要有两个模型：

CBOW：主要用来从原始语句推测目标词汇。CBOW用周围词预测中心词，从而利用中心词的预测结果情况。当训练完成之后，每个词都会作为中心词。把周围词的词向量进行了调整，这样也就获得了整个文本里面所有词的词向量。

Skip-gram：从目标词汇推测原始语境。与CBOW相反的是，Skip-gram使用中心词预测周围词，Skip-gram会利用周围的词的预测结果情况，不断的调整中心词的词向量，最终所有的文本遍历完毕之后，也就得到了文本所有词的词向量。对比而言，Skip-gram进行预测的次数多于CBOW的：因每个词作为中心词时，皆需使用周围词进行预测一回，训练时间相对更长。

其中， h_{i} 表示是否点击（0或1），u_{i}为用户端特征，c_{i}为上下文特征。这一式子其实是点击与期望点击的比值，因此称为CoEc特征，该特征可以更准确的表征某部分流量上广告投放的实际点击率水平，比较适用于点击反馈的动态特征。

(2)模型

经过了上述特征工程处理之后，就需要将特征放入到具体的模型中。针对ctr预估问题，工业界也产生了很多的模型，由最初的逻辑回归模型到目前非常热门的深度学习模型，效果也随之提升了很多。下面就来具体看下ctr预估模型的一路发展。

2.1LR(逻辑回归)

LR是ctr预估模型的最基本的模型，也是工业界最喜爱使用的方案。LR 是广义线性模型，与传统线性模型相比，LR 使用了 Logit 变换将函数值映射到 0~1 区间，映射后的函数值就是 CTR 的预估值。

LR 利用了 Logistic 函数，函数形式为：

优点：由于LR 模型简单，训练时便于并行化，在预测时只需要对特征进行线性加权，所以性能比较好，往往适合处理海量 id 类特征，模型的结果直观易解释。

缺点：LR 的缺点也很明显，首先对连续特征的处理需要先进行离散化，如上文所说，对连续特征的分桶方式有很多种，各种方式都有差异。另外 LR 需要进行人工特征组合，这就需要开发者有非常丰富的领域经验，才能不走弯路。这样的模型迁移起来比较困难，换一个领域又需要重新进行大量的特征工程。

2.2 FM(Factorization Machine)、FFM（Field-aware factorization machine）

在一般的线性模型中，各个特征独立考虑的，没有考虑到特征与特征之间的相互关系。但实际上，大量的特征之间是有关联的。

一般的线性模型为：为了表述特征间的相关性，可以采用多项式模型。在多项式模型中，特征 x_{i} 与 x_{j} 的组合用 x_{i}x_{j} 表示。二阶多项式模型如下：

其中 n 表示样本的特征数量，这里的特征是离散化后的特征。与线性模型相比，FM的模型多了后面的特征组合的部分。

FM主要有如下特点：

1.可以在非常稀疏的数据中进行合理的参数估计

2.FM模型的时间复杂度是线性的

3.FM是一个通用模型，它可以用于任何特征为实值的情况

而FFM则是在FM的基础上，考虑了特征交叉的field的特点，但是也导致它没有办法实现线性的时间复杂度，模型训练要比FM慢一个量级，但是效果会比FM来得更好。在业界，目前已经有公司线上利用FM去预测ctr。

2.3 LR + GBDT

在Facebook2014年的一篇论文中，提及到GBDT+LR的解决方案。即先使用GBDT对一些稠密的特征进行特征选择，得到的叶子节点，再拼接离散化特征放进去LR进行训练。在方案可以看成，利用GBDT替代人工实现连续值特征的离散化，而且同时在一定程度组合了特征，减少了人工的工作量。

从上图可以看到，输入x分别落到2颗树的叶子节点上，每个叶子节点对应的编号就作为新的特征送入LR中，其中新的特征维度与树的数目相同，在实际应用中，需要进行调参的有每棵树的深度、树的总数等。

另外，对于广告来说，ID类特征在CTR预估中是非常重要的特征，直接将AD ID作为feature进行建树不可行，可以考虑为每个AD ID建GBDT树。具体做法，使用GBDT建两类树，非ID建一类树，ID建一类树。

1）非ID类树：不以细粒度的ID建树，此类树作为base，即便曝光少的广告、广告主，仍可以得到有区分性的特征、特征组合。

2）ID类树：以细粒度的ID建一类树，用于发现那些曝光充分的ID有区分性的特征、特征组合。在实际应用中，效果略有提升，但是需要综合考虑GBDT的性能问题。

2.4 Wide & Deep

Wide & Deep 模型是 Google在2016年发表的文章中提出的，并应用到了 Google Play 的应用推荐中。Wide & Deep模型的核心思想是结合线性模型的记忆能力（memorization）和 DNN 模型的泛化能力（generalization），在训练过程中同时优化 2 个模型的参数，从而达到整体模型的预测能力最优。

Wide & Deep模型中使用的特征包括两大类： 一类是连续型特征，主要用于deep模型的训练，包括连续值型的特征以及embedding类型的特征等；一类是离散型特征，主要用于Wide模型的训练，包括稀疏类型的特征以及组合型的特征等。

模型结构：

模型特点：

记忆（memorization）通过特征叉乘对原始特征做非线性变换，输入为高维度的稀疏向量。通过大量的特征叉乘产生特征相互作用的“记忆（Memorization）”，高效且可解释。

泛化（generalization）只需要少量的特征工程，深度神经网络通过embedding的方法，使用低维稠密特征输入，可以更好地泛化训练样本中未出现过的特征组合。

Memorization趋向于更加保守，推荐用户之前有过行为的items。相比之下，generalization更加趋向于提高推荐系统的多样性（diversity）。

2.5 DeepFM

DeepFM是由哈工大与华为诺亚方舟实验室共同发表的论文中提出的，模型有效的结合了神经网络与因子分解机在特征学习中的优点。DeepFM可以同时提取到低阶组合特征与高阶组合特征，并除了得到原始特征之外无需其他特征工程。

模型结构：

比起Wide& Deep的LR部分，DeeFM采用FM作为Wide部分的输出，FM部分如下图：

Deep component 如下图:

Deep Component是用来学习高阶组合特征的。网络里面黑色的线是全连接层，参数需要神经网络去学习。

由于ctr或推荐系统的数据One-hot之后特别稀疏，如果直接放入到DNN中，参数非常多，我们没有这么多的数据去训练这样一个网络。所以增加了一个Embedding层，用于降低纬度。

优点：首先，FM提取低阶组合特征，Deep提取高阶组合特征。但是和Wide & Deep不同的是，DeepFM是端到端的训练，不需要人工特征工程.

其次，共享feature embedding。FM和Deep共享输入和feature embedding不但使得训练更快，而且使得训练更加准确。

相比之下，Wide & Deep的输入vector非常大，里面包含了大量的人工设计的pairwise组合特征，因此增加了计算复杂度。

生态

说到整个程序化交易广告的生态圈，除了以上介绍的SSP、DSP、Adx等，还有其他大大小小的角色在其中发挥着作用。在此，列举几个如下：

目前国内完整的生态圈如下图：

关于趋势，最近有国外的广告科技前沿作者预测，媒体方削减推送给广告交易平台的流量并自主搭建与DSP的直接对接或许会成为趋势，并预测，未来主流大型媒体通过程序化方式售卖的形态很可能是仅和二、三家广告交易平台对接，同时直接和十多家DSP对接，以获得更好的利润和控制权。此趋势如发生，将进一步削弱开放式广告交易平台的作用并进一步减少优质库存通过广告交易平台交易的机会。

对于独立的移动广告技术公司而言，出海的发展机会似乎大于固守本土的机会，2018年广告技术公司上市的情况即是佐证。OTT和OOH以及音频媒体库存正在处于酝酿进入程序化模式的前夜，这或许是未来几年的持续增长点。

参考文献

ABOUT

关于作者

吴威骏：达观推荐算法工程师，负责推荐算法的研究、应用。先后在SAP、力美、百度等公司从事数据挖掘和广告系统的算法开发，对机器学习算法、广告系统有深入研究。

（编辑：百客网 - 百科网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!