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

Both sides previous revision Previous revision | |||

cs-677sp2010:variable-elimination [2014/12/09 16:49] ryancha |
cs-677sp2010:variable-elimination [2014/12/11 23:41] (current) ryancha |
||
---|---|---|---|

Line 4: | Line 4: | ||

Consider the following Bayesian network: | Consider the following Bayesian network: | ||

- | [[File:chainNet.jpg]] | + | [[media:cs-677sp10:chainNet.jpg]] |

To compute p(D), we calculate the joint probability and sum out everything but D: | To compute p(D), we calculate the joint probability and sum out everything but D: | ||

Line 99: | Line 99: | ||

For an example, lets take the following Bayesian network that you have seen before (Russel,Norvig, 2005): | For an example, lets take the following Bayesian network that you have seen before (Russel,Norvig, 2005): | ||

- | [[File:exampleNet.jpg]] | + | [[media:cs-677sp10:exampleNet.jpg]] |

For convenience let B = Burglary, E = Earthquake, A = Alarm, M = Marycalls, and J = Johncalls. | For convenience let B = Burglary, E = Earthquake, A = Alarm, M = Marycalls, and J = Johncalls. | ||

Line 166: | Line 166: | ||

It should be apparent that the structure of the network has a lot to do with how much advantage is gained by the Variable Elimination algorithm. More complicated networks will result in factors that depend on a large number of variables that cannot be easily eliminated. A simple example is shown here: | It should be apparent that the structure of the network has a lot to do with how much advantage is gained by the Variable Elimination algorithm. More complicated networks will result in factors that depend on a large number of variables that cannot be easily eliminated. A simple example is shown here: | ||

- | [[File:graph_structure.jpg]] | + | [[media:cs-677sp10:graph_structure.jpg]] |

The resulting factors are: <b>p(B)p(C)p(D)p(E)p(A|B,C,D,E)</b>. Trying to eliminate even one variable will result in having to enumerate almost every combination of values for each variable, not much different than computing the whole joint distribution. | The resulting factors are: <b>p(B)p(C)p(D)p(E)p(A|B,C,D,E)</b>. Trying to eliminate even one variable will result in having to enumerate almost every combination of values for each variable, not much different than computing the whole joint distribution. | ||

Line 181: | Line 181: | ||

Given the following Bayesian Network (binary values), calculate p(B|A,E) using variable elimination (show steps). | Given the following Bayesian Network (binary values), calculate p(B|A,E) using variable elimination (show steps). | ||

- | [[File:sampleQ.jpg]] | + | [[media:cs-677sp10:sampleQ.jpg]] |

Probabilities: p(variable|condition) = {condition=false, condition=true} | Probabilities: p(variable|condition) = {condition=false, condition=true} |