IR学习笔记 #10 查询相关反馈
本文最后更新于：2022年5月19日 中午
用户在检索信息时，通常会以一个简短的 query 开始，这样的查询往往得不到其最想要的结果。而用户会在得到结果后优化自己的 query，如：增删词项、重新赋权、加入布尔运算符等。
相关反馈（Relevance Feedback）的主要思想就是：在信息检索的过程中通过用户交互来优化查询，从而提高最终的检索效果。我们的目的是实现一个良好的反馈机制。
最佳查询 | Best Query
为了使反馈能让 query 真正往「更好」的方向演变，需要定义评价 query 的一个指标。通常我们在向量空间模型中评价之，因为可以较好地表达相似度。
假设我们要找一个最优查询向量 \(\vec{q}\)，它与相关文档之间的相似度最大，和不相关文档之间的相似度最小。若 \(C_r\) 表示相关文档集，\(C_{nr}\) 表示不相关文档集，我们希望找到的最优的是 \(\vec{q}\) 应当满足： \[ \begin{aligned} \vec{q}_{opt} &= argmax[Sim(\vec{q},C_r)-Sim(\vec{q},C_{nr})] \\ &=argmax(\frac{1}{|C_r|}\sum_{\vec{d}_j\in C_r}{\vec{q}\cdot \vec{d}_j}-\frac{1}{|C_{nr}|}\sum_{\vec{d}_j\in C_{nr}}{\vec{q}\cdot \vec{d}_j}) \\ &=argmax(\vec{q}\cdot \vec{a}) \end{aligned} \]
其中 \(argmax(x)\) 函数是返回使 \(x\) 最大的变量，相似度 \(Sim\) 的求法则采用余弦夹角， \(\vec{q}\) 和 \(\vec{d}\) 采用归一化后的单位向量。此外，我们令： \[ \vec{a}=\frac{1}{|C_r|}\sum_{\vec{d_j}\in{C_r}}{\vec{d_j}} - \frac{1}{|C_{nr}|}\sum_{\vec{d_j}\in{C_{nr}}}{\vec{d_j}} \] 若使 \(\vec{q}\cdot{\vec{a}}\) 最大，\(\vec{q}\) 需要与 \(\vec{a}\) 平行，且 \(\vec{q}\) 为单位向量，故有最佳查询： \[ \vec{q}_{opt}=\frac{1}{|C_r|}\sum_{\vec{d_j}\in{C_r}}{\vec{d_j}} - \frac{1}{|C_{nr}|}\sum_{\vec{d_j}\in{C_{nr}}}{\vec{d_j}} \] 这就是说，最优的查询向量等于相关文档的质心向量和不相关文档的质心向量的差，相当于是最接近相关文档，同时最远离不相关文档。
查询优化 | Query Modification
然而，即使有了上述最佳查询的表示方法，也无法直接求出来——因为检索本来的目的就是要找相关文档，而所有的相关文档事先是未知的。
Rocchio 提出在真实的检索情景中，我们可以利用已检索到的部分相关文档 \(D_r\) 和不相关文档 \(D_{nr}\)，逐步修改原始的查询向量： \[ \vec{q}_m=\alpha\vec{q}_0 + \beta \frac{1}{|D_r|}\sum_{\vec{d_j}\in{D_r}}{\vec{d_j}} - \gamma\frac{1}{|D_{nr}|}\sum_{\vec{d_j}\in{D_{nr}}}{\vec{d_j}} \] 修改后的新查询从 \(\vec{q}_{0}\) 开始，向着相关文档的质心向量靠近了一段距离，而同时又与不相关文档的质心向量远离了一段距离——更加接近最优查询了。通过不断迭代，可以观察到查询效果确实有显著的提升。
查询反馈 | Relevance Feedback
通常情况下，反馈可分为以下两种：
- 真实相关反馈：搜索引擎返回结果，用户提供反馈，搜索引擎根据反馈返回更好的结果。
- 假设相关反馈：搜索引擎得到结果但不返回，根据结果自动优化 query，根据优化后的 query 返回「更好」的结果。
点击流数据 | Clickthrough Data
在真实相关反馈中，用户往往不愿意主动提供反馈信息（如标记相关或不相关文档），于是搜索引擎收集用户的间接反馈。
而点击流数据则是这个领域最常用的一种反馈，可以在不干扰用户的情况下大量收集（此外还有一种补充用户行为信息的方法是眼动追踪）。
同一搜索结果中，用户进行点击浏览的结果被认为是相关的，或者说是「用户更偏好的」。如果用户查看了每个搜索引擎下面显示的文本短摘要后，决定跳过它并点击在排序中低于它的结果，就可以说用户相对更喜欢这个被点击的结果。
局部上下文分析 | Local Context Analysis
在假设相关反馈中，还可分为两种基本方法：
- 局部分析（Local Analysis）：从结果集合排名靠前的文档中产生反馈信息。
- 全局分析（Global Analysis）：从外部资源产生反馈信息，如同义词典（用于扩充查询）。
同义词典构建的代价十分昂贵，通常考虑用上下文和短语结构进行分析获得。而如果把这个思想用于局部分析，则诞生了 LCA 方法：一种聚焦于从反馈结果中筛选出与 query 相关性更高的 term，再用这些 term 扩展 query 重新检索的方法。
大致的步骤如下：
- 找到与这个 query 检索结果排名靠前的文章，使用一个固定长度（如 300 个词）的滑动窗口，来划分段落。引入段落是为了最小化冗长文档中的无关内容。
- 对段落进行检索排序，找到结果排名靠前的段落，对其使用语义分析和文本分词、词性标注技术找到名词项。名词在搜索引擎中往往被视为最重要的词。
- 统计名词项的出现次数，以及出现时离 query 的距离，通过特殊的加权方法来选择出候选 term。
- 将排名靠前的几个候选 term 加入到原始 query 中，进行新的查询。
排序学习 | Learning to Rank
相关反馈信息，包括前述文章中提到的相关度、重要度，其实只是 IR 中许多因子的冰山一角。实际中可能还有若干、数十个因子，这些因子最后会加权构成一个统一的指标函数。
这个指标函数的输入是数据集（包括查询和文档集），输出是最终检索出的 ranklist。如何构造这样一个复杂的函数呢？
对于构造函数，人们最原始的想法通常是拟合所有 <query, ranklist> 点，但是这显然不适用于这种规模的问题。
机器学习的使用 | Machine learning for IR ranking
过去的 IR 系统较少用到机器学习，是因为缺乏训练集，特别是在真实世界中得到的数据集（而不是学术论文中），因为很难收集到用户检索的真实需求和对返回文档的相关反馈。
此外，过去的 IR 系统往往只使用少量的特征（feature），如词项频率、逆文档频率、term 出现的位置等。
少量的特征带来的是构造函数的便利。而随着现在网络的发展、算力的提升，大家开始关注数据集中大量的特征，并尝试用机器学习使用这些特征。
定义 loss function \(l(r_a,r_b)\)，其中 \(r_a\) 是基于用户反馈得到的「标准排名」，\(r_b\) 是通过拟合的排序函数 F 计算出的「模拟排名」。我们要寻找到一个 F 使得损失最小——这就是机器学习的目标。
Example - title & body
下面以一个例子说明机器学习在 IR 中的应用。考虑查询中的 term 出现在文档的 title (标题) 或 body (正文) 中对返回结果排名的影响。
为此，我们需要对 term 出现的四种情况分别打分： \[ \operatorname{score}\left(d, q\right)=g {s_{t}}\left(d, q\right)+(1-g) s_{b}\left(d, q\right) \] 其中 \(s_t\) 和 \(s_b\) 函数是关于 term 是否存在于文档对应位置的布尔函数（0/1），故 score 的结果只有 0, g, 1-g, 1 四种。我们要求的就是权重 g。
在第 j 个查询中，我们对检索结果中的文档 i 定义如下损失函数： \[ \varepsilon\left(g, \Phi_{j}\right)=\left(r\left(d_{i}, q_{j}\right)-\operatorname{score}\left(d_{i}, q_{j}\right)\right)^{2} \] 这里简单的定义 r 函数是关于二者是否相关的布尔函数（0/1），使用平方误差是为了让结果更连续。
在训练集中，我们标注出所有结果的 \(s_t\) 、 \(s_b\) 和 r 函数的取值——八种情况，并分别统计其次数。例如，\(n_{01r}\) 表示 \(s_t=0,s_b=1\) 且相关的例子，\(n_{01n}\) 表示 \(s_t=0,s_b=1\) 且不相关的例子，其平方误差之和为： \[ [1-(1-g)]^{2} n_{01 r}+[0-(1-g)]^{2} n_{01 n} \] 同样的，我们对其他三组也进行计算后相加，化简可得： \[ \left(n_{01 r}+n_{10 n}\right) g^{2}+\left(n_{10 r}+n_{01 n}\right)(1-g)^{2}+n_{00 r}+n_{11 n} \] 要求这个函数的极小值，只需用对关于 g 的导数求零点即可。如果考虑更多的变量，则需要求偏导，再用拉格朗日常数法等数值分析方法。