概
Listwise Ranking.
ListNet
-
以文档检索为例, 假设我们有 query \(q\) 和一堆候选的文档 \(\mathcal{D} = \{d_1, d_2, \ldots, d_n\}\), 我们希望训练一个 score function \(f(\cdot)\), 得到 scores:
\[\{s_1 = f(d_1), \ldots, s_n = f(d_n)\}. \] -
根据这些 scores, 我们可以对检索结果进行排序,
\[[r_1, r_2, \ldots, r_n], \]其中 \(s_{r_k}\) 表示所有文档中排第 \(k\) 个的文档的 score. 于是我们可以推荐一些靠前的 (因为我们认为它们是更靠谱的).
-
本文的目的是设计一个 listwise 的损失, 促使排序结果
\[[r_1, r_2, \ldots, r_n] \approx [y_1, y_2, \ldots, y_n], \]这里 \([y_1, y_2, \ldots, y_n]\) 为真实的偏好排序.
Permutation Probability
-
假设 \(\pi = [\pi_1, \pi_2, \ldots, \pi_n]\) 为 \([n] = [1, 2, \ldots, n]\) 的一个 permutation, 本文希望根据 scores 在空间 \(\Omega_n := \{\pi\}\) 上建立一个分布.
-
概率是如此定义的:
\[\tag{1} \mathbb{P}_s(\pi) = \prod_{j=1}^n \frac{\phi(s_{\pi_j})}{\sum_{k=j}^n \phi(s_{\pi_k})}, \quad \forall \pi \in \Omega_n. \]这里 \(\phi\) 常常取 \(\exp(\cdot)\).
-
一个比较关键的东西是证明它满足概率的一些性质, 非负性只需取合适 \(\phi(\cdot)\) 即可. 下面证明
\[\tag{2} \sum_{\pi \in \Omega_n} \mathbb{P}_s(\pi) = 1. \] -
让我们定义位置给定候选集合 \(\mathcal{C} \subset [n]\), 位置 \(i\) 排在首位的概率为:
\[P(i \text{ is top-1}|i \in \mathcal{C}) = \left \{ \begin{array}{ll} \frac{\phi(s_i)}{\sum_{j \in \mathcal{C}} \phi(s_j)} & i \in \mathcal{C} \\ 0 & i \not \in \mathcal{C} \end{array} \right .. \] -
设想给定一个候选集合 \(\{n\}:=\{1, 2, \ldots, n\}\) 和其上的 scores \(\{s_1, s_2, \ldots, s_n\}\), 我们按照如下方式不放回采样:
- 根据概率 \(P(i \text{ is top-1}| \{n\})\) 采样 \(\pi_1\);
- 根据概率 \(P(i \text{ is top-1}| \{n\} \setminus \{\pi_1\})\) 采样 \(\pi_2\);
- 根据概率 \(P(i \text{ is top-1}| \{n\} \setminus \{\pi_1, \pi_2\})\) 采样 \(\pi_3\) ...
n. 得到 \([\pi_1, \pi_2, \ldots, \pi_n]\).
-
显然,
\[\mathbb{P}_s(\pi) = P(\pi_1 \text{is top-1}|\{n\}) \cdot P(\pi_1 \text{is top-1}|\{n\} \setminus \{\pi_1\}) \cdot \cdots =\prod_{j=1}^n \frac{\phi(s_{\pi_j})}{\sum_{k=j}^n \phi(s_{\pi_k})}. \] -
于是我们成功构造了一个采样过程, 条件 (2) 是成立的.
-
(1) 还有一些很不错的性质, 既然这个分布是依照 scores 设计的, 我们很自然地希望 score 越大的位置靠前的考虑越大. 实际上, 可以证明, 如果 \(s_1 \ge s_2 \cdots \ge s_n\), 我们有
\[\tag{3} \mathbb{P}_s([n]) \ge \mathbb{P}_s(\pi) \ge \mathbb{P}([n, n-1, \ldots, 1]), \forall \pi \in \Omega. \] -
此外, 对于如下的序:
\[\tag{4} \pi = [\cdots, \pi_i, \cdots, \pi_j \cdots], \]如果仅交换 \(\pi_i, \pi_j\) 得到 \(\pi'\) 且 \(s_{\pi_i} > s_{\pi_j}\), 则
\[\mathbb{P}_s(\pi) > \mathbb{P}_s(\pi'). \] -
注: 上面的只要需要证明:
\[\pi = [\pi_i, \cdots, \pi_j] \]这一特殊情形即可.
Top-k Probability
-
有些时候, 我们对于 ranking 的要求不是这么严格, 即通常我可以只要求 Top-k 的 ranking 和 target 尽量一致即可.
-
定义:
\[\mathscr{G}_k(y_1, y_2, \ldots, y_k) = \{\pi \in \Omega_n| \pi_j = y_j, \forall j=1,2,\ldots k\}. \] -
于是, 对应的 Top-k 的概率为:
\[\tag{5} \mathbb{P}_s(\mathscr{G}_k(y_1, y_2, \ldots, y_k)) = \sum_{\pi \in \mathscr{G}(y_1, y_2, \ldots,y_k)} \mathbb{P}_s(\pi). \] -
然而, 这种计算方式需要计算得到 \(n \cdot (n-1) \cdots (n-k + 1) = \frac{n!}{(n-k)!}\) 种 \(\mathbb{P}_s(\pi)\) 然后求和, 过于复杂了.
-
幸好 (5) 有一种极为方便的计算方式, 它等价于:
\[\mathbb{P}_s(\mathscr{G}_k(y_1, y_2, \ldots, y_k)) = \prod_{t=1}^k \frac{\phi(s_{y_t})}{\sum_{j=t}^n \phi (s_{y_t})}. \] -
它依旧可以通过采样的方式理解, 只是这一次我们进行到第 \(k\) 次采样便停止.
- approach Learning pairwise listwise toapproach learning pairwise listwise applications approaches extraction learning learning xgboost rank to predictron end-to-end end learning articles learning to english sim-to-real locomotion learning unsensed listwise pairwise pairwise策略 pairwise modulo 1553 cf