陌路茶色/

Learning to Rank for Information Retrieval and Natural Language Processing——Learning for Ranking Creation

本文为李航老师写的Learning to Rank for Information Retrieval and Natural Language Processing这本书(第二版)第二章以及第四章的阅读笔记。

LEARNING TASK

TRAINING AND TESTING

先给出如下定义:
屏幕快照 2019-10-29 下午2.45.15.png
训练过程如下,训练集为$\{q_1,q_2,...,q_m\}$和对应的文档集$\{D_1,D_2,...,D_m\}$,以及标注集$\{Y_1,Y_2,...,Y_m\}$,其中$D_i=\{d_{i,1},d_{i,2},...,d_{i,n_1}\}$:
屏幕快照 2019-10-29 下午2.49.22.png
以$q_1$为例,对应的文档为$d_{1,1},...d_{1,n_1}$,第一步是rank(人工为这些文档排序,打等级)得到每个文档对应的等级$y_{1,1},y_{1,2},...,y_{1,n_1}$,其中$y_{i,j}$表示文档$d_{i,j}$和查询$q_i$的相关性等级,越相关越大,然后对$q_1$对应的这些文档提取特征得到$x_{1,1},...,x_{1,n_1}$,这样特征和对应的排序得到,然后去学习排序函数$f(x)$【训练集怎么学习排序函数见后面】,测试过程如下:
屏幕快照 2019-10-29 下午3.02.55.png

TRAINING DATA CREATION

如何生成高质量的训练数据对学习ranking creation是至关重要的,一般有两种方法来创建训练数据,第一种是人工标注,首先一系列的query被随机的从搜索系统中被选择出来,然后搜索系统会有对应query的文档集,人工评判这些query-document对,一般包含五个等级:perfect, excellent, good, fair, bad。当然这种标注如果是被多次标注,然后采用多数表决效果是最好的,但是人工标注成本太高,因此常常一个标注只有一个人,这样如果提高人工标注的质量成为学习排序的一个重要因素。

另外一种生成训练集的方式是从点击率中得到,搜索系统返回给用户的文档集被用户点击的文档相应对应着和用户查询query比较高的相关性。

这两种标注即有缺点也有优点,人类标注容易出错,因为标注者并不是query本人,因此不知道那些文档对query用户来说重要,且人工标注成本太高。相反,点击率的方法成本低,同时代表用户真实的判断,但是其缺点是点击率的数据存在噪音,而且只适合频率比较高的query。

FEATURE CONSTRUCTION

ranking 模型$f(q,d)$被定为为$f(x)$,其中$x$表示为基于$q$和$d$的特征向量,也就是说ranking模型是一个基于特征的模型,这就是为什么ranking模型有泛化能力的原因。在机器学习任务中,模型高质量的表现依赖于被使用的特征的有效性,因此如何定义有用的特征成为一个至关重要的问题。

在web搜索中,BM25和PageRank被广泛的作为排序特征使用,实际上这两个特征也可以被使用在无监督模型中,query $q$和文档 $d$的BM25被定义为:
屏幕快照 2019-10-29 下午3.27.56.png
关于BM25请参考我之前写过的一篇文章Multi-Dimensional, Phrase-Based Summarization in Text Cubes中有提到过,就是TF的优化,文章越长,词频(tf)必须比较大才能使BM25比较大,相反,文章比较短,则词频(tf)不需要很大,就能使BM25比较大,这里的BM25指的是TF的优化,而上述BM25(q,d)是判断文档的重要性。

网页$d$的PageRank定义为:
屏幕快照 2019-10-29 下午4.04.07.png
$P(d)$表示访问页面$d$的概率,$P(d_i)$表示访问页面$d_i$的概率,$M(d)$是链接到页面d的页面集合,$L(d_i)$表示页面$d_i$的出度(外链)个数,$N$表示图中节点个数,$\alpha $表示权重。

PageRank的直观理解:如何判断一篇论文的价值,被其他论文引述的次数越多就越重要,如果被权威的论文引用,那么该论文也很重要。PageRank就是借鉴于这一思路,相当于每个到该页面的链接都是对该页面的一次投票,被链接的越多,就意味着被其他网站投票越多。
深入探讨PageRank(一):PageRank算法原理入门

EVALUATION

评估ranking模型的表现是比较模型输出的ranking列表和真实的列表的对比,有NDCG (Normalized Discounted Cumulative Gain), DCG (Discounted Cumulative Gain) , MAP (Mean Average Precision) , WTA (Winners Take All), MRR (Mean Reciprocal Rank), Kendall’s Tau这些方法。

给定一个query $q_i$,和其相关的文档集$D_i$,假设$π_i$是$D_i$排序列表(模型预测),$y_i$是$D_i$的标签集(标注真实集),DCG用来测量排序列表的好坏,对于$q_i$查询在位置$k$的DCG被定位为:
屏幕快照 2019-10-29 下午4.56.21.png
其中$G(\cdot)$表示收益函数,$D(\cdot)$表示位置折扣函数,$\pi_i(j)$表示在$\pi_i$中$d_{i,j}$的位置,即DCG表示前k个位置的累计收益。NDCG表示正则化的DCG:
屏幕快照 2019-10-29 下午5.02.15.png
$DCG_{max}(k)$表示正则化因子,是最好的排序$\pi_i^*$对应的值,也就是说最好的排序$\pi_i^*$对应的NDCG值为1。

收益函数$G(\cdot)$被定义为如下:
屏幕快照 2019-10-29 下午5.05.19.png
其中$y_{i,j}$表示的是ranking列表$\pi_i$中$d_{i,j}$对应的标签$y_{i,j}$。收益函数的直观理解是$y_{i,j}$越大(越相关),那么收益越大,而且是成指数增加。
折扣函数$D(\cdot)$被定义为:
屏幕快照 2019-10-29 下午5.15.15.png
其中$\pi_i(j)$表示文档$d_{i,j}$的在ranking列表中的位置,表示文档越靠前,折扣函数越小。

这样对于查询$q_i$在位置k的DCG以及NDCG的表示如下:
屏幕快照 2019-10-29 下午5.27.06.png
对于查询$q_i$在整个ranking列表的DCG和NDCG为:
屏幕快照 2019-10-29 下午5.29.01.png

MAP在IR中被广泛使用作为评估方法,假定相关分数只有两个等级:1或者0,给定一个query $q_i$,和相关的文档$D_i$,以及模型预测的ranking列表$\pi_i$,$D_i$对应的真实标签$y_i$(该标签只有两个值),对于查询$q_i$的Average Precision被定义为:
屏幕快照 2019-10-29 下午5.38.04.png
其中$P(j)$被定义为:
屏幕快照 2019-10-29 下午5.43.34.png
$\pi_i(j)$表示在$\pi_i$中文档$d_{i,j}$的位置,$P(j)$表示的是到文档$d_{i,j}$位置为止的正确率。

LEARNING APPROACHES

学习rank,尤其是学习ranking creation已经被人们深入研究,这些提出的方法可以被归纳为pointwise方法,pairwise方法,listwise方法。
pointwise方法和pairwise方法将ranking问题转为分类,回归,有序分类(ordinal classification)问题,listwise方法在学习中将ranking列表作为一个实例,并基于ranking列表来学习ranking模型,主要的不同在于它们采用的损失函数。
listwise方法和pairwise方法通常要比pointwise方法表现要好, 最近Yahoo Learning to Rank Challenge, LambdaMART都属于listwise方法,其实现了最好的表现。
也可以按照使用的方法进行归类,下表总结了存在的方法:
屏幕快照 2019-10-29 下午6.01.44.png

POINTWISE APPROACH

本文最前面提到了训练过程(第二张图),其中对每个query对应的文档特征提取后得到$\{(x_{i,1},y_{i,1}),...,(x_{i,n_1},y_{i,n_1})\}$,pointwise方法将其全部混在一起作为分类,回归,或者是有序分类问题(组的结构被忽略,也就是一个query $q_i$对应$n_1$个实例),总结如下(具体方法会在后面章节详述):
屏幕快照 2019-10-29 下午6.26.27.png

PAIRWISE APPROACH

pairwise 方法将排序问题转为成对分类或成对回归问题,同pointwise方法,训练集组的结构被忽略,总结如下(具体方法会在后面章节详述):
屏幕快照 2019-10-29 下午6.34.24.png
从上图可以看出,pairwise方法是在pointwise的基础上,将损失函数改为成对分类结果的差。

LISTWISE APPROACH

这里一个query $q_i$作为一个实例,如下所示:
屏幕快照 2019-10-29 下午6.48.04.png

Methods

PRANK(Perceptron Ranking)

在线有序分类算法,pointwise方法,该方法是基于感知机的,将特征映射到一个有很多超平面的空间中,每一个超平面将特征分割成两个等级,如下图所示:
屏幕快照 2019-11-01 下午5.02.58.png

给定$X \subseteq \Re^n $和$Y=\{1,2,...,l\}$,当满足$wx-b_{r-1}>=0$且$wx-b_r<0$,则模型预测$y=r$,记做:
屏幕快照 2019-11-01 下午5.01.33.png
其中$b_r \in \Re , (r=1,...,l)$,且偏差满足$b_1 \leqslant ... \leqslant b_{l}$
PRank算法如下所示:
屏幕快照 2019-11-01 下午5.03.50.png

OC SVM

OC SVM假定超平面以相同的大空白将任意两个相连的等级分隔开(不但要分正确,还要找到最优的分割平面),如下图所示:
屏幕快照 2019-11-01 下午5.15.06.png
对应的要解决的问题是:
屏幕快照 2019-11-01 下午5.16.17.png

留下一条评论

暂无评论