HMMs Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University March 28th 2007 2005 2007 Carlos Guestrin Adventures of our BN hero Compact representation for probability distributions Fast inference Fast learning But Who are the most popular kids 1 Na ve Bayes 2 and 3 Hidden Markov models HMMs Kalman Filters 2005 2007 Carlos Guestrin Handwriting recognition Character recognition e g kernel SVMs rr r r r c r a z c bc 2005 2007 Carlos Guestrin Example of a hidden Markov model HMM 2005 2007 Carlos Guestrin Understanding the HMM Semantics X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin HMMs semantics Joint distribution X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 Variable elimination order Example 2005 2007 Carlos Guestrin Compute 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 2005 2007 Carlos Guestrin Reusing computation X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 2005 2007 Carlos Guestrin Compute 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 Initialization For i n 1 to 1 Generate a forwards factor by eliminating Xi 1 a backwards factor by eliminating Xi 1 i probability is 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin What you ll implement 1 multiplication 2005 2007 Carlos Guestrin What you ll implement 2 max argmax 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin Bayesian Networks Structure Learning Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University March 28th 2007 2005 2007 Carlos Guestrin Review Bayesian Networks Fast probabilistic inference using variable elimination Flu Compact representation for probability distributions Exponential reduction in number of parameters Sinus Headache Compute P X e Time exponential in tree width not number of variables Today Allergy Learn BN structure 2005 2007 Carlos Guestrin Nose Learning Bayes nets Known structure Unknown structure Fully observable data Missing data Data x 1 x m CPTs P Xi PaXi structure 2005 2007 Carlos Guestrin parameters Learning the CPTs Data For each discrete variable Xi x 1 x m 2005 2007 Carlos Guestrin Information theoretic interpretation of maximum likelihood Flu Allergy Sinus Given structure log likelihood of data 2005 2007 Carlos Guestrin Headache Nose Information theoretic interpretation of maximum likelihood Flu Allergy Sinus Given structure log likelihood of data 2005 2007 Carlos Guestrin Headache Nose Information theoretic interpretation of maximum likelihood 2 Flu Allergy Sinus Given structure log likelihood of data 2005 2007 Carlos Guestrin Headache Nose 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 2005 2007 Carlos Guestrin How many trees are there Nonetheless Efficient optimal algorithm finds best tree 2005 2007 Carlos Guestrin Scoring a tree 1 equivalent trees 2005 2007 Carlos Guestrin Scoring a tree 2 similar trees 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin Can we extend Chow Liu 2 Approximately learning models with tree width up to k Narasimhan Bilmes 04 But O nk 1 and more subtleties 2005 2007 Carlos Guestrin 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 O Nk 1 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin Maximum likelihood overfits Information never hurts Adding a parent always increases score 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin How many graphs are there 2005 2007 Carlos Guestrin 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
View Full Document
Unlocking...