1 1 Param. Learning (MLE) Structure Learning The Good Graphical Models – 10708 Carlos Guestrin Carnegie Mellon University October 1st, 2008 Readings: K&F: 16.1, 16.2, 17.1, 17.2, 17.3.1, 17.4.1 10-708 – ©Carlos Guestrin 2006-2008 10-708 – ©Carlos Guestrin 2006-2008 2 Learning the CPTs x(1) … x(m) Data For each discrete variable Xi2 10-708 – ©Carlos Guestrin 2006-2008 3 Learning the CPTs x(1) … x(m) Data For each discrete variable Xi WHY?????????? 10-708 – ©Carlos Guestrin 2006-2008 4 Maximum likelihood estimation (MLE) of BN parameters – example Given structure, log likelihood of data: Flu Allergy Sinus Nose3 10-708 – ©Carlos Guestrin 2006-2008 5 Maximum likelihood estimation (MLE) of BN parameters – General case Data: x(1),…,x(m) Restriction: x(j)[PaXi] ! assignment to PaXi in x(j) Given structure, log likelihood of data: 10-708 – ©Carlos Guestrin 2006-2008 6 Taking derivatives of MLE of BN parameters – General case4 10-708 – ©Carlos Guestrin 2006-2008 7 General MLE for a CPT Take a CPT: P(X|U) Log likelihood term for this CPT Parameter θX=x|U=u : 10-708 – ©Carlos Guestrin 2006-2008 8 Where are we with learning BNs? Given structure, estimate parameters Maximum likelihood estimation Later Bayesian learning What about learning structure?5 10-708 – ©Carlos Guestrin 2006-2008 9 Learning the structure of a BN Constraint-based approach BN encodes conditional independencies Test conditional independencies in data Find an I-map Score-based approach Finding a structure and parameters is a density estimation task Evaluate model as we evaluated parameters Maximum likelihood Bayesian etc. Data <x1(1),…,xn(1)> … <x1(m),…,xn(m)> Flu Allergy Sinus Headache Nose Learn structure and parameters 10-708 – ©Carlos Guestrin 2006-2008 10 Remember: Obtaining a P-map? Given the independence assertions that are true for P Obtain skeleton Obtain immoralities From skeleton and immoralities, obtain every (and any) BN structure from the equivalence class Constraint-based approach: Use Learn PDAG algorithm Key question: Independence test6 10-708 – ©Carlos Guestrin 2006-2008 11 Score-based approach Data <x1(1),…,xn(1)> … <x1(m),…,xn(m)> Flu Allergy Sinus Headache Nose Possible structures Score structure Learn parameters 10-708 – ©Carlos Guestrin 2006-2008 12 Information-theoretic interpretation of maximum likelihood Given structure, log likelihood of data: Flu Allergy Sinus Headache Nose7 10-708 – ©Carlos Guestrin 2006-2008 13 Information-theoretic interpretation of maximum likelihood 2 Given structure, log likelihood of data: Flu Allergy Sinus Headache Nose 10-708 – ©Carlos Guestrin 2006-2008 14 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)8 Announcements Recitation tomorrow Don’t miss it! HW2 Out today Due in 2 weeks Projects!!! Proposals due Oct. 8th in class Individually or groups of two Details on course website Project suggestions will be up soon!!! 15 10-708 – ©Carlos Guestrin 2006-2008 BN code release!!!! Pre-release of a C++ library for probabilistic inference and learning Features: basic datastructures (random variables, processes, linear algebra) distributions (Gaussian, multinomial, ...) basic graph structures (directed, undirected) graphical models (Bayesian network, MRF, junction trees) inference algorithms (variable elimination, loopy belief propagation, filtering) Limited amount of learning (IPF, Chow Liu, order-based search) Supported platforms: Linux (tested on Ubuntu 8.04) MacOS X (tested on 10.4/10.5) limited Windows support Will be made available to the class early next week. 10-708 – ©Carlos Guestrin 2006-2008 169 10-708 – ©Carlos Guestrin 2006-2008 17 How many trees are there? Nonetheless – Efficient optimal algorithm finds best tree 10-708 – ©Carlos Guestrin 2006-2008 18 Scoring a tree 1: I-equivalent trees10 10-708 – ©Carlos Guestrin 2006-2008 19 Scoring a tree 2: similar trees 10-708 – ©Carlos Guestrin 2006-2008 20 Chow-Liu tree learning algorithm 1 For each pair of variables Xi,Xj Compute empirical distribution: Compute mutual information: Define a graph Nodes X1,…,Xn Edge (i,j) gets weight11 10-708 – ©Carlos Guestrin 2006-2008 21 Chow-Liu tree learning algorithm 2 Optimal tree BN Compute maximum weight spanning tree Directions in BN: pick any node as root, breadth-first-search defines directions 10-708 – ©Carlos Guestrin 2006-2008 22 Can we extend Chow-Liu 1 Tree augmented naïve Bayes (TAN) [Friedman et al. ’97] Naïve Bayes model overcounts, because correlation between features not considered Same as Chow-Liu, but score edges with:12 10-708 – ©Carlos Guestrin 2006-2008 23 Can we extend Chow-Liu 2 (Approximately learning) models with tree-width up to k [Chechetka & Guestrin ’07] But, O(n2k+6) 10-708 – ©Carlos Guestrin 2006-2008 24 What you need to know about learning BN structures so far Decomposable scores Maximum likelihood Information theoretic interpretation Best tree (Chow-Liu) Best TAN Nearly best k-treewidth (in
View Full Document