Graduate Thesis Or Dissertation
 

A factoring approach for probabilistic inference in belief networks

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/rf55z9775

Descriptions

Attribute NameValues
Creator
Abstract
  • Reasoning about any realistic domain always involves a degree of uncertainty. Probabilistic inference in belief networks is one effective way of reasoning under uncertainty. Efficiency is critical in applying this technique, and many researchers have been working on this topic. This thesis is the report of our research in this area. This thesis contributes a new framework for probabilistic inference in belief networks. The previously developed algorithms depend on the topological structure of a belief network to perform inference efficiently. Those algorithms are constrained by the way they use topological information and may not work efficiently for some inference tasks. This thesis explores the essence of probabilistic inference, analyzes previously developed algorithms, and presents a factoring approach for probabilistic inference. It proposes that efficient probabilistic inference in belief networks can be considered as an optimal factoring problem. The optimal factoring framework provides an alternative perspective on probabilistic inference and a quantitative measure of efficiency for an algorithm. Using this framework, this thesis presents an optimal factoring algorithm for poly-tree networks and for arbitrary belief networks (albeit with exponential worst-case time complexity for non-poly-tree networks). Since the optimal factoring problem in general is a hard problem, a heuristic algorithm, called set-factoring, is developed for multiply-connected belief networks. Set factoring is shown to outperform previously developed algorithms. We also apply the optimal factoring framework to the problem of finding an instantiation of all nodes of a belief network which has the largest probability and present an efficient algorithm for that task. Extensive computation of probabilistic inference renders any currently used exact probabilistic inference algorithm intractable for large belief networks. One way to extend this boundary is to consider parallel hardware. This thesis also explores the issue of parallelizing probabilistic inference in belief networks. The feasibility of parallelizing probabilistic inference is demonstrated analytically and experimentally. Exponential-time numerical computation can be reduced by a polynomial-time factoring heuristic. This thesis offers an insight into the effect of the structure of a belief network on speedup and efficiency.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items