AIspace

Practice Exercise 6.C

Variable Elimination

Back to practice exercises.

1: Background Reading

6.4 Probabilistic Inference

2: Learning Goals

Build a belief network for a simple domain.
Define factors. Derive new factors from existing factors.
Carry out variable elimination by using factor representation and using the factor operations.
Use techniques to simplify variable elimination.

3: Directed Questions

What is a factor? [solution]
What are the operations applied to factors in the variable elimination algorithm? [solution]
What do we mean by the term belief network inference problem? [solution]
Define elimination ordering. [solution]
What are the three main steps of variable elimination? [solution]

4: Exercise: Newspaper Delivery

Bill has noticed that his morning newspaper delivery has been sporadic. There are several relevant variables relating to whether or not the paper is delivered. Delivery is dependent on the paper having been successfully printed the previous night. Possible explanations for a paper not having been printed are a malfunction at the printing press, or the end of civilization as we know it.

Before continuing, write down the relevant variables for this scenario.

Let's assign some probabilities. The prior probability of a printer malfunction is 0.05. Bill has been noticing some ominous signs of the apocalypse and so expects the end of civilization with a relatively high probability of 0.001. If the end of civilization is here, then the paper not be printed for sure. If there is a printing malfunction and no end of civilization, there is a probability of 0.05 that the paper will be printed (this is non-zero because the malfunction might be fixed in time). If there is no malfunction and no end of civilization, there is a probability of 0.99 that the paper will be printed. If the paper is not printed it will not be delivered. If it is printed, there is a probability of 0.9 that it will be delivered. The fact that this probability is not 1 suggests that there are other possible causes for the paper not being delivered that we should eventually add to our belief network (e.g. the paperboy being sick).

Construct this belief network in the belief and decision networks tool. Build the truth tables according to the probabilities above.
Bill's paper fails to arrive one morning. He'd like to know the probability that civilization has ended. What are the observed variables, and what is the query variable? [solution]
What are the initial factors (prior to variable elimination)? [solution]
Carry out variable elimination for this inference problem. Specify the elimination ordering you are using. Show each step of your work. [solution]
What is the probability that civilization has ended given the observations? [solution]
We were assuming that the query variable was not observed. If it is observed, does this simplify the inference problem? [solution]

5: Learning Goals Revisited

Build a belief network for a simple domain.
Define factors. Derive new factors from existing factors.
Carry out variable elimination by using factor representation and using the factor operations.
Use techniques to simplify variable elimination.