[Paper] PARWiS：在紧张预算下使用主动成对比较进行胜者判定
Source: arXiv - 2603.01171v1
概述
本文介绍了 PARWiS，一种只通过少量成对比较问题就能从集合中挑选出最佳项目的算法。通过巧妙地选择比较的配对并使用谱排序步骤，PARWiS 即使在预算低至 20 项目仅需 40–80 次比较的情况下，也能恢复出真实的胜者。作者还基于核心思想扩展了两种变体——Contextual PARWiS（利用侧信息）和 RL PARWiS（基于强化学习的配对选择）——并在合成数据以及两个真实推荐数据集（Jester 和 MovieLens）上与流行基线进行对比评估。
关键贡献
- PARWiS algorithm: 将 disruptive pair selection 与 spectral ranking 技术相结合，以最大化每次比较的信息增益。
- Contextual PARWiS: 将项目层面的上下文特征（例如用户人口统计信息、项目元数据）整合到配对选择策略中。
- RL PARWiS: 将配对选择框定为强化学习问题，学习一种能够适应观察到的比较结果的策略。
- Comprehensive empirical evaluation: 将三种变体与 Double Thompson Sampling 以及随机选择基线在合成数据集和真实数据集上进行比较，使用多种预算水平（40、60、80）。
- New performance metrics for low‑budget winner determination: 恢复率、报告获胜者的真实排名、真实获胜者的报告排名、累计后悔以及分离度量 Δ₁,₂（前两项之间的差距）。
方法论
-
问题设定 – 我们有 n 个项目（实验中 n = 20）。学习者可以提出有限数量 B 的两两比较查询（例如，“项目 i 是否比项目 j 更受偏好？”）。目标是输出真正具有最高潜在效用的项目。
-
破坏性配对选择 – 与随机或轮询查询不同，PARWiS 选择 最有可能改变当前排名 的配对。它通过维护一个临时的谱排名（比较矩阵的特征向量），然后挑选出如果进行该比较会导致该特征向量最大位移的配对。
-
谱排名 – 每得到一次新的比较后，算法会更新一个加权邻接矩阵，其中条目 (i, j) 记录 i 战胜 j 的次数。归一化矩阵的左主特征向量作为全局排名估计（类似 PageRank）。
-
上下文扩展 – 当每个项目都有侧信息 xᵢ 时，上下文 PARWiS 会在配对选择得分中加入一个线性模型，用特征预测效用差距，从而使算法倾向于在给定上下文下更具信息量的配对。
-
强化学习扩展 – RL PARWiS 将每一步视为马尔可夫决策过程：
- 状态 = 当前比较矩阵 + 上下文
- 动作 = 选择查询的配对
- 奖励 = 不确定性的降低（或负后悔）
一个策略网络（例如小型前馈 DNN）通过策略梯度在线训练。
-
基线方法
- 双重汤普森抽样 (DTS)：一种贝叶斯 bandit 方法，从后验效用中抽样两个项目并比较它们。
- 随机：在每一步均均匀随机选择一对。
-
评估协议 – 对每个数据集和预算，算法进行多次 Monte‑Carlo 试验。预算耗尽后计算指标，重点关注报告的获胜者与真实最高排名项目的接近程度以及累计后悔的大小。
结果与发现
| 数据集 | 预算 | 指标（越高越好） | PARWiS | RL PARWiS | Contextual PARWiS | DTS | Random |
|---|---|---|---|---|---|---|---|
| Jester (Δ₁,₂ large) | 40 | 恢复比例 | 0.84 | 0.81 | 0.80 | 0.62 | 0.45 |
| 80 | 累计后悔（越低越好） | 0.31 | 0.33 | 0.34 | 0.48 | 0.71 | |
| MovieLens (Δ₁,₂ small) | 40 | 报告获胜者的真实排名 | 3.2 | 3.4 | 3.5 | 5.1 | 7.8 |
| 80 | 真实获胜者的报告排名 | 1.9 | 2.0 | 2.1 | 3.4 | 5.6 |
要点
- PARWiS 和 RL PARWiS 在所有预算下始终优于基线。
- 当前两项之间差距明显（Δ₁,₂ 大）时优势最为突出，如 Jester 数据集。
- 在更模糊的 MovieLens 场景（Δ₁,₂ 小）中，差距收窄，但 PARWiS 仍保持领先。
- Contextual PARWiS 与普通 PARWiS 表现相当；新增特征并未带来明显优势，暗示需要更好的特征工程或更丰富的模型。
Practical Implications
- Recommendation engines 可以使用 PARWiS 通过向用户或众包工作者提出少量 “A vs B” 问题，快速挑选出最有潜力的项目（例如新产品、热门文章），从而节省昂贵的标注成本。
- A/B testing pipelines 可以用 PARWiS‑驱动的抽样取代繁琐的两两测试，以更少的实验次数获得统计上可比的结论。
- Human‑in‑the‑loop ML：当标注员成本高昂（例如医学图像排序）时，PARWiS 会告诉你下一个应呈现的图像对，以在每次标注中最大化诊断洞察。
- RL PARWiS 为自适应、数据驱动的查询策略打开了大门，能够随时间改进，适用于持续收集偏好数据的平台（如音乐流媒体服务）。
- Spectral ranking core 轻量级（对 20 × 20 矩阵进行特征分解几乎不费力），可以直接嵌入微服务，无需重型 GPU。
限制与未来工作
- 可扩展性：当前实验固定 n = 20。将 PARWiS 扩展到数百甚至数千个项目将需要稀疏矩阵技巧或层次分组。
- 上下文特征利用：上下文变体没有产生可测量的提升，这表明所选特征可能不够信息丰富，或者线性模型过于简单。可以探索更具表达能力的模型（例如图神经网络）。
- 强化学习开销：RL PARWiS 增加了策略网络的训练，这在预算极低的场景下可能显得大材小用；在数据稀缺时回退到确定性配对选择器的混合方案可能更高效。
- 静态效用假设：论文假设项目效用在预算期间不漂移。实际系统常常面临非平稳偏好；引入变点检测或在线适应将非常有价值。
结论：PARWiS 表明，通过智能的配对选择和简单的谱排序步骤，即使只能进行几十次比较，也能可靠地挑选出最佳项目。对于构建偏好驱动产品的开发者而言，它提供了一种实用、低成本的替代方案，避免了穷举排序或重量级贝叶斯 bandit 方法的高开销。
作者
- Shailendra Bhandari
Paper Information
- arXiv ID: 2603.01171v1
- Categories: cs.LG, cs.CC, cs.NE
- Published: 2026年3月1日
- PDF: 下载 PDF