Open Collections

Herded Gibbs and discretized herded Gibbs sampling

University of British Columbia

Statistical inference is at the heart of the probabilistic programming approach to artificial intelligence; as far as statistical inference is concerned, the Gibbs sampler is one of the most widely applicable and popular random sampling techniques. On the flip side, deterministic sampling is still nascent and has yet to be widely accepted into the field of Bayesian inference. In this thesis, we advance the domain of deterministic sampling by discussing and evaluating two deterministic sampling techniques inspired by the Gibbs sampler. The first technique is the recently-introduced herded Gibbs sampler and the second is the novel discretized herded Gibbs sampler. Herded Gibbs sampling is an entirely deterministic algorithm with an impressive O(1/T) convergence rate for both models with independent variables and fully connected probabilistic graphical models. However, the convergence for herded Gibbs on sparsely connected probabilistic graphical models is still an open problem. Additionally, the computational complexity of herded Gibbs increases exponentially with the connectivity of the probabilistic graphical model, making it better suited for partially connected graphical models. We empirically demonstrate that herded Gibbs outperforms Gibbs on partially connected probabilistic graphical models for the tasks of image denoising with Markov Random Fields and named entity recognition with Conditional Random Fields. Furthermore, we develop discretized herded Gibbs as a variant of herded Gibbs that attempts to reduce the spatial complexity by approximating herded Gibbs. Though discretized herded Gibbs achieves linear storage requirements and is capable of fast initial convergence rates, it can only approximate the target up to a finite accuracy. This thesis highlights the power of one recent deterministic sampling algorithm and shows that deterministic sampling with good space and time complexity remains an elusive goal.

Text

2013-08-27

CC0 1.0 Universal

http://hdl.handle.net/2429/44896

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/publicdomain/zero/1.0/