Spectral Methods Meet EM: A Provably Optimal Algorithm for Crowdsourcing
The Dawid-Skene estimator has been widely used for inferring the true labels from the noisy labels provided by non-expert crowdsourcing workers. However, since the estimator maximizes a non-convex log-likelihood function, it is hard to theoretically justify its performance. In this paper, we propose a two-stage efficient algorithm for multi-class crowd labeling problems. The first stage uses the spectral method to obtain an initial estimate of parameters. Then the second stage refines the estimation by optimizing the objective function of the Dawid-Skene estimator via the EM algorithm. We show that our algorithm achieves the optimal convergence rate up to a logarithmic factor. We conduct extensive experiments on synthetic and real datasets. Experimental results demonstrate that the proposed algorithm is comparable to the most accurate empirical approach, while outperforming several other recently proposed methods.
Thank you to the authors for their thoughtful feedback.  I agree that there are pros and cons to both method-of-moments and optimization methods, and a detailed discussion of them is not needed in this paper (which, after all, aims to unite them!).  But since the goal is to analyze an algorithm for a specific, practical problem, I think it is important to at least make sure the assumptions -- the main one being that the Dawid-Skene model is the process actually generating the data -- are clear so that a reader can decide whether they are plausible for a given application.Finally, though the dependence on m may sometimes be more important than the dependence on n, I think it is important to explain this limitation when discussing optimality in the abstract and introduction, where the claims currently seem overstated.  Even weakened in this way, they will still be interesting claims backed up by strong results.--previous review below--In this work the authors propose a two-stage method for extractingconsensus labels from the noisy ones assigned by possibly unreliableannotators.  In the first stage, the method applies spectraltechniques under the Dawid-Skene model of label noise to obtainestimates of each annotator's label confusion matrix.  It then usesthese estimates to initialize an EM algorithm, which alternatelyupdates the label estimates and the confusion matrices to improvelikelihood.  The idea to initialize EM with spectral methods is notnew, but in this paper the authors claim to show that the result ofthe two-stage process is near-optimal in an asymptotic sense.Finally, experiments on several real-world datasets show that theproposed method performs comparably to the best existing method.As noted in the introduction, EM algorithms (like the one by Dawid andSkene) generally set out to optimize non-convex likelihood functions,which, being hard, makes it difficult to obtain any kind ofperformance guarantees.  The move to spectral methods allows forresults like Theorem 1, which shows that, given enough data, parameterestimates will converge to the true parameters.  However, there is atradeoff here, which is not mentioned: the guarantee only applies ifthe model is correct.  That is, if annotators have different confusiontendencies on different items, or if their performance drifts overtime, or if they in any other way deviate from the Dawid-Skene model,then Theorem 1 will likely not hold (nor will Theorem 2, in fact).This problem is much less severe for optimization algorithms, like EM,that have the ability to try and fit an imperfect model to real data;they may not have global optimality guarantees, but their objectivescontinue to guide them in settings where spectral theory simply fails.The absence of this consideration is at the core of my biggest concernabout the paper.  In attempting to prove the qualifications of amethod for handling the unreliability and unpredictability of thirdparty annotators, the paper assumes a high degree of regularity intheir behavior.  To paraphrase a saying, some models are useful, butall of them are wrong; I have mixed feelings about a theory thatassumes otherwise.  At the very least, a thoughtful discussion of thisissue would be a valuable addition to the paper.Having said all of that, I am excited about the direction the authorsof this paper have pursued.  In practice, the spectral+EM strategy hasbecome popular; presumably the idea is to get a "best of both worlds"kind of result, where the spectral method hopefully gives a goodinitialization for EM, saving time and improving the final result, butin any case is probably no worse than random initialization.  Becauseof this I find the idea of theory for the combined algorithm highlyinteresting.  I'm not sure, however, whether Theorem 2 really fulfillsthis promise.  In particular, the assumption that the input C matricesare within alpha of the truth (for alpha that is small compared to thetruth) seems to require that the first stage has done basically all ofthe work.  In fact, the E-step used to obtain result (a) of Theorem 2is just choosing the maximum-likelihood y using the given C.  ArguablyEM is not really needed at all for the theory.On the other hand, the experiments almost make the case for theopposite possibility: that EM does most of the work.  Whetherinitialized by the spectral method or simple majority voting, the twoEM methods perform about the same.  In some cases the spectralinitialization leads to immediate convergence, suggesting it has founda good initialization, but even when the initialization is bad, 50iterations of EM seem to bring it in line.  Perhaps, then, the mostpractical use of this method is as a time-saving technique; it wouldbe interesting to see the runtimes in that case.I found Theorem 3 a bit hard to parse; presumably the \hat y and \hatmu in the infima are supposed to be mappings from the observed data tothe quantity in question?  At first glance they appear to just beconcrete values, which makes the claims seem a little strange.  In anycase, I found the theorem itself interesting, but I'm not sure I agreethat it shows that the convergence rate is "near optimal" since itdoesn't address n, which is usually the default convergence clock andarguably has the more dubious scaling in Equation 9, with large powersof k and a hard-to-interpret singular value.  In my opinion this makesthe optimality claims in the abstract and intro somewhat overstated.