Optimistic Knowledge Gradient Policy for Optimal Budget Allocation in Crowdsourcing

Xi Chen, Qihang Lin, Dengyong Zhou
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):64-72, 2013.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-chen13f, title = {Optimistic Knowledge Gradient Policy for Optimal Budget Allocation in Crowdsourcing}, author = {Chen, Xi and Lin, Qihang and Zhou, Dengyong}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {64--72}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/chen13f.pdf}, url = {https://proceedings.mlr.press/v28/chen13f.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Optimistic Knowledge Gradient Policy for Optimal Budget Allocation in Crowdsourcing %A Xi Chen %A Qihang Lin %A Dengyong Zhou %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-chen13f %I PMLR %P 64--72 %U https://proceedings.mlr.press/v28/chen13f.html %V 28 %N 3 %X 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.
RIS
TY - CPAPER TI - Optimistic Knowledge Gradient Policy for Optimal Budget Allocation in Crowdsourcing AU - Xi Chen AU - Qihang Lin AU - Dengyong Zhou BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-chen13f PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 64 EP - 72 L1 - http://proceedings.mlr.press/v28/chen13f.pdf UR - https://proceedings.mlr.press/v28/chen13f.html AB - 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. ER -
APA
Chen, X., Lin, Q. & Zhou, D.. (2013). Optimistic Knowledge Gradient Policy for Optimal Budget Allocation in Crowdsourcing. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):64-72 Available from https://proceedings.mlr.press/v28/chen13f.html.

Related Material