Near-Optimally Teaching the Crowd to Classify

Adish Singla, Ilija Bogunovic, Gabor Bartok, Amin Karbasi, Andreas Krause
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):154-162, 2014.

Abstract

How should we present training examples to learners to teach them classification rules? This is a natural problem when training workers for crowdsourcing labeling tasks, and is also motivated by challenges in data-driven online education. We propose a natural stochastic model of the learners, modeling them as randomly switching among hypotheses based on observed feedback. We then develop STRICT, an efficient algorithm for selecting examples to teach to workers. Our solution greedily maximizes a submodular surrogate objective function in order to select examples to show to the learners. We prove that our strategy is competitive with the optimal teaching policy. Moreover, for the special case of linear separators, we prove that an exponential reduction in error probability can be achieved. Our experiments on simulated workers as well as three real image annotation tasks on Amazon Mechanical Turk show the effectiveness of our teaching algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-singla14, title = {Near-Optimally Teaching the Crowd to Classify}, author = {Singla, Adish and Bogunovic, Ilija and Bartok, Gabor and Karbasi, Amin and Krause, Andreas}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {154--162}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/singla14.pdf}, url = {https://proceedings.mlr.press/v32/singla14.html}, abstract = {How should we present training examples to learners to teach them classification rules? This is a natural problem when training workers for crowdsourcing labeling tasks, and is also motivated by challenges in data-driven online education. We propose a natural stochastic model of the learners, modeling them as randomly switching among hypotheses based on observed feedback. We then develop STRICT, an efficient algorithm for selecting examples to teach to workers. Our solution greedily maximizes a submodular surrogate objective function in order to select examples to show to the learners. We prove that our strategy is competitive with the optimal teaching policy. Moreover, for the special case of linear separators, we prove that an exponential reduction in error probability can be achieved. Our experiments on simulated workers as well as three real image annotation tasks on Amazon Mechanical Turk show the effectiveness of our teaching algorithm.} }
Endnote
%0 Conference Paper %T Near-Optimally Teaching the Crowd to Classify %A Adish Singla %A Ilija Bogunovic %A Gabor Bartok %A Amin Karbasi %A Andreas Krause %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-singla14 %I PMLR %P 154--162 %U https://proceedings.mlr.press/v32/singla14.html %V 32 %N 2 %X How should we present training examples to learners to teach them classification rules? This is a natural problem when training workers for crowdsourcing labeling tasks, and is also motivated by challenges in data-driven online education. We propose a natural stochastic model of the learners, modeling them as randomly switching among hypotheses based on observed feedback. We then develop STRICT, an efficient algorithm for selecting examples to teach to workers. Our solution greedily maximizes a submodular surrogate objective function in order to select examples to show to the learners. We prove that our strategy is competitive with the optimal teaching policy. Moreover, for the special case of linear separators, we prove that an exponential reduction in error probability can be achieved. Our experiments on simulated workers as well as three real image annotation tasks on Amazon Mechanical Turk show the effectiveness of our teaching algorithm.
RIS
TY - CPAPER TI - Near-Optimally Teaching the Crowd to Classify AU - Adish Singla AU - Ilija Bogunovic AU - Gabor Bartok AU - Amin Karbasi AU - Andreas Krause BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-singla14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 154 EP - 162 L1 - http://proceedings.mlr.press/v32/singla14.pdf UR - https://proceedings.mlr.press/v32/singla14.html AB - How should we present training examples to learners to teach them classification rules? This is a natural problem when training workers for crowdsourcing labeling tasks, and is also motivated by challenges in data-driven online education. We propose a natural stochastic model of the learners, modeling them as randomly switching among hypotheses based on observed feedback. We then develop STRICT, an efficient algorithm for selecting examples to teach to workers. Our solution greedily maximizes a submodular surrogate objective function in order to select examples to show to the learners. We prove that our strategy is competitive with the optimal teaching policy. Moreover, for the special case of linear separators, we prove that an exponential reduction in error probability can be achieved. Our experiments on simulated workers as well as three real image annotation tasks on Amazon Mechanical Turk show the effectiveness of our teaching algorithm. ER -
APA
Singla, A., Bogunovic, I., Bartok, G., Karbasi, A. & Krause, A.. (2014). Near-Optimally Teaching the Crowd to Classify. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):154-162 Available from https://proceedings.mlr.press/v32/singla14.html.

Related Material