• Login
    View Item 
    •   oURspace Home
    • Faculty of Graduate Studies and Research
    • Theses and Dissertations
    • Master's Theses
    • View Item
    •   oURspace Home
    • Faculty of Graduate Studies and Research
    • Theses and Dissertations
    • Master's Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Simplifying D-Separation and M-Separation in Bayesian Networks

    Thumbnail
    View/Open
    dosSantos_Andre_200334126_MSC_CS_Fall2016.pdf (1.743Mb)
    Date
    2016-07
    Author
    dos Santos, André Evaristo
    Metadata
    Show full item record
    URI
    http://hdl.handle.net/10294/7635
    Abstract
    Many di erent platforms, techniques, and concepts can be employed while modeling and reasoning with Bayesian networks (BNs). A problem domain is modeled initially as a directed acyclic graph (DAG), denoted B, and the strengths of relationships are quanti ed by conditional probability tables (CPTs). Testing whether two sets X and Z of variables are conditionally independent given another set Y of variables is fundamental to BN modeling and inference. There are two well-known methods, called d-separation and m-separation, for this task. The founder of BNs suggested d-separation as a method for testing independen- cies. The crux of the linear implementation of d-separation is to determine all nodes reachable from X via active paths. We propose inaugural separation (i-separation) as a new method for testing independencies in BNs. i-Separation has several theo- retical and practical advantages. There are at least ve ways in which i-separation is simpler than d-separation, of which the most important is that \blocking" works in an intuitive fashion. An empirical evaluation shows that i-separation tends to be faster than d-separation in large BNs. In practice, d-separation is often utilized, since it has linear-time complexity. How- ever, many have had di culties in understanding d-separation in BNs. m-Separation is an equivalent method that is easier to understand by transforming the problem from directed separation in BNs into classical separation in undirected graphs. Two main steps of this transformation are pruning the BN and adding undirected edges. We propose u-separation as an even simpler method for testing independencies in a BN. Our approach also converts the problem into classical separation in an undi- rected graph. However, our method is based upon the novel concepts of inaugural variables and rationalization. u-Separation can prune fewer edges from the BN and add fewer undirected edges. Thereby, the primary advantage of u-separation over m- separation is that m-separation can prune unnecessarily and add super uous edges. Hence, u-separation is a simpler method in this respect.
    Collections
    • Master's Theses

    Copyright © 2020 University of Regina
    Contact Us | Send Feedback | Archer Library | University of Regina

     

     

    Browse

    All of oURspaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    About

    About oURspacePoliciesLicensesContacts

    Statistics

    View Usage Statistics

    Copyright © 2020 University of Regina
    Contact Us | Send Feedback | Archer Library | University of Regina