[Probability] Exact inference in loopy BN

Node clustering

  • Merge nodes to form polytrees
  • Merge CPTs


  • Size of merged node values = size of merged CPT grows exponential to (NO. VALUES)^(MERGED NODES)
  • Polytree algorithm is linear in CPT size
  • Choosing optimal (efficient inference) clustering (make polytree) scheme is hard to answer

Cutset conditioning

  • Instantiate node so that remaining nodes form a polytree
  • Apply polytree algorithm separately on each subtree


  • Cutset: set of instantiated nodes
  • Number of sub-polytrees grows exponentially with the size of cutset
  • Choosing optimal cutset is also hard to answer

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 )

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.