关于自然语言处理:推荐系统四精排详解排序算法LTRpoitwise-pairwise-listwise相关评价指标

0. 前言召回排序流程策略算法简介

举荐可分为以下四个流程，别离是召回、粗排、精排以及重排：

1. 召回是源头，在某种意义上决定着整个举荐的天花板；
2. 粗排是初筛，个别不会上简单模型；
3. 精排是整个举荐环节的重中之重，在特色和模型上都会做的比较复杂；
4. 重排，个别是做打散或满足业务经营的特定强插需要，同样不会应用简单模型；

• 召回层：召回解决的是从海量候选 item 中召回千级别的 item 问题

  • 统计类，热度，LBS；
  • 协同过滤类，UserCF、ItemCF；
  • U2T2I，如基于 user tag 召回；
  • I2I 类，如 Embedding（Word2Vec、FastText），GraphEmbedding（Node2Vec、DeepWalk、EGES）；
  • U2I 类，如 DSSM、YouTube DNN、Sentence Bert；
• 模型类：模型类的模式是将用户和 item 别离映射到一个向量空间，而后用向量召回，这类有 itemcf，usercf，embedding（word2vec），Graph embedding（node2vec 等），DNN（如 DSSM 双塔召回，YouTubeDNN 等），RNN（预测下一个点击的 item 失去用户 emb 和 item emb）；向量检索能够用 Annoy（基于 LSH），Faiss（基于矢量量化）。此外还见过用逻辑回归搞个预估模型，把权重大的穿插特色拿进去构建索引做召回

• 排序策略，learning to rank 流程三大模式（pointwise、pairwise、listwise），次要是特色工程和 CTR 模型预估；

  • 粗排层：实质上跟精排相似，只是特色和模型复杂度上会精简，此外也有将精排模型通过蒸馏失去简化版模型来做粗排

    • 常见的特色开掘（user、item、context，以及互相穿插）；

  • 精排层：精排解决的是从千级别 item 到几十这个级别的问题

    • CTR 预估：lr，gbdt，fm 及其变种（fm 是一个工程团队不太强又对算法精度有肯定要求时比拟好的抉择），widedeep，deepfm，NCF 各种穿插，DIN，BERT，RNN
    • 多指标：MOE，MMOE，MTL（多任务学习）
    • 打分公式交融: 随机搜寻，CEM（性价比比拟高的办法），在线贝叶斯优化（高斯过程），带模型 CEM，强化学习等
• 重排层：重排层解决的是展现列表总体最优，模型有 MMR，DPP，RNN 系列（参考阿里的 globalrerank 系列）

• 展现层：

  • 举荐理由：统计规定、行为规定、抽取式（个别从评论和内容中抽取）、生成式；排序能够用汤普森采样（简略无效），交融到精排模型排等等
  • 首图优选：CNN 抽特色，汤普森采样
• 摸索与利用：随机策略（简略无效），汤普森采样，bandit，强化学习（Q-Learning、DQN）等
• 产品层：交互式举荐、分 tab、多种类型物料交融

粗排与精排就像级联漏斗，两者指标更多放弃同向一致性，粗排就是跟精排放弃各自为政。如果粗排排序高的，精排排序也高，那么粗排就很好的实现了“帮忙精排缓冲”的目标。而 rerank 环节相似于排序改判：可能波及业务调整、打散、强插、增量分等等。

1. 精排简介

Learning to Rank (LTR)是一类技术办法，次要利用机器学习算法解决理论中的排序问题。传统的机器学习次要解决的问题是一个分类或者回归问题，比方对一个样本数据预测对应的类别或者预测一个数值分值。而 LTR 解决的是一个排序问题，对一个 list 的 item 进行一个排序，所以 LTR 并不太关注这个 list 的每个 item 具体得多少分值，更关注所有 item 的绝对程序。排序通常是信息检索的外围成分，所以 LTR 最常见的利用是搜寻场景，对召回的 document 进行排序。

1.1 精排利用场景

排序学习场景：

• 举荐零碎，基于历史行为的“猜你喜爱”
• 搜寻排序，基于某 Query 进行的后果排序，冀望用户选中的在排序后果中是靠前的 => 无意识的被动举荐
• 排序后果都很重要，猜用户想要点击或者 booking 的 item 就在后果列表后面
• 排序学习是个性化后果，用于搜寻列表、举荐列表、广告等场景

1.2 罕用模型

排序模型依照构造划分，能够分为线性排序模型、树模型、深度学习模型：
从晚期的线性模型 LR，到引入主动二阶穿插特色的 FM 和 FFM，到非线性树模型 GBDT 和 GBDT+LR，到最近全面迁徙至大规模深度学习排序模型。

• 线性排序模型：LR
• 树模型：GBDT,GBDT+LR, LambdaMART
• 深度学习模型: DeepFM,Wide&Deep, ListNet, AdaRank，SoftRank，LambdaRank 等

2.LTR 三大构造：Pointwise, Pairwise, Listwise

序模型依照样本生成办法和损失函数 loss 的不同，能够划分成 Pointwise, Pairwise, Listwise 三类办法：

• Pointwise 排序学习（单点法）：

  • 将训练样本转换为 多分类 问题（样本特色 - 类别标记）或者回归问题（样本特色 - 间断值）
  • 只思考 单个样本的好坏，没有思考样本之间的程序

• Pairewise 排序学习（配对法）：

  • 比拟风行的 LTR 学习办法，将排序问题转换为二元分类问题
  • 接管到用户査询后，返回相干文档列表，确定文档之间的先后顺序关系（多个 pair 的排序问题），只思考了两个文档的绝对程序，没有思考文档在搜寻列表中的地位。

• Listwise 排序学习（列表法）：

  • 它是将每个 Query 对应的所有搜寻后果列表作为一个训练样例
  • 依据训练样例训练失去最优评分函数 F，对应新的查问，评分 F 对每个文档打分，而后依据得分由高到低排序，即为最终的排序后果

2.1 pointwise

pointwise 将其转化为多类分类或者回归问题

Pointwise 类办法，其 L2R 框架具备以下特色：

• 输出空间中样本是单个 doc（和对应 query）形成的特征向量；
• 输入空间中样本是单个 doc（和对应 query）的相关度；
• 假如空间中样本是打分函数；
• 损失函数评估单个 doc 的预测得分和实在得分之间差别。
• 这里探讨下，对于人工标注标签怎么转换到 pointwise 类办法的输入空间：
• 如果标注间接是相关度 $s_j$，则 $doc x_j$ 的实在标签定义为 $y_j=s_j$
• 如果标注是 pairwise preference $s_{u,v}$，则 $doc x_j$ 的实在标签能够利用该 doc 击败了其余 docs 的频次
• 如果标注是整体排序 π，则 $doc x_j$ 的实在标签能够利用映射函数，如将 doc 的排序地位序号当作实在标签

2.1.1 算法简介

依据应用的 ML 办法不同，pointwise 类能够进一步分成三类：基于回归的算法、基于分类的算法，基于有序回归的算法。上面具体介绍。

1. 基于回归的算法
   此时，输入空间蕴含的是实值相关度得分。
   采纳 ML 中传统的回归办法即可。
2. 基于分类的算法
   此时，输入空间蕴含的是无序类别。
   对于二分类，SVM、LR 等均可；对于多分类，晋升树等均可。
3. 基于有序回归的算法
   此时，输入空间蕴含的是有序类别。
   通常是找到一个打分函数，而后用一系列阈值对得分进行宰割，失去有序类别。采纳 PRanking、基于 margin 的办法都能够。

2.1.2 ponitwise 细则

pointwise 办法损失函数计算只与单个 document 无关，实质上是训练一个分类模型或者回归模型，判断这个 document 与以后的这个 query 相干水平，最初的排序后果就是从模型对这些 document 的预测的分值进行一个排序。对于 pointwise 办法，给定一个 query 的 document list，对于每个 document 的预测与其它 document 是独立的。所以模型输出和对应的标签 label 模式如下：

• 输出: 单个 document
• 标签 label: document 所属类型或者分值
  pointwise 办法将排序工作看做对单个文本的回归或者分类工作来做。若文档 document 的相关性等级有 K 种，则咱们能够建模为一个有 K 个类别的 $\{0,1,2,…, K-1\}$ 的 Multi-class 分类工作，则 $y_i \in \R^k$
  一个 k 维度的 one-hot 示意, 咱们能够用穿插熵 loss 作为指标损失函数:

$\left.\mathrm{L}=-\left(\mathrm{y}_{\mathrm{i}} \log \left(\mathrm{p}_{\mathrm{i}}\right)-\left(1-\mathrm{y}_{\mathrm{i}}\right) \log \left(1-\mathrm{p}_{\mathrm{i}}\right)\right]\right)$

参考链接：https://zhuanlan.zhihu.com/p/…

2.1.3 Pointwise 排序学习（单点法）总结：

1. 将文档转化为特征向量，每个文档都是独立的
2. 对于某一个 query，它将每个 doc 别离判断与这个 query 的相干水平
3. 将 docs 排序问题转化为了分类（比方相干、不相干）或回归问题（相干水平越大，回归函数的值越大）
4. 从训练数据中学习到的分类或者回归函数对 doc 打分，打分后果即是搜寻后果，CTR 能够采纳 Pointwise 形式进行学习，对每一个候选 item 给出一个评分，基于评分进行排序
5. 仅仅思考了 query 和 doc 之间的关系，而没有思考排序列表中 docs 之间的关系
6. 次要算法：转换为回归问题，应用 LR，GBDT，Prank, McRank

缺点

• ranking 谋求的是排序后果，并不要求准确打分，只有有绝对打分即可。
• pointwise 类办法并没有思考同一个 query 对应的 docs 间的外部依赖性。一方面，导致输出空间内的样本不是 IID 的，违反了 ML 的根本假如，另一方面，没有充分利用这种样本间的结构性。其次，当不同 query 对应不同数量的 docs 时，整体 loss 将会被对应 docs 数量大的 query 组所摆布，后面说过应该每组 query 都是等价的。

• 损失函数也没有 model 到预测排序中的地位信息。因而，损失函数可能无心的过多强调那些不重要的 docs，即那些排序在前面对用户体验影响小的 doc。

  改良

• Pointwise 类算法也能够再改良，比方在 loss 中引入基于 query 的正则化因子的 RankCosine 办法。

2.2 pairwise

pairwise 将其转化为 pair 分类问题

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_u>s_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$

2.2.1 算法简介

1. 基于二分类的算法
   pairwise 类办法根本就是应用二分类算法即可。
   经典的算法有 基于 NN 的 SortNet，基于 NN 的 RankNet，基于 fidelity loss 的 FRank，基于 AdaBoost 的 RankBoost，基于 SVM 的 RankingSVM，基于晋升树的 GBRank。

2.2.2 pairwise 细则

基于 pairwise 的办法，在计算指标损失函数的时候，每一次须要基于一个 pair 的 document 的预测后果进行损失函数的计算。比方给定一个 pair 对的 document，优化器须要优化的是两个 document 的排序关系，与 groud truth 的排序程序保持一致。指标是最小化与 groud truth 不统一的排序对。在理论利用中，pairwise 办法比 pointwise 成果更好，因为预测绝对的排序相比预测一个类别或者一个分值，更合乎排序的性质。其中模型输出和对应的标签 label 模式如下：

• 输出: 一个 pair 对 document (A,B)
• 输入标签: 绝对程序 label (1, 0.5, 0)

其中 1 示意相关性等级 A >B，0.5 示意相关性等级 A =B，0 示意相关性等级 A <B。

2.2.3 Pairewise 排序学习（配对法）总结：

1. 比拟风行的 LTR 学习办法，将排序问题转换为二元分类问题
2. 接管到用户査询后，返回相干文档列表，确定文档之间的先后顺序关系（多个 pair 的排序问题）
3. 对于同一查问的相干文档集中，对任何两个不同 label 的文档，都能够失去一个训练实例 $（di,dj）$，如果 $di>dj$ 则赋值 +1，反之 -1
4. 没有思考文档呈现在搜寻列表中的地位，排在搜寻后果后面的文档更为重要，如果靠前的文档呈现判断谬误，代价会很高

1. 毛病：
尽管 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 的根本假如，并且也没有充分利用这种样本间的结构性。

2. 改良
pairwise 类办法也有一些尝试，去肯定水平解决上述缺点，比方：

• Multiple hyperplane ranker，次要针对前述第一个缺点
• magnitude-preserving ranking，次要针对前述第一个缺点
• IRSVM，次要针对前述第二个缺点
• 采纳 Sigmoid 进行改良的 pairwise 办法，次要针对前述第三个缺点
• P-norm push，次要针对前述第四个缺点
• Ordered weighted average ranking，次要针对前述第四个缺点
• LambdaRank，次要针对前述第四个缺点
• Sparse ranker，次要针对前述第四个缺点

2.3 listwise

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 则能够间接失去实在标签

2.3.1 算法简介

1. 间接基于评估指标的算法

间接取优化 ranking 的评估指标，也算是 listwise 中最直观的办法。但这并不简略，因为后面说过评估指标都是离散不可微的，具体解决形式有这么几种：

• 优化基于评估指标的 ranking error 的间断可微的近似，这种办法就能够间接利用已有的优化办法，如 SoftRank，ApproximateRank，SmoothRank
• 优化基于评估指标的 ranking error 的间断可微的上界，如 SVM-MAP，SVM-NDCG，PermuRank
• 应用能够优化非平滑指标函数的优化技术，如 AdaRank，RankGP

上述办法的优化指标都是间接和 ranking 的评估指标无关。当初来思考一个概念，informativeness。通常认为一个更有信息量的指标，能够产生更无效的排序模型。而多层评估指标（NDCG）相较二元评估（AP）指标通常更富信息量。因而，有时尽管应用信息量更少的指标来评估模型，但依然能够应用更富信息量的指标来作为 loss 进行模型训练。

通过间接优化排序后果中的评测指标来优化排序工作，然而基于评测指标比方 NDCG 依赖排序后果，是不间断不可导的。所以优化这些不间断不可导的指标函数面临较大的挑战，目前少数优化技术都是基于函数可导的状况。那么如何解决这个问题？常见的有如下两种办法：

• 通过应用优化技术将指标函数转变成间断可导的函数，而后进行求解，比方 SoftRank 和 AdaRank 等模型

• 通过应用优化技术对非间断的不可导指标函数就行求解，比方 LambdaRank

  LambdaRank
  RankNet 优化指标是最小化 pair 对谬误，然而在信息检索畛域比方 NDCG 这样的评测指标，这样的优化指标并不可能最大化成果，通常在信息检索中咱们更关注的是 topN 的排序后果，且相关性越大的文本最须要排在最后面。如下图所示：

  给定一个 query，上图为排序后果展现，其中蓝色的线示意的是相干的文档，灰色的线示意不相干的文档，那么在左图，有 13 个 pair 对谬误，而在右图中，有 11 个 pair 对谬误，在 RankNet，右图的排序后果要比左图好，然而在信息检索指标中，比方 NDCG 指标，左图的成果比左边更好。
  咱们在下面介绍 RankNet 中，将上述 (1)(2) 公式代人到 (3) 公式中，咱们能够失去损失函数如下：

$\mathrm{C}=\frac{1}{2}\left(1-\mathrm{S}_{\mathrm{ij}}\right) \sigma\left(\mathrm{s}_{\mathrm{i}}-\mathrm{s}_{\mathrm{j}}\right)+\log \left(1+\mathrm{e}^{-\sigma\left(\mathrm{s}_{\mathrm{i}}-\mathrm{s}_{\mathrm{j}}\right)}\right)$

具体内容不开展参考博客：https://blog.csdn.net/BGoodHa…
4.1.1 节

LambdaMART

参考上述博客 4.1.2 节

2. 非间接基于评估指标的算法 (定义损失函数)
   这里，不再应用和评估指标相干的 loss 来优化模型，而是设计能掂量模型输入与实在排列之间差别的 loss，如此取得的模型在评估指标上也能取得不错的性能。
   经典的如，ListNet，ListMLE，StructRank，BoltzRank。

ListNet
ListNet 与 RankNet 很类似，RankNet 是用 pair 对文本排序程序进行模型训练，而 ListNet 用的是整个 list 文本排序程序进行模型训练。若训练样本中有 m 个 query，如果对应须要排序的最多文本数量为 n，则 RankNet 的复杂度为 $O(m \cdot n^2)$ 而 ListNet 的复杂度为 $O(m \cdot n)$，所以整体来说在训练过程中 ListNet 相比 RankNet 更高效。

ListMLE
ListMLE 也是基于 list 计算损失函数，论文对 learning to rank 算法从函数凸性，连续性，鲁棒性等多个维度进行了剖析，提出了一种基于最大似然 loss 的 listwise 排序算法，取名为 ListMLE。

上述参考博客：4.2.2 节

2.3.2 Listwise 细则

更多内容参考(https://blog.csdn.net/sinat_3…)[https://blog.csdn.net/sinat_3…]

2.3.3 Listwise 排序学习（列表法）总结：

1. 它是将每个 Query 对应的所有搜寻后果列表作为一个训练样例
2. 依据训练样例训练失去最优评分函数 F，对应新的查问，评分 F 对每个文档打分，而后依据得分由高到低排序，即为最终的排序后果
3. 间接思考整体序列，针对 Ranking 评估指标（比方 MAP, NDCG）进行优化
4. 次要算法：ListNet, AdaRank，SoftRank，LambdaRank, LambdaMART 等 LambdaMART 是对 RankNet 和 LambdaRank 的改良，在 Yahoo Learning to Rank Challenge 较量中的冠军模型

listwise 类相较 pointwise、pairwise 对 ranking 的 model 更天然，解决了 ranking 应该基于 query 和 position 问题。

listwise 类存在的次要缺点是：一些 ranking 算法须要基于排列来计算 loss，从而使得训练复杂度较高，如 ListNet 和 BoltzRank。此外，地位信息并没有在 loss 中失去充分利用，能够思考在 ListNet 和 ListMLE 的 loss 中引入地位折扣因子。

2.4 三类办法代表汇总

wiki 有很全的三类办法代表：

2019    FastAP [30]    listwise    Optimizes Average Precision to learn deep embeddings
2019    Mulberry    listwise & hybrid    Learns ranking policies maximizing multiple metrics across the entire dataset
2019    DirectRanker    pairwise    Generalisation of the RankNet architecture
2019    GSF [31]    listwise    A permutation-invariant multi-variate ranking function that encodes and ranks items with groupwise scoring functions built with deep neural networks.
2020    RaMBO[32]    listwise    Optimizes rank-based metrics using blackbox backpropagation[33]
2020    PRM [34]    pairwise    Transformer network encoding both the dependencies among items and the interactions
between the user and items

2020    SetRank [35]    listwise    A permutation-invariant multi-variate ranking function that encodes and ranks items with self-attention networks.
2021    PiRank [36]    listwise    Differentiable surrogates for ranking able to exactly recover the desired metrics and scales favourably to large list sizes, significantly improving internet-scale benchmarks.
2022    SAS-Rank    listwise    Combining Simulated Annealing with Evolutionary Strategy for implicit and explicit learning to rank from relevance labels
2022    VNS-Rank    listwise    Variable Neighborhood Search in 2 Novel Methodologies in AI for Learning to Rank
2022    VNA-Rank    listwise    Combining Simulated Annealing with Variable Neighbourhood Search for Learning to Rank

2.5 评估指标

更多内容参考(https://blog.csdn.net/sinat_3…)[https://blog.csdn.net/sinat_3…]

2.5.1 WTA(Winners take all)

2.5.2 MRR(Mean Reciprocal Rank)

2.5.3 RC(Rank Correlation)

2.5.4 MAP(Mean Average Precision)

2.5.5 NDCG(Normalized Discounted Cumulative Gain)

2.5.6 小结

能够发现，这些评估指标具备两大个性：

• 基于 query，即不论一个 query 对应的 docs 排序有多蹩脚，也不会重大影响整体的评估过程，因为每组 query-docs 对平均指标都是雷同的奉献。
• 基于 position，即显式的利用了排序列表中的地位信息，这个个性的副作用就是上述指标是离散不可微的。
  一方面，这些指标离散不可微，从而没法利用到某些学习算法模型上；另一方面，这些评估指标较为权威，通常用来评估基于各类形式训练进去的 ranking 模型。因而，即便某些模型提出新鲜的损失函数结构形式，也要受这些指标启发，合乎上述两个个性才能够。

3. 举荐参考链接