You are here

Acceleration Methods Forbayesian Network Sampling

Title: Acceleration Methods Forbayesian Network Sampling.
92 views
69 downloads
Name(s): Yu, Haohai, author
Van Engelen, Robert A., professor directing dissertation
Van Hoeij, Mark, university representative
Mascagni, MichaelV., committee member
Liu, Xiuwen, committee member
Department of Computer Science, degree granting department
Florida State University, degree granting institution
Type of Resource: text
Genre: Text
Issuance: monographic
Date Issued: 2011
Publisher: Florida State University
Place of Publication: Tallahassee, Florida
Physical Form: computer
online resource
Extent: 1 online resource
Language(s): English
Abstract/Description: Bayesian inference with Bayesian networks is a #P-complete problem in general. Exact Bayesian inference is feasible in practice only on small-scale Bayesian networks or networks that are dramatically simplified, such as with naive Bayes or other approximations. Stochastic sampling methods, in particular importance sampling, form one of the most prominent and efficient approximate inference techniques that gives answers in reasonable computing time. A critical problem for importance sampling is to choose an importance function to efficiently and accurately sample the posterior probability distribution given a set of observed variables (also referred to as evidence). Choosing an importance function, or designing a new function, faces two major hurdles: how to approach the posterior probability distribution accurately and how to reduce the generation of undesirable inconsistent samples caused by deterministic relations in the network (also known as the rejection problem). In my dissertation I propose Refractor Importance Sampling, consisting of a family of importance sampling algorithms to effectively break the lower bound on the error of the importance function to ensure it can approach the posterior probability distribution of a Bayesian network given evidence. The aim is to increase the convergence rate of the approximation and to reduce sampling variance. I also propose Posterior Subgraph Clustering to improve the sampling process by breaking a network into several small independent subgraphs. To address the rejection problem, I propose Zero Probability Backfilling and Compressed Vertex Tree methods to detect and store deterministic constrains that are the root cause of inconsistent samples. The rejection problem is NP-hard and I prove in my dissertation that even limiting the inconsistent samples to a certain degree with positive probability is too hard to be polynomial. I propose the k-test to measure the hardness of the rejection problem by scaling the clause density of a CNF constructed from a Bayesian network. In the final part of my dissertation, I design and implement importance sampling algorithms for GPU platforms to speed up sampling by exploiting fine-grain parallelism. GPUs are cost-effective computing devices. However, the randomness of memory-intensive operations by Bayesian network sampling causes difficulties to obtain computational speedups with these devices. In my dissertation I propose a new method, Parallel Irregular Wavefront Sampling, to improve memory access on GPU by leveraging the conditional independence relations between variables in a network. I improve this scheme further by using the posterior distribution as an oracle to reduce costly memory fetches in the GPU. The proposed methods are implemented and experimentally tested. The results show a significant contribution in efficiency and accuracy of Bayesian network sampling for Bayesian inference with real-world and synthetic benchmark Bayesian networks.
Identifier: FSU_migr_etd-0912 (IID)
Submitted Note: A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
Degree Awarded: Summer Semester, 2011.
Date of Defense: June 22, 2011.
Keywords: Bayesian Inference, Bayesian Network, Importance Sampling, GPGPU
Bibliography Note: Includes bibliographical references.
Advisory Committee: Robert A. van Engelen, Professor Directing Dissertation; Mark van Hoeij, University Representative; MichaelV. Mascagni, Committee Member; Xiuwen Liu, Committee Member.
Subject(s): Computer science
Persistent Link to This Record: http://purl.flvc.org/fsu/fd/FSU_migr_etd-0912
Owner Institution: FSU

Choose the citation style.
Yu, H. (2011). Acceleration Methods Forbayesian Network Sampling. Retrieved from http://purl.flvc.org/fsu/fd/FSU_migr_etd-0912