10708 RecitationVariable elimination algorithm10708 RecitationVariable EliminationOctober 12, 20062KGA BMRCT F0.1 0.9C|M,RT FTTTF 0.5 0.5FT 0.6 0.4FF0.7 0.30.05 0.95G|A,BT FTTTF 0.7 0.3FT 0.5 0.5FF0.9 0.10.1 0.9B|A T FTF 0.6 0.40.8 0.2K|G T FTF 0.6 0.40.7 0.3M|G T FTF 0.5 0.50.6 0.4R|M T FTF 0.1 0.90.7 0.3KGA BMRC3T F0.1 0.9B|A T FTF 0.6 0.40.8 0.2C|M,RT FTTTF 0.5 0.5FT 0.6 0.4FF0.7 0.30.05 0.95G|A,BT FTTTF 0.7 0.3FT 0.5 0.5FF0.9 0.10.1 0.9K|G T FTF 0.6 0.40.7 0.3R|M T FTM|G T FTF 0.5 0.50.6 0.4F 0.1 0.90.7 0.3KGA BMRC4T F0.1 0.9B|A T FTF 0.6 0.40.8 0.2C|M,RT FTTTF 0.5 0.5FT 0.6 0.4FF0.7 0.30.05 0.95G|A,BT FTTTF 0.7 0.3FT 0.5 0.5FF0.9 0.10.1 0.9K|G T FTF 0.6 0.40.7 0.3R|M T FTM|G T FTF 0.5 0.50.6 0.4F 0.1 0.90.7 0.3KGA BMRC5T F0.1 0.9C|M,RT FTTTF 0.5 0.5FT 0.6 0.4FF0.7 0.30.05 0.95G|A,BT FTTTF 0.7 0.3FT 0.5 0.5FF0.9 0.10.1 0.9B|A T FTF 0.6 0.40.8 0.2K|G T FTF 0.6 0.40.7 0.3M|G T FTF 0.5 0.50.6 0.4R|M T FTF 0.1 0.90.7 0.36KGA BMRCT F0.1 0.9B|A T FTF 0.6 0.40.8 0.2C|M,RT FTTTF 0.5 0.5FT 0.6 0.4FF0.7 0.30.05 0.95G|A,BT FTTTF 0.7 0.3FT 0.5 0.5FF0.9 0.10.1 0.9K|G T FTF 0.6 0.40.7 0.3M|G T FTF 0.5 0.50.6 0.4R|M T FTF 0.1 0.90.7 0.37KGA BMRCT F0.1 0.9B|A T FTF 0.6 0.40.8 0.2C|M,RT FTTTF 0.5 0.5FT 0.6 0.4FF0.7 0.30.05 0.95G|A,BT FTTTF 0.7 0.3FT 0.5 0.5FF0.9 0.10.1 0.9K|G T FTF 0.6 0.40.7 0.3R|M T FTM|G T FTF 0.5 0.50.6 0.4F 0.1 0.90.7 0.38KGA BMRCT F0.1 0.9B|A T FTF 0.6 0.40.8 0.2C|M,RT FTTTF 0.5 0.5FT 0.6 0.4FF0.7 0.30.05 0.95G|A,BT FTTTF 0.7 0.3FT 0.5 0.5FF0.9 0.10.1 0.9K|G T FTF 0.6 0.40.7 0.3M|G T FTF 0.5 0.50.6 0.4R|M T FTF 0.1 0.90.7 0.39Variable elimination algorithm Given a BN and a query P(X|e) ∝ P(X,e) Instantiate evidence e Prune non-active vars for {X,e} Choose an ordering on variables, e.g., X1, …, Xn Initial factors {f1,…,fn}: fi= P(Xi|PaXi) (CPT for Xi) For i = 1 to n, If Xi∉{X,E} Collect factors f1,…,fkthat include Xi Generate a new factor by eliminating Xifrom these factors Variable Xihas been eliminated! Normalize P(X,e) to obtain P(X|e)IMPORTANT!!!1011KGA BMRCT F0.1 0.9C|M,RT FTTTF 0.5 0.5FT 0.6 0.4FF0.7 0.30.05 0.95G|A,BT FTTTF 0.7 0.3FT 0.5 0.5FF0.9 0.10.1 0.9B|A T FTF 0.6 0.40.8 0.2K|G T FTF 0.6 0.40.7 0.3M|G T FTF 0.5 0.50.6 0.4R|M T FTF 0.1 0.90.7
View Full Document
Unlocking...