Abstract
Crowdsourced clustering leverages human intelligence to group items based on subjective similarity. However, the high cost and potential unreliability of crowd workers necessitate budget-efficient task allocation. This paper proposes a Bayesian Markov Decision Process (MDP) framework using an "Optimistic Knowledge Gradient" (Opt-KG) policy. By dynamically selecting item pairs and evaluating worker reliability, the system maximizes clustering accuracy under a fixed budget. Experimental results on simulated and real-world datasets demonstrate that Opt-KG significantly outperforms standard baselines in convergence speed and final accuracy.
Introduction
Clustering is a foundational task in machine learning, but it often relies on similarity metrics that are difficult for machines to compute, such as the subjective similarity between two paintings or songs. In these cases, crowdsourcing provides a solution by collecting binary labels (similar/not similar) from human workers. However, crowdsourcing is expensive, and human workers are often fallible or inconsistent. A naive approach—asking many workers about every possible pair—quickly exhausts the budget. The central challenge addressed in this work is how to dynamically allocate a limited budget to the most informative pairs and the most reliable workers to maximize clustering accuracy.
Methods
The authors model the problem as a finite-horizon Bayesian Markov Decision Process (MDP).
The Similarity Graph and Bayesian Framework
Items are represented as nodes in a graph where edges are weighted by the probability that two items belong to the same cluster. The clustering goal is framed as a minimum-weight K-cut problem—partitioning the graph into $K$ groups by removing edges with the smallest total weight. Uncertainty regarding the similarity between item pairs is modeled using Beta distributions.
The Opt-KG Policy
To solve the computationally intensive MDP, the authors propose an Optimistic Knowledge Gradient (Opt-KG) policy. Unlike standard methods that look at the expected improvement of a query, Opt-KG considers the best possible outcome. This "optimism" encourages the algorithm to explore ambiguous pairs that could significantly alter the clustering structure, preventing it from getting stuck repeatedly labeling the same pairs.
Handling Unreliable Workers
When workers are unreliable, the joint distribution of item similarity and worker reliability becomes complex. The authors employ a variational approximation (moment matching) to maintain computational efficiency while simultaneously learning which workers to trust.
Results and Discussion
The approach was evaluated using both simulated data and real-world datasets (Soybean, Olive oil, Meat, and Iris).
Performance Comparison
In simulations, the Opt-KG policy reached high clustering accuracy and Normalized Mutual Information (NMI) significantly faster than random assignment or the standard Knowledge Gradient.
Key Insights
- Dynamic Focus: The algorithm shifts the budget toward "challenging" pairs on cluster boundaries, avoiding spending resources on pairs that are obviously similar or different.
- Worker Filtering: The model identifies noisy workers early and stops assigning tasks to them, funneling the budget toward more consistent contributors.
- Real-World Success: On the Soybean dataset, Opt-KG achieved an accuracy of 0.98 with a budget of only $T=10$ stages, compared to 0.94 for random assignment.
Conclusion
This work demonstrates that a Bayesian MDP framework with an optimistic policy can effectively manage the trade-offs in crowdsourced clustering. While the current model assumes a fixed number of clusters ($K$) and equal task costs, it provides a robust foundation for budget-efficient human-in-the-loop machine learning. Future work may explore dynamic pricing and scenarios where the number of clusters is unknown.
Summary updated