DOC PREVIEW
CMU CS 10708 - Structure Learning

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1 1 Structure Learning (The Good), The Bad, The Ugly Inference Graphical Models – 10708 Carlos Guestrin Carnegie Mellon University October 13th, 2008 Readings: K&F: 17.3, 17.4, 17.5.1, 8.1, 12.1 10-708 – ©Carlos Guestrin 2006-2008 10-708 – ©Carlos Guestrin 2006-2008 2 Decomposable score  Log data likelihood  Decomposable score:  Decomposes over families in BN (node and its parents)  Will lead to significant computational efficiency!!!  Score(G : D) = ∑i FamScore(Xi|PaXi : D)2 10-708 – ©Carlos Guestrin 2006-2008 3 Structure learning for general graphs  In a tree, a node only has one parent  Theorem:  The problem of learning a BN structure with at most d parents is NP-hard for any (fixed) d≥2  Most structure learning approaches use heuristics  Exploit score decomposition  (Quickly) Describe two heuristics that exploit decomposition in different ways 10-708 – ©Carlos Guestrin 2006-2008 4 Understanding score decomposition Difficulty SAT Grade Happy Job Coherence Letter Intelligence3 10-708 – ©Carlos Guestrin 2006-2008 5 Fixed variable order 1  Pick a variable order  e.g., X1,…,Xn  Xi can only pick parents in {X1,…,Xi-1}  Any subset  Acyclicity guaranteed!  Total score = sum score of each node 10-708 – ©Carlos Guestrin 2006-2008 6 Fixed variable order 2  Fix max number of parents to k  For each i in order  Pick PaXi⊆ {X1,…,Xi-1}  Exhaustively search through all possible subsets  PaXi is maximum U⊆ {X1,…,Xi-1} FamScore(Xi|U : D)  Optimal BN for each order!!!  Greedy search through space of orders:  E.g., try switching pairs of variables in order  If neighboring vars in order are switched, only need to recompute score for this pair  O(n) speed up per iteration4 10-708 – ©Carlos Guestrin 2006-2008 7 Learn BN structure using local search Starting from Chow-Liu tree Local search, possible moves: Only if acyclic!!! • Add edge • Delete edge • Invert edge Select using favorite score 10-708 – ©Carlos Guestrin 2006-2008 8 Exploit score decomposition in local search  Add edge and delete edge:  Only rescore one family!  Reverse edge  Rescore only two families Difficulty SAT Grade Happy Job Coherence Letter Intelligence5 10-708 – ©Carlos Guestrin 2006-2008 9 Some experiments Alarm network 10-708 – ©Carlos Guestrin 2006-2008 10 Order search versus graph search  Order search advantages  For fixed order, optimal BN – more “global” optimization  Space of orders much smaller than space of graphs  Graph search advantages  Not restricted to k parents  Especially if exploiting CPD structure, such as CSI  Cheaper per iteration  Finer moves within a graph6 10-708 – ©Carlos Guestrin 2006-2008 11 Bayesian model averaging  So far, we have selected a single structure  But, if you are really Bayesian, must average over structures  Similar to averaging over parameters  Inference for structure averaging is very hard!!!  Clever tricks in reading 10-708 – ©Carlos Guestrin 2006-2008 12 What you need to know about learning BN structures  Decomposable scores  Data likelihood  Information theoretic interpretation  Bayesian  BIC approximation  Priors  Structure and parameter assumptions  BDe if and only if score equivalence  Best tree (Chow-Liu)  Best TAN  Nearly best k-treewidth (in O(Nk+1))  Search techniques  Search through orders  Search through structures  Bayesian model averaging7 10-708 – ©Carlos Guestrin 2006-2008 13 Inference in graphical models: Typical queries 1 Flu Allergy Sinus Headache Nose  Conditional probabilities  Distribution of some var(s). given evidence 10-708 – ©Carlos Guestrin 2006-2008 14 Inference in graphical models: Typical queries 2 – Maximization Flu Allergy Sinus Headache Nose  Most probable explanation (MPE)  Most likely assignment to all hidden vars given evidence  Maximum a posteriori (MAP)  Most likely assignment to some var(s) given evidence8 10-708 – ©Carlos Guestrin 2006-2008 15 Are MPE and MAP Consistent? Sinus Nose  Most probable explanation (MPE)  Most likely assignment to all hidden vars given evidence  Maximum a posteriori (MAP)  Most likely assignment to some var(s) given evidence P(S=t)=0.4 P(S=f)=0.6 P(N|S) C++ Library  Now available, join:  http://groups.google.com/group/10708-f08-code/  The library implements the following functionality:  random variables, random processes, and linear algebra  factorized distributions, such Gaussians, multinomial distributions, and mixtures  graph structures and basic graph algorithms  graphical models, including Bayesian networks, Markov networks, andjunction trees  basic static and dynamic inference algorithms  parameter learning for Gaussian distributions, Chow Liu  Fairly advanced C++ (not for everyone ) 10-708 – ©Carlos Guestrin 2006-2008 169 10-708 – ©Carlos Guestrin 2006-2008 17 Complexity of conditional probability queries 1  How hard is it to compute P(X|E=e)? Reduction – 3-SAT 10-708 – ©Carlos Guestrin 2006-2008 18 Complexity of conditional probability queries 2  How hard is it to compute P(X|E=e)?  At least NP-hard, but even harder!10 10-708 – ©Carlos Guestrin 2006-2008 19 Inference is #P-complete, hopeless?  Exploit structure!  Inference is hard in general, but easy for many (real-world relevant) BN structures 10-708 – ©Carlos Guestrin 2006-2008 20 Complexity for other inference questions  Probabilistic inference  general graphs:  poly-trees and low tree-width:  Approximate probabilistic inference  Absolute error:  Relative error:  Most probable explanation (MPE)  general graphs:  poly-trees and low tree-width:  Maximum a posteriori (MAP)  general graphs:  poly-trees and low tree-width:11 10-708 – ©Carlos Guestrin 2006-2008 21 Inference in BNs hopeless?  In general, yes!  Even approximate!  In practice  Exploit structure  Many effective approximation algorithms (some with guarantees)  For now, we’ll talk


View Full Document

CMU CS 10708 - Structure Learning

Documents in this Course
Lecture

Lecture

15 pages

Lecture

Lecture

25 pages

Lecture

Lecture

24 pages

causality

causality

53 pages

lecture11

lecture11

16 pages

Exam

Exam

15 pages

Notes

Notes

12 pages

lecture

lecture

18 pages

lecture

lecture

16 pages

Lecture

Lecture

17 pages

Lecture

Lecture

15 pages

Lecture

Lecture

17 pages

Lecture

Lecture

19 pages

Lecture

Lecture

42 pages

Lecture

Lecture

16 pages

r6

r6

22 pages

lecture

lecture

20 pages

lecture

lecture

35 pages

Lecture

Lecture

19 pages

Lecture

Lecture

21 pages

lecture

lecture

21 pages

lecture

lecture

13 pages

review

review

50 pages

Semantics

Semantics

30 pages

lecture21

lecture21

26 pages

MN-crf

MN-crf

20 pages

hw4

hw4

5 pages

lecture

lecture

12 pages

Lecture

Lecture

25 pages

Lecture

Lecture

25 pages

Lecture

Lecture

14 pages

Lecture

Lecture

15 pages

Load more
Download Structure Learning
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Structure Learning and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Structure Learning 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?