#elimination-order

Question 1: Single choice

mediumAI-checkedProbabilistic & Graphical Models

After conditioning, a model over binary $x_2, x_3, x_4, x_5$ factorises as $\phi_A'(x_2, x_3)\,\phi_B(x_2, x_3, x_4)\,\phi_C(x_4, x_5)\,\phi_D'(x_4)$ . To compute the marginal of $x_2$ by variable elimination, you can sum out the variables in the order $(x_4, x_5, x_3)$ or $(x_5, x_4, x_3)$ . Which order is cheaper?

$(x_4, x_5, x_3)$ , because $x_4$ has the most neighbours and removing it first simplifies the graph1
Both cost the same, since the resulting marginal is identical2
$(x_4, x_5, x_3)$ , because $x_5$ appears in only one factor and can be ignored3
$(x_5, x_4, x_3)$ , because the largest intermediate table has $2^3$ instead of $2^4$ entries4

Timed test