Back to search

University of British Columbia

Herded Gibbs and discretized herded Gibbs sampling

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Eskelinen, Mareija

Rights

dc:rights
Statement dc:rights
  • CC0 1.0 Universal
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/44896

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Eskelinen, Mareija. Herded Gibbs and discretized herded Gibbs sampling. master's thesis, University of British Columbia, 2013. http://hdl.handle.net/2429/44896