刘文飞，林鸿飞

(大连理工大学 信息检索研究室，辽宁 大连 116024)

1 引言

目前在线广告已经成为搜索引擎公司的主要收入来源，在线广告主要有两种形式，搜索广告和上下文广告。搜索广告是指搜索引擎根据用户提交的查询内容，选择相关的的广告投放在搜索结果页面的顶端或者右端，并且根据用户的点击收取广告商相应费用。上下文广告是指广告联盟网络将广告商提供的广告投放在第三方的网站上，可以是博客或者新闻网站，根据用户点击或者展示次数等方式收取广告商费用，费用将由第三方网站和广告联盟网络共同所有。本文研究前一种广告形式。

搜索广告的收益取决于广告点击率，而广告点击率与投放的广告是否符合用户的查询意图直接相关，研究表明[1]，投放不相关或者相关性比较低的广告会对搜索引擎公司产生不利的影响，因为它们几乎不会产生广告的点击，反而会影响用户的体验，因此为用户查询返回相关性高的广告至关重要。

目前，大多数搜索引擎只提供基于关键字的搜索，用户提交的查询各种各样，包含的关键字比较少，另外广告商提供的广告只包含一些竞价词和简短的标题、描述信息等，而且广告的标题和描述主要用来吸引用户的眼球，而不是去“迎合”用户的查询，这使得搜索引擎理解用户的查询意图，返回与查询相关的广告变得十分困难。目前可以采用查询扩展技术解决这一问题，一些研究者采用广告集合本身来选择扩展词进行查询扩展[2]，取得了比较好的效果，然而由于广告集合本身所包含的信息有限，可以选择利用外部资源来进行查询扩展，例如，可以通过挖掘查询日志[3]、搜索引擎返回的Top-k网页结果[4-5]来获取扩展词。本文选择利用网页查询结果来获取扩展词，因为中文中存在大量的歧义性和多义性，用户输入的查询也经常出现输入错误的情况，搜索引擎本身已经融入了多种解决这种问题的方法，研究也表明[6]利用网页查询结果对广告查询具有一定积极意义。

对于广告查询扩展选择扩展词的方法目前主要是基于TF[7]、TFIDF[4]、聚类方法[2]等，它们能在一定程度上提高广告检索效果，但它们基于的特征比较单一，大部分没有融入语义信息，选择的扩展词中存在一定的噪音成分。为了能有效地降低扩展词中的噪音成分，选择出高质量的扩展词，本文将基于词共现的扩展词选取方法引入到广告查询扩展中，计算扩展词和查询词在网页查询结果中的共现度，并融合传统的扩展词选择方法，获得与原始查询语义相关的扩展词以提高广告检索效果。

本文余下的组织结构为： 第二节对查询扩展技术以及计算广告学领域的研究现状进行了介绍和分析；第三节介绍目前搜索引擎和索引中的广告组织形式；第四节介绍基于词共现和多特征融合的两种广告扩展词选取方法，并简单介绍了扩展词的权重分配方法和广告查询的检索模型；第五节介绍实验数据集的构造和实验结果评价方法，并对不同的扩展词选取方法、不同的扩展词数目下的查询扩展方法以及不同参数设置下的多特征融合方法得出的结果进行了分析；最后第六节总结本文的研究工作并对未来的研究方向进行展望。

2 相关工作

近些年来计算广告学的研究发展非常迅速，从简单的查询和竞价词之间的直接匹配发展到模糊匹配，完成计算广告产业中一次重要的变革，在模糊匹配中，广告检索类似于传统的文本检索，把广告的竞价词信息和创意作为文档进行检索，这大大促进了在线广告的发展。

目前研究主要分为两大类： 上下文广告和搜索广告。在搜索广告中，研究的主要有广告的索引结构、广告查询扩展、广告查询意图分析等。传统的信息检索一般是查询短、文档较长，而在广告检索中，查询和文档都比较短，使得准确率很难达到一个较好的水平，因此目前对查询扩展的研究比较多。

文献[2]中利用广告数据集中竞价词和创意之间的关系，采用迭代聚类方法，将相关的词项聚合在一起，以此来进行广告查询扩展。文献[3]中通过挖掘查询日志中同一个Session中的类似的查询来对查询进行重构，这种方式可以消除利用外部或者自身资源进行伪相关反馈方法产生的主题漂移问题。文献[7]对概率模型、语言模型等在广告检索上的效果进行了比较分析，并比较了基于TF的从网页搜索结果中提取扩展词的方法。文献[4]同时对查询和广告本身都进行扩展，加入了从网页搜索结果中提取的一些扩展词、短语和类别信息，这里提取扩展词的方法基于TFIDF，其中IDF表示候选扩展词在广告数据集中的逆文档频率。

从以上可以看出，目前大部分方法从资源中选取扩展词还是基于单特征的，而且没有融入语义信息，这就无法避免扩展词中出现噪音成分，因此本文将基于词共现选择扩展词的方法引入到广告检索中，并融合了扩展词的TF特征和词性信息，取得了很好的检索效果。

3 广告形式

在开始介绍本文提出的查询扩展方法前，需要了解下广告在搜索引擎以及索引中的形式。通常我们通过搜索引擎对互联网进行检索的时候可能在结果页的上方或者右侧出现一些广告结果，其中每一个广告包含标题、描述和URL，这样的三个域在广告商的广告管理中被定义为广告的创意，而且在广告商设定广告的时候，除了需要为每一个广告设定一个创意以供搜索结果中显示，还需要为每个广告设定几个到几十个不等的竞价词，传统的直接匹配方法就是如果用户的查询和其中一个竞价词匹配，那么就会根据竞价排名和网页质量等因素在结果中排序后显示前几条广告，因此这种方法也一般只能在用户输入高频查询时得到显示。而目前模糊匹配方法会将广告的所有域都考虑进来，这也大大降低了用户在设定竞价词时候的难度，并且能匹配到一些低频的查询。

在建立索引时，我们将每个广告当成一篇文档，由于处理的是中文的广告数据集，广告的URL域对检索几乎没有作用，因此索引中每篇文档含有三个域： 标题、描述和竞价词。

4 广告查询扩展方法

4.1 基于词共现的扩展词选取方法

本文将用户查询Q输入到Baidu搜索引擎中得到前k个网页查询结果，记为Dk，Dk={d1,d2，…dk}。目前搜索引擎在理解用户的查询意图上已经做了很多工作，它们可以消除中文查询中存在的歧义和拼写错误等问题，因此我们把Dk作为与查询相关的文档集合，从中选取扩展词进行广告查询扩展。

对于用户查询Q={q1,q2,…q|Q|}含有多个词项qi(1≤i≤|Q|)，每个词项qi在Dk中都有一些相关的词项，如何选择一些相关的词项来进行查询扩展成为首要的问题。Xu和Croft的研究[8]表明，利用词项之间的共现度来选取扩展词，能够取得更好的扩展效果，这里共现度是指两个词项在一定的文本窗口下共同出现的次数。

在网页查询结果集上，我们将词共现信息作为扩展词项的选取评分标准，在这里我们定义的文本窗口是指Dk中某一个网页查询结果d。下面我们定义扩展词t和查询词项qi在网页查询结果集Dk中的共现度co_degree(t,qi|Dk):

其中k表示Dk中网页查询结果总数，tf(*,d)表示词项在网页查询结果d中出现的频率。

我们可以通过co_degree(t,qi|Dk)从网页查询结果集Dk中选取与qi共现度高的几个词作为扩展词。但是，每个查询词项qi只能反应原始查询Q的部分信息，如果只是对每个qi进行简单的扩展就会容易产生主题漂移的问题。

因此在考虑一个扩展词t和原始查询Q的相关性的时候，我们需要考虑t和所有查询词项的qi共现度信息，在这里，我们假设查询词之间相互独立，不存在依赖关系。由于查询中的每个词项具有不同的重要性，我们在计算时需要引入一个量来度量词项的重要性，我们这里检索的数据集是广告集合，因此我们用词项在广告数据集中逆文档频率来度量词项对于广告检索的重要性。我们最终得出的扩展词评分公式如式(2)：

其中，idf(*,C)定义如下：

C表示广告数据集，N表示广告数据集中广告总的数目，df(*,C)表示词项在广告数据集中的文档频率。

表1 查询日志中不同词性的出现频率

注： 词项出现总次数为： 163 183 916。

4.2 多特征融合的扩展词选取方法

4.2.1 扩展词的词性信息

我们在观察具有广告查询意图的查询时发现，查询中不同词性的词项出现的频率有很大差异，名词、动词等出现的最为频繁，因此在选择扩展词的时候可以把扩展词的词性作为一个评价因素，我们定义每个词都具有一定的词性值，用不同词性在查询中出现的频率来量化词性值。由于我们无法获得大量的具有广告查询意图的查询，因此在计算时将不同的词性出现在查询日志中的频率作为词的词性值，之所以选择查询日志中的词性频率来度量词的词性值，是由于广告商在设定广告竞价词的时候，大部分是根据搜索引擎的广告系统推荐的竞价词，而这些推荐的竞价词就是频率较高的用户查询中的词项或者短语。

在搜狗实验室提供的2008年6月份的查询日志上，我们统计不同词性的词的频率如上页表1所示(列出了出现频率较高的10位)。

4.2.2 利用线性插值进行多特征融合方法

目前，针对扩展词的选取问题，越来越多的研究表明[9]，只利用某一个统计属性很难区分扩展词的相关性，在选取相关扩展词的过程中，综合扩展词多方面的评价指标是目前的研究趋势。因此，本文在4.1节描述的基于词共现的扩展词选取方法基础之上，提出融入传统的TF特征和上述的词性信息，利用线性插值方法将词共现度、TF、词性信息组合在一起来计算扩展词与原始查询Q的相关程度，如式(4)所示：

其中，α、β和γ相加之和为1，MAXSCORE表示所有扩展词中词共现度得分的最大值，tf(t,Dk)表示扩展词t在网页查询结果Dk中出现的频率，NDk表示Dk中词项总数，cxt表示扩展词的词性值。

4.3 扩展词权重分配方法及检索模型

在查询扩展中，扩展词有着不同的重要性，因此，如何对扩展后的查询中的词项进行权重分配便是一个问题。王斌和丁国栋等[10]提出了将扩展词的评分加入到传统的Rocchio公式中，取得了很好的效果。式(5)是权重分配函数的形式：

其中，Score(q′)表示扩展词q′的评分值；MaxScore表示所有扩展词的最大评分值；α和β在实验中分别设置为0.8和0.2。

在索引中，一个广告对应着一篇文档d，每篇文档共有三个域： 标题、描述、竞价词。由于文档中三个域重要性有所不同，因此实验中我们采用BM25F模型来计算查询和文档的相关性。

5 实验设计及结果分析

5.1 实验数据

实验中采用的广告数据集来自国内搜索引擎公司中搜索广告系统的真实数据，共计310 240个广告，每个广告包含一个创意和平均15个竞价词。

查询集包含50个查询，根据搜狗实验室提供的2008年6月份的查询日志，我们从中随机选择查询，由于我们研究的是广告查询扩展对广告检索效果的影响，所以在随机选择时需要保证选择的查询在广告数据集中至少有一个广告与之相关，也就是说查询需具有一定的广告查询意图，这样便于对实验方法进行评价。对于查询是否具有查询意图的判定属于计算广告学中另一个研究范畴，本文不涉及此内容。

对于扩展词的外部资源网页搜索结果，我们是将每个查询放入Baidu搜索引擎中，取前100条网页结果构造而成。

为了评价检索的性能，我们需要对查询和广告文档之间的相关性进行人工标注，由于真实的搜索引擎返回的广告结果只含有标题、描述和链接，我们在判定其相关性的时候也只关注广告文档中的标题和描述。在标注时每个查询和广告文档之间的相关性分为五个等级： 完全相关；比较相关；基本相关；几乎不相关；完全不相关。共生成11 307条标注结果。

5.2 评价方法

为了评价我们提出的查询扩展方法，我们采用DCG(Discounted Cumulative Gain)作为评价指标。DCG评价方法被广泛用于评价有多级相关性判断的排序方法中，本文中广告和查询的相关性判断分为五个等级，此方法正好合适。DCG方法评价一个查询的计算公式如式(6)：

其中，g(i)表示返回结果中排序为i位置的文档的相关性得分，五个等级的得分从完全相关到完全不相关的得分依次为10、7、3、0.5、0，k表示考虑结果的最大深度。最终我们用所有查询的DCG@1、DCG@3、DCG@10的平均值来作为评价依据。

5.3 实验结果与分析

首先我们给出几种检索方法的检索性能结果，如表2所示，其中“无扩展”表示直接用原始查询在广告数据集用BM25F方法进行检索，“基于TF”表示利用网页查询结果中词项的频率高低进行扩展词选取的查询扩展方法，表2中几种扩展方法我们选取的扩展词数目都是取扩展词质量得分前30的。

表2 几种查询扩展方法的性能

注： 此表中所示的“多特征融合1”方法的结果是在α、β、γ分别为0.5、0.5、0时得到的；“多特征融合2”方法的结果是在α、β、γ分别为0.45、0.45、0.1时得到的。

从表2中基于TF方法的查询扩展的结果可以看出，利用网页查询结果集可以有效地提高检索性能，说明网页查询结果是一种质量较高的外部扩展资源。而利用词共现方法相对于基于TF方法又有一定程度上的提高，这是因为词共现方法是通过计算查询词和扩展词在网页查询结果中的共现度来作为评价因素的，它可以融入语义信息，为广告查询扩展选择更多语义相关的扩展词，降低扩展时的噪音。基于多特征融合方法的检索效果表现最好，其中“多特征融合1”只将TF特征和词共现度信息线性融合在一起，没有考虑词性信息，结果比基于TF和基于词共现的方法的结果都有提高，说明扩展词的TF、词共现度信息在扩展词的选取中都发挥了积极作用，它们是从不同的方面量化了扩展词的质量；“多特征融合2”方法是同时考虑了词项的TF、词共现和词性信息，效果是几种方法中最佳的，由此可见，词性信息在评价扩展词的质量时也发挥了积极作用。

在用多特征融合方法进行扩展词选取时，我们对参数的选择做了多组实验， 其中几组具有代表性实验中的参数如表3所示，其对应的检索结果如图1所示。

表3 多特征融合方法中参数的设置

对于广告查询扩展词的数量的选择，我们在基于词共现的查询扩展方法下，分别选取了不同数量的扩展词进行检索，检索效果如图2所示，从图中我们能看出在选择前30扩展词时检索效果达到最佳，选择更多或者更少扩展词导致检索效果变得越来越差，逐渐向未扩展时的检索效果退化，这是因为，如果选择扩展词较少，则忽略了一些质量较高的扩展词，不能达到最佳的扩展效果，而如果扩展词选择过多，则会引入更多的和广告查询不相关的扩展词，影响扩展效果。

图1 不同的参数设置对检索结果的影响

图2 选择TOP-k扩展词的检索结果

在图1中，通过比较CO1和CO2的结果可以发现，融入词性值有利于检索性能的提升，而CO3中将词性值的权重继续加大，则导致了检索性能的下降，说明词性值对扩展词评价的贡献度有限，不能将词性值的权重设得过高。另外通过比较CO4和CO2、CO5结果可以看出，CO4的结果表现最好，词共现度、TF值和词性值三个特征赋予不同的权重会产生不同的检索效果，适当地提升词共现度的权重可以使得检索效果更好，如果使得TF特征具有最大权重，则得不到最好的检索效果。综合以上几种不同参数的实验结果，可以得出三种特征对于评价扩展词的质量的重要性从高到低依次是： 词共现信息，TF特征，词性值。

6 结束语

本文使用搜索引擎中的网页查询结果作为查询的伪相关文档，引入了基于词共现的方法来为查询选择有利于广告检索的扩展词，并在此基础上，提出了融入传统的TF特征和词性信息，使得选择的扩展词和原始查询的意图具有更高的相关性，实验结果显示，多特征融合从网页查询结果集中选取扩展词方法比传统的基于TF方法和基于词共现的方法在检索性能上都有明显的提高。

本文在进行查询扩展时，原始查询词项和扩展词之间都是基于独立性假设的，而实际上，尤其对于广告检索，词与词之间的依存关系非常重要，利用这些依存关系可以发现更多语义相关的扩展词，减少扩展词中噪音成分。另外本文只是基于共现度这一种查询扩展方法来进行讨论，尚未对多种查询扩展方法的检索效果进行比较。我们下一步的工作将研究如何挖掘广告扩展词之间的依存关系，以及多种扩展方法在利用网页查询结果作为扩展资源进行查询扩展的优劣。

[1] A. Broder, M. Ciaramita, D. Metzler, et al. To swing or not to swing: learning when (not) to advertise[C]//Proceeding of the 17th ACM Conference on Information and Knowledge Management (CIKM ’2008), Napa Valley, California, 2008： 1003-1012.

[2] H. Wang, Y. Liang, L. Fu, et al. Efficient query expansion for advertisement search[C]//Proceedings of the 32nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’2009), Boston, 2009： 51-58.

[3] R. Jones, B. Rey, O. Madani, et al. Generating query substitutions[C]//Proceedings of the 15th International Conference on World Wide Web (WWW’2006), New York, 2006： 387-396.

[4] A. Z. Broder, P. Ciccolo, M. Fontoura, et al. Search advertising using web relevance feedback[C]//Proceeding of the 17th ACM Conference on Information and Knowledge Management (CIKM’2008), Napa Valley, California, 2008： 1013-1022.

[5] A. Broder, P. Ciccolo, E. Gabrilovich, et al. Online expansion of rare queries for sponsored search[C]//Proceedings of the 18th International Conference on World Wide Web (WWW’2009), Madrid, 2009： 511-520.

[6] C. Danescu, A. Broder, E. Gabrilobich, et al. Competing for users’ attention: on the interplay between organic and sponsored search results[C]//Proceedings of the 19th International Conference on World Wide Web (WWW’2010), New York, 2010： 291-300.

[7] H. Raghavan, R. Iyer. Evaluating vector-space and probabilistic models for query to ad matching[C]//SIGIR’08 Workshop on Information Retrieval in Advertising (IRA), 2008.

[8] J. Xu, B. Croft. Query expansion using local and global document analysic[C]//Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’1996), Zurich, Switzerland, 1996： 4-11.

[9] G. Cao, J. Nie, J. Cao, et al. Selecting good expansion terms for pseudo-relevance feedback[C]//Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’2008), Singapore, 2008： 243-250.

[10] 丁国栋，白硕，王斌. 一种基于局部共现的查询扩展方法[J]. 中文信息学报，2006，20(3)： 84-91.