上海网站公司,喀什网站建设百度推广,专门做正品的网站手机版,网站设计语言有哪些Ranking 是信息检索领域的基本问题#xff0c;也是搜索引擎背后的重要组成模块。本文将对结合机器学习的 ranking 技术——learning2rank——做个系统整理#xff0c;包括 pointwise、pairwise、listwise 三大类型#xff0c;它们的经典模型#xff0c;解决了什么问题…Ranking 是信息检索领域的基本问题也是搜索引擎背后的重要组成模块。本文将对结合机器学习的 ranking 技术——learning2rank——做个系统整理包括 pointwise、pairwise、listwise 三大类型它们的经典模型解决了什么问题仍存在什么缺陷。关于一些扩展话题和具体应用可能会在下一篇文章介绍包括在 QA 领域的实践情况。
本文主要参考刘铁岩老师的《Learning to Rank for Information Retrieval》和李航老师的《Learning to rank for information retrieval and natural language processing》。 1、概述
1.1 Ranking
Ranking 模型可以粗略分为基于相关度和基于重要性进行排序的两大类。 早期基于相关度的模型通常利用 query 和 doc 之间的词共现特性如布尔模型、VSM如 TFIDF、LSI 等、概率排序思想BM25、LMIR 等等方式。 基于重要性的模型利用的是 doc 本身的重要性如 PageRank、TrustRank 等。 这里我们关注基于相关度的 ranking。
相关度的标注
最流行也相对好实现的一样方式时人工标注 MOS即相关度等级。其次是人工标注 pairwise preference即一个 doc 是否相对另一个 doc 与该 query 更相关。最 costly 的方式是人工标注 docs 与 query 的整体相关度排序。
评估指标
即评估 query 与 docs 之间的真实排序与预测排序的差异。 大部分评估指标都是针对每组 query-docs 进行定义然后再在所有组上进行平均。常用的基于度量的 ranking 错误率如下
MAP 首先suppose we have binary judgment for the documents, i.e., the label is one for relevant documents and zero for irrelevant documents定义docs 排序列表 π 中位置 k 的 precision 为 其次令 m 为该 query 对应的 docs 数量m_1 为该 query 对应的标签为1的 docs 数量则有 average precisionAP为 最后对所有 query 求得 AP 进行平均即得到 MAP。NDCG 首先Discounted cumulative gain DCG考量了 relevance judgment in terms of multiple ordered categories以及对位置信息进行了折扣考量。定义 docs 排序列表 π 中位置 k 的 DCG 为 其中函数 G 是 对应 doc 的 rating 值通常采用指数函数如 G(x)2^x-1函数 η 即位置折扣因子通常采用 η(j)1/log(j1)。 其次对 DCGk 进行归一化规整到0-1Z_k 表示 DCGk 的可能最大值从而有 NDCG
可以发现这些评估指标具备两大特性
基于 query 即不管一个 query 对应的 docs 排序有多糟糕也不会严重影响整体的评价过程因为每组 query-docs 对平均指标都是相同的贡献。基于 position 即显式的利用了排序列表中的位置信息这个特性的副作用就是上述指标是离散不可微的。
一方面这些指标离散不可微从而没法应用到某些学习算法模型上另一方面这些评估指标较为权威通常用来评估基于各类方式训练出来的 ranking 模型。因此即使某些模型提出新颖的损失函数构造方式也要受这些指标启发符合上述两个特性才可以。这些细节在后面会慢慢体会到。
1.2 Learning to Rank
Learning2Rank 即将 ML 技术应用到 ranking 问题训练 ranking 模型。通常这里应用的是判别式监督 ML 算法。经典 L2R 框架如下
特征向量 x 反映的是某 query 及其对应的某 doc 之间的相关性通常前面提到的传统 ranking 相关度模型都可以用来作为一个维度使用。L2R 中使用的监督机器学习方法主要是判别式类。
根据上图的基本元素输入空间、假设空间、输出空间、损失函数方面的差异L2R可以分为三大类pointwise 类pairwise 类listwise 类。总结如下后面章节将进行详细说明。
2、Pointwise Approach
2.1 特点
Pointwise 类方法其 L2R 框架具有以下特征
输入空间中样本是单个 doc和对应 query构成的特征向量输出空间中样本是单个 doc和对应 query的相关度假设空间中样本是打分函数损失函数评估单个 doc 的预测得分和真实得分之间差异。
这里讨论下关于人工标注标签怎么转换到 pointwise 类方法的输出空间
如果标注直接是相关度 s_j则 doc x_j 的真实标签定义为 y_js_j如果标注是 pairwise preference s_{u,v}则 doc x_j 的真实标签可以利用该 doc 击败了其他 docs 的频次如果标注是整体排序 π则 doc x_j 的真实标签可以利用映射函数如将 doc 的排序位置序号当作真实标签
根据使用的 ML 方法不同pointwise 类可以进一步分成三类基于回归的算法、基于分类的算法基于有序回归的算法。下面详细介绍。
2.2 基于回归的算法
此时输出空间包含的是实值相关度得分。
采用 ML 中传统的回归方法即可。
2.3 基于分类的算法
此时输出空间包含的是无序类别。
对于二分类SVM、LR 等均可对于多分类提升树等均可。
2.4 基于有序回归的算法
此时输出空间包含的是有序类别。
通常是找到一个打分函数然后用一系列阈值对得分进行分割得到有序类别。采用 PRanking、基于 margin 的方法都可以。
2.5 缺陷
回顾概述中提到的评估指标应该基于 query 和 position
ranking 追求的是排序结果并不要求精确打分只要有相对打分即可。pointwise 类方法并没有考虑同一个 query 对应的 docs 间的内部依赖性。一方面导致输入空间内的样本不是 IID 的违反了 ML 的基本假设另一方面没有充分利用这种样本间的结构性。其次当不同 query 对应不同数量的 docs 时整体 loss 将会被对应 docs 数量大的 query 组所支配前面说过应该每组 query 都是等价的。损失函数也没有 model 到预测排序中的位置信息。因此损失函数可能无意的过多强调那些不重要的 docs即那些排序在后面对用户体验影响小的 doc。
2.6 改进
Pointwise 类算法也可以再改进比如在 loss 中引入基于 query 的正则化因子的 RankCosine 方法。
3、Pairwise Approach
3.1 特点
Pairwise 类方法其 L2R 框架具有以下特征
输入空间中样本是同一 query 对应的两个 doc和对应 query构成的两个特征向量输出空间中样本是 pairwise preference假设空间中样本是二变量函数损失函数评估 doc pair 的预测 preference 和真实 preference 之间差异。
这里讨论下关于人工标注标签怎么转换到 pairwise 类方法的输出空间
如果标注直接是相关度 s_j则 doc pair (x_u,x_v) 的真实标签定义为 y_{u,v}2*I_{s_us_v}-1如果标注是 pairwise preference s_{u,v}则 doc pair (x_u,x_v) 的真实标签定义为y_{u,v}s_{u,v}如果标注是整体排序 π则 doc pair (x_u,x_v) 的真实标签定义为y_{u,v}2*I_{π_u,π_v}-1
3.2 基于二分类的算法
pairwise 类方法基本就是使用二分类算法即可。
经典的算法有 基于 NN 的 SortNet基于 NN 的 RankNet基于 fidelity loss 的 FRank基于 AdaBoost 的 RankBoost基于 SVM 的 RankingSVM基于提升树的 GBRank。
3.3 缺陷
虽然 pairwise 类相较 pointwise 类 model 到一些 doc pair 间的相对顺序信息但还是存在不少问题回顾概述中提到的评估指标应该基于 query 和 position
如果人工标注给定的是第一种和第三种即已包含多有序类别那么转化成 pairwise preference 时必定会损失掉一些更细粒度的相关度标注信息。doc pair 的数量将是 doc 数量的二次从而 pointwise 类方法就存在的 query 间 doc 数量的不平衡性将在 pairwise 类方法中进一步放大。pairwise 类方法相对 pointwise 类方法对噪声标注更敏感即一个错误标注会引起多个 doc pair 标注错误。pairwise 类方法仅考虑了 doc pair 的相对位置损失函数还是没有 model 到预测排序中的位置信息。pairwise 类方法也没有考虑同一个 query 对应的 doc pair 间的内部依赖性即输入空间内的样本并不是 IID 的违反了 ML 的基本假设并且也没有充分利用这种样本间的结构性。
3.4 改进
pairwise 类方法也有一些尝试去一定程度解决上述缺陷比如
Multiple hyperplane ranker主要针对前述第一个缺陷magnitude-preserving ranking主要针对前述第一个缺陷IRSVM主要针对前述第二个缺陷采用 Sigmoid 进行改进的 pairwise 方法主要针对前述第三个缺陷P-norm push主要针对前述第四个缺陷Ordered weighted average ranking主要针对前述第四个缺陷LambdaRank主要针对前述第四个缺陷Sparse ranker主要针对前述第四个缺陷
4、Listwise Approach
4.1 特点
Listwise 类方法其 L2R 框架具有以下特征
输入空间中样本是同一 query 对应的所有 doc与对应的 query构成的多个特征向量列表输出空间中样本是这些 doc和对应 query的相关度排序列表或者排列假设空间中样本是多变量函数对于 docs 得到其排列实践中通常是一个打分函数根据打分函数对所有 docs 的打分进行排序得到 docs 相关度的排列损失函数分成两类一类是直接和评价指标相关的还有一类不是直接相关的。具体后面介绍。
这里讨论下关于人工标注标签怎么转换到 listwise 类方法的输出空间
如果标注直接是相关度 s_j则 doc set 的真实标签可以利用相关度 s_j 进行比较构造出排列如果标注是 pairwise preference s_{u,v}则 doc set 的真实标签也可以利用所有 s_{u,v} 进行比较构造出排列如果标注是整体排序 π则 doc set 则可以直接得到真实标签
根据损失函数构造方式的不同listwise 类可以分成两类直接基于评价指标的算法间接基于评价指标的算法。下面详细介绍。
4.2 直接基于评价指标的算法
直接取优化 ranking 的评价指标也算是 listwise 中最直观的方法。但这并不简单因为前面说过评价指标都是离散不可微的具体处理方式有这么几种
优化基于评价指标的 ranking error 的连续可微的近似这种方法就可以直接应用已有的优化方法如SoftRankApproximateRankSmoothRank优化基于评价指标的 ranking error 的连续可微的上界如 SVM-MAPSVM-NDCGPermuRank使用可以优化非平滑目标函数的优化技术如 AdaRankRankGP
上述方法的优化目标都是直接和 ranking 的评价指标有关。现在来考虑一个概念informativeness。通常认为一个更有信息量的指标可以产生更有效的排序模型。而多层评价指标NDCG相较二元评价AP指标通常更富信息量。因此有时虽然使用信息量更少的指标来评估模型但仍然可以使用更富信息量的指标来作为 loss 进行模型训练。
4.3 非直接基于评价指标的算法
这里不再使用和评价指标相关的 loss 来优化模型而是设计能衡量模型输出与真实排列之间差异的 loss如此获得的模型在评价指标上也能获得不错的性能。 经典的如 ListNetListMLEStructRankBoltzRank。
4.4 缺陷
listwise 类相较 pointwise、pairwise 对 ranking 的 model 更自然解决了 ranking 应该基于 query 和 position 问题。
listwise 类存在的主要缺陷是一些 ranking 算法需要基于排列来计算 loss从而使得训练复杂度较高如 ListNet和 BoltzRank。此外位置信息并没有在 loss 中得到充分利用可以考虑在 ListNet 和 ListMLE 的 loss 中引入位置折扣因子。
5、总结
实际上前面介绍完可以看出来这三大类方法主要区别在于损失函数。不同的损失函数知音了不同的模型学习过程和输入输出空间。
