# Crowdsourcing via Pairwise Co-occurrences: Identifiability and Algorithms

arXiv: https://arxiv.org/abs/1909.12325 · HTML: https://mlsanity.com/paper/1909.12325/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2019.

## Built on by (most cited first, 23 of 23)

- [Deep Learning From Crowdsourced Labels: Coupled Cross-entropy Minimization, Identifiability, and Regularization](https://mlsanity.com/paper/2306.03288/) (2023)
- [Probabilistic Simplex Component Analysis](https://mlsanity.com/paper/2103.10027/) (2021)
- [Identifiability-Guaranteed Simplex-Structured Post-Nonlinear Mixture Learning via Autoencoder](https://mlsanity.com/paper/2106.09070/) (2021)
- [Crowdsourcing via Annotator Co-occurrence Imputation and Provable Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2106.07193/) (2021)
- [Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach](https://mlsanity.com/paper/2109.11135/) (2021)
- [Deep Clustering with Incomplete Noisy Pairwise Annotations: A Geometric Regularization Approach](https://mlsanity.com/paper/2305.19391/) (2023)
- [Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses](https://mlsanity.com/paper/2104.14562/) (2021)
- [LLMs Judging LLMs: A Simplex Perspective](https://mlsanity.com/paper/2505.21972/) (2025)
- [Diverse Influence Component Analysis: A Geometric Approach to Nonlinear Mixture Identifiability](https://mlsanity.com/paper/2510.17040/) (2025)
- [Ensemble learning using individual neonatal data for seizure detection](https://mlsanity.com/paper/2204.07043/) (2022)
- [Checking the Sufficiently Scattered Condition using a Global Non-Convex Optimization Software](https://mlsanity.com/paper/2402.06019/) (2024)
- [Learning From Crowdsourced Noisy Labels: A Signal Processing Perspective](https://mlsanity.com/paper/2407.06902/) (2024)
- [A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits](https://mlsanity.com/paper/2111.12550/) (2021)
- [Robust Assignment of Labels for Active Learning with Sparse and Noisy Annotations](https://mlsanity.com/paper/2307.14380/) (2023)
- [Detecting adversaries in Crowdsourcing](https://mlsanity.com/paper/2110.04117/) (2021)
- [Identify ambiguous tasks combining crowdsourced labels by weighting Areas Under the Margin](https://mlsanity.com/paper/2209.15380/) (2022)
- [Recovering Top-Two Answers and Confusion Probability in Multi-Choice Crowdsourcing](https://mlsanity.com/paper/2301.00006/) (2022)
- [Understanding the Essence: Delving into Annotator Prototype Learning for Multi-Class Annotation Aggregation](https://mlsanity.com/paper/2508.02123/) (2025)
- [Metric Learning in an RKHS](https://mlsanity.com/paper/2508.04476/) (2025)
- [Robustness of Minimum-Volume Nonnegative Matrix Factorization under an Expanded Sufficiently Scattered Condition](https://mlsanity.com/paper/2511.04291/) (2025)
- [Hyperspectral Image Data Reduction for Endmember Extraction](https://mlsanity.com/paper/2512.10506/) (2025)
- [Unsupervised Ensemble Learning Through Deep Energy-based Models](https://mlsanity.com/paper/2601.20556/) (2026)
- [AHEAD: Advancing Multi-Class Label Aggregation with Interpretable Cross-Annotator Modeling](https://mlsanity.com/paper/2607.18465/) (2026)

## Abstract (arXiv)

The data deluge comes with high demands for data labeling. Crowdsourcing (or, more generally, ensemble learning) techniques aim to produce accurate labels via integrating noisy, non-expert labeling from annotators. The classic Dawid-Skene estimator and its accompanying expectation maximization (EM) algorithm have been widely used, but the theoretical properties are not fully understood. Tensor methods were proposed to guarantee identification of the Dawid-Skene model, but the sample complexity is a hurdle for applying such approaches---since the tensor methods hinge on the availability of third-order statistics that are hard to reliably estimate given limited data. In this paper, we propose a framework using pairwise co-occurrences of the annotator responses, which naturally admits lower sample complexity. We show that the approach can identify the Dawid-Skene model under realistic conditions. We propose an algebraic algorithm reminiscent of convex geometry-based structured matrix factorization to solve the model identification problem efficiently, and an identifiability-enhanced algorithm for handling more challenging and critical scenarios. Experiments show that the proposed algorithms outperform the state-of-art algorithms under a variety of scenarios.