Timezone: »
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.
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
-
2021 : CSFCube - A Test Collection of Computer Science Research Articles for Faceted Query by Example »
Sheshera Mysore · Tim O'Gorman · Andrew McCallum · Hamed Zamani -
2022 : Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests »
Erica Cai · Andrew McGregor · David Jensen -
2022 Poster: Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings »
Dongxu Zhang · Michael Boratko · Cameron Musco · Andrew McCallum -
2022 Poster: Estimation of Entropy in Constant Space with Improved Sample Complexity »
Maryam Aliakbarpour · Andrew McGregor · Jelani Nelson · Erik Waingarten -
2022 Poster: Structured Energy Network As a Loss »
Jay Yoon Lee · Dhruvesh Patel · Purujit Goyal · Wenlong Zhao · Zhiyang Xu · Andrew McCallum -
2021 Poster: Capacity and Bias of Learned Geometric Embeddings for Directed Graphs »
Michael Boratko · Dongxu Zhang · Nicholas Monath · Luke Vilnis · Kenneth L Clarkson · Andrew McCallum -
2020 Poster: Improving Local Identifiability in Probabilistic Box Embeddings »
Shib Dasgupta · Michael Boratko · Dongxu Zhang · Luke Vilnis · Xiang Li · Andrew McCallum -
2019 : Coffee Break & Poster Session 2 »
Juho Lee · Yoonho Lee · Yee Whye Teh · Raymond A. Yeh · Yuan-Ting Hu · Alex Schwing · Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Christian Bueno · Aditya Sanghi · Pradeep Kumar Jayaraman · Ignacio Arroyo-Fernández · Andrew Hryniowski · Vinayak Mathur · Sanjay Singh · Shahrzad Haddadan · Vasco Portilheiro · Luna Zhang · Mert Yuksekgonul · Jhosimar Arias Figueroa · Deepak Maurya · Balaraman Ravindran · Frank NIELSEN · Philip Pham · Justin Payan · Andrew McCallum · Jinesh Mehta · Ke SUN -
2019 : Coffee Break & Poster Session 1 »
Yan Zhang · Jonathon Hare · Adam Prugel-Bennett · Po Leung · Patrick Flaherty · Pitchaya Wiratchotisatian · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam · Theja Tulabandhula · Fabian Fuchs · Adam Kosiorek · Ingmar Posner · William Hang · Anna Goldie · Sujith Ravi · Azalia Mirhoseini · Yuwen Xiong · Mengye Ren · Renjie Liao · Raquel Urtasun · Haici Zhang · Michele Borassi · Shengda Luo · Andrew Trapp · Geoffroy Dubourg-Felonneau · Yasmeen Kussad · Christopher Bender · Manzil Zaheer · Junier Oliva · Michał Stypułkowski · Maciej Zieba · Austin Dill · Chun-Liang Li · Songwei Ge · Eunsu Kang · Oiwi Parker Jones · Kelvin Ka Wing Wong · Joshua Payne · Yang Li · Azade Nazi · Erkut Erdem · Aykut Erdem · Kevin O'Connor · Juan J Garcia · Maciej Zamorski · Jan Chorowski · Deeksha Sinha · Harry Clifford · John W Cassidy -
2019 : Opening Remarks »
Manzil Zaheer · Nicholas Monath · Ari Kobren · Junier Oliva · Barnabas Poczos · Ruslan Salakhutdinov · Andrew McCallum -
2019 Workshop: Sets and Partitions »
Nicholas Monath · Manzil Zaheer · Andrew McCallum · Ari Kobren · Junier Oliva · Barnabas Poczos · Ruslan Salakhutdinov -
2019 : Andrew McCallum: Learning DAGs and Trees with Box Embeddings and Hyperbolic Embeddings »
Andrew McCallum -
2019 Poster: Sample Complexity of Learning Mixture of Sparse Linear Regressions »
Akshay Krishnamurthy · Arya Mazumdar · Andrew McGregor · Soumyabrata Pal -
2019 Poster: Search-Guided, Lightly-Supervised Training of Structured Prediction Energy Networks »
Amirmohammad Rooshenas · Dongxu Zhang · Gopal Sharma · Andrew McCallum -
2019 Poster: Offline Contextual Bandits with High Probability Fairness Guarantees »
Blossom Metevier · Stephen Giguere · Sarah Brockman · Ari Kobren · Yuriy Brun · Emma Brunskill · Philip Thomas -
2017 : Invited Talk: "Light Supervision of Structured Prediction Energy Networks" »
Andrew McCallum -
2017 : Poster Session - Session 2 »
Ambrish Rawat · Armand Joulin · Peter A Jansen · Jay Yoon Lee · Muhao Chen · Frank F. Xu · Patrick Verga · Brendan Juba · Anca Dumitrache · Sharmistha Jat · Robert Logan · Dhanya Sridhar · Fan Yang · Rajarshi Das · Pouya Pezeshkpour · Nicholas Monath -
2017 Poster: Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samples »
Haw-Shiuan Chang · Erik Learned-Miller · Andrew McCallum -
2014 Workshop: 4th Workshop on Automated Knowledge Base Construction (AKBC) »
Sameer Singh · Fabian M Suchanek · Sebastian Riedel · Partha Pratim Talukdar · Kevin Murphy · Christopher Ré · William Cohen · Tom Mitchell · Andrew McCallum · Jason E Weston · Ramanathan Guha · Boyan Onyshkevych · Hoifung Poon · Oren Etzioni · Ari Kobren · Arvind Neelakantan · Peter Clark -
2012 Poster: MAP Inference in Chains using Column Generation »
David Belanger · Alexandre T Passos · Sebastian Riedel · Andrew McCallum -
2011 Workshop: Big Learning: Algorithms, Systems, and Tools for Learning at Scale »
Joseph E Gonzalez · Sameer Singh · Graham Taylor · James Bergstra · Alice Zheng · Misha Bilenko · Yucheng Low · Yoshua Bengio · Michael Franklin · Carlos Guestrin · Andrew McCallum · Alexander Smola · Michael Jordan · Sugato Basu -
2011 Poster: Query-Aware MCMC »
Michael Wick · Andrew McCallum -
2009 Poster: FACTORIE: Probabilistic Programming via Imperatively Defined Factor Graphs »
Andrew McCallum · Karl Schultz · Sameer Singh -
2009 Poster: Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference »
Michael Wick · Khashayar Rohanimanesh · Sameer Singh · Andrew McCallum -
2009 Spotlight: Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference »
Michael Wick · Khashayar Rohanimanesh · Sameer Singh · Andrew McCallum -
2009 Poster: Rethinking LDA: Why Priors Matter »
Hanna Wallach · David Mimno · Andrew McCallum -
2009 Spotlight: Rethinking LDA: Why Priors Matter »
Hanna Wallach · David Mimno · Andrew McCallum