Crowdsourcing has become a primary means for label collection in many real-world machine learning applications. A classical method for inferring the true labels from the noisy labels provided by crowdsourcing workers is Dawid-Skene estimator. In this paper, we prove convergence rates of global optimizers of Dawid-Skene estimator. The revealed exponent in the rate of convergence is shown to be optimal via a lower bound argument. A projected EM algorithm is analyzed and is shown to achieve nearly the same exponent as that of the global optimizers. Our work resolves the long standing issue of whether Dawid-Skene estimator has sound theoretical guarantees besides its good performance observed in practice. In addition, a comparative study with majority voting illustrates both advantages and pitfalls of Dawid-Skene estimator.
Though the framework of Dawid and Skene has been widely used and well extended in crowdsourcing on the algorithmic side, there has been no theoretical work addressing convergence and optimality issues under the Dawid-Skene setting. To the best of our knowledge, the only exception is the work of @cite_6 . They proposed a belief propagation algorithm using a Haldane prior A Haldane prior assumes each worker's ability is either @math or @math with equal probabilities. on workers' abilities and derive its rate of convergence under the one-coin model. They essentially reveal the exponent @math in the rate of convergence under the assumption that workers' abilities are bounded, while in our work both @math and @math play important roles on the exponent in various regimes. In addition, they consider the question of task assignment which is not addressed in our paper.
@cite_6
1522318289
Crowdsourcing has become a primary means for label collection in many real-world machine learning applications. A classical method for inferring the true labels from the noisy labels provided by crowdsourcing workers is Dawid-Skene estimator. In this paper, we prove convergence rates of global optimizers of Dawid-Skene estimator. The revealed exponent in the rate of convergence is shown to be optimal via a lower bound argument. A projected EM algorithm is analyzed and is shown to achieve nearly the same exponent as that of the global optimizers. Our work resolves the long standing issue of whether Dawid-Skene estimator has sound theoretical guarantees besides its good performance observed in practice. In addition, a comparative study with majority voting illustrates both advantages and pitfalls of Dawid-Skene estimator.