This shows you the differences between two versions of the page.

Both sides previous revision Previous revision | |||

cs-677sp2010:undirected-models [2014/12/09 09:50] ryancha |
cs-677sp2010:undirected-models [2014/12/11 16:40] ryancha |
||
---|---|---|---|

Line 11: | Line 11: | ||

To show one situation where this model is appropriate, suppose we have a model with four Bernoulli nodes {A, B, C, D} with independency properties $(A \perp C | \{B, D\})$ and $(B \perp D | \{A, C\})$. How would you represent this model as a Bayesian network? | To show one situation where this model is appropriate, suppose we have a model with four Bernoulli nodes {A, B, C, D} with independency properties $(A \perp C | \{B, D\})$ and $(B \perp D | \{A, C\})$. How would you represent this model as a Bayesian network? | ||

- | [[File:Ben_img1directedA.png]] In this attempt, we get the property $(A \perp C | \{B, D\})$, but this network also implies that B and D are independent given only A. | + | [[media:cs-677sp10:Ben_img1directedA.png]] In this attempt, we get the property $(A \perp C | \{B, D\})$, but this network also implies that B and D are independent given only A. |

- | [[File:Ben_img1directedB.png]] This network also implies $(A \perp C | \{B, D\})$, but this network also implies that B and D are marginally independent. | + | [[media:cs-677sp10:Ben_img1directedB.png]] This network also implies $(A \perp C | \{B, D\})$, but this network also implies that B and D are marginally independent. |

- | [[File:Ben_img1undirected.png]] The only good way to naturally capture this network is with an MRF as shown in the image to the left. | + | [[media:cs-677sp10:Ben_img1undirected.png]] The only good way to naturally capture this network is with an MRF as shown in the image to the left. |

Now that we have shown a situation where a Bayesian network comes up lacking, we will go through a comparison of Markov random fields and Bayesian networks and how the techniques we have applied in class can also apply to MRFs. | Now that we have shown a situation where a Bayesian network comes up lacking, we will go through a comparison of Markov random fields and Bayesian networks and how the techniques we have applied in class can also apply to MRFs. | ||

Line 24: | Line 24: | ||

There are, however, dependencies that an MRF cannot represent. One of these is the induced dependency as shown below. If the child node is observed and has multiple parents, in a Bayesian network (BN) information can flow between the parent nodes. In an MRF, no information can flow across known nodes. | There are, however, dependencies that an MRF cannot represent. One of these is the induced dependency as shown below. If the child node is observed and has multiple parents, in a Bayesian network (BN) information can flow between the parent nodes. In an MRF, no information can flow across known nodes. | ||

- | [[File:Ben_induceddependency.png]] | + | [[media:cs-677sp10:Ben_induceddependency.png]] |

No information can flow because of the three Markov properties that define conditional independence for a Markov network: | No information can flow because of the three Markov properties that define conditional independence for a Markov network: | ||

Line 30: | Line 30: | ||

*''Pairwise Markov property'': Any two non-adjacent random variables are conditionally independent given all other variables in the network are observed. | *''Pairwise Markov property'': Any two non-adjacent random variables are conditionally independent given all other variables in the network are observed. | ||

- | [[File:Ben_pairwise.png]] $(A \perp Z | \{all other nodes\})$ | + | [[media:cs-677sp10:Ben_pairwise.png]] $(A \perp Z | \{all other nodes\})$ |

*''Local Markov property'': A variable is conditionally independent of all other variables given its neighbors. | *''Local Markov property'': A variable is conditionally independent of all other variables given its neighbors. | ||

- | [[File:Ben_local.png]] $(B \perp C | \{neighbors of C\})$ | + | [[media:cs-677sp10:Ben_local.png]] $(B \perp C | \{neighbors of C\})$ |

*''Global Markov property'': Any two subsets of variables are conditionally independent given a separating subset where every path between the two subsets pass through the observed subset. | *''Global Markov property'': Any two subsets of variables are conditionally independent given a separating subset where every path between the two subsets pass through the observed subset. | ||

- | [[File:Ben_global.png]] $(S1 \perp S2 | \{S\})$ | + | [[media:cs-677sp10:Ben_global.png]] $(S1 \perp S2 | \{S\})$ |

These properties also lead to the conclusion that the Markov blanket for any particular node A in an MRF is simply A and all the nodes adjacent to A. | These properties also lead to the conclusion that the Markov blanket for any particular node A in an MRF is simply A and all the nodes adjacent to A. | ||

Line 258: | Line 258: | ||

# Moralize. | # Moralize. | ||

- | [[File:Bayestomarkov.png]] | + | [[media:cs-677sp10:Bayestomarkov.png]] |

Moralizing handles the induced dependency problem that was described in the Section 2. The term moralize comes from the idea that it would be immoral for any child node to have multiple parents if the parents were not connected. Therefore, an undirected edge must be introduced between any parents nodes that share a child. | Moralizing handles the induced dependency problem that was described in the Section 2. The term moralize comes from the idea that it would be immoral for any child node to have multiple parents if the parents were not connected. Therefore, an undirected edge must be introduced between any parents nodes that share a child. | ||

Line 267: | Line 267: | ||

Converting from a Markov to a Bayesian network faces an interesting problem: data flow. In the Markov network below information can flow from B to C, but if this were converted to a Bayesian network, this flow of information would not exist. | Converting from a Markov to a Bayesian network faces an interesting problem: data flow. In the Markov network below information can flow from B to C, but if this were converted to a Bayesian network, this flow of information would not exist. | ||

- | [[File:Markovtobayesproblem.png]] | + | [[media:cs-677sp10:Markovtobayesproblem.png]] |

To overcomes this, you perform three steps: | To overcomes this, you perform three steps: | ||

Line 274: | Line 274: | ||

# Add directionality. | # Add directionality. | ||

- | [[File:Markovtobayes.png]] | + | [[media:cs-677sp10:Markovtobayes.png]] |

It is important that when adding directionality, a topological sort is performed and that directionality is set in the direction of the sort. This guarantees the necessary dependencies. | It is important that when adding directionality, a topological sort is performed and that directionality is set in the direction of the sort. This guarantees the necessary dependencies. | ||

Line 283: | Line 283: | ||

Given the Bayesian network below, convert the network to a Markov random field. Then, assuming that each node can take a state of zero or one, create a potential table assigning values of your choice to the potentials. Then find the following probabilities: $P(a^0, b^1, c^1), P(a^1), P(b^1 | c^1), P(a^0 | b^0, c^0)$. Show your work so that it is easy to follow what you did. | Given the Bayesian network below, convert the network to a Markov random field. Then, assuming that each node can take a state of zero or one, create a potential table assigning values of your choice to the potentials. Then find the following probabilities: $P(a^0, b^1, c^1), P(a^1), P(b^1 | c^1), P(a^0 | b^0, c^0)$. Show your work so that it is easy to follow what you did. | ||

- | [[File:Examquestion.png]] | + | [[media:cs-677sp10:Examquestion.png]] |

= References and Further Reading = | = References and Further Reading = |