Learn To Rank是一种学习方法,通过训练模型来解决排序的问题,在信息检索,NLP,Data Mining领域有着很多的应用。

排序问题

在信息检索中,给定一个query,搜索引擎会召回(粗筛选)一系列相关的Documents(term匹配,keyword匹配,semantic匹配),之后对这些Documents排序,最后输出Top N的Documents。

排序问题即使用一个模型 f(q,d)来对该query下的documents进行排序,这个模型可以是人工设定一些参数的模型,也可以是用机器学习算法自动训练出来的模型。在Web Search领域,因为在Web Search 中,有很多信息可以用来确定query-doc pair的相关性,而另一方面,由于大量的搜索日志的存在,可以将用户的点击行为日志作为training data,使得通过机器学习自动得到排序模型成为可能。

排序问题的核心在于找出query和doc之间的相关性,对相关性进行排序。

learn to rank 是监督学习,分为train和test两个阶段:

image-20200214232441639

training data set 的生成

由于learning to rank是监督学习,因此对每一条记录都需要label。通常feature vector容易获取,而label实际上反映了query-doc pair的真实相关程度。通常有两种label的获取方式:

  • 人工标注,即对抽样出来作为training data的query-doc pair人为地进行相关程度的判断和标注,一般标注的相关程度分为5档:perfect,excellent,good,fair,bad。
    • 例如,query=“Microsoft”。document为Microsoft的官网是perfect;介绍Microsoft的wikipedia则是excellent;一篇将Microsoft作为其主要话题的网页则是good;一篇只是提到了Microsoft这个词的网页则是fair,而一篇跟Microsoft毫不相关的网页则是bad。人工标注的方法可以通过多人同时进行,最后以类似投票表决的方式决定一个query-doc pair的相关程度,这样可以相对减少各个人的观点不同带来的误差。
  • 通过搜索日志获取。搜索日志记录了人们在实际生活中的搜索行为和相应的点击行为,点击行为隐含了query-doc pair的相关性,所以可以被用来作为query-doc pair的相关程度的判断。一种最简单的方法就是利用同一个query下,不同doc的点击数的多少来作为它们相关程度的大小。

通过搜索日志的方式获取的方法存在一些偏差,即用户偏向于点击位置靠前的doc,即便这个doc并不相关或者相关性不高。因此有一些tricky和general的方法用来处理这种“position bias”的偏差:

  1. 当位置靠后的doc的点击数都比位置靠前的doc的点击数要高了,那么靠后的doc的相关性肯定要比靠前的doc的相关性大。
  2. Joachims等人则提出了一系列去除bias的方法,例如 Click > Skip Above, Last Click > Skip Above, Click > Earlier Click, Click > Skip Previous, Click > No Click Next等。
  3. 一个doc的点击数比另一个doc的点击数多,并不一定说明前者比后者更相关。但即使前者比后者位置靠前,两者的点击数相差5-10倍,这时候我们还是愿意相信前者更加相关。
  4. click model,根据用户的点击信息对用户真正看到的doc进行“筛选”,进而能更准确地看出用户到底看到了哪些doc,没有看到哪些doc,更准确反应点击数/展示数(即展现CTR)来确定各个doc的相关性大小。

feature 的生成

一般Learning to Rank的模型的feature分为两大类:relevance 和 importance(hotness),即query-doc pair 的相关性feature,和doc本身的热门程度的feature。两者中具有代表性的分别是 BM25 和 PageRank。

Evaluation

比较模型的输出结果,和真实结果(ground truth)之间的差异大小。用于Information Retrieval的排序衡量指标通常有:NDCG,MAP等。

NDCG

NDCG表示了从第1位doc到第k位doc的“归一化累积折扣信息增益值”,主要思想是相关性高且等级高的结果,值应该比较高。

  • 高关联度的结果比一般关联度的结果更影响最终的指标得分
  • 有高关联度的结果出现在更靠前的位置的时候,指标会越高

CG:累计增益cumulative gain

只考虑到了相关性的关联程度,没有考虑到位置的因素,是一个搜素结果相关性分数的总和。
$$
\mathrm{CG}_{\mathrm{p}}=\sum_{i=1}^{p} r e l_{i}
$$
rel表示i的相关性。

折损累计增益(DCG)

即对每一个CG的结果,除以一个折算值,目的是为了排名越靠前的结果影响力越大:
$$
\mathrm{DCG}_{\mathrm{p}}=\sum_{i=1}^{p} \frac{r e l_{i}}{\log _{2}(i+1)}=r e l_{1}+\sum_{i=2}^{p} \frac{r e l_{i}}{\log _{2}(i+1)}
$$
归一化折损累计增益(NDCG)

归一化之后的折损累积增益,由于搜索的词不同,因此返回的检索数量是不同的,DCG是一个累加值,因此没法针对两个不同的结果进行比较,需要求一个归一化之后的结果:
$$
\mathrm{nDCG}_{\mathrm{p}}=\frac{D C G_{p}}{I D C G_{p}}
$$
其中IDCG是理想情况下最大的DCG:
$$
\mathrm{IDCG}_{\mathrm{p}}=\sum_{i=1}^{|R E L|} \frac{2^{r e l_{i}}-1}{\log _{2}(i+1)}
$$
即从大到小,取前p个结果组成的集合。

MAP

对每个相关文档检索出准确率平均值的算术平均值。首先对每一个query计算一个AP:
$$
A P=\frac{\sum_{j=1}^{n_{i}} P(j) \cdot y_{i, j}}{\sum_{j=1}^{n_{i}} y_{i, j}}
$$
$y_{ij}$即每个doc的label(1和0),而每个query-doc pair的P值代表了到$d_{ij}$这个doc所在的位置为止的precision:
$$
P(j)=\frac{\sum_{k: \pi_{i}(k) \leq \pi_{i}(j)} y_{i, k}}{\pi_{i}(j)}
$$
其中pi表示排序中的位置。

Formulation

通过建立一个损失函数,即经验风险函数,通过最小化这个函数来达到模型训练的目的:
$$
\hat{R}(F)=\frac{1}{m} \sum_{i=1}^{m} L\left(F\left(\mathbf{x}_{i}\right), \mathbf{y}_{i}\right)
$$
由于上式优化函数不连续,因此我们寻求一个替代函数,通过优化次优函数得到次优解,替代方案有许多种,可以选择的方法有:

pointwise loss

平方误差:
$$
L^{\prime}(F(\mathbf{x}), \mathbf{y})=\sum_{i=1}^{n}\left(f\left(x_{i}\right)-y_{i}\right)^{2}
$$
pairwise loss

例如hinge loss,exponential loss,logistic loss等
$$
L^{\prime}(F(\mathbf{x}), \mathbf{y})=\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \phi\left(\operatorname{sign}\left(y_{i}-y_{j}\right), f\left(x_{i}\right)-f\left(x_{j}\right)\right)
$$
listwise loss
$$
L^{\prime}(F(\mathbf{x}), \mathbf{y})=\exp (-N D C G)
$$

Learn To Rank

pointwise:输入数据为单个doc以及query

pairwise:输入数据为同一个query对应的两个doc,以及query

listwise:输入数据为同一个query对应的若干doc,以及query

pointwise和pairwise方法将排序问题转化为classification,regression,ordinal classification等问题。而listwise方法则将一个ranking list作为一个instance来进行训练,其实会考虑每个query下所有doc之间的顺序关系。

这三种类型的Learning to Rank方法的具体算法一般有:

1) Pointwise: Subset Ranking, McRank, Prank, OC SVM

2) Pairwise: Ranking SVM, RankBoost, RankNet, GBRank, IR SVM, Lambda Rank, LambdaMart

3) Listwise: ListNet, ListMLE, AdaRank, SVM MAP, Soft Rank

inference

本文为学习笔记,参考如下网页:https://www.cnblogs.com/bentuwuying/p/6681943.html