一种基于因子图的搜索广告转化预测模型

顾智宇，秦 涛，王 斌

(1. 中国科学院 计算技术研究所，北京 100190；2. 微软亚洲研究院，北京 100080)



一种基于因子图的搜索广告转化预测模型

顾智宇1，秦 涛2，王 斌1

(1. 中国科学院 计算技术研究所，北京 100190；2. 微软亚洲研究院，北京 100080)

基于转化的广告方式在应用和研究中逐渐得到重视，采用该方式的搜索广告在广告排序时需要对候选广告的转化概率进行预测，以提高广告的转化率，优化搜索引擎的广告收益。该文在对搜索广告中影响转化的各特征进行提取与分析的基础上，提出了描述广告、查询、用户三个因素与转化事件关系的概率因子图模型，并基于该模型对广告转化进行预测。最后我们使用从某商业搜索引擎采集的实际数据对预测模型进行评价并与朴素贝叶斯方法进行对比，实验结果表明，三类因素对转化具有不同程度的影响，我们提出的因子图模型可以较好地预测广告的转化。

搜索广告；概率预测模型；CPA广告

1 引言

互联网广告的形式主要有搜索广告(Sponsored Search)、上下文广告(Contextual Advertising)、展示广告(Display Advertising)等。其中搜索广告约占互联网广告总份额的46%，是互联网广告中最为重要的部分。并且，广告收入尤其是搜索广告收入是大部分搜索引擎公司的主要收入来源。例如Google在2010年的总营收中广告收入所占比例在96%以上，在广告收入中66%为搜索广告收入。搜索广告模式从早期的基于展示次数收费(Cost-per-mille，CPM)发展到当前主流的基于点击收费(Cost-per-click，CPC)后，近年来提出了基于转化收费的广告模式(Cost-per-Action，CPA)。基于转化的搜索广告的流程如图1所示。当用户使用搜索引擎进行查询时，搜索引擎将相关广告展示于搜索结果页面上，典型地在搜索结果的右侧或上方。若用户点击感兴趣的广告，则将被带到广告的着陆页。当用户进一步在着陆页上进行特定的动作，例如点击着陆页中的“下载”按钮时，将触发搜索引擎植入在着陆页中的一段脚本，该脚本把用户的本次动作反馈到搜索引擎，记录为一次转化，搜索引擎据此进行收费。被称为转化(Conversion or Action)的上述用户特定动作由广告商定义，常见的有购买商品、注册信息、下载软件等。对于广告商， 由于CPA广告在广告产生效果后才支付广告费用，减少了广告的风险；而对于搜索引擎，CPA广告能够避免CPC广告中可能出现的点击欺诈现象[1]，因而近年来CPA广告逐渐得到重视和发展。

图1 基于转化的搜索广告的流程

(1)

在本文的余下部分中，首先在第2节介绍相关的研究工作，然后在第3节对影响转化率的各因素进行分析，从中提取特征，第4节用描述因子图用于转化预测的概率模型，并在第5节给出相关实验结果和分析，最后在第6节进行总结。

2 相关工作

目前为止针对广告转化预测的研究为数不多，而且尚未有面向搜索广告的转化预测研究。文献[2]对展示广告的点击后转化事件进行了分析，从广告商、发布商、用户等信息中提取特征，在进行特征选择后建立最大熵模型对转化事件进行预测。而文献[3]则着重考虑了广告的点击/转化预测中的数据稀疏性问题，针对性地提出了利用广告商和发布商信息的层次树结构对数据在不同层次上进行聚合的方法。但上述工作都是针对展示广告进行，而搜索广告与展示广告有较大的差异，首先搜索广告发布的形式不同，由于搜索广告是在同一搜索引擎上发布，并不具备展示广告在各种不同网页上发布时的不同发布商信息，更重要的是，搜索广告由于是被用户搜索时所输入的查询所触发，而用户查询是用户意图的重要指示，对广告的转化有较强影响，因此在进行搜索广告的转化预测时，必须对用户查询进行分析和利用。

目前对于搜索广告的转化主要集中在经验性分析上，其中，文献[4]分析了广告的关键字对转化率的影响，以帮助广告商优化广告。文献[5]则分析了广告的着陆页与转化率的关系，他们发现大部分着陆页可划分为广告商主页、搜索转移(SearchTransfer)、分类浏览这三种类型，对Yahoo搜索广告数据进行的统计表明不同类型的着陆页的平均转化率有明显的差异。而文献[6]则主要针对用户查询与转化的关系进行了分析，通过回归分析计算了查询长度、查询中是否包含特定关键字等特征与广告转化率的相关性。其结果表明某些特定关键字对转化率有较大影响。但是上述工作都没有建立理论模型来对搜索广告的转化进行直接预测。

图2 广告点击率与转化率的分布

针对CPC广告的点击预测已有较多的研究工作，如文献[7-8]等提出了基于概率的点击预测方法。然而广告的点击与转化是两个不同的事件，具有不同的性质和影响因素。通过利用某商业搜索引擎所记录的两个星期内的广告展示、点击与转化数据，我们计算了广告点击率与转化率分布，其中点击率定义为广告该时间段内点击次数与展示次数之比，转化率定义为广告一定时间段内转化次数与点击次数之比，并在图2中进行了对比。从图中可见虽然大部分广告都分布于转化率/点击率较低的区间，但转化率的分布更为不均匀，曲线更陡。并且，广告的点击率与转化率的关联性很弱，具有高点击率的广告并不一定具有高转化率，反之亦然。经计算，上述数据集的广告点击率与转化率的相关系数仅为0.023。此外，影响广告的点击与转化的因素并不完全相同。例如，如图3所示，在上述广告数据中可发现广告的显示位置对广告的点击率有大的影响，广告在展示于搜索结果上方时点击率明显高于广告显示在结果右侧，而对转化率的影响却很微小。因此，对于广告的转化预测，有必要对特征重新分析并建立不同的模型。

图3 广告显示于搜索结果上方或右侧对点击率与转化率的不同影响

3 影响转化的特征分析

为了研究影响转化的因素，我们对某商业搜索引擎的广告日志进行采样，分析各因素与转化率的关系，从中提取用于预测广告转化的特征。广告的转化首先受广告自身影响，例如广告的内容和向用户展示的广告文本，尤其是着陆页的类型和内容。其次是触发广告的查询，包括查询的意图、查询与广告的相关程度以及查询进行的时间等。由于转化实际是用户的行为，所以用户因素也是影响转化的原因，包括用户的性别、年龄等个人信息，以及用户的搜索历史、广告点击历史、广告转化历史数据等。在文献[7-8]等点击率预测等工作中也曾使用了与广告、查询或者用户相关的特征，但考虑到转化率预测问题与点击率预测问题的上述差异，本工作不仅增加了历史转化率、着陆页文本、查询时间及用户转化历史等对转化影响密切的新特征，并对特征重新分析，建立不同的模型，即利用因子图进行预测。以下首先对这三组特征逐一分析。

3．1 广告特征

不同内容的广告的转化概率有明显不同，例如软件下载广告的转化概率可能比销售电器的广告的转化概率高很多。从搜索引擎的角度看，一个广告包括三部分： 向用户显示的内容、用户点击后显示的着陆页、广告数据库中的元信息。广告显示的内容包括广告的标题、正文和显示URL。广告数据库中元信息包括广告竞价关键字、广告商对广告的出价、广告所属的广告活动(Campaign)、广告商ID等。从各部分中可提取下列与广告转化率相关联的特征。

(2)

广告标题与文本： 广告的标题与文本同样表示了广告的内容，我们从广告的标题和文本中提取有用词项，同样地使用上述方法计算相关系数并选择前100个词项作为二元特征。

着陆页文本： 由于着陆页对转化有较大影响，因此我们抓取了每个广告的着陆页并提取其中的文本，同样地用上述方法选择前100个词项作为特征。不同的是，由于在上面广告标题与文本为短文本，我们仅将词项出现与否作为二元特征，而在此着陆页文本为较长的文本，因此使用词项的TF-IDF值作为连续值特征。

广告历史转化率： 大部分广告的转化率在时间上都比较平稳，这意味着可以使用广告的历史转化率预测当前广告的转化。我们将广告在过去一星期的转化率的平均值作为广告的历史转化率特征。

广告出价： 图4表示了广告出价与转化率的关系，其中横轴表示广告出价，正规化到(0, 1)区间，纵轴为转化率。图中转化率与报价显示出相关性。在(0,0.8)区间内，随着广告出价的提高，广告的转化率有上升的趋势。这是因为转化率高的广告可以给广告商带来更多的收益，因此广告商倾向于提高其报价。而在0.8以上的出价可认为是广告商的竞争性出价而非合理出价，所以该区间的转化率反而有所下降。由此，我们将正规化后的广告出价作为转化预测的一个特征。

图4 广告出价与转化率的关系

3．2 查询特征

如上所述，搜索广告与网页广告的最大区别是搜索广告由用户的查询所触发，而查询揭示了用户当前的意图，与转化紧密关联，例如具有购买意图的用户往往有更高的转化率。查询中所包含的影响转化率的特征包括查询本身的特征以及查询与广告的相关特征，如下所示。

查询类别： 我们按照ODP目录将查询分类为12个类别，作为查询的类别特征。图5展示了每种类别所对应的广告平均转化率。可见各类别的平均转化率有较大的差别，其中Business(商业)、Recreation(娱乐)、Shopping(购物)等具有商业意图的类别的转化率明显高于Science(科技)等类别。

图5 不同查询类别的转化率

查询的历史转化率： 与广告类似，查询的历史信息同样可作为预测转化的特征。除了查询串本身的历史转化率之外，我们还对每个查询中各词项分别统计包含该词项的查询的历史转化率，将上述各词项历史转化率的平均值和最大值作为特征。使用的历史数据的时间窗口长度为一个星期。

查询时间： 图6表示一天中的查询时间与转化率的关系，在不同时间的查询转化率有明显差别，10点左右的查询转化率最低，而晚上的转化率则较高，这可以理解为人们在工作时间和休息时间对待购物的区别。因此我们将查询在一天中的时间作为特征。

图6 查询时间与转化率的关系

查询与关键字的匹配类型： 搜索引擎在利用广告的竞价关键字与查询匹配时，有多种匹配方式，包括查询与关键字完全一致的精确匹配、关键字为查询的一个子串的部分匹配、关键字为查询的一个子集的宽泛匹配等。不同的匹配方式所返回的广告与查询的相关程度不同，导致转化率有所不同，因此我们将匹配类型作为一个特征。

查询与广告文本的相似度： 除了使用竞价关键字的匹配类型外，我们还考虑使用广告的文本信息作为广告与查询的相关度的衡量。在此使用向量空间模型计算广告文本与查询的相似度作为特征，见式(3)。

(3)

其中wiq、wia分别是查询Q和广告A的文本的各词项的TF-IDF值。

3．3 用户特征

用户特征包括两类，一类为用户年龄、性别、位置等用户的个人信息，另一类为用户的历史记录如用户的搜索历史和广告点击历史。

爱德华·萨义德在《东方学》一书中，提出东方主义是与西方殖民主义和帝国主义紧密联系在一起的西方关于东方的话语形式，通过使东方成为西方属下的“他者”，使东方主义臣服于西方对东方的霸权统治。在东方主义话语中，东方国家被标以五花八门的消极特征：无声、淫逸、阴弱、专制、落后、非理性。相反，西方则总是被赋予积极的特征：阳刚、民主、理性、道德、强悍、进步。在萨义德的后殖民理论中，西方人往往被称为具有主体性的“自我”，殖民地人民则被称为“他者”（萨义德 2007：1-36）。萨义德认为，在西方文学家或者学者眼里的“东方并非现实存在的东方，而是被东方化了的东方”（同上：136），是被西方控制的对象。

用户性别、年龄： 我们将用户以10岁为间隔划分为八个年龄段，图7中表示了不同年龄段用户的转化率。 从图中可见，除了0-10岁区间，年龄较大的用户具有较高的转化率，这可能是因为该部分用户经济条件较好而具有较高的购买力。而对于0-10岁区间用户，考虑到其使用搜索引擎、点击广告并发生消费的可能性，我们认为该年龄段的异常是由于用户注册搜索引擎帐户时未正确填写真实年龄所致，故不考虑该年龄段，将其余年龄段作为用户的年龄特征。此外用户的性别也作为特征之一。

图7 年龄与转化率的关系

用户地理位置： 由于使用的广告数据为英文广告，受众主要分布在英语国家，因此将用户的地理位置划分为美国、加拿大、英国、其他地区等四个范围，将其作为地理位置特征。

用户搜索历史： 用户的搜索提示了该用户的兴趣与关注点，把用户最近一个星期内的查询的集合视为表示用户兴趣的一个文档，来计算其和广告文本在向量空间模型中的相似度，计算公式仍为与3.2节中文本相似度计算公式(3)类似，其中wiq换成查询集合文档中词项的权值。

用户广告转化历史： 为了表示用户是否有在网上购物的习惯，我们对每个用户统计了最近60天内的转化次数作为用户转化特征。

4 转化预测模型

基于上述特征，我们提出用于预测广告转化的概率模型，下面首先利用因子图(FactorGraph)对模型的各层次进行描述，然后给出模型的学习和推断的方法。因子图[9]是概率图模型的一种，它通过二分图的形式表示函数与变量的依赖关系，二分图中的一类顶点表示函数，另一类顶点表示变量，下面用实心框和空心圆区分这两类顶点。顶点之间的连线表示依赖关系。借助因子图我们可以将概率函数分解为各因子，用子图清晰地表示各因子的关系，并能够在其上利用消息传播算法有效地进行概率推断。

4．1 转化预测模型描述

• 广告得分：sa

• 用户得分：su

• 总得分：s

其中，总得分由各因素得分决定：

(4)

上式中N(·)表示正态分布概率。通过f函数建立总得分s与子项得分sa,sq,su的联系，即总得分s具有以w1·sa+w2·sq+w3·sa为中心，以β为标准差的正态分布。隐变量w1～3分别为各子项得分的权值，具有正态分布的先验。因此，包含上述两个函数的因子图如图8所示，它表示了总得分与子项得分的关系。

图8 总得分与各子项得分的概率关系的因子图

而子项得分将分别由广告特征、查询特征、用户特征决定，即sa,sq,su由xa,xq,xu以及权值wa,wq,wu决定：

(5)

其中作为隐变量的wa,wq,wu也具有正态分布的先验。上述函数的因子图可分别用图9中各图表示。

图9 各子项得分与特征的概率关系的因子图

最后，我们使用logistic函数建立总得分s与转化事件的概率关系，即给定s下的转化概率为式(6)。

(6)

(7)

图10 包含隐变量的联合概率的因子图

4．2 模型训练与预测

5 实验与分析

5．1 实验数据与评价标准

实验使用的数据来自于某商业搜索引擎，该搜索引擎的广告服务器可获取的日志信息中每天记录了数千万条点击信息，并且记录了与点击相关的查询信息与用户信息，我们将从中采样作为实验数据，并进一步从中提取特征。我们从搜索引擎2011年12月的前两周的广告日志中随机采样了200 000条广告点击记录作为实验数据，每周各100 000条记录，从中抽取转化结果与特征。使用了转化历史信息的特征则从相应时间段的广告日志中统计，例如12月5日的记录所对应广告的历史转化率的值将从11月28日至12月4日一个星期全部的广告日志中统计。对于特征提取完成的数据，我们把第一周的数据用作训练数据，第二周的数据作为测试数据。

(8)

(9)

(10)

而AUC值为ROC曲线(ReceiverOperatingCharacteristiccurve)下的面积，ROC曲线是表示测试中假阳率与真阳率关系的曲线，广泛用于衡量分类器的性能。一般认为若AUC值在0.8以上则可视为较好的结果。

5．2 实验结果

根据上述评价指标，我们将本文提出的概率预测模型与朴素贝叶斯(NaïveBayesian)方法进行对比。本概率预测模型采用Infer.Net实现[11]，朴素贝叶斯方法则使用weka工具包*http://www.cs.waikato.ac.nz/ml/weka/实现。

表1 模型性能对比

表1列出了概率预测模型与朴素贝叶斯方法下的相对信息增益和AUC值，图11为两者的准确率-召回率曲线。概率预测模型其准确率-召回率曲线在朴素贝叶斯的曲线之上，相对信息增益与朴素贝叶斯方法相比有23.3%的提升。概率预测模型的AUC值为0.852，可认为它能够对转化事件进行较好的预测。

图11 准确率-召回率曲线

5．3 各因子对转化预测的影响

为了分别考察广告、查询、用户在转化中的重要性，我们分别从模型中移除这三个因子，即从图10的模型中依次移除图9中代表广告因子、查询因子、用户因子的三个部分，将移除后的模型与原模型进行对比。图12表示了原模型与分别移除部分因子后的相对信息增益。从图中可见， 移除任何一个因子后相对信息增益都有显著降低，但各因子的影响并非完全相同。其中，移除查询因子后性能下降最大，说明相对其他两类因子，查询在转化预测中起到更重要的作用，证明了代表用户当前意图的查询在转化中的重要作用，这正是搜索广告相对于上下文广告的不同之处。相对地，移除用户因子后性能下降相对较小，说明用户的长期兴趣对转化的作用不如当前意图的对转化的作用大。

图12 模型移除不同因子后对性能的影响

6 总结

在本文中，我们通过分析搜索广告中影响广告转化的各因素，包括广告因素、查询因素和用户因素，从中提取特征，并建立概率预测模型用三个因子描述上述因素，用以预测广告的转化概率。通过实验证明了该模型具有较好的性能，有效地解决了基于转化的搜索广告的广告排序问题。

[1] Mitchell D. Click fraud and halli-bloggers[J]. New York Times, 2005, July.

[2] Rosales R, Cheng H, Manavoglu E. Post-click conversion modeling and analysis for non-guaranteed delivery display advertising[C]//Proceedings of the fifth ACM international conference on Web search and data mining. 2012:293-302.

[3] Kota N, Agarwal D. Temporal multi-hierarchy smoothing for estimating rates of rare events[C]//Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining. 2011:1361-1369.

[4] Rutz O, Bucklin R. A model of individual keyword performance in paid search advertising[OL]. 2007. http://dx.doi.org/10.2139/ssrn.

[5] Becker H, Broder A, Gabrilovich E, et al. What happens after an ad click?: quantifying the impact of landing pages in web advertising[C]//Proceeding of the 18th ACM conference on information and knowledge management. 2009:57-66.

[6] Ghose A, Yang S. An empirical analysis of sponsored search performance in search engine advertising[C]//Proceedings of the international conference on Web search and web data mining. 2008:241-250.

[7] Graepel T, Candela J, Borchert T, et al. Web-scale Bayesian click-through rate prediction for sponsored search advertising in Microsoft’s Bing search engine[C]//Proceedings of the Twenty-Seventh International Conference on Machine Learning (ICML-10). 2010:13-20.

[8] Hillard D, Manavoglu E, Raghavan H, et al. The sum of its parts: reducing sparsity in click estimation with query segments[J]. Information Retrieval, 2011:1-22.

[9] Kschischang F, Frey B, Loeliger H. Factor graphs and the sum-product algorithm[J]. Information Theory, IEEE Transactions on, 2001, 47(2):498-519.

[10] Minka T. Expectation Propagation for approximate Bayesian inference[C]//Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-01). San Francisco, CA: Morgan Kaufmann, 2001:362-369.

[11] T Minka J G, J Winn, Knowles D. Infer.NET 2.4[OL]. Microsoft Research Cambridge, 2010, http://research.microsoft.com/infernet.

A Factor Graph Based Conversion Prediction Model for Sponsored Search

GU Zhiyu1, QIN Tao2, WANG Bing1

(1.Institue of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. Microsoft Research Asia, Beijing 100080, China)

The CPA (Cost-per-Action) Advertising is attracting more and more attention in both industry and research. Sponsored search based on CPA requires predicting conversion probability for each candidate ad during ad ranking, in order to raise conversion rate and optimize ad revenue for search engine. After extracting and analyzing features which may influence conversion of ads, we propose a probabilistic factor graph based model for ad conversion prediction which describes the relation between the conversion event and three factors, i.e. ad, query, and user. The model is evaluated and compared with Naive Bayesian method on real-world data gathered from a commercial search engine. The experiment demonstrates a good result in the ad conversion prediction, as well as different influences of the three factors.

sponsored search；probabilistic prediction model；CPA advertising

顾智宇(1981-)，博士研究生，主要研究领域为信息检索、计算广告学。E⁃mail：guzhiyu@ict．ac．cn秦涛(1981-)，博士，研究员，主要研究领域为互联网经济、博弈论、机器学习、信息检索和计算广告学。E⁃mail：taoqin@microsoft．com王斌(1972-)，博士，研究员，主要研究领域为信息检索与自然语言处理。E⁃mail：wangbin@iie．ac．cn

1003-0077(2015)03-0140-10

2012-04-18 定稿日期： 2012-07-16

TP391

A