Optimal inference with local expressions Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/k3569689b

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Probabilistic inference using Bayesian networks is now a well-established approach for reasoning under uncertainty. Among many e ciency-driven tech- niques which have been developed, the Optimal Factoring Problem (OFP) is distinguished for presenting a combinatorial optimization point of view on the problem. The contribution of this thesis is to extend OFP into a theoretical frame- work that not only covers the standard Bayesian networks but also includes non-standard Bayesian networks. A non-standard Bayesian network has struc- tures within its local distributions that are signi cant to the problem. This thesis presents value sets algebra as a coherent framework that facilitates formal treatments of inference in both standard and non-standard Bayesian networks as a combinatorial optimization problem. Parallel to value sets algebra theory local expression languages allow one to symbolically encode Bayesian network distributions. Such symbolic encod- ings allow all the structural and numerical information in distributions to be represented in the most compact form. However, the symbolic and syntactic exibilities in local expression languages have the usual drawback of allow- ing possible incoherent expressions. Value sets algebra leads us to an e cient coherency veri cation on such expressions. This thesis views optimal inference with local expressions as an optimal search problem. The search space for this problem is shown to be so large that it renders any exhaustive search impractical. Hence it is necessary to turn to heuristic solutions. Using A* heuristic framework and ideas from OFP, which is the counterpart of this problem for standard Bayesian networks, a heuris- tic algorithm for the problem is developed. As a key feature, this algorithm di erentiates between symbolic combinations of expressions and arithmetic op- erations in the expressions. Cost bearing arithmetic operations are performed only when su cient information is available to guarantee that no saving oppor- tunities are lost. On the other hand, expressions are combined in a way that quickly provides maximum opportunity for e cient arithmetic operations. This thesis also explores the representation of Intercausal Independencies (ICI) in Bayesian networks and de nes some new operators in local expression language which are shown to facilitate more e cient ICI representations.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Language
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2009-01-27T15:30:36Z (GMT). No. of bitstreams: 1 Mohammad_Borujerdi.pdf: 539067 bytes, checksum: e6b55b284763d691d97596afa38a8238 (MD5)
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2009-01-27T15:28:44Z (GMT) No. of bitstreams: 1 Mohammad_Borujerdi.pdf: 539067 bytes, checksum: e6b55b284763d691d97596afa38a8238 (MD5)
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2009-01-27T15:30:35Z (GMT) No. of bitstreams: 1 Mohammad_Borujerdi.pdf: 539067 bytes, checksum: e6b55b284763d691d97596afa38a8238 (MD5)
  • description.provenance : Submitted by Philip Vue (vuep@onid.orst.edu) on 2009-01-26T18:21:22Z No. of bitstreams: 1 Mohammad_Borujerdi.pdf: 539067 bytes, checksum: e6b55b284763d691d97596afa38a8238 (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items