When Less Is More: Binary Feedback Can Outperform Ordinal Comparisons in Ranking Recovery¶

讲者: Shirong Xu
会场: Prediction-Powered Inference and Network Data Analysis
报告题目: When Less Is More: Binary Feedback Can Outperform Ordinal Comparisons in Ranking Recovery
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述¶

这个方向是什么¶

这个子方向研究的是基于成对比较数据（paired comparison data）的排序恢复（ranking recovery）问题。核心统计问题是：给定一组物品（items），每个物品有一个潜在的偏好参数 θᵢ，我们只能观测到用户对物品对的比较结果（如“A比B好”或“A比B好很多”），目标是恢复 θ 的排序（ordering），即物品的完整排名。该方向当前已相当成熟，有大量经典参数模型（Bradley-Terry-Luce, Thurstone-Mosteller）和现代算法（计数算法、谱方法、MLE），但一个长期未被挑战的直觉是：序数比较数据（ordinal，如“强烈偏好A”）比二值比较数据（binary，如“偏好A”）包含更多信息，因此理应带来更准确的排序估计。本文正是挑战这一直觉。

发展脉络（history）¶

奠基工作（1950s–1990s）：
Bradley and Terry (1952) 和 Thurstone (1994) 分别提出了二值成对比较的经典参数模型（BTL 和 TM），奠定了用 logistic 或 probit 链接函数建模 P(i ≻ j) = F(θᵢ - θⱼ) 的基础。
Glenn and David (1960)、Rao and Kupper (1967)、Davidson (1970) 将 BTL 模型扩展到包含平局（tie）的三水平序数比较。
Agresti (1992) 进一步引入相邻类别 logit 模型，支持多于三个水平的序数比较，并指出当只有两个类别时退化为 BTL。
Stern (1990) 提出了一个统一框架，将 BTL 和 TM 作为伽马分布形状参数的特例。
主要进展（2010s–2020s）：
Shah and Wainwright (2018) 证明了计数算法（counting algorithm）在排序恢复中的最优性、鲁棒性和计算效率，并指出在大规模比较图中 MLE 的计算负担过重。该文是本文的核心方法参考。
Chen et al. (2019, 2022a, 2022b) 系统研究了谱方法和正则化 MLE 在 top-K 和全排序恢复中的最优性，建立了排序恢复的 minimax 理论。
Han et al. (2022) 提出了一个能同时处理连续和序数观测的广义成对比较框架，其“强度链接函数”概念（对称、单调递增）被本文直接继承。
当前 frontier 与本文位置：
当前前沿关注大规模、稀疏比较图下的排序恢复（如 Shah and Wainwright 2018），以及将比较数据用于 LLM 的人类反馈强化学习（RLHF）（如 Zhu et al. 2023; Poddar et al. 2024）。
本文的位置：在 Han et al. (2022) 的广义框架基础上，专门研究序数 vs 二值数据的排序恢复性能。作者声称这是首次从理论上证明二值化序数数据可以加速排序恢复的指数收敛速率，挑战了“序数数据信息更丰富”的直觉。

子线索聚类¶

线索一：经典参数模型（BTL/TM 及其序数扩展）。包括 Bradley and Terry (1952)、Thurstone (1994)、Glenn and David (1960)、Rao and Kupper (1967)、Davidson (1970)、Agresti (1992)、Stern (1990)。这一簇关注如何用参数形式刻画比较概率。
线索二：排序恢复算法与理论。包括 Shah and Wainwright (2018)（计数算法）、Chen et al. (2019, 2022a, 2022b)（谱方法、MLE 最优性）、Busa-Fekete et al. (2013)（自适应采样）。这一簇关注如何从比较数据中高效、准确地恢复排序。
线索三：广义比较模型。包括 Han et al. (2022)（连续+序数统一框架）、Stern (2011)（连续数据 BTL 扩展）。本文属于这一簇，但专门聚焦于序数 vs 二值的性能对比。

这个方向在追问的核心问题¶

哪种反馈形式（二值 vs 序数）对排序恢复更有效？ 这是本文直接回答的问题。
在什么条件下，信息更少的二值数据反而优于信息更多的序数数据？ 本文给出的答案是：当序数数据的信噪比（SNR）较低时，二值化能大幅降低噪声。
如何刻画序数比较数据的“模式”（pattern）对排序性能的影响？ 本文通过模式函数 ψ_γ 和 SNR(X_γ) 来量化。
计数算法 vs MLE 在排序恢复中的权衡？ 本文在附录 A.2 中进行了实证比较，指出计数算法在 n ≫ L 时更优，MLE 在 n 小 L 大时更优。

⚠️ 作者的 framing¶

作者把缺口 frame 成什么：作者声称“序数比较数据比二值数据包含更多信息”这一直觉在渐近意义下不成立，并证明二值化能加速收敛。作者将本文定位为“首次从理论上揭示这一反直觉现象”的工作。
哪些竞争路线被他淡化或回避了：
MLE 的视角：作者在附录 A.2 中承认，当 ψ_γ 正确指定时，MLE 对 K 和 ψ_γ 的形式是不变的（Theorem A10），即序数和二值数据在 MLE 下给出相同的估计量。这意味着本文的核心结论（二值化更好）仅对计数算法成立，对 MLE 不成立。作者在正文中对此着墨不多，只在附录中提及。
有限样本 vs 渐近：作者的主要结论（Theorem 4 和 6）是渐近的（L → ∞），且需要 L 超过某个阈值 L₀ 才成立。作者在模拟中展示了这个阈值的存在，但未给出 L₀ 的显式界。
什么明显该被引 / 该存在、却没出现在 intro 里？
关于“信息损失”的经典讨论：例如，将连续数据离散化（binning）的信息损失理论（如 Heitjan 1989, Journal of the American Statistical Association）未被引用。本文的“二值化”本质上是一种极端离散化，相关文献可能提供更一般的视角。
RLHF 中二值 vs 序数反馈的实证比较：作者引用了 Zhu et al. (2023) 和 Poddar et al. (2024) 作为 LLM 应用的例子，但未引用任何直接比较二值和序数反馈在 RLHF 中效果的实证论文（如 Ethayarajh et al. 2022, Understanding Dataset Difficulty with V-Usable Information 或类似工作）。这可能是一个值得研究者去查的 gap。

张力¶

未见明显对立引用。所有被引工作基本在各自设定下自洽，没有出现“在相同条件下得出相反结论”的情况。唯一的潜在张力是：计数算法 vs MLE 的优劣取决于 n 和 L 的相对大小（附录 A.2），但这并非矛盾，而是互补。

二、最核心、最简单的例子 / 数学问题¶

第一步：符号、模型、可观测数据交代清楚¶

符号：
θ = (θ₁, …, θₙ)ᵀ：n 个物品的真实偏好参数向量。θᵢ 越大，物品 i 排名越高。为可识别，假设 1ₙᵀθ* = 0。
γᵢⱼ = θᵢ - θⱼ*：物品 i 和 j 之间的偏好差异。
y⁽ˡ⁾ᵢⱼ：第 l 次比较中，物品 i 相对于 j 的序数比较结果。取值于 Υ(K) = { -K, …, -1, 1, …, K }（无平局）。正值表示 i 优于 j，绝对值表示偏好强度。
sign(y⁽ˡ⁾ᵢⱼ)：y⁽ˡ⁾ᵢⱼ 的二值化版本，取值于 { -1, 1 }。
a⁽ˡ⁾ᵢⱼ ~ Bernoulli(p)：观测指示变量，a⁽ˡ⁾ᵢⱼ = 1 表示 y⁽ˡ⁾ᵢⱼ 被观测到。独立于 y。
L：每对物品的最大比较次数。
n：物品数量。
K：序数水平的“半宽度”（正负各 K 个水平，共 2K 个非零水平）。
ϕ(·)：强度链接函数（strength link function），单调递增且奇对称（ϕ(x) = -ϕ(-x)）。
ψ_γ(·)：模式函数（pattern function），关于 k 的偶函数（ψ_γ(k) = ψ_γ(-k)），控制序数水平的分布模式。
G(ϕ, ψ_γ, γ, K)：本文提出的序数比较模型，Y ~ G 表示 Y 的分布由 ϕ、ψ_γ、γ 和 K 参数化。
X_γ ~ Geo(ψ_γ, K)：一个辅助离散随机变量，取值于 [K] = {1, …, K}，其分布由 ψ_γ 通过 softmax 定义：P(X_γ = k) ∝ exp(ψ_γ(k))。用于刻画序数水平的“幅度”分布。
SNR(X_γ) = [E(X_γ)]² / Var(X_γ)：X_γ 的信噪比。
Sᵢ 和 \~Sᵢ：基于原始序数数据和二值化数据的“胜场计数”（win-count）。
模型：
数据生成机制：对于每对物品 (i, j) 和每次比较 l，观测值 y⁽ˡ⁾ᵢⱼ 独立地服从 G(ϕ, ψ_{γᵢⱼ}, γᵢⱼ, K)。其概率质量函数为： P(y⁽ˡ⁾ᵢⱼ = k) = (1 / Ψ) · exp( ϕ(sign(k) · γᵢⱼ) + ψ_{γᵢⱼ}(k) ), k ∈ Υ(K) 其中 Ψ = Σ_{k∈Υ(K)} exp(ϕ(sign(k)γᵢⱼ) + ψ_{γᵢⱼ}(k)) 是归一化常数。
关键结构：ϕ 捕捉偏好差异的方向和强度；ψ_γ 捕捉序数水平的“基线频率”（如极端值出现更少）。ψ_γ 是 γ 的偶函数，且 ψ_γ(k) 关于 k 对称。
当 K=1 时，模型退化为二值比较模型：P(sign(y) = 1) = exp(2ϕ(γ)) / (1 + exp(2ϕ(γ)))。特别地，若 ϕ(x) = x/2，则得到 BTL 模型；若 ϕ(x) = ½ log(Φ(x)/(1-Φ(x)))，则得到 TM 模型。
可观测数据：
可观测：对于每对物品 (i, j) 和每次比较 l，我们观测到 y⁽ˡ⁾ᵢⱼ（若 a⁽ˡ⁾ᵢⱼ = 1）。观测数据是 { y⁽ˡ⁾ᵢⱼ : a⁽ˡ⁾ᵢⱼ = 1, i < j, l ∈ [L] }。
不可观测 / 潜在：真实偏好参数 θ* 是潜在变量，不可直接观测。模式函数 ψ_γ 的具体形式也是未知的（但本文假设其存在且满足偶函数性质）。比较缺失指示 a⁽ˡ⁾ᵢⱼ 是随机缺失的，但缺失机制已知（Bernoulli(p)）。

第二步：讲最小内核——两物品排序问题¶

本文的核心思想可以用一个两物品（n=2）的排序问题来完全体现。这是整篇论文的“最小内核”，所有一般性结果（n 物品、全排序）都是这个特例的推广。

设定：只有两个物品，偏好参数为 θ₁ 和 θ₂。不失一般性，假设 γ = θ₁ - θ₂ > 0，即物品 1 真正优于物品 2。我们观测到 L 次独立比较 y⁽ˡ⁾₁₂ ~ G(ϕ, ψ_γ, γ*, K)，每次以概率 p 被观测到（a⁽ˡ⁾₁₂ ~ Bernoulli(p)）。目标是判断哪个物品更好。
计数算法：定义两个分数：
原始分数：A = (1/L) Σ_{l=1}^L a⁽ˡ⁾₁₂ · y⁽ˡ⁾₁₂
二值化分数：B = (1/L) Σ_{l=1}^L a⁽ˡ⁾₁₂ · sign(y⁽ˡ⁾₁₂) 若 A > 0（或 B > 0），则判定物品 1 优于物品 2。
核心命题（Theorem 3 和 4 的简化版）：当 L → ∞ 时，P(B > 0) 和 P(A > 0) 都趋于 1（即两种方法都能正确排序），但 P(B > 0) 的收敛速度比 P(A > 0) 更快。具体地，存在一个阈值 L₀，使得对所有 L ≥ L₀，有 P(B > 0) > P(A > 0)。这意味着二值化数据在排序恢复中更准确。
为什么？——信噪比分析：
由 Theorem 1(3)，E(y) = tanh(ϕ(γ)) · μ，Var(y) = σ² + μ²(1 - tanh²(ϕ(γ)))，其中 μ = E(X_γ), σ² = Var(X_γ)。
二值化后，E(sign(y)) = tanh(ϕ(γ))，Var(sign(y)) = 1 - tanh²(ϕ(γ))。
定义 SNR(y) = [E(y)]² / Var(y)，SNR(sign(y)) = [E(sign(y))]² / Var(sign(y)) = sinh²(ϕ(γ*))。
由 Theorem 1(3) 的 SNR 公式：SNR(y) = tanh²(ϕ(γ)) / [ 1/SNR(X_γ) + 1 - tanh²(ϕ(γ*)) ]。
由于 SNR(X_γ) < ∞（除非 X_γ 退化），我们有 SNR(y) < SNR(sign(y))，即二值化后的信噪比更高。
直觉：序数数据虽然包含了幅度信息（|y|），但也引入了幅度噪声（Var(|y|) > 0）。二值化丢弃了幅度信息，但同时也丢弃了幅度噪声，从而提高了信噪比。当 L 足够大时，更高的 SNR 转化为更快的收敛速度和更低的错误概率。
关键结论：这个两物品例子揭示了本文的核心机制：二值化是一种“方差减少”技术，它牺牲了信息（幅度）但换来了更低的噪声，在渐近意义下反而提升了排序性能。性能提升的程度由 SNR(X_γ) 决定：SNR(X_γ) 越小（即序数水平的幅度分布越分散），二值化的收益越大。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在成对比较数据的排序恢复问题中，比较序数比较数据（ordinal）与二值比较数据（binary）的性能，挑战“序数数据信息更丰富”的直觉。
核心工具 / 方法：提出了一个广义加性序数比较模型 G(ϕ, ψ_γ, γ, K)，将二值模型作为特例（K=1）纳入；使用计数算法（counting algorithm）进行排序恢复，并借助大偏差理论（Cramér's Theorem）和信噪比分析来比较两种数据的渐近性能。
主要结论：在计数算法下，二值化序数数据可以显著加速排序恢复的指数收敛速率（Theorem 4, 6）；性能差距由模式函数 ψ_γ 的信噪比 SNR(X_γ) 决定，SNR 越小收益越大（Theorem 3）；刻画了使 SNR 最小化的模式函数，即二值化收益最大的情形（Theorem 7, 8）。

关键设定与假设¶

模型假设：
无平局：y 取值于 Υ(K) = { -K, …, -1, 1, …, K }，不含 0。附录 A.1.1 讨论了含平局的扩展，通过将平局视为缺失来处理。
强度链接函数 ϕ：单调递增且奇对称（ϕ(x) = -ϕ(-x)）。这保证了 P(y>0) = exp(2ϕ(γ)) / (1 + exp(2ϕ(γ)))，且 sign(y) 的分布仅由 ϕ 决定。
模式函数 ψ_γ：关于 k 的偶函数（ψ_γ(k) = ψ_γ(-k)），且是 γ 的偶函数。这保证了模型的可识别性（Theorem 1 的证明中用到）。
随机缺失模式：a⁽ˡ⁾ᵢⱼ ~ Bernoulli(p)，独立于 y。比较图是 Erdős–Rényi 随机图。
可识别性约束：1ₙᵀθ* = 0。
相比已有文献的放宽或强化：
放宽：相比经典的 BTL/TM 模型（仅二值），本文模型支持任意 K 个序数水平。
强化：相比 Han et al. (2022) 的广义框架，本文专门假设了 ψ_γ 是 γ 的偶函数，这简化了理论分析（Theorem 1 的 SNR 公式推导）。
关键假设：ψ_γ 是 γ 的偶函数。这个假设在 Han et al. (2022) 中也有，但本文未讨论如果这个假设被违反会怎样。这是值得注意的。

主要结果¶

Theorem 1（模型性质）：给出了 G 模型下 y 的分布性质，包括 P(y>0) 的表达式（与 ϕ 有关，与 ψ_γ 无关）、对称性、以及 SNR 的显式公式。关键：SNR(y) = tanh²(ϕ(γ)) / [ 1/SNR(X_γ) + 1 - tanh²(ϕ(γ)) ]，且当 K=1 时 SNR(y) = sinh²(ϕ(γ)) 达到最大。
Theorem 2（与经典模型的联系）：当 K=1 且 ϕ 取特定形式时，G 模型退化为 BTL 或 TM 模型。
Theorem 3（两物品渐近性能）：给出了 P(A>0) 和 P(B>0) 的渐近正态近似（通过 CLT），并证明 P(B>0) 的渐近极限大于 P(A>0) 的极限。关键：差距由 Δ(γ) = 1 / [ SNR(X_γ) · tanh²(ϕ(γ)) ] 决定，SNR(X_γ) 越小差距越大。
Theorem 4（两物品指数收敛速率）：核心定理。证明 lim_{L→∞} P(B ≤ 0) / P(A ≤ 0) = 0，即二值化数据的错误概率以更快的指数速率收敛到 0。证明使用了 Cramér 大偏差定理（Theorem A11）和 Lemma A1，比较了两种数据的速率函数（rate function）I₁(0) 和 I₂(0)，并证明 I₁(0) > I₂(0)。
Theorem 5（多物品排序一致性）：证明基于 S 和 \~S 的排序都几乎必然收敛到真实排序。
Theorem 6（多物品全排序误差比率）：核心定理。证明 lim_{L→∞} E[τ(\~S, θ)] / E[τ(S, θ)] = 0，即二值化数据的全排序误差（Kendall tau 距离）以更快的速率收敛到 0。证明思路复杂，涉及对 I(Sᵢ ≤ Sⱼ) 的精细分解和 Lemma A3 的应用。
Theorem 7（无约束下最小 SNR）：SNR(X_γ) ≥ 4K / (K-1)²，等号在 X_γ 为两点分布（取值 1 和 K）时达到。这意味着当序数水平集中在极端值时，二值化收益最大。
Theorem 8（单调约束下最小 SNR）：当 ψ_γ 非增（即 P(X_γ = k) ≥ P(X_γ = k+1)）时，SNR(X_γ) ≥ 24(K+1) / (4K² - 4K + 1)，等号在 X_γ 在 {2, …, K} 上均匀分布且额外质量在 1 上时达到。这更符合真实数据（极端值出现更少）的模式。

证明路线与技术技巧¶

整体路线（以 Theorem 4 为例）：
问题转化：将 P(B > 0) > P(A > 0) 等价于 P(-B ≥ 0) < P(-A ≥ 0)。
大偏差分析：应用 Cramér 定理（Theorem A11），将 P(-B ≥ 0) 和 P(-A ≥ 0) 的指数收敛速率分别与速率函数 I₁(0) 和 I₂(0) 联系起来。
计算速率函数：利用 Lemma A1，计算 I₁(0) 和 I₂(0) 的显式表达式。关键步骤是计算 MGF：E[exp(-λ a y)] 和 E[exp(-λ a sign(y))]。
比较速率函数：证明 I₁(0) > I₂(0)。这依赖于 Jensen 不等式和 cosh 的凸性，以及 X_γ 非退化的假设。关键跳跃点：Lemma A1 中 Q(p, γ*) > 0 的证明，它依赖于 cosh 的凸性和 Jensen 不等式。
结论：由于 I₁(0) > I₂(0)，P(-B ≥ 0) 以更快的指数速率衰减，因此对于足够大的 L，P(B > 0) > P(A > 0)。
关键跳跃点：
Lemma A1 的证明：计算 MGF 并化简为包含 cosh(ϕ(γ) + λk) 的项。这是连接模型 G 和大偏差理论的关键。
Theorem 4 中 I₁(0) > I₂(0) 的证明：需要证明 Q(p, γ) > 0。作者使用了 Jensen 不等式：由于 cosh 是凸函数，加权平均 cosh(ϕ(γ) + λk) 大于 cosh(ϕ(γ) + λ E[X_γ])。由于 X_γ 非退化，不等式严格成立，从而 Q(p, γ) > 0。
Theorem 6 的证明：将全排序误差 E[τ(S, θ)] 分解为所有物品对 (i, j) 的 P(Sᵢ ≤ Sⱼ) 之和。然后对每个 P(Sᵢ ≤ Sⱼ) 进行复杂的组合分解（Step 1），并利用 Lemma A3 证明 P(\~Sᵢ ≤ \~Sⱼ) / P(Sᵢ ≤ Sⱼ) → 0。关键*：Lemma A3 再次使用大偏差理论，证明对于任意一对物品，二值化数据的错误概率以更快的指数速率衰减。
技术技巧点名：
Cramér 大偏差定理：用于刻画错误概率的指数收敛速率（Theorem 4, Lemma A1, Lemma A3）。
Jensen 不等式 + cosh 凸性：用于证明 Q(p, γ*) > 0，这是比较速率函数的关键。
组合分解：在 Theorem 6 的证明中，将 P(Sᵢ ≤ Sⱼ) 分解为关于所有其他物品的胜场计数的组合和，这是处理多物品排序复杂性的标准技巧。
CLT 近似：用于 Theorem 3 的渐近正态分析，提供直观的 SNR 解释。
线性规划 + 两点分布：用于 Theorem 7 中最小化 SNR 的推导，证明最优分布是两点分布。

真实例子与应用¶

数据：MovieLens 100K 数据集（Harper and Konstan, 2015）。
场景：用户对电影的评分（1-5 星）。作者筛选出被至少 200 次评分的电影，对每个用户，计算其所有已评分电影对的评分差（非零），作为序数比较数据。
方法应用：
对每对电影，随机划分 70% 的比较数据为训练集，30% 为测试集。
在训练集上，用两种方法估计偏好方向：
- 序数方法：计算评分差之和的符号。
- 二值方法：计算评分差符号之和的符号。
在测试集上，用估计的偏好方向预测比较结果，计算预测准确率。
重复 100 次，得到稳定估计。
结果：
左图（Figure 10a）：二值方法的预测准确率显著高于序数方法（配对 t 检验：t = 18.5978, p = 3.4 × 10⁻⁷⁷）。
右图（Figure 10b）：当二值方法表现更好时，对应的比较次数（样本量）通常更大。这与 Theorem 4 的结论一致：二值化优势在 L 足够大时显现。
这个例子想说明什么：验证了理论结果在真实数据上的有效性，表明二值化在推荐系统场景中确实能提升排序/偏好预测的准确性。

🔎 结论是否比证明窄¶

是。本文的核心结论“二值化优于序数”严格依赖于计数算法。作者在附录 A.2 中明确证明（Theorem A10）：当模式函数 ψ_γ 正确指定时，MLE 对 K 和 ψ_γ 的形式是不变的，即序数和二值数据在 MLE 下给出相同的估计量。这意味着本文的结论不适用于 MLE。作者在正文中对此着墨不多，仅在附录中提及，并在附录 A.2 的模拟中承认 MLE 在 n 小 L 大时优于计数算法。这是一个重要的窄化。
此外，结论是渐近的（L → ∞），且需要 L 超过某个阈值 L₀。作者在模拟中展示了 L₀ 的存在，但未给出其显式界。在有限样本下，序数数据可能仍然更好（如 Figure 4 中 L 较小时红色曲线高于蓝色曲线）。

四、开放问题（点到为止，扎根具体语句）¶

有限样本下的显式阈值 L₀：Theorem 4 和 6 保证了存在 L₀ 使得二值化更优，但未给出 L₀ 的显式表达式。能否给出 L₀ 关于 γ、p、ψ_γ 和 K 的显式界？这需要更精细的 Berry-Esseen 型或大偏差非渐近界。扎根于 Theorem 4 的陈述：“there exists a positive integer L₀ (depending on γ₁₂, p and ψ_{γ*₁₂})”。
MLE 下的性能比较：本文的核心结论仅对计数算法成立。在 MLE 下，序数和二值数据是否等价（Theorem A10）？如果 ψ_γ 被误设，MLE 下是否也会出现类似的反直觉现象？这是一个自然的延伸。扎根于附录 Theorem A10 及其讨论。
模式函数 ψ_γ 的估计：本文假设 ψ_γ 是已知的（或至少其形式被正确指定）。在实际应用中，ψ_γ 是未知的。如何从数据中估计 ψ_γ？如果 ψ_γ 被误设，本文的结论是否仍然稳健？扎根于模型设定中对 ψ_γ 的依赖。
含平局（ties）的扩展：附录 A.1.1 讨论了将平局视为缺失的扩展，但未给出完整的理论分析。在含平局的设定下，二值化是否仍然优于序数？平局概率 s 如何影响阈值 L₀？扎根于附录 A.1.1 的讨论。

Maintained by 陈星宇 · Homepage · Source on GitHub