在这个信息爆炸的时代,搜索引擎已成为人们在互联网的数据海洋中遨游不可或缺的工具。无论是查找信息、获取资源还是寻求帮助、发现机遇,都离不开搜索引擎的指引与参考。可以说,搜索引擎已经成为了互联网中的“基础设施”。根据CNNIC中国互联网络发展状况统计报告显示,截至 2016 年 1 月,已有82.3%的互联网用户使用搜索引擎,在互联网网络应用中排名第二;而在移动端也有 77.1% 的用户使用移动端搜索引擎,在移动应用中排名第三。由此可见,搜索引擎已成为大多数互联网用户必不可少的应用之一,因此搜索引擎所提供的搜索结果质量对于用户体验有着极为重要的影响。
在搜索引擎对于不同搜索结果的质量(结果相关性)进行判断(预测)时,最为传统的方法是基于结果内容的相关性预测方法[1],该方法通过对搜索时用户提交的查询词以及所有结果的文本内容进行处理,从中提取出有效的衡量 结果相关性的特征(例如TF-IDF[2]、BM25[3]等),从而利用上述特征或指标来衡量不同搜索结果与查询词之间的相关性,进而对所有结果进行筛选和排序。这些方法为搜索引擎系统快速并准确地从大量结果中筛选出符合用户真实搜索需求的结果列表提供了最为基础有效的解决方案,成为了当前搜索引擎架构中基础的模块之一。然而上述方法并不能完美解决搜索结果相关性预测及排序等问题,例如Lv等[4]指出,当结果内容信息很长时,BM25指标会变得不能正确衡量结果的相关性。因此,除了结果的内容信息外,搜索引擎有必要引入更多的信息去更好地衡量搜索结果的相关性,从而为搜索用户提供更好的结果排序。
由于互联网网页中往往包含大量超链接,这些超链接使互联网网页得以互相连接,从而组成了不同的网络结构。因此,一个简单的推断是在该网络结构中,不同位置的节点其具有的重要性程度可能不同。所以第2种方法是利用互联网网页的链接结构推断不同结果的重要性[5]、可靠性[6]等,从而对不同结果的相关性有更好地估计。上述方法为搜索引擎结果相关性估计和结果排序起到了进一步改进的作用,同样成为了搜索引擎的重要模块之一。
除了上述方法外,近年来,利用互联网群体智慧[7]来改善搜索结果相关性估计[8]的方法开始受到关注,并成为另一种提升搜索引擎结果相关性估计和改进搜索引擎排序的重要方法。由于每天都有大量的用户与搜索引擎进行交互,这些搜索引擎用户在与搜索引擎的交互过程中反映出的隐性反馈信息(主要是点击行为信息)也是搜索引擎改进结果排序的重要影响因素。直观来说,如果很多的搜索用户在搜索同一个查询时点击了某个搜索结果,那么该搜索结果就有可能是一个相关的结果。由于每天搜索引擎都可以收集到海量的用户隐性反馈信息,如果我们能从这些信息中挖掘出用户对于搜索结果的真实相关性反馈,那么就可以利用上述信息对搜索引擎的相关性预测进行更好地改进。
然而,用户在搜索过程中的点击行为可能会受到多种因素的影响。研究表明,由于搜索用户受到结果位置[9-10]、展现形式[11]、可信度[12]等各种因素的影响,将反馈信息直接应用于结果相关性估计任务往往难以取得较好的效果。针对这一问题,研究人员提出了构建描述用户点击行为的点击模型[13-15]来尝试解决上述问题。点击模型是用来描述用户从开始搜索到搜索结束过程中点击行为的发生过程的模型,不同的模型会尝试描述用户在搜索过程中受到的不同因素的影响,以及这些影响之间的相互关联(例如,不同的点击模型会对用户检验不同位置的搜索结果的概率有不同的估计,进而尝试去除结果展现位置等因素对用户行为的偏置性影响),最终利用大规模的用户点击信息去推测模型中的不同影响因素所发挥的作用程度,从而更为准确地估计结果的真实相关性和新页面下用户的点击概率,达到更好利用隐性反馈信息的目的。
作为一种用户交互信息的有效利用方法,点击模型在学术界得到了充分关注,并在工业界得到了广泛的应用。传统的点击模型主要针对于传统同质化的搜索页面(搜索页面中的结果均采用相近的文本形式展现,结果之间除了文字内容不同外并没有明显的展现形式差异)进行设计。随着Web2.0时代的到来,富媒体展现形式被越来越多地应用于搜索交互界面,搜索结果也变得越来越异质化[16],这些变化使得用户的检验行为(注意力分布偏好、浏览顺序等)发生了明显的改变[17],传统的点击模型已经不能正确地描述用户的真实行为,相应的排序方法也难以取得较优的效果。因此研究人员开始提出针对于垂直搜索结果的点击模型以及针对非顺序检验行为的点击模型。
1 基于位置的点击模型主流的点击模型大都基于点击模型方面最基础的研究[9],认为用户在浏览搜索引擎时采用的是沿着搜索结果列表从上到下依次浏览的方式,根据这个假设,用户的浏览顺序与搜索结果的位置顺序是一致的。因此大多数的点击模型都是基于位置的构建方式(我们称作基于位置的点击模型)。另外,由于点击模型中最主要的信息来源为用户的交互信息(主要是点击信息),因此模型对于用户行为以及结果相关性的推断都来源于点击行为。因此大多数的点击模型都假设搜索页面中的所有结果是同质的(所有具有类似的形式,仅在内容上有所区别,对应到模型中即为仅在结果相关性上有所区别),在排除结果相关性影响之后这些结果对于用户的行为不构成影响。
上述两条假设成为了主流点击模型的基础假设,因此本部分的相关工作介绍主要介绍这些点击模型相关内容,其他的与之有所区别的点击模型会在本工作与这些工作相关的章节进行介绍。
大多数的点击模型利用名为检验假设(examination hypothesis) [9]的用户行为假设来对用户的点击行为和其中蕴含的结果反馈之间的关联进行建模,其具体描述为给定一个查询词q 和对应的搜索结果列表 D=<d1,d2,…,di,…,dM>通常为 10,即页面中包含10条搜索结果。对于其中第i个结果di,该结果是否被点击(Ci=1)当且仅当这个结果被用户检验(Ei=1),并且这个结果是一个相关的结果(Ai=1),而相关与检验则是两个独立的变量。
Ci=1→Ei=1,Ai=1
Ei=0→Ci=0
Ai=0→Ci=0
根据以上假设,一个搜索结果被点击的概率可以用式(1)表示:
(1) |
这样我们在知道用户的点击信息之后,通过推断用户的检验信息,就能推断出每个结果的真实相关性信息。图 1为检验假设的模型示意图。
1.1 级联模型级联模型[9]假设用户的浏览行为是沿着搜索结果列表从上到下依次检验的,当且仅当用户检验了某个结果并且该用户没有做出点击该结果的行为,该用户才会继续检验排在该结果后一位的搜索结果。其模型的示意图如图 2所示。针对该结果的公式为
P(E1)=1
P(Ei+1=1|Ei=1,Ci)=1-Ci
1.2 DCM模型由级联模型的假设可知,该模型只能描述用户仅有一次点击的搜索情况,而实际的用户行为中,用户可能会发生多次点击,因此Guo等[13]提出了dependency click model (DCM)模型,该模型沿用了用户顺次向下检验的行为假设,同时假设当用户点击之后仍然有一定的概率继续下一步的浏览行为,其浏览行为描述公式为
P(Ei+1=1|Ei=1,Ci=0)=1
P(Ei+1=1|Ei=1,Ci=1)=λi
1.3 UBM模型接下来,Dupret等[14]提出了user browsing model (UBM)模型,如图 3所示。他们通过实验研究发现用户检验某个位置的结果的概率不仅和当前该结果所处的位置相关,同时还和该结果与用户上一次点击的结果的距离有着非常重要的关联,因此他们的模型假设:
P(Ei=1|C1…i-1)=λri,di
式中:ri表示当前该结果的位置,而di表示当前结果和上次点击的结果的位置距离。
1.4 DBN模型Chapelle等[15]提出了dynamic Bayesian network (DBN)模型,如图 4。该模型首次将用户的浏览过程中的满意度行为引入模型描述中。该模型假设用户每点击一条结果之后都会有一定的满意度改变,而一旦用户在某次点击之后达到了满意的程度,那么他/她就会停止检验后续的结果并结束这次查询:
(Si=1|Ci=1)=su
P(Ei+1|Ei=1,Si=0)=λ
式中:Si表示用户点击了第i个结果之后的满意程度,λ表示了用户不满意的情况下继续检验后续结果的概率。
除了上述模型之外,Guo等[23]提出了click chain model (CCM)模型描述用户可能存在的略过行为;Hu等[24]尝试区分不同查询意图下用户浏览行为的区别,从而对已有的点击模型进行改进;Chen等[25]提出了noise-aware click model (NCM)尝试从所有的点击信息中区分哪些是用户真实的结果相关性判断,哪些是由于其他原因造成的不可信的点击。
可以看到,以上的一系列的点击模型都是基于用户的检验顺序严格从上到下进行一遍以及所有结果具有同质属性这两个基本的假设进行研究的。
2 针对垂直搜索结果的点击模型随着Web2.0时代的快速发展,搜索引擎页面正在变得越来越异质化,大量的包含富文本信息的搜索结果被引入搜索页面。这些搜索结果来自于搜索引擎的多个具有特定搜索目标的子引擎,通常被称为垂直搜索引擎。这些来自垂直搜索引擎的垂直搜索结果(例如图片搜索引擎得到的图片结果)往往与传统的结果具有不同的展现形式,因此现今的搜索页面上的搜索结果正在变得非常异质化,这也使得用户的浏览行为习惯和偏好可能产生比较大的变化。
Wang等[11]对一家中文商业搜索引擎的大规模搜索日志进行了分析(详细分析结果请见2.1小节),发现当前中文搜索环境下超过80%的搜索结果页面包含有垂直结果,并且不同展现形式的垂直结果对用户的行为产生了很大的影响,包括对于垂直结果本身(局部影响)和对整个搜索页面(全局影响)。因此,对于现今的搜索引擎来说,考虑不同垂直结果是非常重要的因素。
他们根据中文搜索引擎常见的搜索结果对结果展现形式进行了分类,如图 5所示:
1) 普通结果:非垂直结果,最常见的搜索结果展现形式,由一条超链接标题和一段文本摘要组成。
2) 文本类垂直结果:由一段文本摘要和多条超链接标题组成,例如新闻类或者百科类搜索结果。
3) 多媒体类垂直结果:主要由一组多媒体组件(通常为一组图片)组成,如视频、图片类搜索结果。
4) 应用类垂直结果:由嵌入搜索页面的一组组件组成,用户可以通过与组件交互直接得到搜索结果,例如计算汇率兑换的计算器。
2.1 FCM模型Chen等[16]最早提出了针对垂直结果的点击模型,他们分析了部分垂直结果对用户点击的影响,提出了federated click model (FCM)模型,该模型假设用户的检验概率可能会受到最近的上一个垂直结果的影响(吸引假设):
P(A=1)=hposrvert
P(Ei=1|A=0)=φi
P(Ei=1|A=1)=φi+(1-φi)βdist
式中:A表示用户是否被垂直结果所吸引,如果用户被垂直结果吸引A=1,那么该用户的检验其他普通结果的概率会受到一定的影响。
2.2 VCM模型Wang等[11]利用眼动追踪设备对用户的搜索浏览行为进行了深入的分析,他们发现不同展现类型的垂直结果对用户的视线注视行为有着很大的影响,如图 6所示。
图 6左侧为不含垂直结果的页面,右侧为包含多媒体垂直结果的页面,热度图越暖色表示用户的视觉注视越多。可以看到,当多媒体垂直结果加入页面后,用户的视线被很大程度吸引,从而不再像左图一样自上而下递减分布。
Wang等[11]针对用户的浏览行为变化进行了深入的分析,最终总结了4个用户行为偏置假设:
1) 吸引力偏置假设:如果有一个垂直结果在搜索结果页面中出现,那么用户有一定的概率首先检验该垂直结果。
2) 全局影响偏置假设:如果有一个垂直结果在搜索结果页面中出现,并且用户首先检验了该垂直结果,那么用户会对整个页面有一个全局印象,该印象会使得用户对普通搜索结果的检验和点击偏好产生影响。
3) 首位偏置影响假设:如果有一个垂直结果在搜索结果页面中出现,并且该垂直结果被排在了第1位,那么用户就可能会更多地点击该垂直结果而较少点击其他结果。
4) 浏览顺序偏置影响假设:如果有一个垂直结果在搜索结果页面中出现,并且用户首先检验了该垂直结果,那么用户会在接下来回看垂直结果之前的搜索结果,回看的路径或者回到顶端自上而下浏览,或者沿着自下而上的顺序反序浏览。
相应的点击模型描述为
P(Ci=1|Ei=0)=0
P(Ci=1|Ei=1)=P(Ai=1|Ei=1)
P(F=1)=φtv,lv
P(Fi=1|F=0,C1:i-1)=γi,i-1i
P(Fi=1|F=1,C1:i-1)=γi,i-1i+θq,i
P(Ai=1|Ei=1,F=0)=αq,i
P(Ai=1|Ei=1,F=1)=αq,i+βq,i
P(B=1|F=0)=0
P(B=1|F=1)=σtv,lv
其描述的用户浏览行为决策过程可以用图 7表示。用户在开始浏览时,他会有一定的机率决定是否首先去检验垂直结果,如果首先检验了垂直结果,那么用户会继续约定是否回到页面顶端自上而下浏览,亦或是自下而上反序浏览。
3 基于点击顺序的点击模型已有的眼动追踪实验研究工作[18]表明,搜索引擎用户的浏览习惯可以分为两种类型:深度优先策略和宽度优先策略。其中深度优先策略描述用户的检验顺序是顺着搜索结果列表的结果序列自上而下浏览搜索结果并在浏览每个搜索结果的同时决定是否点击。而宽度优先策略则是另一种类型,它描述用户在点击搜索结果之前会预先检验一系列的搜索结果,然后再在其中选择自己最中意的若干结果点击。由于根据深度优先假设,用户点击时受到的很重要的位置偏执影响能够很容易被模型所考虑进去,因此大多数的点击模型[13-15]都遵从深度优先假设,也就是用户自上而下浏览一遍搜索结果列表。
然而,眼动视线追踪实验研究[19]表明,仅有34%的搜索用户的浏览序列是顺序(自上而下)的,而有50%以上的查询会话中用户会发生回访行为(自下而上的浏览搜索结果)或者略过的行为。因此研究人员有必要对用户的非顺序浏览(点击和检验)行为进行研究。
3.1 TCM模型Xu等最先提出了名为temporal click model (TCM) [20]的模型在广告搜索中描述用户的点击行为。这个模型尝试将所有可能的检验序列全部计算出现概率,因此只能描述仅包含两个结果(广告)的页面,所描述的非顺序点击行为为:用户首先点击了第2个搜索结果,然后再点击了第1个搜索结果。因此这个工作很难像其他点击模型一样扩展到描述整个搜索结果列表。
3.2 POM模型Wang等提出了名为partially observable Markov model (POM) [21]的点击模型来描述用户的任意浏览行为。POM模型将用户的检验事件当做一个部分可观测的随机过程来进行描述。其流程示意图如图 8所示,对于一个可以观测的点击行为序列,该模型会试图寻找所有可能的检验序列并分别计算各种检验序列的可能性。
尽管这个模型能够描述用户的非顺序检验行为,但模型仅考虑了用户在不同位置之间的检验跳转概率(也就是说,不同用户,不同查询,不同搜索结果下用户的检验跳转行为是一致的),因此该模型并不能针对具体的查询和结果给出点击概率预测和结果相关性预测,并且难以在实际环境中应用,并和已有的点击模型进行比较。
3.3 PSCM模型Wang等[22]利用眼动视线追踪设备对用户的非顺序浏览行为进行了深入的分析,在总结了用户浏览行为的一般规律后提出了如下两个用户非顺序浏览行为假设。
1) 局部检验线性假设:在两次点击之间,用户倾向于沿着点击方向检验结果而不再改变检验方向,无论用户的点击方向是向上还是向下。
2) 非一阶检验假设:尽管用户在两次点击之间的检验行为是局部线性有序的,但用户并不是一个挨着一个检验搜索结果,而是会略过一些搜索结果。
相应的模型示意图如图 9所示,点击行为首先根据时间信息记录为时间序列,接下来对于每一个点击对,根据局部检验线性假设,用户在点击对之间是线性的浏览行为,因此可以用一个基于位置点击模型的子模块来描述这个点击对之间的用户浏览行为。而由于用户可能会略过一些结果,因此点击对之间的所有搜索结果并不是都被用户检验,而是需要模型推断用户检验了哪些搜索结果。
4 点击模型开源工具及数据集由于点击模型具有很强的实用性,因此很多搜索引擎公司都有部分模型的内部实现方案,而研究人员也针对点击模型开发了一系列的开源工具实现:
1) ClickModelProject (https://github.com/varepsilon/clickmodels)是一个基于Python的开源点击模型项目,本文中介绍的DCM、UBM、DBN等模型在该开源项目中均有实现。
2) PyClick (https://github.com/markovi/PyClick)是一个基于Python的开源点击模型项目,本文中介绍的FCM、VCM等模型在该开源项目中均有实现。
3) THUIRClick (https://github.com/THUIR/PSCMModel)是一个基于Python的开源点击模型项目,本文中介绍的TCM、POM、PSCM等模型在该开源项目中均有实现。
除了开源工具之外,业界搜索引擎公司也公布了一批公开的搜索日志资源:
1) Yandex (https://www.kaggle.com/c/yandex-personalized-web-search-challenge)是一家俄文和英文搜索引擎公司,其公布了2012年某一个月的搜索日志。
2) Sogou (http://www.sogou.com/labs/dl/q-e.html)是一家中文搜索引擎公司,其公布了2012年部分时段的搜索日志。
3) Microsoft (http://research.microsoft.com/en-us/um/people/nickcr/wscd09/)公布了2006年MSN的某一个月的搜索日志。
5 结束语点击模型作为一种用户交互信息的有效利用方法,在学术界得到了充分关注,并在工业界得到了广泛的应用。本文主要介绍了点击模型的发展过程以及不同点击模型的功能。同时介绍了部分点击模型研究中可用的资源。随着大数据时代的不断推进,点击模型作为一种有效利用搜索引擎海量用户交互数据的方法,必将在学术界得到更为全面的研究,也将在工业界得到更为深入的应用。
[1] | ROBERTSON S, ZARAGOZA H. The probabilistic relevance framework:BM25 and beyond[M]. Hanover, MA: Now Publishers Inc, 2009. |
[2] | SPARCK JONES K. A statistical interpretation of term specificity and its application in retrieval[J]. Journal of documentation, 1972, 28(1) : 11-21DOI:10.1108/eb026526. |
[3] | ROBERTSON S E, WALKER S, JONES S, et al. Okapi at trec-3[Z]. Nist Special Publication Sp, 1995, 109:109. |
[4] | LV Y, ZHAI C. When documents are very long, bm25 fails![C]//Proceedings of the 34th International ACM SIGIRConference on Research and Development in Information Retrieval. New York:ACM, 2011:1103-1104. |
[5] | PAGE L, BRIN S, MOTWANI R, et al. The pagerank citation ranking:bringing order to the web[Z]. Stanford:Stanford University, 1999. |
[6] | GYONGYI Z, GARCIA-MOLINA H, PEDERSEN J. Combating web spam with trustrank[C]//Proceedings of the 30th International Conference on Very Large Data Bases. Toronto, Canada:VLDB Endowment, 2004:576-587. |
[7] | SUROWIECKI J. The wisdom of crowds[Z]. Anchor, 2005. |
[8] | AGICHTEIN E, BRILL E, DUMAIS S, et al. Learning user interaction models for predicting web search result preferences[C]//Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY, USA:ACM, 2006:3-10. |
[9] | CRASWELL N, ZOETER O, TAYLOR M, et al. An experimental comparison of click position-bias models[C]//Proceedings of the 2008 International Conference on Web Search and Data Mining. New York, NY, USA:ACM, 2008:87-94. |
[10] | JOACHIMS T, GRANKA L, PAN B, et al. Accurately interpreting clickthrough data as implicit feedback[C]//Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY, USA:ACM, 2005:154-161. |
[11] | WANG C, LIU Y, ZHANG M, et al. Incorporating vertical results into search click models[C]//Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval. New York, NY, USA:ACM, 2013:503-512. |
[12] | YUE Y S, PATEL R, ROEHRIG H. Beyond position bias:Examining result attractiveness as a source of presentation bias in clickthrough data[C]//Proceedings of the 19th International Conference on World Wide Web. New York, NY, USA:ACM, 2010:1011-1018. |
[13] | GUO F, LIU C, WANG Y M. Efficient multiple-click models in web search[C]//Proceedings of the Second ACM International Conference on Web Search and Data Mining. New York, NY, USA:ACM, 2009:124-131. |
[14] | DUPRET G E, PIWOWARSKI B. A user browsing model to predict search engine click data from past observations[C]//Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY, USA:ACM, 2008:331-338. |
[15] | CHAPELLE O, ZHANG Y. A dynamic bayesian network click model for web search ranking[C]//Proceedings of the 18th International Conference on World Wide Web. New York, NY, USA:ACM, 2009:1-10. |
[16] | CHEN D Q, CHEN W Z, WANG H X, et al. Beyond ten blue links:enabling user click modeling in federated web search[C]//Proceedings of the 5th ACM International Conference on Web Search and Data Mining. New York, NY, USA:ACM, 2012:463-472. |
[17] | LIU Z Y, LIU Y Q, ZHOU K, et al. Influence of vertical result in web search examination[C]//Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY, USA:ACM, 2015:193-202. |
[18] | KLÖCKNER K, WIRSCHUM N, JAMESON A. Depth-and breadth-first processing of search result lists[C]//CHI'04 Extended Abstracts on Human Factors in Computing. New York, NY, USA:ACM, 2004:1539. |
[19] | LORIGO L, PAN B, HEMBROOKE H, et al. The influence of task and gender on search and evaluation behavior using google[J]. Information processing & management, 2006, 42(4) : 1123-1131. |
[20] | XU W H, MANAVOGLU E, CANTU-PAZ E. Temporal click model for sponsored search[C]//Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY, USA:ACM, 2010:106-113. |
[21] | WANG K S, GLOY N, LI X L. Inferring search behaviors using partially observable Markov (POM) model[C]//Proceedings of the third ACM International Conference on Web Search and Data Mining. New York, NY, USA:ACM, 2010:211-220. |
[22] | WANG C, LIU Y Q, WANG M, et al. Incorporating non-sequential behavior into click models[C]//Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY, USA:ACM, 2015:283-292. |
[23] | GUO F, LIU C, KANNAN A, et al. Click chain model in web search[C]//Proceedings of the 18th International Conference on World Wide Web. New York, NY, USA:ACM, 2009:11-20. |
[24] | HU B T, ZHANG Y C, CHEN W Z, et al. Characterizing search intent diversity into click models[C]//Proceedings of the 20th International Conference on World Wide Web. New York, NY, USA:ACM, 2011:17-26. |
[25] | CHEN W Z, WANG D, ZHANG Y C, et al. A noise-aware click model for web search[C]//Proceedings of the 5th ACM International Conference on Web Search and Data Mining. New York, NY, USA:ACM, 2012:313-322. |