bayesstructlearning

1 Oct 29th, 2001Copyright © 2001, Andrew W. Moore Bayes Net Structure Learning Andrew W. Moore Associate Professor School of Computer Science Carnegie Mellon University www.cs.cmu.edu/~awm awm@cs.cmu.edu 412-268-7599 Note to other teachers and users of these slides. Andrew would be delighted if you found this source material useful in giving your own lectures. Feel free to use these slides verbatim, or to modify them to fit your own needs. PowerPoint originals are available. If you make use of a significant portion of these slides in your own lecture, please include this message, or the following link to the source repository of Andrew’s tutorials: http://www.cs.cmu.edu/~awm/tutorials . Comments and corrections gratefully received. Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 2 Reminder: A Bayes Net 2 Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 3 Estimating Probability Tables Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 4 Estimating Probability Tables 3 Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 5 Scoring a structure å å å = ÷÷ø ö ççè æ = = ==+ - = m j k X v kjkjk j VvXPVvXPVPR R N 1 uesparent val of nscombinatio num 1 ) of(arity 1 params )|(log)|()( log 2 Score (Which of these fits the data best?) N. Friedman and Z. Yakhini, On the sample complexity of learning Bayesian networks, Proceedings of the 12th conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, 1996 Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 6 Scoring a structure å å å = ÷÷ø ö ççè æ = = ==+ - = m j k X v kjkjk j VvXPVvXPVPR R N 1 uesparent val of nscombinatio num 1 ) of(arity 1 params )|(log)|()( log 2 Score Number of non- redundant parameters defining the net #Records #Attributes Sums over all the rows in the prob- ability table for Xj The parent values in the k’th row of Xj’s probability table All these values estimated from data 4 Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 7 Scoring a structure å å å = ÷÷ø ö ççè æ = = ==+ - = m j k X v kjkjk j VvXPVvXPVPR R N 1 uesparent val of nscombinatio num 1 ) of(arity 1 params )|(log)|()( log 2 Score All these values estimated from data This is called a BIC (Bayes Information Criterion) estimate This part is a penalty for too many parameters This part is the training set log- likelihood BIC asymptotically tries to get the structure right. (There’s a lot of heavy emotional debate about whether this is the best scoring criterion) Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 8 Searching for structure with best score 5 Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 9 Learning Methods until today In pu ts Classifier Predict category In pu ts Density Estimator Prob- ability In pu ts Regressor Predict real no. Dec Tree, Sigmoid Perceptron, Sigmoid N.Net, Gauss/Joint BC, Gauss Naïve BC, N.Neigh Joint DE, Naïve DE, Gauss/Joint DE, Gauss Naïve DE Linear Regression, Quadratic Regression, Perceptron, Neural Net, N.Neigh, Kernel, LWR Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 10 Learning Methods added today In pu ts Classifier Predict category In pu ts Density Estimator Prob- ability In pu ts Regressor Predict real no. Dec Tree, Sigmoid Perceptron, Sigmoid N.Net, Gauss/Joint BC, Gauss Naïve BC, N.Neigh Joint DE, Naïve DE, Gauss/Joint DE, Gauss Naïve DE, Bayes Net Structure Learning (Note, can be extended to permit mixed categorical/real values) Linear Regression, Quadratic Regression, Perceptron, Neural Net, N.Neigh, Kernel, LWR 6 Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 11 But also, for free… In pu ts Classifier Predict category In pu ts Density Estimator Prob- ability In pu ts Regressor Predict real no. Dec Tree, Sigmoid Perceptron, Sigmoid N.Net, Gauss/Joint BC, Gauss Naïve BC, N.Neigh, Bayes Net Based BC Joint DE, Naïve DE, Gauss/Joint DE, Gauss Naïve DE, Bayes Net Structure Learning Linear Regression, Quadratic Regression, Perceptron, Neural Net, N.Neigh, Kernel, LWR Copyright © 2001, Andrew W. Moore Bayes Net Structure: Slide 12 And a new operation… In pu ts Classifier Predict category In pu ts Density Estimator Prob- ability In pu ts Regressor Predict real no. Dec Tree, Sigmoid Perceptron, Sigmoid N.Net, Gauss/Joint BC, Gauss Naïve BC, N.Neigh, Bayes Net Based BC Joint DE, Naïve DE, Gauss/Joint DE, Gauss Naïve DE, Bayes Net Structure Learning Linear Regression, Quadratic Regression, Perceptron, Neural Net, N.Neigh, Kernel, LWR In pu ts Inference Engine Learn P(E1|E2) Joint DE, Bayes Net Structure Learning