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. / Graduation date: 1994
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/35631 |
| Date | 08 June 1993 |
| Creators | Li, Zhaoyu |
| Contributors | D'Ambrosio, Bruce |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.1835 seconds