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

By Michael Kearns, Yishay Mansour, Andrew Y. Ng. 1997

Assignment methods are at the heart of many algorithms for unsupervised learning and clustering -- in particular, the well-known K-means and Expectation-Maximizatian (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.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

Citations in the corpus

Generating Sentences from a Continuous Space (2015, methodology): “Iterated conditional modes is a technique for finding the maximum joint assignment of a set of variables by alternately maximizing conditional distributions, and is a generalization of “hard-em” algorithms like k-means (Kearns et al., 1998).”
Mixture Models for Diverse Machine Translation: Tricks of the Trade (2019, background): “Second, hard mixtures yield more diverse generations than soft mixtures, similar to how K-Means tends to ﬁnd centroids that are farther apart from each other compared to the means found by a mixture of Gaussians (Kearns et al., 1998).”
Learning Probabilistic Hierarchical Task Networks as Probabilistic Context-Free Grammars to Capture User Preferences (2014, background): “For much more analysis and discussion of the specific tradeoffs between hard- and soft-EM see [Kearns et al. 1997; Kandylas et al. 2007]; for a comprehensive treatment of theoretical and practical issues in probabilistic reasoning over graphs in general see [Koller and Friedman 2009].”
Adaptive computation and machine learning (1998, methodology): “Under certain generative model-based assumptions, one can good initialization for K-Means connect the mixture of Gaussians model to K-Means with squared Euclidean distance (Kearns et al., 1997).”
Secrets of GrabCut and Kernel K-Means (2015, methodology): “This also emphasizes the well-known bias of basic K-means to equal size clusters [16, 3].”
Frequency-sensitive competitive learning for scalable balanced clustering on high-dimensional hyperspheres (2004, background): “FSCL was originally formulated to remedy the problem of underutilization of parts of a codebook in vector quantization.”
Sense discovery via co-clustering on images and text (2015, background): “hard-EM style iterations [22] to maximize the scoring function S .”
Alternatives to the k-means algorithm that find better clusterings (2002, background): “Kearns and colleagues have analyzed the differences between hard and soft membership from an information-theoretic standpoint [9].”
Mathematical Programming for Data Mining: Formulations and Challenges (1999, background): “3) and the EM Algorithm can be found in [71].”
Example Based 3D Reconstruction from Single 2D Images (2006, background): “It can be shown that this process is in fact a hard-EM optimization [17] of the following global target function.”
Task-Agnostic Online Reinforcement Learning with an Infinite Mixture of Gaussian Processes (2020, background): “However, this involves a trade-off [36] between how well the data are balanced and the density accuracy.”
A Unified Framework for Model-based Clustering (2003, methodology): “A stochastic variant of the mk-means algorithm, stochastic mk-means, was described by Kearns et al. (1997) as posterior assignment (as opposed to k-means assignment and EM assignment).”
Competitive Training of Mixtures of Independent Deep Generative Models (2018, background): “entical realizations of X, they must have been generated by the same mechanism. While a soft assignment is also possible, we focus on training with hard assignments which is known to converge faster [Kearns et al., 1998]. From a practical perspective, this implies dividing the data distribution into”
Active Semi-Supervision for Pairwise Constrained Clustering (2004, methodology): “Under certain generative model-based assumptions, one can connect the mixture of Gaussians model to the KMeans model [21].”
Clustering with Bregman Divergences (2005, background): “Underlying both hard and soft Euclidean kmeans is a Gaussian “noise” model, which corresponds to a squared-Euclidean distortion function [15].”