Node clustering

• Merge nodes to form polytrees
• Merge CPTs

Catch

• 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

Catch

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