##### Differences

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

 cs-677sp2010:variable-elimination [2014/12/09 09:49]ryancha cs-677sp2010:variable-elimination [2014/12/11 16:41] (current)ryancha Both sides previous revision Previous revision 2014/12/11 16:41 ryancha 2014/12/09 09:49 ryancha 2014/12/09 09:49 ryancha created 2014/12/11 16:41 ryancha 2014/12/09 09:49 ryancha 2014/12/09 09:49 ryancha created 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)​. 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)​. 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}