Semisupervised Clustering, AND-Queries and Locally Encodable Source Coding

Arya Mazumdar, Soumyabrata PalNeurIPS 2017 · OpenReview

Overview

This paper bridges the gap between semisupervised clustering and information theory by proving that clustering with limited queries is mathematically equivalent to locally encodable source coding. The authors demonstrate that traditional "same-cluster" (XOR) queries are fundamentally limited in noisy environments. To overcome this, they propose AND-queries, which are more efficient, robust to noise, and significantly easier for human crowd-workers to answer accurately.

The Challenge of Semisupervised Clustering

In semisupervised clustering—a common task in crowdsourcing—the goal is to group $n$ elements into $k$ categories. To achieve this, an algorithm asks an "oracle" (such as a human worker) simple binary questions about pairs of elements.

This process faces two primary challenges:

  1. Cost: Every query costs time and money. The objective is to recover the clusters using the absolute minimum number of queries.
  2. Noise: Human workers make mistakes. Traditional methods often require $O(n \log n)$ queries to handle this noise, which becomes prohibitively expensive for large datasets.

The authors identify a specific theoretical bottleneck in existing approaches: most research relies on "same-cluster" queries (e.g., "Do items $u$ and $v$ belong to the same category?"). In information theory, this is equivalent to a Boolean XOR operation. The authors prove that XOR queries are fundamentally inefficient for "approximate recovery"—scenarios where we are willing to accept a small fraction of errors to drastically save on query costs.

A New Information-Theoretic Framework

The paper introduces a novel theoretical framework by viewing clustering as locally encodable source coding. In this paradigm, the cluster labels are the "source," and the query answers are the "compressed bits." The "local" aspect arises because each query only involves a small, constant number of elements ($\Delta$).

Key Innovations

  • AND-Queries: Instead of asking if two items are in the same cluster, the authors propose asking: "Do both items $u$ and $v$ belong to cluster $i$?"
  • Threshold-Based Recovery: For noisy scenarios, they propose a non-adaptive algorithm. It builds a $d$-regular graph of queries and assigns labels based on whether the number of positive responses for a specific label exceeds a calculated threshold.
  • Information-Theoretic Lower Bounds: They derive new bounds on the minimum number of queries needed for both exact and approximate recovery, demonstrating how prior knowledge of cluster sizes can be exploited to beat the standard $n$-query limit.

Key Insights

  • The XOR Limitation vs. The AND Advantage: XOR queries are symmetric. If the oracle is noisy, there is no "gap" between the expected number of 'yes' answers for different labels, making them hard to distinguish without many repetitions. AND queries, however, are asymmetric. This creates a measurable gap in expectations that a threshold-based algorithm can easily exploit.
  • Human Psychology Matters: The authors validated their theory using a real-world crowdsourced dataset of 200 IMDB movies. The error rate for AND-queries was 10.5%, while the error rate for "same-cluster" queries on the exact same pairs was 23.4%. AND-queries are cognitively easier: to say "no" to an AND query, a worker only needs to know that one item doesn't fit the category. For a "same-cluster" query, they must know the categories of both items.

Key Results

Query Complexity for Approximate Recovery

The authors prove that their AND-query scheme can recover a $(1-\delta)$ proportion of labels with only $O(n \log \frac{k}{\delta})$ non-adaptive queries, even with a noisy oracle.

Comparison of error rate vs. normalized queries for AND-queries and same-cluster queries.

As shown above, the proposed AND-query scheme significantly outperforms the theoretical lower bound of traditional "same cluster" queries, achieving a lower error rate ($\delta$) for a given normalized number of queries.

Exact Recovery

The authors also explored the limits of perfect clustering. They showed that for two clusters, if the prior probability $p$ of an item belonging to a specific cluster is between 0.0694 and 0.5, it is possible to recover all labels exactly using fewer than $n$ queries.

Normalized number of queries required for exact recovery based on prior probability.

The upper bound curve demonstrates that when the prior probability $p$ is moderately skewed, the normalized number of queries ($m/n$) required for exact recovery drops below 1.0, proving that sub-linear query complexity is achievable under the right conditions.

Limitations and Future Work

  • Non-Adaptive Focus: The paper focuses on non-adaptive queries (asking all questions at once in parallel). While ideal for crowdsourcing, adaptive strategies (where the next question depends on previous answers) might yield even lower bounds.
  • Constant $\Delta$: The theory assumes queries involve a small constant number of elements. Scaling this to larger hyper-graph queries remains an open area.
  • Independent Noise: The model assumes the oracle's errors are independent. In reality, some items are "harder" to categorize than others, leading to correlated errors. Future work could explore more complex, real-world noise models.

Summary updated

Abstract

Source coding is the canonical problem of data compression in information theory. In a locally encodable source coding, each compressed bit depends on only few bits of the input. In this paper, we show that a recently popular model of semisupervised clustering is equivalent to locally encodable source coding. In this model, the task is to perform multiclass labeling of unlabeled elements. At the beginning, we can ask in parallel a set of simple queries to an oracle who provides (possibly erroneous) binary answers to the queries. The queries cannot involve more than two (or a fixed constant number $\Delta$ of) elements. Now the labeling of all the elements (or clustering) must be performed based on the (noisy) query answers. The goal is to recover all the correct labelings while minimizing the number of such queries. The equivalence to locally encodable source codes leads us to find lower bounds on the number of queries required in variety of scenarios. We are also able to show fundamental limitations of pairwise `same cluster' queries - and propose pairwise AND queries, that provably performs better in many situations.
BibTeX
@inproceedings{mazumdar2017semisupervised,
  author = {Arya Mazumdar and Soumyabrata Pal},
  title = {{Semisupervised Clustering, AND-Queries and Locally Encodable Source Coding}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=S1VTOO-OZB},
}
Figure