Summary Exam Review Session D-Separation and Variable Elimination January 27, 2018 If a V-structure is open, because a descendent of the middle node is observed, is that descendant part of the active trail? No, the descendant is not part of the active trail. Given a Bayesian Network and two nodes X and Y that are connected by an active path, are X and Y dependent, or is the statement inconclusive? As there exists an active trail, X and Y are not d-separated, but in general we cannot say they are dependent. We have the following: d-sep(X; Y ) ⇒ X and Y are independent X and Y are independent 6⇒ d-sep(X; Y ) In the example above, without knowing the probability distribution, we cannot say that X and Y are dependent (it could be that all nodes in the Bayesian Network are independent!). But, for any given Bayesian Network, such that there is an active trail from X to Y, there exists a probability distribution that factorizes according to this network and X and Y are dependent. For the variable elimination algorithm, does starting with leaf nodes always give a good ordering? No, this works only for polytrees. How can we determine a good ordering for the variable elimination algorithm for general Bayesian Networks? Finding a good ordering, which does not result exponentially many operations during the marginalization, is NP-hard for general Bayesian Networks. However, one can use heuristics, like starting with low degree nodes, to avoid that the new factors depends on a lot of other nodes. 1