CMU 11642 Search Engine 基于 Feature 的结果获取

LeToR

作者 QIFAN 日期 2017-03-24
CMU 11642 Search Engine 基于 Feature 的结果获取

Feature-based 方法介绍

之前的 Boolean , BM25 ,Indri 都是直接根据公式计算排名,到了 expansion query 有了一点学习的意味。Learning to Rank 就是结合多个种类的依据(evidence)来进行模型学习。把学习中的任何一种依据都看成是一个 feature 。比如说 $BM25_{title}$ ,$PageRank$ 都可以作为 feature 。训练方式和其他机器学习方式类似,假设要学习的值为 Y ,feature 向量(组)为 X ,w 代表向量的比重,那 1)通过训练集学习出模型 $Y=f(X;w)$ ; 2)通过这个模型算出测试集的 Y 。

举一个简单的线性例子:
$Score(q,d)=\sum{w_i}*f_i(q,d)=f(x,w)$
$q$ query , $d$ document, $w$ weight, $x$ feature vector

LeToR

LeToR (learning to rank)是监督性学习的一种,可以用来做分类,做回归。用于排序时,通常通过计算不同排序的分数来找到最好的排序,我们不 care 具体分数,只关心顺序。

之前我们学习了各种各样的信息获取模型用于文件匹配,而 LeToR 的过程是多层级的模型叠加,它并不是“找”文件,而是“排序”文件:

  1. 精确匹配 boolean 模型(UnRankedBoolean)用于产生初始文件集
  2. 最佳匹配获取模型(BM25,Indri)用于排序并获取前 $n_1$ 个结果
  3. 学习模型(Expansion Query)用于重新对前 $n_1$ 个文件排序,再获取前 $n_2$ 个。

这个过程中文本集的规模像一个倒立的金字塔一样(如下图),越往下数据量越少,使用的模型也更复杂,目标也逐渐从“快速 efficient”变为“有效 effective”。
letor

LeToR 有三个主要的维度:

  • 文件表示(features)
  • 训练集的种类或风格
  • 机器学习算法

Feature

Feature 可以是任何一种可以用于排序的依据,feature 可以看成是某个 document 的表示。下面是一些例子:

feature comment
$x_{CoordinaitonMatch}$ 文档中匹配 query terms 的个数
$x_{VSM}$ 文档 d 对于查询语句 q 的空间向量分数(Vector space)
$x_{BM25}$ 文档 d 对于查询语句 q 的 BM25 分数
$x_{Indri}$ 文档 d 对于查询语句 q 的 Infri 分数
$x_{PageRank}$ 文档 d 的 PageRank

机器学习时训练集中的文件排序由标准化后的某个 feature 的值表示,每一个 document 用的 feature 都可以不一样。(有点玄学)

其实就是把各种各样的 feature 丢进模型中进行训练,产生一个训练好黑箱模型,接着再

训练学习算法的三种方式

Pointwise

训练集数据单个文件 x 的分数,学习目标是用训练好的模型给每个文件生成一个分数。训练方式可以是回归(如线性回归)或者分类(如 SVM)

该方法的训练目标是文件的具体分数,但是我们的目标是得到正确的排序,只要排序正确分数并不重要。所以 Pointwise 学习的目标有点走偏,也导致这个方式效果不太好。

Pairwise

训练集数据是两两文件的相对顺序,如训练集中的某条记录是 $(\vec x_1, \vec x_2)$ ,这代表着希望文件 1 的排在文件 2 前,学习后使得模型 $h(\vec x_1) > h(\vec x_2)$ ,$h(\vec x)$ 是学习后的模型。$\vec x$ 表示某个文件的 feature 向量。

将偏好排序转变为两类学习问题:
$prefer(d_i, d_j) \to h(\vec x_i) > h(\vec x_j) \to (w^T\vec x_i) > (w^T\vec x_j) \to w^T(\vec x_i - \vec x_j) > 0 \to h(\vec x_i - \vec x_j) > 0$

训练目标是最小化归类错误的文件对数量,这与训练初衷(得到正确的 ranking )还是有些出入。

不足:

  • 相关文件对和不相关文件对数量一样的 query 会主导训练集,因为这种 query 产生的训练对最多。
  • 对噪音类敏感,因为一个噪音记录会产生很多训练对。
  • Pointwise 的毛病依然存在,letor 的初衷是得到正确的排序,而不仅仅是相对位置。

Listwise

训练集是文件列表(list)的排序。

  • 训练数据:$x_1 > x_2 > … > x_n$
  • 学习模型:$h(x_1) > h(x_2) > …$
    某个 ranking 的值可以是某个 metric ,如 NDCG@N 或者 MAP@N 。训练目标就是最大化这个 metric 的值。这与 letor 的目标相符。

不足:
有些 metric 如 NDCG@N 并不是连续的,算法的优化也困难。

总结

  • Pointwise ,以 “文件分数” 为训练目标,目标太跑偏。最弱。
  • Pairwise 以最大化正确文件对数量为目标,目标跑偏,很容易实现
  • Listwise 以最大化 metric 为目标,很难优化。

Benchmark 数据集

  • LeToR Collection
    Microsoft 用现存的公开数据生成的,包括了 field 相关的 feature (tf ,idf 等),文件层面的 feature (PageRank ,inlink 数量等)
  • The Yahoo Challenge! Dataset
  • Microsoft Learning to Rank Dataset