Classic HMM tutorial see class website L R Rabiner A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition Proc of the IEEE Vol 77 No 2 pp 257 286 1989 HMMs cont Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University March 29th 2006 1 Announcements This weeks recitation Go through several BNs topics representation inference learning in the context of an example very useful for homework 2 Understanding the HMM Semantics X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 3 HMMs semantics Details X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Just 3 distributions 4 Learning HMMs from fully observable data is easy X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Learn 3 distributions 5 Possible inference tasks in an HMM X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Marginal probability of a hidden variable Viterbi decoding most likely trajectory for hidden vars 6 Using variable elimination to compute P Xi o1 n X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Compute Variable elimination order Example 7 What if I want to compute P Xi o1 n for each i X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Compute Variable elimination for each i Variable elimination for each i what s the complexity 8 Reusing computation X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Compute 9 The forwards backwards algorithm X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Initialization For i 2 to n Generate a forwards factor by eliminating Xi 1 Initialization For i n 1 to 1 Generate a backwards factor by eliminating Xi 1 i probability is 10 Most likely explanation X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Compute Variable elimination order Example 11 The Viterbi algorithm X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Initialization For i 2 to n Generate a forwards factor by eliminating Xi 1 Computing best explanation For i n 1 to 1 Use argmax to get explanation 12 What you ll implement 1 multiplication 13 What you ll implement 2 max argmax 14 Higher order HMMs X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Add dependencies further back in time better representation harder to learn 15 What you need to know Hidden Markov models HMMs Very useful very powerful Speech OCR Parameter sharing only learn 3 distributions Trick reduces inference from O n2 to O n Special case of BN 16 Koller Friedman Chapters handed out Chapter 11 short Chapter 12 12 1 12 2 12 3 covered in the beginning of semester 12 4 Learning parameters for BNs Chapter 13 13 1 13 3 1 13 4 1 13 4 3 basic structure learning Learning BN tutorial class website ftp ftp research microsoft com pub tr tr 95 06 pdf TAN paper class website http www cs huji ac il nir Abstracts FrGG1 html Bayesian Networks Structure Learning Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University March 29th 2006 17 Review Bayesian Networks Compact representation for probability distributions Exponential reduction in number of parameters Fast probabilistic inference using variable elimination Flu Allergy Sinus Headache Nose Compute P X e Time exponential in tree width not number of variables Today Learn BN structure 18 Learning Bayes nets Known structure Unknown structure Fully observable data Missing data Data CPTs P Xi PaXi x 1 x m structure parameters 19 Learning the CPTs Data For each discrete variable Xi x 1 x M WHY 20 Information theoretic interpretation of maximum likelihood Flu Allergy Sinus Given structure log likelihood of data Nose Headache 21 Maximum likelihood ML for learning BN structure Possible structures Flu Learn parameters using ML Score structure Allergy Sinus Headache Nose Data x1 1 xn 1 M x1 xn M 22 How many trees are there 23 Nonetheless Efficient optimal algorithm finds best tree Information theoretic interpretation of maximum likelihood 2 Flu Allergy Sinus Given structure log likelihood of data Nose Headache 24 Information theoretic interpretation of maximum likelihood 3 Flu Allergy Sinus Given structure log likelihood of data Nose Headache 25 Mutual information Independence tests Statistically difficult task Intuitive approach Mutual information Mutual information and independence Xi and Xj independent if and only if I Xi Xj 0 Conditional mutual information 26 Decomposable score Log data likelihood 27 Scoring a tree 1 equivalent trees 28 Scoring a tree 2 similar trees 29 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 weight 30 Chow Liu tree learning algorithm 2 Optimal tree BN Compute maximum weight spanning tree Directions in BN pick any node as root breadth firstsearch defines directions 31 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 32 Can we extend Chow Liu 2 Approximately learning models with tree width up to k Narasimhan Bilmes 04 But O nk 1 33 Scoring general graphical models Model selection problem What s the best structure Flu Allergy Sinus Headache Nose Data x 1 1 x n 1 x 1 m x n m The more edges the fewer independence assumptions the higher the likelihood of the data but will overfit 34 Maximum likelihood overfits Information never hurts Adding a parent always increases score 35 Bayesian score avoids overfitting Given a structure distribution over parameters Difficult integral use Bayes information criterion BIC approximation equivalent as M Note regularize with MDL score Best BN under BIC still NP hard 36 How many graphs are there 37 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 38 Learn BN structure using local search Starting from Chow Liu tree Local search possible moves Add edge Delete edge Invert edge Score using BIC 39 What you need to know about learning BNs Learning BNs Maximum likelihood or MAP learns parameters Decomposable score Best tree Chow Liu Best TAN Other BNs usually local search with BIC score 40
View Full Document
Unlocking...