SODA 2020 | 只需少量问题的多问题同伴预测
关键词：peer prediction
导读
本文是离散算法国际研讨会（SODA 2020）入选论文《只需少量问题的多问题同伴预测（Dominantly Truthful Multi-task Peer Prediction with a Constant Number of Tasks）》的解读。该论文作者为北京大学前沿计算研究中心助理教授孔雨晴博士。
Arxiv link: https://arxiv.org/abs/1911.00272
背景介绍
传统算法可能会假设算法的输入已经给定，我们只要专注于高效算法的设计与分析即可。然而在现如今的世界中，算法的输入并非给定，且往往是从大规模人群中收集的（譬如众多推荐系统算法）。这种情况下，对算法输入质量的控制变得十分重要。在这个时候，不仅是算法的设计，信息收集机制的设计也成为了一个重要问题。
然而，这个问题面临了一个核心挑战：需要收集的信息可能具有主观性（如餐厅评论），且不像大多数标准数学题的答案那样具有可验证性。因此，对这种主观信息的收集与评估就成为了一个核心问题。
解决的问题
本篇论文就是在这种情境下考虑了一种特殊设定下的不可验证信息收集评估机制问题。具体来说，该论文考虑了收集人群对一系列相似的主观多选题反馈的机制设计问题（如询问：1. 你喜欢学一食堂吗？2. 你喜欢学五食堂吗？3. 你喜欢勺园吗？4. 你喜欢燕南食堂吗？或1. 你喜欢蔡徐坤吗？2. 你喜欢吴亦凡吗？3. 你喜欢鹿晗吗？4. 你喜欢高晓松吗？）。如果我们付给回答者同样的钱，那么他们可能并没有动力诚实回答。如果我们根据大家是否服从“大众选择”来支付大家奖励，那么少数派将不会被激励。
喜欢？不喜欢？……
之前的工作已经成功设计出了一系列具有好的激励性质的奖励机制。这些奖励机制通过根据人们喜好的相关性设计出相应的奖励。如果一个回答者和其他回答者的答案非常相关，哪怕是负相关，这个回答者的奖励就会高。在这些机制下，理论上来说，每个人的最优选择就是诚实地回答自己的喜好，哪怕自己的口味和大众并不相符。然而，这些机制有一个致命的问题让它们很难被应用到实际中：它们需要参与者回答大量的问题，从而学习参与者之间的喜好关系（正相关、负相关或更复杂的关系），由此来支付参与者的奖励。
本篇工作解决了该问题，并提出了第一个只需要少量常数问题的奖励机制，DMI-机制。这个机制的运行非常简单，不需要任何相关先验知识（如参与者之间的喜好关系），适用于任何参与者类型（参与者不需要拥有同质背景）。同时，这个机制拥有几乎最优的理论性质：不管别人怎么样，每个人的最优选择就是诚实地回答自己的喜好。这个机制也可以被用来评估大众反馈的质量：在一些条件下，拥有高奖励的人大概率也给出了高质量的反馈。
这个机制的核心即是本篇工作提出的一个新的信息量测量公式，DMI。它是基于两个离散随机变量的联合分布矩阵的行列式的互信息。它也被证明在解决机器学习领域的噪音标签问题起到核心作用[1]。
下图描述了 DMI-机制的运行过程：我们考虑只有两个参与者的情况（多个参与者的情况可以简化成为只有两个参与者的情况）。下图左侧为机制收集的两个参与者的回答情况。他们一共回答了11道是否题。1代表喜欢，0代表不喜欢。这11道题是按照不同顺序随机发给这两位参与者的。机制将问题任意分成两类，保证每一类大于多选题的选择个数 C。在这个具体的例子里，C=2。对于每一类问题集，我们将参与者的答案转化成为一个 C×C 的计数矩阵。在这个具体的例子里，因为两位参与者在上面的问题集里，同时不喜欢一个食堂/明星，因此矩阵左上角的计数为1。其它的情况也类似。两个矩阵的行列式乘积即为参与者的奖励。
注意，在上述例子中，虽然两个参与者的喜好是负相关的（导致两个计数矩阵的行列式均为负值），但其乘积仍然为正数。
结论及应用
本篇工作理论上证明了以上 DMI-机制的有效性。本篇工作的一个自然的衍生便是 DMI-机制在真实场景下的直接应用。除了餐厅评论以外，其它可能的场景还包括论文同行评议，大规模作业互相批改，学生对老师的教学评估等等。
Reference:
[1] Y. Xu*, P. Cao*, Y. Kong, Y. Wang, "LDMI: A Novel Information-theoretic Loss Function for Training Deep Nets Robust to Label Noise," to appear in NeurIPS 2019.
SODA
离散算法国际研讨会（ACM-SIAM Symposium on Discrete Algorithms, SODA）由计算机协会（ACM）和工业与应用数学学会（SIAM）两大国际学术组织联合主办，与 STOC、FOCS 一起被公认为是算法领域的三大顶级学术会议。SODA 2020将于2020年1月5-8日在美国盐湖城举行。
近 期 科 研 进 展
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。