LambdaRank算法详解：最大化NDCG的排序学习方法

LambdaRank算法详解：最大化NDCG的排序学习方法

引用

CSDN

1.

https://m.blog.csdn.net/qq_22866291/article/details/144870803

LambdaRank是一种用于排序学习（Learning to Rank, LTR）的模型，特别适用于推荐系统和信息检索任务。它通过直接优化排序评价指标（如NDCG），确保模型的学习目标与实际应用目标一致。本文将详细介绍LambdaRank的核心思想、算法原理及其在推荐系统中的应用。

1.背景与动机

传统的排序学习方法通常使用点对点或列表级别的损失函数，但这些方法往往不能直接优化最终的排序评价指标（如NDCG）。LambdaRank通过引入Lambda权重λij，能够直接优化NDCG等排序评价指标，从而更有效地捕捉用户的偏好和行为模式。

1.1 NDCG的特点

NDCG（Normalized Discounted Cumulative Gain）是一种常用的排序质量评估标准，用于衡量推荐列表中相关商品的位置分布情况。具体解释可以参考笔者文章【召回评价指标NDCG、MAP】。其公式如下：

$$
\text{DCG} = \sum_{i=1}^{n} \frac{2^{rel_i} - 1}{\log_2(i+1)}
$$

$$
\text{NDCG} = \frac{\text{DCG}}{\text{IDCG}}
$$

• rel_i是第i个商品的相关性得分。
• n是推荐列表的长度。
• IDCG是理想情况下的DCG值，即所有相关商品都排在最前面。

NDCG考虑了每个商品的相关性得分，并根据其位置进行了折扣处理。排在前面的商品有更高的权重，因此如果高相关性的商品排在前面，NDCG值会更高。这是一个全局评价指标，因为它考虑了整个推荐列表的整体结构和位置分布。

1.2 传统排序学习方法的局限性

1.2.1 点对点方法（Pairwise Methods）

• 工作原理：这类方法通过比较商品对之间的相对顺序来优化模型。例如，如果商品A应该排在商品B前面，则损失函数会惩罚不正确的排序。
• 局限性：
• 局部优化：只关注商品对之间的相对顺序，而忽略了整个列表的整体质量。这种方法无法直接捕捉到NDCG所需的全局信息，因为它没有考虑商品在整个列表中的具体位置。
• 难以直接优化全局评价指标：由于NDCG是一个全局评价指标，依赖于所有商品的位置分布，而点对点方法只能优化局部的相对顺序，因此难以直接优化NDCG。

1.2.2 点级方法（Pointwise Methods）

• 工作原理：这类方法将排序问题视为回归或分类问题，直接预测每个商品的相关性得分。
• 局限性：
• 忽略相对顺序：只关注单个商品的相关性得分，忽略了商品之间的相对顺序。这种方法无法有效捕捉到NDCG所需的全局信息，因为它没有考虑商品在整个列表中的相对位置。
• 难以捕捉全局信息：NDCG不仅取决于单个商品的相关性得分，还取决于它们在整个列表中的位置分布。点级方法无法有效捕捉这种全局信息。

1.2.3 列表级方法（Listwise Methods）

• 工作原理：这类方法直接优化整个推荐列表的质量，通常使用复杂的损失函数来评估整个列表的表现。
• 局限性：
• 计算复杂度高：需要同时考虑多个商品的相对顺序，计算复杂度较高，尤其是在推荐列表较长的情况下。
• 难以解释：损失函数复杂，难以直观理解其优化过程，且不一定能直接对应到NDCG等具体的评价指标。
• 间接优化：虽然列表级方法试图优化整个列表的质量，但它们使用的损失函数通常是基于其他评价指标（如交叉熵等），而不是直接针对NDCG进行优化。

1.3 LambdaRank的优势

LambdaRank通过引入Lambda权重λij，能够直接优化NDCG等排序评价指标，从而克服了传统方法的局限性。具体优势如下：

• 直接优化NDCG：通过引入Lambda权重，LambdaRank衡量交换商品i和商品j的位置对NDCG的影响。如果交换这对商品的位置会导致NDCG显著下降，那么λij的值会较大，确保模型更关注这对商品的相对顺序。
• 全局与局部结合：通过求和符号∑i,j，LambdaRank遍历所有商品对，确保模型从全局角度优化整个推荐列表的排序质量。
• 高效计算：虽然涉及所有商品对，但通过引入λij，模型可以忽略那些对NDCG影响较小的商品对，提高计算效率。
• 稳定更新：通过Sigmoid函数将评分差值映射到概率空间，避免极端值对模型的影响，使得参数更新更加稳定和合理。

1.4 总结

传统排序学习方法（如点对点、点级和列表级方法）之所以不能直接优化NDCG，主要是因为它们在设计上侧重于局部优化或使用间接手段，无法有效捕捉NDCG所需的全局信息。LambdaRank通过引入Lambda权重和精心设计的损失函数，能够直接优化NDCG等排序评价指标，确保模型的学习目标与最终的应用目标高度一致，从而更有效地捕捉用户的偏好和行为模式，提高推荐系统的性能。

2. NDCG（Normalized Discounted Cumulative Gain）

NDCG是一种常用的排序质量评估标准，用于衡量推荐列表中相关商品的位置分布情况。其公式如下：

$$
\text{DCG} = \sum_{i=1}^{n} \frac{2^{rel_i} - 1}{\log_2(i+1)}
$$

$$
\text{NDCG} = \frac{\text{DCG}}{\text{IDCG}}
$$

• rel_i是第i个商品的相关性得分。
• n是推荐列表的长度。
• IDCG是理想情况下的DCG值，即所有相关商品都排在最前面。

NDCG考虑了每个商品的相关性得分，并根据其位置进行了折扣处理。排在前面的商品有更高的权重，因此如果高相关性的商品排在前面，NDCG值会更高。

3. Lambda权重

Lambda权重λij衡量了交换商品i和商品j的位置对整个推荐列表NDCG值的影响。具体来说：

• 变化量：λij反映了交换商品i和商品j的位置后，NDCG值的变化量。
• 重要性：如果交换i和j的位置会导致NDCG显著下降，那么λij的值会较大；反之则较小。这确保了模型更关注那些对排序质量影响较大的商品对。

计算Lambda权重的具体公式为：

$$
\Delta \text{NDCG}_{ij} = (2^{rel_i} - 2^{rel_j}) \cdot \left( \frac{1}{\log_2(r_j + 1)} - \frac{1}{\log_2(r_i + 1)} \right)
$$

$$
\lambda_{ij} = \left| \Delta \text{NDCG}_{ij} \right|
$$

4. 损失函数

LambdaRank的损失函数设计是为了最小化NDCG下降的可能性，并最大化NDCG上升的可能性。具体公式如下：

$$
L_{\text{LambdaRank}} = -\sum_{i,j} \lambda_{ij} \cdot (\sigma(\Delta s_{ij}) - \sigma(-\Delta s_{ij}))
$$

其中：

• λij是根据NDCG变化量计算的权重。
• σ(x)是Sigmoid函数，用于将评分差值映射到概率空间。
• Δsij = si - sj是商品i和商品j的评分差值。

公式说明

• 求和符号∑：遍历所有商品对，确保模型从全局角度优化整个推荐列表的排序质量。
• 负号-：将最大化NDCG的问题转化为最小化损失的问题，使得模型能够通过最小化损失函数来优化排序质量。
• Lambdaλij：反映了交换商品i和j的位置后，NDCG值的变化量。如果交换后导致NDCG显著下降，那么λij的值会较大；反之则较小。这确保了模型更关注那些对排序质量影响较大的商品对。
• σ(Δsij)：模型认为商品i应该排在商品j前面的概率
• σ(-Δsij)：模型认为商品j应该排在商品i前面的概率，即σ(Δsji)
• σ(Δsij)-σ(-Δsij)：模型对这对商品相对顺序的置信度差异。如果这个差异较大且正数，说明模型非常确信商品i应该排在商品j前面；反之则表示模型不太确定这对商品的相对顺序。

5. 评分调整与优化

为了最小化损失函数L_LambdaRank，模型会逐步调整商品的评分，使得高相关性的商品排在前面。具体步骤如下：

5.1 计算梯度

使用梯度下降法，计算评分调整的方向和幅度。对于每个商品i，其评分si的梯度为：

$$
\frac{\partial L_{\text{LambdaRank}}}{\partial s_i} = -\sum_j \lambda_{ij} \cdot \sigma'(\Delta s_{ij}) \cdot \text{sign}(\Delta s_{ij})
$$

其中，σ'(x)是Sigmoid函数的导数：

$$
\sigma'(x) = \sigma(x) \cdot (1 - \sigma(x))
$$

5.2 更新评分

根据梯度更新评分：

$$
s_i \leftarrow s_i - \eta \cdot \frac{\partial L_{\text{LambdaRank}}}{\partial s_i}
$$

其中，η是学习率，控制每次更新的步长。

示例

假设有两个商品A和B，当前评分为sA = 0.8和sB = 0.6，并且根据NDCG计算得到λAB = 9.24。

1. 计算初始损失项

$$
\Delta s_{AB} = s_A - s_B = 0.8 - 0.6 = 0.2
$$

$$
\sigma(0.2) = \frac{1}{1 + e^{-0.2}} \approx 0.5498
$$

$$
\sigma(-0.2) = \frac{1}{1 + e^{0.2}} \approx 0.4502
$$

$$
\sigma(0.2) - \sigma(-0.2) = 0.5498 - 0.4502 = 0.0996
$$

$$
L_{AB} = -\lambda_{AB} \cdot (\sigma(0.2) - \sigma(-0.2)) = -9.24 \cdot 0.0996 \approx -0.920
$$

2. 计算梯度

假设经过计算后，得到以下梯度值：

• ∂L_LambdaRank/∂sA ≈ -0.462
• ∂L_LambdaRank/∂sB ≈ 0.462

说明

• 偏导数为负值：表示增加该商品的评分会降低损失函数的值，从而有助于优化排序，反之同理！！！
• 通过梯度下降法，模型会增加高相关性商品的评分并减少低相关性商品的评分，逐步优化整个推荐列表的排序质量。

3. 更新评分

假设学习率为η = 0.1，则：

• 商品A的新评分为：

$$
s_A \leftarrow 0.8 - 0.1 \cdot (-0.462) = 0.8 + 0.0462 = 0.8462
$$

• 商品B的新评分为：

$$
s_B \leftarrow 0.6 - 0.1 \cdot 0.462 = 0.6 - 0.0462 = 0.5538
$$

通过上述过程，可以看到：

• 商品A的评分增加了：因为它应该排在B前面，增加sA可以降低损失函数的值，从而有助于优化排序。
• 商品B的评分减少了：因为它应该排在A后面，减少sB可以降低损失函数的值，从而有助于优化排序。

6. 总结

LambdaRank通过引入Lambda权重λij和精心设计的损失函数，能够高效地捕捉商品之间的相对关系，并直接优化排序评价指标（如NDCG），从而提高推荐系统的性能。这种设计使得模型的学习目标与最终的应用目标高度一致，能够更有效地捕捉用户的偏好和行为模式，从而提高推荐系统的性能。

关键点回顾

• NDCG：衡量推荐列表中相关商品的位置分布情况。
• Lambda权重：衡量交换商品对NDCG的影响，确保模型更关注重要的商品对。
• 损失函数：通过最小化损失函数，模型能够逐步优化排序，使得高相关性的商品排在前面。
• 评分调整：通过梯度下降法更新评分，逐步优化整个推荐列表的排序质量。