1 引 言

检索结果排序算法的优劣是影响整个信息检索系统的关键因素。传统的信息检索系统主要通过建立简单的模型或规则对内容排序, 模型中的参数主要通过人工方式进行调节。为提升排序效果, 新建立的模型往往引入更多的参数, 但是人工调节模型参数的方式已经不能适应多维海量数据的变化。排序学习算法是一类基于海量数据获得训练模型的机器学习方法, 这类算法能自动调节模型的参数, 避免主观经验主义, 较大程度地提高了检索性能, 现已被广泛应用于文档检索、专家搜索、机器翻译等多个方面^[1-2]。

作为一种有监督学习, 排序学习需要在大量已标注训练数据的基础上建立模型。但实际应用中标注数据数量不足的情况导致训练模型的可靠性大大降低。尽管依靠人工标注方式可以解决标注数据不足这一问题, 然而人工方式耗时耗力, 并且标注结果具有一定的主观性, 标注质量难以控制。因此, 降低训练数据标注的复杂性并且提高数据标注的质量成为排序学习中的一个重要研究方向。

半监督学习同时利用了已标注样本的标记信息和未标注样本的先验信息, 能够在标记样本有限的情况下取得较好的学习效果。将半监督学习技术应用到排序问题中可以减少标注代价, 提高排序算法的性能。重启随机游走(Random Walk with Restart, RWR)^[3]作为一种半监督方法, 可以基于标记数据和未标记数据之间的相似度信息完成未标注数据的标注工作。因此针对排序学习中训练数据标注不足的难题, 本文提出一种基于随机游走模型的排序学习方法, 利用RWR完成训练数据的自动标注。

2 半监督排序学习的相关研究

目前已有许多半监督排序学习算法。Zhang等^[4]对于无标签数据的应用提出基于聚类的方法选择高质量的训练查询。对于有限标签的应用提出基于分类的方法。该方法利用查询特征预测给定查询的检索增益, 选择具有高性能增益的查询创建用于排序算法的伪标签。Duh等^[5]提出一个转换学习框架, 该框架基于从测试数据中产生更多的特征, 通过Boosting并入这些特征, 进而学习到对应于不同查询的排序函数。Duh等^[6]提出一种转换元算法, 关键思想是使训练过程适应于每个测试列表。根据框架的基本思想提出两种半监督排序学习方法: 特征生成方法从未标记测试数据中发现更多显著特征并在测试集上训练一个排序器; 重要性加权的方法通过重新加权训练数据以匹配每个测试列表中的统计数据。Kim等^[7]提出基于马尔科夫随机游走和图形正则化的半监督排序学习方法。主要思想是提出一种增量算法, 该算法通过将数据投影到相似矩阵的特征向量来确定特征, 并根据这些特征学习线性排序函数。此外, 有很多研究^[8-9]将协同训练算法扩展到半监督排序问题中。

半监督排序算法对于减少排序算法对标记数据的依赖性具有重大现实意义, 此类研究也逐步受到国内学者更多的关注。何海江等^[10]提出一种协同训练的多样本排序学习算法, 使用两类排序学习机在已标记数据集上构造排序函数, 由似然损失计算查询对应的两个文档排列的相似性, 为文档排列相似度低的查询贴上标签, 使排序学习机新增训练数据。高炜等^[11]针对本体提出一种半监督k-部排序学习算法, 将训练样本分成带标记和不带标记两类, 通过推进的方法优化指数亏损模型, 得到组合权值, 并通过贪心的方法得到排序特征, 由此得到排序函数。缪志高^[12]针对排序学习中标记训练数据不足的情况提出两种半监督排序学习算法: 第一种算法结合了正则化和提升两种技术, 在原有的损失函数中引入基于“光滑性假设”的正则化惩罚项, 通过理论分析得出使损失函数最小化的提升算法; 第二种算法中, 先利用标签传播算法给无标记样例附上标签, 然后在增加的数据集上运行正则化形式的Listwise方法。张新^[13]提出基于分类的查询过滤方法和基于聚类的直推学习方法, 利用这两种方法筛选高质量的查询并应用于半监督学习算法中。奚凌然等^[14]提出一种结合标签传播的排序学习算法, 其基本思想是利用标签传播完成训练数据的自动标注, 再基于得到的训练集利用RankingSVM实现排序学习。

受以上工作的启发, 本文提出一种基于重启随机游走模型的半监督排序学习算法。该算法针对每个查询独立进行, 首先根据查询下文档间的相似信息构造随机游走图, 利用RWR完成未标记文档标签的预测, 再基于得到的训练集利用ListNet实现排序学习。在OHSUMED数据集上的实验表明本文所提出算法在解决排序学习训练数据标注不足问题上的有效性。

3 相关工作

3.1 排序学习模型

排序学习是指在处理排序问题时利用机器学习训练模型的方法。根据不同的应用场景和损失函数, 文献[15-16]将排序学习算法分为Pointwise、Pairwise和Listwise三个类别。ListNet^[16]是一种基于Listwise的经典排序算法。在ListNet中, 其训练集描述如下: 训练集中有若干个查询$Q=\{{{q}^{(1)}},{{q}^{(2)}},\cdots ,{{q}^{(m)}}\}$, 每个查询${{q}^{(i)}}$都与一个文档列表${{d}^{(i)}}=(d_{1}^{(i)},d_{2}^{(i)},\cdots ,d_{{{n}^{(i)}}}^{(i)})$相关联, $d_{j}^{(i)}$是查询${{q}^{(i)}}$下的第j个文档。每个列表文档${{d}^{(i)}}$与得分列表${{y}^{(i)}}=(y_{1}^{(i)},y_{2}^{(i)},\cdots ,y_{{{n}^{(i)}}}^{(i)})$相关联, 其中$y_{j}^{(i)}$表示文档$d_{j}^{(i)}$与查询${{q}^{(i)}}$的相关度。每个查询-文档对$({{q}^{(i)}},d_{j}^{(i)})$都用特征向量$x_{j}^{(i)}$表示。这样可构造出一个训练样本${{T}^{(i)}}=\{{{x}^{(i)}},{{y}^{(i)}}\}$, 所有的训练样本都按照此方法构造。

根据训练样例创建一个打分函数f : 对每个特征向量$x_{j}^{(i)}$(对应文档$d_{j}^{(i)}$), 其输出一个得分$f(x_{j}^{(i)})$。当该打分函数的打分结果与人工标注的理想结果最接近时, 该函数最优, 以下是用K-L距离定义的损失函数^[16]:

$L(y,z)=-\sum\limits_{\forall g\in G}{{{p}_{y}}(g)}\log ({{p}_{z}}(g))$ (1)

其中, G是文档所有可能排列的集合, ${{p}_{y}}(g)$和${{p}_{z}}(g)$分别是由打分函数f和人工标注的理想函数得到的排列的概率分布。给定查询${{q}^{(i)}}$和它的相关特征向量集合$\{{{x}^{(i)}}\}_{j=1}^{{{n}^{(i)}}}$, 在Plackett-Luce中, 由打分函数f得出的序列π的概率分布^[16]为:

${{p}_{f}}(\pi )=\prod\limits_{j=1}^{{{n}^{(i)}}}{\frac{\Phi (s_{\pi }^{(i)}(j))}{\sum\limits_{k=j}^{{{n}^{(i)}}}{\Phi (s_{\pi }^{(i)}(k))}}}$ (2)

其中, $s_{\pi }^{(i)}(j)$是序列π中排在第j位文档的相关性得分, 由函数f给出。$\Phi $是变形函数。通过使用梯度下降算法能使得上述损失函数达到最小, 从而得到一个最优打分函数。根据得到的排序模型能计算查询下每个文档的得分, 并输出按得分大小排序的文档序列。

3.2 重启随机游走模型

重启随机游走是一种特殊类型的随机游走^[17]。该模型包括生成随机游走图、在图上随机游走两个部分。

(1) 随机游走图的生成

重启随机游走构建图的基本思路是: 将训练集合D中的每个训练数据$d\in D$映射为图中的一个点, 根据两点之间的相关程度决定是否用边将两点相连。为方便求解, 一般将图构建成完全图, 将两点之间的相似度作为边的权重。当两点之间的相似度很小或者为0时, 节点之间边的权重做零值处理。

假设加权图用$G=(V,E)$表示, V是图G中的节点集合, E是图G中边的集合, 其中节点的个数为n。边权重使用高斯核函数计算, 公式如下:

$W(i,j)=\exp (-\frac{d_{ij}^{2}}{{{\sigma }^{2}}})$ (3)

其中, $\sigma $是个参数变量, 经验设定$\sigma =$ $\sum\nolimits_{i\ne j}{||{{x}_{i}}-{{x}_{j}}||/[n(n-1)]}$。${{d}_{ij}}$为两个图像节点之间的欧氏距离, 表示为:

$d_{ij}^{2}=\sum\limits_{t=1}^{k}{{{(x_{i}^{t}-x_{j}^{t})}^{2}}}$ (4)

(2) 随机游走过程

在使用重启随机游走算法之前, 要先根据权重矩阵计算图G的概率转移矩阵P^[18]:

$P(i,j)=\left\{ \begin{matrix} \frac{W(i,j)}{\sum\limits_{t=1}^{n}{W(i,t)}}\ \ \ \ \ ({{V}_{i}},{{V}_{j}})\in G \\ \ 0\ \ \ \ ({{V}_{i}},{{V}_{j}})\notin G\ \\\end{matrix} \right.$ (5)

P(i, j)表示从顶点${{V}_{i}}$到顶点${{V}_{\text{j}}}$的转移概率。公式(5)可解释为对于顶点${{V}_{i}}$, 在它所有的邻居节点中, 如果一个顶点与顶点${{V}_{i}}$的相似性越小, 则游走到该节点的概率越低。概率转移矩阵还可以表示为$P={{D}^{-1}}W$,其中${{d}_{i}}=\sum\limits_{j}{W(i,j)},$表示节点${{V}_{i}}$的度, D=diag (d₁,d₂,…,d_n)。

随机游走过程用以下函数^[18]表示:

${{p}^{(t+1)}}(j)=(1-\alpha )\sum\limits_{i=1}^{n}{{{p}^{(t)}}}(i)P(i,j)+\alpha {{e}_{j}}$ (6)

$\alpha $称为跳转概率, 是固定参数, 满足$0\le \alpha \le 1$。e称为有偏分布, 是一个概率分布函数, 满足${{e}_{j}}$≥0, $\sum\nolimits_{j}{{{e}_{j}}}=1$。迭代开始时, ${{p}^{(0)}}(j)={{e}_{j}}$。公式(6)能在有限步内收敛, 达到稳态值。

4 基于重启随机游走模型的排序学习方法

ListNet方法中构造的训练样本形式为${{T}^{(i)}}=\{{{x}^{(i)}},{{y}^{(i)}}\}$, 其中${{x}^{(i)}}$是与查询${{q}^{(i)}}$相关的文档的特征向量序列, ${{y}^{(i)}}$是文档的得分序列。为了得到该形式的训练集, 首先需要对查询${{q}^{(i)}}$下的${{n}^{(i)}}$个文档进行相关性标注, 即得到${{y}^{(i)}}$序列的具体值, 之后可以用ListNet算法进行排序学习。在由人工标注相关度时, 对于某个查询${{q}^{(i)}}$, 需要人工标出与该查询相关的文档。对于某个查询, 可能相关文档众多, 用户查询也多种多样, 训练数据全部依靠人工标注不易实现。

假设训练集中有若干已标注文档和若干未标注文档, 半监督学习可以利用已标注的文档自动完成未标注文档的相关度标注, 克服人工标注的缺陷。重启随机游走模型作为一种半监督学习技术有着广泛的应用^[19-20]。Wang等^[19]利用随机游走给图像进行标签的标注。Szummer 等^[20]在NIPS会议上提出使用随机游走处理部分标签数据的问题。因此, 本文将重启随机游走(RWR)模型应用于排序问题, 提出一种基于RWR的半监督排序学习算法。算法流程如图1所示。

显示原图| 下载原图ZIP| 生成PPT

图1   基于RWR的半监督排序算法流程

   

构造随机游走图时, 图中的每个点对应一个文档, 边的权重代表文档之间的相似性。实际上, 给文档标注相关性得分是一个单标记问题, 即每个文档只对应一个分数值, 但使用随机游走模型时将该问题看做多标记问题处理。在使用公式(6)时, ${{p}^{(t+1)}}(j)$是一个概率分布, 表示在(t+1)次迭代时图中的顶点${{V}_{j}}$对应的标签概率分布, 当游走过程归于稳态时, 顶点的稳态概率分布中最大的概率值对应的分数即为给文档标注的分数。另外, 在迭代开始时, ${{e}_{j}}$是一个概率向量, 若已知节点${{V}_{j}}$标注了某个分数值, 该分数值对应的数值为1, 向量中的其他元素都为0。若节点${{V}_{j}}$的相关分数值未知, 将该向量的每个元素赋值为1/h, h是向量中包含的元素个数, 即不同的相关度个数。若每个查询下的文档都被标注为很相关、部分相关、不相关三种不同的相关度, 对于未标注的顶点${{V}_{j}}$来说, ${{e}_{j}}=\left( \frac{1}{3},\frac{1}{3},\frac{1}{3} \right)$。根据文献[21]可知, 本文建立的重启随机游走模型一定能达到最终的收敛状态, 即所有节点的标签不再随着迭代发生变化。当该模型达到收敛时, 所有未标注文档的相关度得到了标注, 可以作为ListNet的训练数据。当输入测试数据时, 利用得到的排序模型可以计算出文档与查询的相关度大小, 并输出按分数大小排序的文档序列。

由于ListNet是将每个查询下的所有文档列表作为一个训练样例, 每个文档的得分都是依赖具体查询而言的, 所以标注过程也要针对每个查询独立进行。例如训练集$Q=\{{{q}^{(1)}},{{q}^{(2)}},\cdots ,{{q}^{(m)}}\}$中包含m个查询, 则需要构建m个随机游走图, 执行m次重启随机游走算法。本文算法针对每个查询完成标注工作, 这也要求每个查询下都有已经标注好的文档。另外, 由于随机游走模型中所有未标注节点的分数值都来自已经标注的节点, 因此, 为保证标注过程中所有可能的分数值都出现, 在实际应用中需要确保每个查询下的已标注节点覆盖所有可能的相关性分数值。

在信息检索的实际应用中, 影响查询与文档相关度的因素非常多。若某查询下的两个文档非常相似, 其中一个文档与该查询的相关程度较大, 理论上另一文档与该查询也应有较大的相关度, 这两个文档应该具有相似的相关度标签; 相反地, 若某查询下的两个文档相似度很小, 其中一个文档与该查询密切相关, 另一文档与该查询的相关程度应该较小, 这两个文档的相关度标签差异较大。基于此, 在本文构造的随机游走图中顶点之间根据相似度大小进行跳转, 从而完成标签信息的传递, 使得相似度大的文档标注有相似的标签。另外RWR模型作为一种半监督学习方法自动完成训练数据的标注, 使得数据标注不受人的主观影响, 标注质量较好控制。相比于人工标注训练数据, 该方法所需的时间、人力成本远远降低, 效率大大提高。本文提出的方法对于降低排序学习对标记数据集的依赖性、提高排序学习器的泛化性能具有重要的意义。

5 实 验

5.1 数据集

本文基于微软亚研究院的LETOR 3.0^[22]公开数据集OHSUMED^[23]①(①https://onedrive.live.com/?authkey=%21ACnoZZSZVfHPJd0&id=8FEADC23D838BDA8%21107&cid=8FEADC23D838BDA8.)验证算法的性能。该数据集是从在线医学数据信息库Medline中提取出来的, 其中包括106个查询, 共有16 140个查询-文档对, 平均每个查询有150个文档。查询下文档的相关度分为三个等级: 完全相关、部分相关、不相关, 分别用2、1、0来标注。OHSUMED中的文档被表示成特征向量的形式, 每个文档包含45维特征, 这些特征包括TF-IDF、HITS、PageRank等。

当文档的某一特征值缺失时, OHSUMED中的QueryLevelNorm利用该查询下所有文档在该特征上的最小值替代空值, 并且为方便计算, 将数值进行查询级别的归一化处理, 数据格式如表1所示。

5.2 实验方案及结果分析

(1) 随机游走模型的标注准确率验证

本实验直接采用QueryLevelNorm数据集验证随机游走模型的标签预测性能。OHSUMED数据集原本是为全监督学习设计的, 这里为了模拟半监督学习的情形, 随机选取比例为p的文档作为训练样本, 剩余(1-p)的文档作为测试样本, 设置测试文档的标记完全未知, 基于训练集预测测试文档与对应查询的相关度。

利用重启动随机游走模型标注阶段需要针对每个查询单独进行, 即分别对106个查询下的文档划分训练集和测试集, 最终使用随机游走模型完成文档的标注工作。因为RWR模型中所有未标注节点的标签都来自于初始已标注节点, 因此为保证传播过程中所有可能的标签都会出现, 本文在实验中限定每个标签在训练样本中都至少有一个实例。比如本文数据集的标签是0、1、2, 限定训练样本的相关度要覆盖这三个取值。

随机游走模型通过已标注的节点预测未标注节点的标签, 一般来说, 训练样本所占比例越大, 标注的结果准确率越高; 另一方面, 利用随机游走模型进行半监督学习是为了减少人工标注的工作量, 因此当标注准确率满足可用性条件时, 训练样本所占比例越小, 人工标注的工作量越小。为确定合适的训练样本比例p, 本文选择6种不同训练样本所占比例的情况进行实验, 即p为10%, 20%, 30%, 40%, 50%, 60%。

为减少随机因素的影响, 在每个查询上重复200次独立实验, 实验结果以均值±方差(avg±std)的形式输出。106个查询均匀地存放于S1、S2、S3、S4、S5这5个文件中, 表2展示了每个文件中查询的平均标注准确率与训练样本所占比例p的关系。

从表2可知, 随着训练样本比例的增加, 利用RWR得到的标注结果准确率逐渐增加。且各结果之间的方差较小, 说明RWR半监督学习的效率受样本数据的影响较小。当p=40%时, 标注准确率达到80%以上。当p=50%时, 标注准确率超过90%。当p=60%时, 标注准确率较p=50%时的准确率有所提升, 但需求的人工标注工作量增加。一般认为准确率达到90%即达到可用性要求, 因此将p=50%时的半监督学习结果作为结合随机游走模型排序学习方法的训练数据。

(2) 不同排序学习算法的排序性能对比

在排序学习阶段, 将上述公开数据集中人工标注好的数据作为基准训练数据。作为一种Listwise方法, ListNet考虑了所有文档的偏序关系, 具有更好的排序精确性, 因此选择ListNet算法作为排序学习的基础。RankNet^[24]作为一种重要的Pairwise方法考虑了同一查询下文档对的偏序关系, 其排序效果优于Pointwise, 逊于Listwise。因此, 将基于基准数据的ListNet排序结果作为本文方法的性能上限, 将基于基准数据的RankNet排序结果作为本文方法的性能下限, 本阶段将结合随机游走模型的ListNet方法与上述两种方法进行排序性能的对比。使用MAP和NDGG@n两个指标衡量排序性能。其中MAP是排序模型对目标文档的相关性的预测准确率, 衡量总体排序效果, MAP值越大, 排序效果越好; NDGG@n计算排序结果中前n个文档的评估增益值, NDGG值越大, 得到的相关序列中前n个文档的排序越准确。

为更好地评估结果, 在排序学习阶段将排序结果进行5-折交叉验证, 数据设置如表3所示。

结合RWR的ListNet算法使用p=50%时的标注结果作为训练数据, RankNet和单纯的ListNet使用基准数据作为训练数据。表4列出了RankNet、RWR+ ListNet和ListNet在MAP指标下的对比结果。可知, 结合RWR的ListNet方法在MAP上的性能值略低于RankNet方法和ListNet方法, 其中比ListNet低6.6%, 比RankNet下的MAP值低3.1%。根据RWR+ListNet得到的排序结果平均准确率与其他两种方法得到的排序结果准确率存在较小差距。

图2和图3分别是p=40%和p=50%时三种排序学习算法在NDGG@n指标上的性能对比。横轴是NDGG@n中n的取值, 即计算NDGG值时查询结果序列的位置, 纵轴是NDGG得分值, 该值为5-折交叉验证的均值。

显示原图| 下载原图ZIP| 生成PPT

图2   p=40%时三种排序算法在NDGG@n上的对比

   

显示原图| 下载原图ZIP| 生成PPT

图3   p=50%时三种排序算法在NDGG@n上的对比

   

由图2和图3可知, 结合RWR的ListNet方法在NDGG@n指标上的性能总体上介于RankNet和ListNet之间。当p=40%时, 结合RWR的ListNet方法的性能全部高于RankNet, 但与ListNet方法存在较大差距。原因是p=40%时重启随机游走模型标注的准确率在87%左右, 未达到可用性要求, 增大了由此得到的排序模型的误差率。当p=50%时, 结合RWR的ListNet方法在n{1,2,3,4,5,6,7,8,9,10}时的性能值都明显优于RankNet。当n=5时, 结合RWR的ListNet方法的排序性能与传统的ListNet方法相同, 在n大于6之后和ListNet性能只存在微小的差距。在实际的检索使用中, 用户往往只是浏览排在序列前面的结果, 排名靠前的结果对排序性能的影响较大, NDGG@n评估排序性能时考虑了这一点。实验结果表明, 当p= 50%时, 结合RWR的ListNet方法排序性能接近传统的ListNet方法, 并且能节省50%的人工标注量, 验证了本文方法的优越性。

本文使用的数据集是专门用于排序算法性能测试的公开数据集, 其标签准确性高。但在实际人工标注训练数据时, 标注的标签通常取决于专家的知识和主观判断, 标注质量难以控制, 可能存在人工标注质量低于p=50%时利用RWR半监督学习的情况。在这种情况下, 基于重启随机游走的排序学习方法将获得最好的排序性能。另外, 相比于本文实验的数据集, 在信息检索领域的实际应用场景中, 特征接近的用户实际需求往往更相近。比如在电子商务领域, 消费能力相同的用户对某商品具有非常相似的消费意向, 这些具有相似消费能力特征的用户对于某个查询的搜索结果选择倾向具有很大的类似性。本文提出的基于RWR的半监督排序学习算法基于特征值之间的相似度进行标签标记, 因此在这种情况下标注准确率会变高, 达到较好排序效果所需的训练数据标注比例会低于50%。

6 结 语

本文提出一种基于重启动随机游走模型的排序学习方法。先使用随机游走算法完成基于图的半监督学习, 根据已标注文档的相关度标注出未标注文档的相关度, 原理上也是根据文档之间的相似性进行标签信息的传递; 再基于已标注的训练数据使用Listwise模型的ListNet算法进行排序学习。相比于传统的RankNet方法、ListNet方法, 本文提出的方法使用自动标注的训练数据, 能够在实现较高排序性能的前提下节省50%的人工标注量, 对于解决排序学习中训练数据标注不足、标注质量难以控制的难题具有指导意义。由于本文方法要求对每个查询单独进行随机游走, 这对实际应用中多样查询下的文档标注工作来说仍然需要花费较多精力完成。对此方法的改善将作为今后继续研究的方向。

作者贡献声明:

贺婉莹: 设计研究方案, 采集、分析数据, 进行实验, 起草、修改论文, 论文最终版本修订;

杨建林: 提出研究思路, 修改论文。

利益冲突声明

所有作者声明不存在利益冲突关系。

支撑数据

支撑数据由作者自存储, E-mail: 1461242580@qq.com。

[1] 贺婉莹. chooseTrainSamples.m. 训练样本选择程序.

[2] 贺婉莹. RandWalkRestart.m. 重启随机游走程序.

[3] 贺婉莹. evaluateResult.m. 标注准确率评估程序.

参考文献

文献选项

• 原文顺序
• 文献年度倒序
• 文中引用次数倒序
• 被引期刊影响因子