第 5 题：ListNet vs ListMLE，Listwise 方法的计算复杂度瓶颈在哪里？
题目
ListNet vs ListMLE，Listwise 方法的计算复杂度瓶颈在哪里？
完整讲解
一、Listwise 思想
Listwise 方法用整个文档列表作为训练单位，损失基于列表级的排列或概率，与 NDCG 等列表指标更一致。常见两种：ListNet（基于排列概率的 top-one 近似） 与 ListMLE（基于列表似然）。
二、ListNet
- 把「理想排序」和「预测排序」都看成排列分布；ListNet 用 top-one 概率来近似：即「排第一的文档是哪个」的分布。
- 理想 top-one：按标签得分做 softmax；预测 top-one：按模型得分做 softmax。损失为两者之间的交叉熵（或 KL），即对「谁该排第一」的分布做 CE。
- 复杂度：只需对当前列表做一次 softmax（按标签/按预测），O(L) 前向与梯度，L 为列表长度；不枚举排列，因此可行。但 top-one 只是排列的一个粗糙近似，对「第二、第三是谁」不直接建模。
三、ListMLE
- 用列表似然：把「正确排序」视为一个排列 $\pi^$，定义在给定模型下该排列的似然（即按 $\pi^$ 顺序依次「当前文档排第一」的连乘概率），取负对数作为损失。
- 形式等价于：按真实顺序依次做 softmax（每次在「剩余文档」中选当前最相关的），损失 = 这些 softmax 的负对数和。
- 复杂度：要按顺序做 L 次 softmax，每次候选集从 L 减到 L-1、…、1，单样本是 O(L²) 级别（或 O(L) 次、每次 O(L) 的 softmax）；列表越长越贵，且实现要处理「剩余集合」的 mask 与归一化。
四、Listwise 的复杂度瓶颈
- 排列空间巨大：完整排列分布有 L! 种，无法显式计算。ListNet 用 top-one 近似，避免枚举；ListMLE 用似然，只沿一条正确路径计算，但也要沿路径做多次 softmax。
- 瓶颈：
- ListNet：单列表 O(L)，瓶颈在列表长度 L 和 batch 内列表数；可接受。
- ListMLE：单列表 O(L²) 或 O(L·L)，L 大时（如 L=100）明显变慢；且需要「按真实顺序」构造计算图，实现更复杂。
- 工程上：常对列表做截断（只取 top-L），或采样子列表；或改用 Pairwise（RankNet/LambdaRank）折中复杂度与效果。
面试要点
- ListNet：用 top-one 概率近似排列分布，损失为两分布 CE；复杂度 O(L)，不枚举排列。
- ListMLE：列表似然，按真实顺序依次 softmax 连乘取负对数；复杂度 O(L²) 级，L 大时贵。
- Listwise 瓶颈：排列数 L! 不可枚举；ListNet 用 top-one 降为 O(L)；ListMLE 沿一条路径但要多次 softmax，O(L²)。
记忆要点
- ListNet：top-one 排列近似 + CE，O(L)。
- ListMLE：列表似然，按真实顺序多次 softmax，O(L²)。
- 瓶颈：ListNet 可接受；ListMLE 的 L 次 softmax 与剩余集合处理是主要成本。