10701 Recitation Suyash Shringarpure 11 8 2011 Plan Homework questions Lecture questions Bayesian networks D separation Variable elimination Message passing Junction trees Undirected graphs Bayesian networks E A B C D D separation A C T F A C B T F E A B A D B T F C B What What else D Factorized probabilty P A B C D E E A B Parameters Na ve Factorized C D Conditional probabilty tables A C P B 1 A P A 0 0 0 1 0 0 2 0 1 0 8 1 0 8 1 0 0 7 A 1 1 0 4 B D P E 1 0 0 0 7 0 1 0 5 1 0 0 1 E 1 1 0 4 B C D C P C B P D 1 0 0 9 0 0 8 1 0 1 1 0 1 Inference problem What is P E 1 A C P B 1 A P A 0 0 0 1 0 0 2 0 1 0 8 1 0 8 1 0 0 7 A 1 1 0 4 B D P E 1 0 0 0 7 0 1 0 5 1 0 0 1 E 1 1 0 4 B C D C P C B P D 1 0 0 9 0 0 8 1 0 1 1 0 1 Variable elimination Elimination of a variable Marginalizing out that variable from all factors that include that variable For example factors for B are E A B C D Variable elimination Initial factors f1 fn CPT P Node Parents Choose an elimination order IMPORTANT To eliminate X Collect all factors f1 fk that contain X Generate a new factor by marginalizing X g X j 1 k fj Add g to the factor set and repeat Example Order 1 A C D B P A B C D E P A P C P B C A P D B P E D B P E 1 A B C D P A B C D E 1 A B C D P A P C P B C A P D B P E 1 D B According to the order eliminate A first Elimination steps A B C D P A P C P B C A P D B P E 1 D B B C D P D B P E 1 D B P C A P A P B C A mA B C Contd B C D P D B P E 1 D B P C A P A P B C A B C D P D B P E 1 D B P C mA B C B D P D B P E 1 D B C P C mA B C mC B Contd B D P D B P E 1 D B C P C mA B C B D P D B P E 1 D B mC B B mC B D P D B P E 1 D B mD B Contd B mC B D P D B P E 1 D B B mC B mD B Answer Complexity Computing mY X1 Xn Additions Multiplications Elimination complexity depends on Order effects Worst order for the given graph E A B C D Message passing A two pass algorithm over the BN that answers multiple inference queries On trees elimination message passing Guaranteed converge and accuracy How about this graph E A B C D Message passing Loops are bad Messages travel forever In general Elimination Message passing on clique trees Example graph E A B C D Clique tree P A P C P B C A P D B P E 1 D B P D B P E 1 D B P C P A P B C A P D B P E 1 D B P C mA B C Eliminate A P D B P E 1 D B mC B Eliminate C mC B mD B E 1 Eliminate D mB E 1 Eliminate B P E 1 Cliques E BE BED BC ABC Tree Clique tree Cliques E BE BED BC ABC Tree Junction trees Maximal clique trees Edge between two cliques if they share variables Messages ensure consistency of marginals of common variables Complexity depends on clique size Result Marginals of each clique Junction tree example HMM Rightward message Leftward message Undirected graphs Junction tree algorithms work for undirected graphs as well To avoid loops we triangularize cycles If not run loopy belief propagation No guarantees Works often in practice Approx inference If P x is complex Replace by simpler Q x Criterion for choosing form of Q x Computational cost Criterion for choosing parameters of Q x Minimize KL Q P Simplest Q
View Full Document
Unlocking...