Poster
Compact Representation of Uncertainty in Clustering
Craig Greenberg · Nicholas Monath · Ari Kobren · Patrick Flaherty · Andrew McGregor · Andrew McCallum

Thu Dec 6th 05:00 -- 07:00 PM @ Room 210 #51
in Thu Poster Session B »

For many classic structured prediction problems, probability distributions over the dependent variables can be efficiently computed using widely-known algorithms and data structures (such as forward-backward, and its corresponding trellis for exact probability distributions in Markov models). However, we know of no previous work studying efficient representations of exact distributions over clusterings. This paper presents definitions and proofs for a dynamic-programming inference procedure that computes the partition function, the marginal probability of a cluster, and the MAP clustering---all exactly. Rather than the Nth Bell number, these exact solutions take time and space proportional to the substantially smaller powerset of N. Indeed, we improve upon the time complexity of the algorithm introduced by Kohonen and Corander (2016) for this problem by a factor of N. While still large, this previously unknown result is intellectually interesting in its own right, makes feasible exact inference for important real-world small data applications (such as medicine), and provides a natural stepping stone towards sparse-trellis approximations that enable further scalability (which we also explore). In experiments, we demonstrate the superiority of our approach over approximate methods in analyzing real-world gene expression data used in cancer treatment.

Keywords: Clustering

Author Information

Craig Greenberg (University of Massachusetts Amherst / NIST)
Nicholas Monath (University of Massachusetts Amherst)
Ari Kobren (UMass Amherst)
Patrick Flaherty (University of Massachusetts, Amherst)
Andrew McGregor (University of Massachusetts Amherst)
Andrew McCallum (UMass Amherst)

More from the Same Authors