Polytree

• (1) singly connected, (2) no loops, (3) at most one path between any two nodes
• Efficient algorithms for exact inference

Process

Notes

• Termination
  • Root node does not have parents, so probability will be given.
  • Leaf node does not have children, so no recursive call can happen down stream.
  • Computing Evidence node’s probability is trivial, because it can be done by recursive call of marginalization. (Trivial)
• Runtime analysis
  • Linear in number of nodes and in size of CPTs.
• Problem solving in general
  • Start off with Bayes rule if the order is wierd, Product rule to remove something, Marginalization if something is missing…

Reference