View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Treecost-based Preprocessing for Probabilistic Networks

        Thumbnail
        View/Open
        Thesis - Myrna van de Burgwal.pdf (782.5Kb)
        Publication date
        2015
        Author
        Burgwal, M.D. van de
        Metadata
        Show full item record
        Summary
        Probabilistic inference is an important problem in probability theory and concerns the process of computing the probability distribution of variables, given the evidence of other variables. An often used algorithm for this problem is the junction-tree propagation algorithm. To minimise the time to process all the probabilities by means of the algorithm, an optimal tree decomposition is required. A good parameter that measures the optimality of a tree decomposition is treecost. Unfortunately, computing the tree decomposition with minimal treecost is NP-hard Nevertheless, it can be simpli?ed by applying reduction rules that shrink the graph. These rules are familiar from treewidth, which is a well-studied parameter compared to treecost. In this thesis, a set of reduction rules are introduced and proven to be valid. This set includes rules that remove vertices and separate the graph by its components. Thereafter, experiments are conducted on input graphs, which are real-life probabilistic networks. Results of the experiment show that the graphs are reduced signi?cantly, due to these reduction rules. This, in turn, decreases the time to solve probabilistic inference. Prior knowledge about graph theory and complexity theory is assumed for this thesis.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/19659
        Collections
        • Theses
        Utrecht university logo