liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Optimizing Queries in Bayesian Networks
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology.
2012 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

This thesis explores and compares different methods of optimizing queries in Bayesian networks. Bayesian networks are graph-structured models that model probabilistic variables and their influences on each other; a query poses the question of what probabilities certain variables assume, given observed values on certain other variables. Bayesian inference (calculating these probabilities) is known to be NP-hard in general, but good algorithms exist in practice.

Inference optimization traditionally concerns itself with finding and tweaking efficient algorithms, and leaves the choice of algorithms' parameters, as well as the construction of inference-friendly Bayesian network models, as an exercise to the end user. This thesis aims towards a more systematic approach to these topics: We try to optimize the structure of a given Bayesian network for inference, also taking into consideration what is known about the kind of queries that are posed.

First, we implement several automatic model modifications that should help to make a model more suitable for inference. Examples of these are the conversion of definitions of conditional probability distributions from table form to noisy gates, and divorcing parents in the graph. Second, we introduce the concepts of usage profiles and query interfaces on Bayesian networks and try to take advantage of them. Finally, we conduct performance measurements of the different options available in the used library for Bayesian networks, to compare the effects of different options on speedup and stability, and to answer the question of which options and parameters represent the optimal choice to perform fast queries in the end product.

The thesis gives an overview of what issues are important to consider when trying to optimize an application's query performance in Bayesian networks, and when trying to optimize Bayesian networks for queries.

The project uses the SMILE library for Bayesian networks by the University of Pittsburgh, and includes a case study on script-generated Bayesian networks for troubleshooting by Scania AB.

Place, publisher, year, edition, pages
2012. , 79 p.
Keyword [en]
Bayesian Networks, SMILE, Noisy-MAX, inference, relevance reasoning
National Category
Computer Science
URN: urn:nbn:se:liu:diva-86716ISRN: LIU-IDA/LITH-EX-A--12/062-SEOAI: diva2:580727
Subject / course
Master's programme in Computer Science
2012-10-30, Muhammad al-Khwarizmi, 23:44 (English)
Available from: 2013-01-15 Created: 2012-12-25 Last updated: 2013-01-15Bibliographically approved

Open Access in DiVA

Optimizing Queries in Bayesian Networks(765 kB)265 downloads
File information
File name FULLTEXT01.pdfFile size 765 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Search in DiVA

By author/editor
Förstner, Johannes
By organisation
Database and information techniquesThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 265 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 94 hits
ReferencesLink to record
Permanent link

Direct link