# Active clustering for labeling training data

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

## Key facts

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

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

- [Pervasive Label Errors in Test Sets Destabilize Machine Learning Benchmarks](https://mlsanity.com/paper/2103.14749/) (2021)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Leveraging Transitive Relations for Crowdsourced Joins](https://mlsanity.com/paper/1408.6916/) (2014)
- [A Correlation Clustering Approach to Link Classification in Signed Networks -- Full Version --](https://mlsanity.com/paper/1301.4769/) (2013)
- [Semi-Supervised Clustering with Inaccurate Pairwise Annotations](https://mlsanity.com/paper/2104.02146/) (2021)

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

- [A3S: A General Active Clustering Method with Pairwise Constraints](https://mlsanity.com/paper/2407.10196/) (2024)

## Abstract (arXiv)

Gathering training data is a key step of any supervised learning task, and it is both critical and expensive. Critical, because the quantity and quality of the training data has a high impact on the performance of the learned function. Expensive, because most practical cases rely on humans-in-the-loop to label the data. The process of determining the correct labels is much more expensive than comparing two items to see whether they belong to the same class. Thus motivated, we propose a setting for training data gathering where the human experts perform the comparatively cheap task of answering pairwise queries, and the computer groups the items into classes (which can be labeled cheaply at the very end of the process). Given the items, we consider two random models for the classes: one where the set partition they form is drawn uniformly, the other one where each item chooses its class independently following a fixed distribution. In the first model, we characterize the algorithms that minimize the average number of queries required to cluster the items and analyze their complexity. In the second model, we analyze a specific algorithm family, propose as a conjecture that they reach the minimum average number of queries and compare their performance to a random approach. We also propose solutions to handle errors or inconsistencies in the experts' answers.