Optimistic Knowledge Gradient Policy for Optimal Budget Allocation in Crowdsourcing
Optimistic Knowledge Gradient Policy for Optimal Budget Allocation in Crowdsourcing
复制标题
DOI：
--
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
X. Chen;Qihang Lin;Dengyong Zhou
中科院分区：
文献类型：
--
作者：
X. Chen;Qihang Lin;Dengyong Zhou
在真实的众包应用中，来自群体的每个标签通常都有一定的成本。给定一个预先确定的预算，由于不同的任务有不同的模糊度，不同的工人有不同的专业知识，我们希望找到一种最佳的方式来分配预算之间的实例工人对，使整体标签质量可以最大化。为了解决这个问题，我们从最简单的设置开始，假设所有工人都是完美的。我们制定了一个贝叶斯马尔可夫决策过程（MDP）的问题。使用动态规划（DP）算法，可以获得最优分配政策，为给定的预算。然而，DP在计算上是难以处理的。为了解决计算上的挑战，我们提出了一种新的近似策略，称为乐观知识梯度。它实际上是有效的，而理论上它的一致性可以得到保证。然后，我们扩展的MDP框架来处理不均匀的工人和任务的上下文信息。对模拟数据和真实的数据的实验表明了该方法的优越性。
In real crowdsourcing applications, each label from a crowd usually comes with a certain cost. Given a pre-fixed amount of budget, since different tasks have different ambiguities and different workers have different expertises, we want to find an optimal way to allocate the budget among instance-worker pairs such that the overall label quality can be maximized. To address this issue, we start from the simplest setting in which all workers are assumed to be perfect. We formulate the problem as a Bayesian Markov Decision Process (MDP). Using the dynamic programming (DP) algorithm, one can obtain the optimal allocation policy for a given budget. However, DP is computationally intractable. To solve the computational challenge, we propose a novel approximate policy which is called optimistic knowledge gradient. It is practically efficient while theoretically its consistency can be guaranteed. We then extend the MDP framework to deal with inhomogeneous workers and tasks with contextual information available. The experiments on both simulated and real data demonstrate the superiority of our method.