G&R Blog Release Regulation

Overview

1.形式化了在 list 上的 Permutation 概率模型, 利用极大似然定义排列概率模型, 思想来源于 Plackett-Luce model
2.提出了 ListNet, 一个在 Permutation 维度建模排序损失的一个网络, 关键贡献是定义了 listwise 的 ranking 损失函数

Permutation Probability 排列概率模型

1.原 paper 上的 formulation 过于复杂, 我们略微简化下
2.一个排列的概率模型是如何定义的 ? 用排列中逐个元素出现的最大似然定义, 最早起源于 Plackett-Luce model

反过来从随机事件角度来理解, 每一种排列结果可以理解为每个元素出现的概率乘积事件, 可以理解为无放回的抽扑克的过程, 第一次抽出来一张 a, (不放回), 再抽出来一张 b (不放回), 再抽出来一张假设是 c (不放回), 现在问抽出来 1-2-3 这种顺排列的概率是多少 ?

3.排列概率模型定义: 总共有 $n$ 个文档, 编号为 $1..n$, 给定每个文档的相关性打分 $s=(s_1,s_2,..,s_n)$, 生成的一个排列是 $\pi$, 基于最大似然的过程, 生成排列 $\pi$ 的概率为 $P(\pi)$

$$P(\pi)=\prod_{j=1}^{n}\frac{\phi(s_j)}{\sum_{k=j}^{n}\phi(s_k)}$$

其中 $\phi(.) > 0$ 是一个增函数, 且满足某种归一化的性质

举个例子, 有 a/b/c 3 个文档, 真实反馈 (例如同一个 query 下点击的次数) ground truth 是 a=6, b=4, c=3, 假设有 f/g 两个打分函数 (来自于2个模型)

f(a)=3 f(b)=2 f(c)=1
g(a)=6 g(b)=4 g(c)=3

比较下 $P_f([abc])$ 和 $P_f([cba])$, $P_g([abc])$ 和 $P_g([cba])$, 简单起见令 $\phi(x)=x$

$$\begin{aligned} P_f([abc])&=\frac{\phi(s_a)}{\phi(s_a)+\phi(s_b)+\phi(s_c)}*\frac{\phi(s_b)}{\phi(s_b)+\phi(s_c)}*\frac{\phi(s_c)}{\phi(s_c)}=\frac{3}{6}*\frac{2}{3}*\frac{1}{1}=\frac{6}{18}=0.333 \\ P_f([cba])&=\frac{\phi(s_c)}{\phi(s_a)+\phi(s_b)+\phi(s_c)}*\frac{\phi(s_b)}{\phi(s_b)+\phi(s_a)}*\frac{\phi(s_a)}{\phi(s_a)}=\frac{1}{6}*\frac{2}{5}*\frac{3}{3}=\frac{2}{30}=0.066 \\ P_g([abc])&=\frac{\phi(s_c)}{\phi(s_a)+\phi(s_b)+\phi(s_c)}*\frac{\phi(s_b)}{\phi(s_b)+\phi(s_a)}*\frac{\phi(s_a)}{\phi(s_a)}=\frac{6}{13}*\frac{4}{7}*\frac{3}{3}=\frac{24}{91}=0.263 \\ P_g([cba])&=\frac{\phi(s_c)}{\phi(s_a)+\phi(s_b)+\phi(s_c)}*\frac{\phi(s_b)}{\phi(s_b)+\phi(s_a)}*\frac{\phi(s_a)}{\phi(s_a)}=\frac{3}{13}*\frac{4}{10}*\frac{6}{6}=\frac{12}{130}=0.092 \\ \end{aligned}$$

我们发现对于输出排序 abc 的概率都远高于排序 cba 的概率, 是符合直觉的; 且我们发现两个模型都是很好的模型

TopK/Top-one Probability 前K/前1概率模型

对于任意一个 permuation, 上面的最大似然估计方法给出了一个有效的概率模型, 但存在一个问题, 假设一个 list 总共有 $N$ 个 doc, 共有 $N!$ 个排列, 且每个排列计算复杂度较高; 我们可以做个简化, 我们计算每个排列的时候, 只取 topK 个概率, 剩下不管: 达到的效果是, 我们的极大似然似然在前 K 个最重要的元素的排序上

$$P(\pi)=\prod_{j=1}^{K}\frac{\phi(s_j)}{\sum_{k=j}^{n}\phi(s_k)}$$

特殊地, 我们只关注排序第 1 个元素的概率, 得到 Top-one Probability 的表达

$$P(\pi)=\frac{\phi(s_j)}{\sum_{k=j}^{n}\phi(s_k)}$$

Top-one Probability 用再看下上面的例子, 感知看下有没有什么变化

$$\begin{aligned} P_f([abc])&=\frac{\phi(s_a)}{\phi(s_a)+\phi(s_b)+\phi(s_c)}=\frac{3}{6}=0.5 \\ P_f([cba])&=\frac{\phi(s_c)}{\phi(s_a)+\phi(s_b)+\phi(s_c)}=\frac{1}{6}=0.16 \\ P_g([abc])&=\frac{\phi(s_c)}{\phi(s_a)+\phi(s_b)+\phi(s_c)}=\frac{6}{13}=0.46 \\ P_g([cba])&=\frac{\phi(s_c)}{\phi(s_a)+\phi(s_b)+\phi(s_c)}=\frac{3}{13}=0.23 \\ \end{aligned}$$

体感上分布发生了一定的变化, 但是仍然是一个有效的概率模型

ListNet

有了上面用 Top-one probability 替代 permuation probability 的简化, 我们将概率模型具象化, 也就是给出一个合理的 $\phi(x)=\text{exp}(x)$

$$P(\pi)=\prod_{j=1}^{K}\frac{\phi(s_j)}{\sum_{k=j}^{n}\phi(s_k)}\approx \frac{\exp(s_j)}{\sum_{k=j}^{n}\exp(s_k)}$$

基于以上概率模型得到损失函数, 回归到 LTR 问题的一般形式, 假设 query 为 $q$, 模型输出打分为 $s_q$, 采用交叉熵损失的范式, 得到标准的损失函数为

$$\mathcal L(y_q, s_q)=-\sum_{j\in D_q}y_i\log\frac{\exp(s_i)}{\sum_{j\in D_q}\exp(s_j)}$$

Reference

[1]. Learning to Rank: From Pairwise Approach to Listwise Approach. Zhe Cao et al.
[2]. 论文分享 Learning to Rank: From Pairwise Approach to Listwise Approach. https://blog.csdn.net/Mr_tyting/article/details/80554849
[3]. Scale Calibration of Deep Ranking Models. Le Yan et al.
[4]. Listwise Approach to Learning to Rank-Theory and Algorithm.

---

转载请注明来源, from goldandrabbit.github.io