# An Information-Theoretic Analysis of Hard and Soft Assignment Methods for Clustering

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2013.

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

- [Parametric Information Maximization for Generalized Category Discovery](https://mlsanity.com/paper/2212.00334/) (2022)
- [Boosting Vision-Language Models with Transduction](https://mlsanity.com/paper/2406.01837/) (2024)
- [Transductive Zero-Shot and Few-Shot CLIP](https://mlsanity.com/paper/2405.18437/) (2024)
- [Realistic Test-Time Adaptation of Vision-Language Models](https://mlsanity.com/paper/2501.03729/) (2025)
- [Do We Really Need Dice? The Hidden Region-Size Biases of Segmentation Losses](https://mlsanity.com/paper/2104.08717/) (2021)
- [Adaptive Dimension Reduction and Variational Inference for Transductive Few-Shot Classification](https://mlsanity.com/paper/2209.08527/) (2022)
- [Towards Practical Few-Shot Query Sets: Transductive Minimum Description Length Inference](https://mlsanity.com/paper/2210.14545/) (2022)
- [Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation](https://mlsanity.com/paper/2303.16521/) (2023)
- [Learning to Superoptimize Real-world Programs](https://mlsanity.com/paper/2109.13498/) (2021)
- [Improvement and generalization of ABCD method with Bayesian inference](https://mlsanity.com/paper/2402.08001/) (2024)
- [UNEM: UNrolled Generalized EM for Transductive Few-Shot Learning](https://mlsanity.com/paper/2412.16739/) (2024)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [ORION: ORthonormal Text Encoding for Universal VLM AdaptatION](https://mlsanity.com/paper/2602.19530/) (2026)
- [Simplex Clustering via sBeta with Applications to Online Adjustment of Black-Box Predictions](https://mlsanity.com/paper/2208.00287/) (2022)
- [Discriminative Entropy Clustering and its Relation to K-means and SVM](https://mlsanity.com/paper/2301.11405/) (2023)
- [Improving the Utility of Differentially Private Clustering through Dynamical Processing](https://mlsanity.com/paper/2304.13886/) (2023)
- [k-MLE, k-Bregman, k-VARs: Theory, Convergence, Computation](https://mlsanity.com/paper/2409.06938/) (2024)

## Abstract (arXiv)

Assignment methods are at the heart of many algorithms for unsupervised learning and clustering - in particular, the well-known K-means and Expectation-Maximization (EM) algorithms. In this work, we study several different methods of assignment, including the "hard" assignments used by K-means and the ?soft' assignments used by EM. While it is known that K-means minimizes the distortion on the data and EM maximizes the likelihood, little is known about the systematic differences of behavior between the two algorithms. Here we shed light on these differences via an information-theoretic analysis. The cornerstone of our results is a simple decomposition of the expected distortion, showing that K-means (and its extension for inferring general parametric densities from unlabeled sample data) must implicitly manage a trade-off between how similar the data assigned to each cluster are, and how the data are balanced among the clusters. How well the data are balanced is measured by the entropy of the partition defined by the hard assignments. In addition to letting us predict and verify systematic differences between K-means and EM on specific examples, the decomposition allows us to give a rather general argument showing that K ?means will consistently find densities with less "overlap" than EM. We also study a third natural assignment method that we call posterior assignment, that is close in spirit to the soft assignments of EM, but leads to a surprisingly different algorithm.