[Probability] Polytree

Polytree

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

Process

Screen Shot 2018-10-29 at 1.29.49 AMScreen Shot 2018-10-29 at 1.29.56 AMScreen Shot 2018-10-29 at 1.30.09 AMScreen Shot 2018-10-29 at 1.30.17 AM

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

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.