点击模型

在搜索引擎中，点击模型是指对用户的历史点击文档进行建模，用来预测文档相关性。

网页搜索排序传统上基于人工设计的排序函数，如BM25等。近几年，排序学习的引入大大的降低了融合大量特征的繁琐程度，不过由于排序学习是监督学习，因此需要大量的人工标注人员对文档进行标注，这需要大量的人工成本，而且由于网页的相关性会随着网页内容的更新等发生变化，尤其是时效性类的新闻网页，保持所有的人工标注是最新的是不可行的。

用户的点击日志记录了用户对搜索结果满意程度的重要信息，能够提供对相关性预测价值非常高的信息。相比较人工标注而言，点击的获得成本更低，而且点击体现的总是最近的相关性。

1. 点击的偏置

1) 位置偏向性（position bias）

排序越靠前的文档被用户浏览（examine）和点击的概率越大。

眼动仪实验

2) 吸引偏向性

标题、摘要、垂直结果（图片、视频、音乐等）、色情、娱乐八卦、SEO结果等会吸引用户的点击。

3) relevance bias

perceived relevance != actual(real) relevance or pre-click relevance != post-click relevance

4) query-intent bias

用户输入的query只是真实意图冰山之一角。

2. 正反馈

如果只依靠点击，容易产生正反馈，即点击多的排序高，排序越高相对点击就会越多，导致正向反馈，新的、好的文档排不上来。正反馈是一把双刃剑，好的文档一直排前也是我们期望达到的。

3. 感知相关性

用户点击是感知相关性，即根据标题、摘要等判断的相关性，而且仅仅是用户认为的相关性，因此区别于文档实际的相关性。

4. 稀疏性

长尾查询无法覆盖，或者点击数太少以至于点击数据不可靠。

点击稀疏问题分为两个方面，一个是不完全点击问题，对于一个query而言，用户仅仅点击有限数量的文档，因此点击是不完全的；另一个是缺失点击问题，对大量的queries和documents，用户没有点击数据。

5. 点击作弊等

如机器人点击等。

6. 用户个性化

用户的点击行为是一种个性化行为。

7. 冷启动问题（Cold Start Problem）

新查询的点击预测问题

8. Externality

单条url的点击行为与SERP（Search Engine Return Pages）内其他结果的行为是有关联的。

9. Query session and Search session

同Externality类似，用户的一个完整的查询task可能包括多次query提交，即一个或多个query session组成了search session，显然同一个search session内多个query session是有关联的。

1. position modelposition model假设点击依赖于相关性（relevance）和检验（examination）。每一个排序位置有一个被检验到的确定概率，这个概率随着排序位置递减而递减，并且仅依赖于排序位置。url上的一个点击表明这个url被用户查看并认为相关。position model认为搜索返回结果页中的url是独立的，因此不能够在检验概率中捕获不同url之间的联系。举例来说，对于一个query的两个相关性一样的url，用户可能仅仅点击了排序靠前的url，满足用户需求，因此就结束了搜索过程。这样，位置偏置不能够充分的解释第二条url上点击的稀少。
2. cascade modelcascade model假设用户顺序检验url，直到一个相关文档被点击。这样，检验的概率间接的依赖两个因素：url的排序和url之前的所有url的相关性。cascade model做了一个很强的假设，即每次搜索过程只有一次点击，因此它不能解释放弃搜索或者有多于一次点击的搜索。即使cascade model如此的严格，但在解释排序较高的url的点击上，依然远好于其他position model模型。在较低的url排序位置，cascade model表现较其他position model模型相对差一些。

点击模型的相关工作如下。

点击模型一个众所周知的挑战是位置偏向性（position bias）。这种偏向性被Granka et al [2004]首次注意到，他们发现一个文档排序越高，即使是不相关的，也会吸引更多的用户点击。此后，Richardson et al [2007]提出了对低排序位置的文档提权；Craswell et al [2008]把这种思想形式化为检验假设（examination hypothesis）。给定一个查询和一个排序位置是的文档，检验假设假定给定检验事件下二值点击事件的概率如下：

这里我们用表示位置的文档被点击，否则此值为0，的定义类似。此外，表征了查询和文档的相关程度。很显然，在查看之后点击的条件概率。这样，点击率（CTR）可以表示如下：

这样CTR被分解为位置偏向性（）和文档相关性（）。

检验假设的一种重要扩展是UBM模型[Georges Dupret and Benjamin Piwowarski, SIGIR'08]。UBM假设检验事件不仅依赖于位置，也依赖于同一个query session里前面的点击位置,,意味着之前没有点击。全局参数表征了从位置到位置的转移概率。我们用表示:

使用UBM的一个类似的模型是贝叶斯浏览模型（BBM）[C. Liu et al, 2009],BBM采用贝叶斯方法把每个随机变量作为概率分布推导，这类似于General Click Model（GCM, [Z. Zhu et al, 2010]）。GCM考虑了大量的偏向性来扩展模型，并说明了以前的模型都是GCM的特例。Hu et al[2011]扩展UBM描述点击日志里的查询意图的多样性。Chen et al[2011]提出了一个全页的点击模型，这个模型考虑到了搜索结果页的所有结果，包括自然结果和广告结果，把搜索结果作为一个整体来帮助CTR预测。

cascade模型是另一个扩展。cascade模型假设用户从上到下不会跳过的浏览文档。因此，一个文档被检验仅当前面的文档都被检验。

对cascade模型两个重要的改进是CCM[F, Guo et al, 2009]和DBN[O Chapelle and Y. Zhang, 2009]模型。两个模型都强调了检验概率也依赖于前面文档的点击和相关性。此外，允许用户停止检验，即放弃搜索。CCM使用了前面文档的相关性信息，而DBN则引入了一个用户满意的参数。这个参数表明如果用户对当前点击的文档满意，那么他将不会再浏览下面的文档。否则，存在一个概率用户继续搜索。

这里是一个表示用户满意的隐事件。

有三个其他的模型没有应用cascade assumption。SUM（session utility model, [G. Dupret and C. Liao, 2010]），给定一个query，点击文档集合的相关性以用户停在这个query session的概率来表征。adPredictor 模型（[T. Graepel et al, 2010]）以线性组合带权值的特征来解释点击率。PRM（pure relevance model, [R. Srikant et al, 2010]）认为一个文档的相关性不是恒定不变的，而是受其他位置的点击影响。

TCM（Task-centric Click Model, [Yuchen Zhang et al, 2011]）不同于上述的假设和方法。TCM针对如何对包括多个query和query会话的整个搜索会话作为一个整体和动态的实体进行探索。TCM是整合了整个搜索会话数据的一个更加细致和有效的点击模型。

随着搜索引擎的发展，搜索结果页的展现越来越丰富，搜索引擎都有很多垂直结果（如图片或视频），理解用户点击行为作为反馈信息是一种有效的方法，很多点击模型主要解决位置偏向性问题（position bias），提高普通搜索结果的排序效果，普通结果的展现样式是一样的。然而，当把垂直结果和普通结果组合在一起的时候，展现的巨大不同将导致用户行为的偏向，也就使得以前的点击模型失效。在中国一个流行的搜索引擎的帮助下，我们收集了大量的包含垂直结果和普通结果的行为信息的数据集。我们也利用眼动仪学习了用户在现实世界中的检验行为。通过这些分析，我们发现不同的结果展现可能造成不同的用户偏向，无论对于垂直结果还是对于整个结果列表。这些偏向性包括：垂直结果（尤其是带多媒体组件的）的检验偏向性，垂直结果的信任偏向性，垂直结果的更高概率的重新访问。基于这些发现，一个处理考虑位置偏向性之外还考虑这些偏向性的新的点击模型被构建来描述包含垂直结果的搜索结果页的相互作用。实验结果显示新的考虑垂直结果的点击模型（Vertical-aware Click Model, VCM）能够比已有的模型更好的理解联合搜索的用户点击行为，在对数似然和困惑度上都变现的更好。

从用户的角度出发，我们有必要对用户的偏向进行建模，显而易见，不同用户使用搜索引擎的习惯是不同的。已经有研究者对这个问题进行了研究并发表了论文。

目前大部分的点击模型都隐含的假设所有的用户是一致的，即他们在浏览搜索结果的时候行为是一致的。然而，大量的研究已经表明用户有多样化的行为模式，这可以被本文的眼动仪实验和点击日志分析证实。对所有用户一致的点击模型很难捕获到多样性的点击行为，因此我们提出了把用户的偏好结合到现有的许多点击模型中和提出了一个新的点击模型这两种方式。在大规模点击日志集合的实验结果表明加入用户偏向的点击模型一致的明显优于传统模型。

DBN，Dynamic Bayesian Network Click Model，由雅虎实验室的Olivier Chapelle和Ya Zhang提出，发表在2009年WWW会议上。

1. 检验假设：如果用户点击了一个文档，当且仅当用户检验过这个文档并认为这个文档相关。
2. 用户按顺序从上到下浏览文档，并且根据认为相关与否决定是否点击。

DBN模型有两点区别于传统的cascade model，一是因为用户点击不一定意味着对文档满意，因此DBN对感知相关性（perceived relevance）和实际相关性（actual relevance）做了区分；二是在搜索过程中，DBN不限定用户点击的文档数目。

1. 去除一段时间内query的session数比较少的query。
2. 对于不符合模型假设的：点击不是按顺序点击的，去除，或者人工交换顺序。

DBN模型参数估计采用EM算法。

DBN模型

如下假设或者叙述描述了DBN模型：

1. 用户点击某个url当且仅当用户查看了这个url并被其吸引。被吸引的概率仅依赖于这个url。
2. 与cascade模型一样，用户从上到下浏览文档，直到用户决定停下来。
3. 在用户点击并且打开了某个url之后，用户存在一定的概率对这个url满意。
4. 如果用户没有点击某个url，说明用户不满意。
5. 一旦用户对某个打开访问的url满意，用户终止搜索过程。
6. 如果用户对当前的结果不满意，以概率r用户会放弃本次搜索，1-r的概率查看下一条url。
7. 如果用户没有查看位置i，那么用户也不会查看位置i后续的位置。
8. url被吸引存在一个Beta先验概率。url被点击情况下能够满足用户需求，也存在一个Beta先验概率。

虽然上述的一些假设不符合实际的情况，一方面可以进行扩展，另一方面DBN的作者通过实验证明，这样的模型已经能够准确的解释用户的点击行为了。

用户在搜索过程中，如果发现当前的文档并不满足需求，可能存在两种情况，一是继续查看下一条文档，直到找到满意的文档为止，二是放弃本次搜索过程。如果假设用户是坚持不懈的第一种情况，DBN的参数估计可以大大的简化，简化的DBN结果如下：

其中，au表示文档吸引程度，su表示用户满意程度。α和β表示的相应的先验概率。再简化一点，如果忽略先验概率，那么文档吸引程度就是点击的比例，用户满意程度就是末次点击占总点击的比例。

A Simplified DBN Model

DBN可以对实际相关性建模，如果定义url的相关性是一个在用户查看条件下满意的概率，那么：

ru表示文档u的相关性，Si表示u满足用户需求与否，Ci是用户点击，Ei是查看，i是u展示位置。

DBN的完整参数估计算法如下图所示。

DBN参数估计 M step

DBN参数估计 E step

DBN和其他模型联系

1. examination model（属于position model的一种求解方式）是DBN的一个特例，此时，url的检验Ei是独立的，并且仅依赖于位置。这样，Si（用户点击情况下满意的概率）将变得没有意义，因为无法被推导出来。
2. cascade model也是DBN的一个特例，此时，r=1，su=1，即，用户持续浏览url直到发现一个相关文档，然后点击，并对结果满意，结束搜索。

对于position model来说，不同位置的url对于用户的吸引针对导航型或信息性的查询是应该区分对待的，原因很简单，导航型的query，CTRs随着位置降低衰减的更快。但是DBN模型的作者认为，这种衰减并不是查询类型的函数，而是排序靠前的url质量的函数。DBN模型不用区分查询类型，本身就能反映不同类型的查询。

1. 考虑带广告、查询纠错、用户翻页的情况。
2. landing page的用户行为，如停留时间等。
3. 没有点击url而满足了用户需求，如用户从摘要获取到了想要的结果。
4. 满意变量不要求是二值变量，例如对信息性查询，典型情况是，用户在每个页面上寻找信息片段，全部的信息需求被满足后才停止搜索。
5. 非线性的examination model，即用户可以前向后向跳转。
6. 解决正反馈。
7. 利用query smoothing 推导其他文档的相关性。