5. Assume that you know all functions in this factor graph on categorical variables X = {x1, x2, x3, x4, x5}:

(a) Set up and show in step-by-step detail (using equations) an efficient calculation of the marginal probabilities of each variable using the Sum-Product Algorithm. Take variable x1 to serve as the root variable.

(b) Suppose that a new, known factor fe is added to the graph which (only) connects variable nodes x3 and x4. Is the resulting factor graph a tree? Modify your solution in part (a) to determine P(x2). Hint: Think about how you would modify Homework Problem 4.2 (Bishop 5.2) to handle the Sum-Product Algorithm.

(c) Consider again the Chest Clinic BN of Problem 1 above. Assume that the value of a is observed (known) for a given patient.

i. Draw the Factor Graph for the Chest Clinic BN of Problem 1 given knowledge of (evidence on) the value of a. Be sure to give the factor-graph factors in terms of the Chest Clinic BN conditional probabilities. Is this evidence-conditional factor graph a tree?

ii. Describe in words how you would determine the probability of variable d given knowledge of (evidence on) a using the Sum-Product Algorithm on a factor graph. Although you don’t have to describe the algorithm in step-by-step detail, you must draw the appropriate factor graph giving the appropriate factor-graph factors in term of the Chest-Clinic conditional probabilities and give your verbal description referencing that factor graph. In particular, specifically mention all initialization nodes and the root node when describing your algorithm.