Inference by Enumeration in BNs

• The probability of a specific value combination x of the X : $P(X=x|e)$

  the most likely value combination of the X given the evidence e : $x^*$$=$$arg max_x P(X=x |e)$
• Compute for each possible assingment of values x of the query variables X and you have to full conditional distribution P(X|E=e)
• What is the goal of inference by enumeration for probabilistic queries

  Compute $P(X|e)$ for some sets of variable X,E contained in X and some specfici value assignment E=e
• Inference by Enumeration algorithm :

  1. Compute P(X,e) via Inference By Enumeration, Z = (ensemble) X - X -E $P(X,e) =$$\sum_{x \in Val(Z)} P(X,e,z)$
  2. Compute normalisation constant Z from the above as $Z =$$P(e) =$$\sum_x P(x,e)$
  3. condition via renormalisation : $P(X|e) =$$\frac{1}{Z} P(X,e)$
• It can be show that the problem of inference in graphical models is NP-hard, and therefore requires exponential time (worst case)

  many real-world problems aren't worst case
• Problems with inference :

  • computations are highly redudant
  • many terms are computed many times
• Exact inference can be feasible in very sparse networks but it is still exponential and thus intractable in general