# Crowdsourcing via Annotator Co-occurrence Imputation and Provable Symmetric Nonnegative Matrix Factorization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 57 references that are in the map.
- First posted on arXiv 14 Jun 2021.

## Builds on (most cited first, 17 of 17)

- [Deep learning from crowds](https://mlsanity.com/paper/1709.01779/) (2017)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing](https://mlsanity.com/paper/1406.3824/) (2014)
- [Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications](https://mlsanity.com/paper/1803.01257/) (2018)
- [On Identifiability of Nonnegative Matrix Factorization](https://mlsanity.com/paper/1709.00614/) (2017)
- [Robust Volume Minimization-Based Matrix Factorization for Remote Sensing and Document Clustering](https://mlsanity.com/paper/1608.04290/) (2016)
- [Crowdsourcing via Pairwise Co-occurrences: Identifiability and Algorithms](https://mlsanity.com/paper/1909.12325/) (2019)
- [Error Rate Bounds and Iterative Weighted Majority Voting for Crowdsourcing](https://mlsanity.com/paper/1411.4086/) (2014)
- [Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective](https://mlsanity.com/paper/2006.08183/) (2020)
- [Block-Randomized Stochastic Proximal Gradient for Low-Rank Tensor Factorization](https://mlsanity.com/paper/1901.05529/) (2019)
- [Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers](https://mlsanity.com/paper/1904.11608/) (2019)
- [Blind Multiclass Ensemble Classification](https://mlsanity.com/paper/1712.02903/) (2017)
- [Regularized Minimax Conditional Entropy for Crowdsourcing](https://mlsanity.com/paper/1503.07240/) (2015)
- [Beyond AMT: An Analysis of Crowd Work Platforms](https://mlsanity.com/paper/1310.1672/) (2013)
- [Recovery Guarantee of Non-negative Matrix Factorization via Alternating Updates](https://mlsanity.com/paper/1611.03819/) (2016)
- [Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations](https://mlsanity.com/paper/1706.04097/) (2017)
- [Joint Tensor Factorization and Outlying Slab Suppression with Applications](https://mlsanity.com/paper/1507.04436/) (2015)

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

- [Deep Learning From Crowdsourced Labels: Coupled Cross-entropy Minimization, Identifiability, and Regularization](https://mlsanity.com/paper/2306.03288/) (2023)
- [Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach](https://mlsanity.com/paper/2109.11135/) (2021)
- [Ground Truth Inference for Weakly Supervised Entity Matching](https://mlsanity.com/paper/2211.06975/) (2022)
- [Deep Clustering with Incomplete Noisy Pairwise Annotations: A Geometric Regularization Approach](https://mlsanity.com/paper/2305.19391/) (2023)
- [Learning From Crowdsourced Noisy Labels: A Signal Processing Perspective](https://mlsanity.com/paper/2407.06902/) (2024)
- [AHEAD: Advancing Multi-Class Label Aggregation with Interpretable Cross-Annotator Modeling](https://mlsanity.com/paper/2607.18465/) (2026)

## Abstract (arXiv)

Unsupervised learning of the Dawid-Skene (D&S) model from noisy, incomplete and crowdsourced annotations has been a long-standing challenge, and is a critical step towards reliably labeling massive data. A recent work takes a coupled nonnegative matrix factorization (CNMF) perspective, and shows appealing features: It ensures the identifiability of the D&S model and enjoys low sample complexity, as only the estimates of the co-occurrences of annotator labels are involved. However, the identifiability holds only when certain somewhat restrictive conditions are met in the context of crowdsourcing. Optimizing the CNMF criterion is also costly -- and convergence assurances are elusive. This work recasts the pairwise co-occurrence based D&S model learning problem as a symmetric NMF (SymNMF) problem -- which offers enhanced identifiability relative to CNMF. In practice, the SymNMF model is often (largely) incomplete, due to the lack of co-labeled items by some annotators. Two lightweight algorithms are proposed for co-occurrence imputation. Then, a low-complexity shifted rectified linear unit (ReLU)-empowered SymNMF algorithm is proposed to identify the D&S model. Various performance characterizations (e.g., missing co-occurrence recoverability, stability, and convergence) and evaluations are also presented.