Sampling Table Configurations for the Hierarchical Poisson-Dirichlet Process
Lecture notes in computer sciencePublished 1 January 2011
Changyou Chen, Lan Du, Wray Buntine
Citations34
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new table representation for the hierarchical PDPs is proposed by introducing an auxiliary latent variable, called table indicator, to record which customer takes responsibility for starting a new table, and a block Gibbs sampling algorithm is developed, which can jointly sample the data item and its table contribution.
Abstract
Hierarchical modeling and reasoning are fundamental in machine intelligence, and for this the two-parameter Poisson-Dirichlet Process (PDP) plays an important role. The most popular MCMC sampling algorithm for the hierarchical PDP and hierarchical Dirichlet Process is to conduct an incremental sampling based on the Chinese restaurant metaphor, which originates from the Chinese restaurant process (CRP). In this paper, with the same metaphor, we propose a new table representation for the hierarchical PDPs by introducing an auxiliary latent variable, called table indicator, to record which customer takes responsibility for starting a new table. In this way, the new representation allows full exchangeability that is an essential condition for a correct Gibbs sampling algorithm. Based on this representation, we develop a block Gibbs sampling algorithm, which can jointly sample the data item and its table contribution. We test this out on the hierarchical Dirichlet process variant of latent Dirichlet allocation (HDP-LDA) developed by Teh, Jordan, Beal and Blei. Experiment results show that the proposed algorithm outperforms their "posterior sampling by direct assignment" algorithm in both out-of-sample perplexity and convergence speed. The representation can be used with many other hierarchical PDP models.
Keywords
Computer ScienceMathematics
Journal of Machine Learning ResearchLatent dirichlet allocation
27,049 Citations2003David M. Blei, Andrew Y. Ng +1 more
Journal of the American Statistical AssociationHierarchical Dirichlet Processes
3,567 Citations2006Yee Whye Teh, Michael I. Jordan +2 more
This work considers problems involving groups of data where each observation within a group is a draw from a mixture model and where it is desirable to share mixture components between groups, and considers a hierarchical model, specifically one in which the base measure for the childDirichlet processes is itself distributed according to a Dirichlet process.
Journal of the American Statistical AssociationGibbs Sampling Methods for Stick-Breaking Priors
1,556 Citations2001Hemant Ishwaran, Lancelot F. James
Two general types of Gibbs samplers that can be used to fit posteriors of Bayesian hierarchical models based on stick-breaking priors are presented and the blocked Gibbs sampler, based on an entirely different approach that works by directly sampling values from the posterior of the random measure.
The Annals of ProbabilityThe two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
1,255 Citations1997Jim Pitman, Marc Yor
The Infinite Gaussian Mixture Model
987 Citations1999Carl Edward Rasmussen
This paper presents an infinite Gaussian mixture model which neatly sidesteps the difficult problem of finding the "right" number of mixture components and uses an efficient parameter-free Markov Chain that relies entirely on Gibbs sampling.
Journal of the ACMThe nested chinese restaurant process and bayesian nonparametric inference of topic hierarchies
667 Citations2010David M. Blei, Thomas L. Griffiths +1 more
An application to information retrieval in which documents are modeled as paths down a random tree, and the preferential attachment dynamics of the nCRP leads to clustering of documents according to sharing of topics at multiple levels of abstraction.
A hierarchical Bayesian language model based on Pitman-Yor processes
498 Citations2006Yee Whye Teh
It is shown that an approximation to the hierarchical Pitman-Yor language model recovers the exact formulation of interpolated Kneser-Ney, one of the best smoothing methods for n-gram language models.
Online Variational Inference for the Hierarchical Dirichlet Process
330 Citations2011Chong Wang, John Paisley +1 more
This work proposes an online variational inference algorithm for the HDP, an algorithm that is easily applicable to massive and streaming data, and lets us analyze much larger data sets.
Cambridge University Press eBooksHierarchical Bayesian nonparametric models with applications
328 Citations2010Yee Whye Teh, Michael I. Jordan
The role of hierarchical modeling in Bayesian nonparametrics is discussed, focusing on models in which the infinite-dimensional parameters are treated hierarchically, and the value of these hierarchical constructions is demonstrated in a wide range of practical applications.
The MIT Press eBooksAdaptor Grammars: A Framework for Specifying Compositional Nonparametric Bayesian Models
274 Citations2007Mark Johnson, Thomas L. Griffiths +1 more
This paper presents a general-purpose inference algorithm for adaptor grammars, making it easy to define and use such models, and illustrates how several existing nonparametric Bayesian models can be expressed within this framework.
Journal of the ACMSpace-time tradeoffs for approximate nearest neighbor searching
232 Citations2009Sunil Arya, Theocharis Malamatos +1 more
There is a single approach to nearest neighbor searching, which both improves upon existing results and spans the spectrum of space-time tradeoffs, and new algorithms for constructing AVDs and tools for analyzing their total space requirements are provided.
Interpolating between types and tokens by estimating power-law generators
215 Citations2005Sharon Goldwater, Mark Johnson +1 more
It is shown that taking a particular stochastic process - the Pitman-Yor process - as an adaptor justifies the appearance of type frequencies in formal analyses of natural language, and improves the performance of a model for unsupervised learning of morphology.
Collapsed Variational Inference for HDP
145 Citations2007Yee Whye Teh, Kenichi Kurihara +1 more
This work obtains the first variational algorithm to deal with the hierarchical Dirichlet process and with hyperparameters ofDirichlet variables, and shows a significant improvement in accuracy.
A Bayesian Interpretation of Interpolated Kneser-Ney
108 Citations2006YW Teh
A stochastic memoizer for sequence data
98 Citations2009Frank Wood, Cédric Archambeau +3 more
An unbounded-depth, hierarchical, Bayesian nonparametric model for discrete sequence data that can be estimated from a single training sequence, yet shares statistical strength between subsequent symbol predictive distributions in such a way that predictive performance generalizes well is proposed.
Lecture notes in computer scienceDiscrete Component Analysis
90 Citations2006Wray Buntine, Aleks Jakulin
A unified theory for analysis of components in discrete data is presented, and the methods compared with techniques such as independent component analysis, non-negative matrix factorisation and latent Dirichlet allocation are compared.
Machine LearningA segmented topic model based on the two-parameter Poisson-Dirichlet process
75 Citations2010Lan Du, Wray Buntine +1 more
This paper takes the simplest form of structure, a document consisting of multiple segments, as the basis for a new form of topic model, and uses the marginalized posterior of a two-parameter Poisson-Dirichlet process (or Pitman-Yor process) to handle the hierarchical modelling.
Lecture notes in computer scienceEstimating Likelihoods for Topic Models
66 Citations2009Wray Buntine
A number of recent methods for estimating the likelihood of unseen documents, for instance to perform testing or model comparison, become available and improves their theory, performance, and testing.
Variational Inference for the Nested Chinese Restaurant Process
52 Citations2009Chong Wang, David M. Blei
To employ variational methods, a tree-based stick-breaking construction of the nCRP mixture model is derived, and a novel variational algorithm is developed that efficiently explores a posterior over a large set of combinatorial structures.
IEEE Transactions on Pattern Analysis and Machine IntelligenceHierarchical Bayesian Modeling of Topics in Time-Stamped Documents
48 Citations2009Iulian Pruteanu-Malinici, Lu Ren +3 more
This work considers the problem of inferring and modeling topics in a sequence of documents with known publication dates as well as the US Presidential State of the Union addresses from 1790 to 2008, and proposes a hierarchical model that infers the change in the topic mixture weights as a function of time.
arXiv (Cornell University)A Bayesian View of the Poisson-Dirichlet Process
48 Citations2010Wray Buntine, Marcus Hütter
A Bayesian interpretation of the Poisson-Dirichlet process is presented: it is a mixture using an improper and infinite dimensional Dirichlet distribution, and thus all its sampling properties fit naturally.
International series in intelligent technologiesAdvances in Machine Learning
43 Citations2002Maarten W. van Someren
Some application types from different domains are reviewed taking under consideration the user perspective and possible future prospects in Machine Learning are identified in the areas of relational learning and compound methods that construct models able to mix representation forms.
Sequential Latent Dirichlet Allocation: Discover Underlying Topic Structures within a Document
40 Citations2010Lan Du, Wray Buntine +1 more
By taking into account the sequential structure within a document, the SeqLDA model has a higher fidelity over LDA in terms of perplexity (a standard measure of dictionary-based compressibility) and yields a nicer sequential topic structure than LDA.
The Infinite Markov Model
30 Citations2007Daichi Mochihashi, Eiichiro Sumita
A nonparametric Bayesian method of estimating variable order Markov processes up to a theoretically infinite order by extending a stick-breaking prior to trees of infinite depth associated with a hierarchical Chinese restaurant process, which directly infers the hidden orders of Markov dependencies from which each symbol originated.
A note on the implementation of hierarchical dirichlet processes
24 Citations2009Phil Blunsom, Trevor Cohn +2 more
This work presents an alternative formulation of collapsed Gibbs samplers for non-parametric Bayesian models which is exact and can be computed easily, however this approach does not work for hierarchical models, for which case an efficient data structure is presented which has a better space complexity than the naive approach.
CORE Scholar (Wright State University)Bayesian Modeling of Dependency Trees Using Hierarchical Pitman-Yor Priors
20 Citations2008Hanna Wallach, Charles Sutton +1 more
Two hierarchical Bayesian models for dependency trees are described and Eisner’s classic generative dependency model can be substantially improved by using a hierarchical Pitman-Yor process as a prior over the distribution over dependents of a word.
ANU Open Research (Australian National University)Bayesian Networks on Dirichlet Distributed Vectors
3 Citations2010Wray Buntine, Lan Du +1 more
This paper presents generalized networks of Dirichlet distributions, and shows how, using the two-parameter Poisson-Dirichlet distribution and Gibbs sampling, one can do approximate inference over them.