  Crowdsourcing is becoming increasingly important in entity resolution tasks
due to their inherent complexity such as clustering of images and natural
language processing. Humans can provide more insightful information for these
difficult problems compared to machine-based automatic techniques.
Nevertheless, human workers can make mistakes due to lack of domain expertise
or seriousness, ambiguity, or even due to malicious intents. The
state-of-the-art literature usually deals with human errors via majority voting
or by assigning a universal error rate over crowd workers. However, such
approaches are incomplete, and often inconsistent, because the expertise of
crowd workers are diverse with possible biases, thereby making it largely
inappropriate to assume a universal error rate for all workers over all
crowdsourcing tasks.
  To this end, we mitigate the above challenges by considering an uncertain
graph model, where the edge probability between two records A and B denotes the
ratio of crowd workers who voted Yes on the question if A and B are same
entity. In order to reflect independence across different crowdsourcing tasks,
we apply the well-established notion of possible worlds, and develop
parameter-free algorithms both for next crowdsourcing, as well as for entity
resolution problems. In particular, using our framework, the problem of entity
resolution becomes equivalent to finding the maximum-likelihood clustering;
whereas for the next crowdsourcing, we identify the record pair that maximally
increases the reliability of the maximum-likelihood clustering. Based on
detailed empirical analysis over real-world datasets, we find that our proposed
solution, PERC (probabilistic entity resolution with imperfect crowd) improves
the quality by 15% and reduces the overall cost by 50% for the
crowdsourcing-based entity resolution problem.
