Clustering from Multiple Uncertain Experts

Yale Chang, Junxiang Chen, Michael H. Cho, Peter J. Castaldi, Edwin K. Silverman, Jennifer G. DyAISTATS 2017 · OpenReview

Abstract

Utilizing expert input often improves clustering performance. However, in a knowledge discovery problem, ground truth is unknown even to an expert. Thus, instead of one expert, we solicit the opinion from multiple experts. The key question motivating this work is: which experts should be assigned higher weights when there is disagreement on whether to put a pair of samples in the same group? To model the uncertainty in constraints from different experts, we build a probabilistic model for pairwise constraints through jointly modeling each expert’s accuracy and the mapping from features to latent cluster assignments. After learning our probabilistic discriminative clustering model and accuracies of different experts, 1) samples that were not annotated by any expert can be clustered using the discriminative clustering model; and 2) experts with higher accuracies are automatically assigned higher weights in determining the latent cluster assignments. Experimental results on UCI benchmark datasets and a real-world disease subtyping dataset demonstrate that our proposed approach outperforms competing alternatives, including semi-crowdsourced clustering, semi-supervised clustering with constraints from majority voting, and consensus clustering.

Introduction

In semi-supervised clustering, algorithms are typically guided by human input in the form of pairwise constraints—specifying whether two samples "must-link" or "cannot-link." Most existing methods assume these constraints originate from a single, infallible expert. However, in complex domains like medical research, the ground truth is often unknown even to specialists. When multiple experts are consulted, they inevitably provide conflicting and sparse advice. This paper addresses the challenge of combining inconsistent constraints from multiple experts with varying, unknown levels of expertise without allowing noisy input to degrade clustering performance.

The Proposed Framework

The authors propose a joint probabilistic framework that simultaneously learns data clustering and expert reliability. Unlike generative models that make strict assumptions about data distribution, this approach uses a discriminative clustering model (multiple logistic regression) to map features to latent cluster probabilities. This flexibility allows the model to easily cluster new data points that were never seen by any expert.

Probabilistic graphical model for pairwise constraints from multiple experts.

Each expert's reliability is modeled using Bernoulli distributions parameterized by sensitivity (correctly identifying must-links) and specificity (correctly identifying cannot-links). The model is trained using the Expectation-Maximization (EM) algorithm. In the E-step, it estimates latent cluster assignments; in the M-step, it updates clustering weights and individual expert accuracy parameters. A key mathematical insight is that the optimization naturally scales an expert's influence based on their accuracy, effectively giving more reliable experts a "louder voice" in the final decision.

Experimental Evaluation

The model was evaluated on 11 UCI benchmark datasets and a real-world dataset of 987 patients with Chronic Obstructive Pulmonary Disease (COPD). For the UCI benchmarks, synthetic experts with varying accuracies were generated to simulate realistic uncertainty.

Performance comparison on the Mushroom dataset showing the proposed method outperforming alternatives across varying constraint counts.

On the benchmark datasets, the proposed approach consistently outperformed competing methods such as SemiCrowd, ITML, and MPCKMeans in terms of Normalized Mutual Information (NMI). On the COPD dataset, which featured constraints from 27 actual experts, the model identified four distinct patient subtypes. It was the only method tested that yielded statistically significant differences across critical clinical outcomes, including mortality and lung function decline.

Conclusion

By explicitly modeling individual expert uncertainty alongside a discriminative clustering model, this framework provides a robust solution for knowledge discovery when ground truth is elusive. While the current model assumes linear cluster boundaries and requires multiple initializations due to a non-convex objective, it represents a significant step forward in handling real-world, noisy human input in machine learning.

Summary updated

Abstract

Utilizing expert input often improves clustering performance. However in a knowledge discovery problem, ground truth is unknown even to an expert. Thus, instead of one expert, we solicit the opinion from multiple experts. The key question motivating this work is: which experts should be assigned higher weights when there is disagreement on whether to put a pair of samples in the same group? To model the uncertainty in constraints from different experts, we build a probabilistic model for pairwise constraints through jointly modeling each expert’s accuracy and the mapping from features to latent cluster assignments. After learning our probabilistic discriminative clustering model and accuracies of different experts, 1) samples that were not annotated by any expert can be clustered using the discriminative clustering model; and 2) experts with higher accuracies are automatically assigned higher weights in determining the latent cluster assignments. Experimental results on UCI benchmark datasets and a real-world disease subtyping dataset demonstrate that our proposed approach outperforms competing alternatives, including semi-crowdsourced clustering, semi-supervised clustering with constraints from majority voting, and consensus clustering.
BibTeX
@inproceedings{chang2017clustering,
  author = {Yale Chang and Junxiang Chen and Michael H. Cho and Peter J. Castaldi and Edwin K. Silverman and Jennifer G. Dy},
  title = {{Clustering from Multiple Uncertain Experts}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=s-V1Hy8o9cX},
}
Figure