🤖 machine learning

Finding the Signal in the Spam: Jointly Learning Rewards and Worker Reliability from Pairwise Comparisons

本文提出了一种基于期望最大化（EM）的算法，该算法通过利用 Polya-Gamma 隐变量将玻尔兹曼理性模型（Boltzmann-rational model）转化为一个易于处理的矩阵感知问题，从而从带有噪声的两两比较中联合学习项目奖励和工人可靠性，并证明了其在众包场景下针对欺诈者和对抗性工人的卓越鲁棒性。

原作者： Kaustubh Shivshankar Shejole, Tanish Agarwal, Arpit Agarwal, Avishek Ghosh

发布于 2026-08-12

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Kaustubh Shivshankar Shejole, Tanish Agarwal, Arpit Agarwal, Avishek Ghosh

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图找出镇上最好的披萨。你请了一百位朋友投票选出哪种切片更好吃：是意大利香肠味还是芝士味。你的大多数朋友都给出了诚实且深思熟虑的答案。但也有少数人在瞎猜，因为他们饿了，根本没看披萨。有一位朋友是个恶作剧者，总是为了抬杠而故意选错；还有一位朋友因为太累了，无论配料是什么，都只是机械地点击左边的按钮。如果你只是简单地统计票数，你的“最佳披萨”名单就会被这些不可靠的声音搞得一团糟。这正是**众包（crowdsourcing）**的核心问题：让一群人做决策，但要应对并非每个人都在认真观察、甚至有人在刻意误导你的情况。

在计算机科学领域，这被称为“从成对比较中学习（learning from pairwise comparisons）”。这就是推荐系统决定下一步向你展示哪部电影，或者人工智能模型通过人类反馈来学习如何写出更好文章的方式。目标是根据“谁胜过谁”的关系，找到每个项目的隐藏“分数”或“奖励”。但要准确做到这一点，你必须解决一个棘手的谜题：在没有“金标准”答案进行校验的情况下，你如何知道哪些朋友在说实话，而哪些人在灌水？这篇论文深入探讨了这一混乱局面，试图将信号（真实的偏好）与噪声（垃圾信息）分离出来。

来自印度理工学院孟买分校（IIT Bombay）的研究团队提出了一种巧妙的新方法来解决这个谜题，称为 BoRaEM。该方法并不假设每个人都同样聪明，也不试图预先寻找一份单独的“优秀工人”名单，而是同时学习两件事：每个项目的真实得分以及每个工人的胜任程度。他们使用了一个名为“玻尔兹曼理性（Boltzmann-rational）”的模型，该模型想象每个工人都有一个“理性旋钮”。如果旋钮设定为 1，则该工人是完美的专家；如果设定为 0，则是一个随机点击按钮的灌水者；如果设定为 -1，则是一个试图破坏结果的对手。

这篇论文中的数学魔术在于使用了一种被称为“Polya-Gamma 变量”的技术。你可以把它想象成在食谱中加入了一种秘密配料，能将一个杂乱、无法烹饪的方程变成一个平滑、易于求解的方程。这使得他们能够使用一种称为“期望最大化（EM）”的算法，通过迭代地猜测得分和工人技能，然后不断优化这些猜测，直到它们稳定在最可能的答案上。他们在数学上证明了这个过程是稳定的，并且即使在数据有噪声的情况下也能收敛到一个良好的解。

当他们在模拟数据和真实世界数据集（例如通过比较面孔来判断谁看起来更年长，或评判阅读文章的难度）上进行测试时，他们的方法脱颖而出。在注入了高达 44% 的灌水者（涵盖从随机点击者到恶意撒谎者）的模拟实验中，BoRaEM 依然保持冷静。当旧方法崩溃失败时，BoRaEM 依然表现稳健，能够正确识别出真实的排名。论文表明，通过共同学习谁是可靠的以及各项指标的价值，我们可以构建出更加值得信赖的排序系统，即便是在一个充满噪声和不良行为者的世界里。它并不是能瞬间解决一切的魔杖，但它提供了一种强大的、具有理论依据的方法，让我们能在充满谎言的人群中寻找到真相。

技术摘要：从垃圾信息中寻找信号

问题定义

本文研究了如何从通过众包平台（如 Amazon Mechanical Turk）收集的成对比较数据中学习项目奖励（item rewards）的挑战。在这种场景下，比较任务通常由大量具有显著异质性的工人进行。这些工人可能是理想的标注者，也可能是随机垃圾发送者（以均匀分布进行随机标注），或者是对抗性代理（故意提供反向响应）。

核心问题是从包含 $N$ 个成对比较的数据集 $D = \{(w_i, l_i, s_i)\}_{i=1}^N$ 中联合估计两个潜在向量：

项目奖励 ( $r \in \mathbb{R}^K$ )： $K$ 个项目的底层质量得分。
工人能力 ( $\beta \in [-1, 1]^M$ )： 每个工人 $M$ 的可靠性参数。

作者采用了 Boltzmann-rational 模型，这是对 Bradley–Terry–Luce (BTL) 模型的扩展。在该模型中，工人 $s$ 偏好项目 $w$ 优于项目 $l$ 的概率为：
$P[w \succ l \mid s] = \sigma(\beta_s(r_w - r_l))$
其中 $\sigma$ 是逻辑函数（logistic function）。此处 $\beta_s = 1$ 代表理想标注者， $\beta_s = 0$ 代表随机垃圾发送者， $\beta_s = -1$ 代表对抗性工人。目标是在无法获取金标准（gold-standard）数据集的情况下恢复 $r$ 和 $\beta$ ，这在现实世界的众包场景中是一个常见的限制，因为获取真值（ground truth）既昂贵又困难。

方法论：BoRaEM

作者提出了 BoRaEM，一种旨在处理该模型中直接极大似然估计（MLE）非凹性（non-concave）问题的期望最大化（EM）算法。

1. Pólya-Gamma 增广

为了将难以处理的逻辑似然函数转换为易于处理的形式，该方法采用了 Pólya-Gamma (PG) 增广 (Polson et al., 2013)。通过引入每个比较的潜在变量 $\omega_i \sim \text{PG}(1, 0)$ ，逻辑似然被重写为条件高斯形式。这使得对数似然可以表示为 M 步中的二次目标函数，从而促进高效优化。

2. EM 算法

E-步（E-Step）： 给定当前的奖励估计值 ( $r^{(t)}$ ) 和能力估计值 ( $\beta^{(t)}$ )，算法计算潜在 PG 变量的期望 $\kappa_i^{(t)} = \mathbb{E}[\omega_i \mid \eta_i^{(t)}]$ ，其中 $\eta_i^{(t)} = \beta_s^{(t)}(r_w^{(t)} - r_l^{(t)})$ 。该期望可以通过双曲正切函数以闭式解形式导出。
M-步（M-Step）： 算法使用 交替最大化（Alternating Maximization, AM） 对 $\beta$ $β$ 和 $r$ $r$ 进行最大化，以最大化期望完全数据对数似然（Q 函数）：
- 更新 $\beta$ ： 每个工人的能力更新是基于奖励差值的加权和的闭式解。
- 更新 $r$ ： 项目奖励的更新涉及求解线性系统 $Hr = b $。矩阵$ H$ 是由当前的能力估计和 PG 期望构建的。为了确保可识别性（由于模型在缩放和平移下具有不变性），奖励在每次迭代后都会被中心化至零均值并归一化为单位均方根。

3. 理论收敛性

一个关键的理论贡献是将 M 步优化重新表述为一个 秩-1 矩阵感知问题（rank-1 matrix sensing problem）。通过定义矩阵 $X = \beta r^\top$ ，M 步变为最小化 $\|A(\beta r^\top) - u\|_2^2$ ，其中 $A$ 是一个线性算子。

作者证明，在温和的假设下（工人与项目的均匀采样），算子 $A$ 满足 限制等距性质（Restricted Isometry Property, RIP）。
利用非凸低秩矩阵恢复的结果 (Park et al., 2017)，他们建立了 M 步目标函数的每一个局部最小值都接近全局最小值的结论。
因此，证明了 EM 算法单调增加似然值，并收敛至一个驻点，且每一步的估计误差都受到真实矩阵的内在秩-1 近似误差的限制。

实验结果

作者在合成数据集和真实世界数据集（FaceAge 和 Reading Difficulty/Passage）上评估了 BoRaEM，并将其与包括标准 BTL、RankCentrality (RC)、CrowdBT、FactorBT、BARP、HBTL 和 HTCV 在内的基准方法进行了比较。

关键发现：

对垃圾发送者的鲁棒性： 在合成实验中，当垃圾发送者（随机、位置偏差、对抗性）的比例变化至约 44% 时，BoRAEM 与 HBTL 和 HTCV 一样保持了较高的性能（通过 Kendall's Tau、准确率和加权准确率衡量）。相比之下，未显式建模工人能力的方法（如 BT、RC、BARP）性能显著下降。
可扩展性： 随着工人数量 ( $M$ ) 和项目数量 ( $K$ ) 的增加，BoRAEM 保持稳定，在稀疏测量机制下表现优于 CrowdBT。
真实世界表现： 在 FaceAge 数据集上，BoRAEM 在所有方法中取得了最佳整体性能。在规模较小且具有主观性的 Reading Difficulty 数据集上，它保持了竞争力，尽管所有方法都面临着任务固有难度的挑战。
效率： 由于 M 步中的闭式更新，BoRAEM 展示了与其它先进方法相比具有竞争力的运行时间。

意义与主张

本文声称提供了一个用于处理众包排序中多样化垃圾行为的 统一框架。其主要意义在于：

联合学习： 成功地在不需要金标准数据集进行初始化的情况下，同时学习项目奖励和工人能力。
理论保证： 为这种特定的 Boltzmann-rational 公式提供了理论收敛保证，证明了在 RIP 条件下，算法收敛于接近全局最优解的解。这建立并扩展了先前关于类似模型（如 Jin et al. [2020]）的理论工作。
实际有效性： 证明了其针对对抗性和随机噪声的强大鲁棒性，使其成为现实世界平台中处理异质且未知工人质量问题的可行替代方案。

作者将其工作定位为现有方法的理论驱动型替代方案，特别是在无法忽略恶意或低质量标注者的场景下。