DOC PREVIEW
CMU CS 10708 - Param. Learning (MLE) Structure Learning

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 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 12 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 12 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 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

CMU CS 10708 - Param. Learning (MLE) 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 Param. Learning (MLE) 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 Param. Learning (MLE) 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 Param. Learning (MLE) 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?