Outline Graphical Models Anna Goldenberg Ot observations Oo P Q O p q0 q1 t 1 DBN Undirected Models Unification Summary HMM in short qT O1 T 1 Kalman Filter HMMs q0 Gaussian Linear Models ML 701 qt hidden states Dynamic Models is a Bayes Net satisfies Markov property independence of states given present with discrete states time steps are discrete OT p qt 1 qt T t 1 p Ot qt What about continuous HMMs Example of use What about continuous HMMs SLAM Simultaneous Localization and Mapping http www stanford edu paskin slam Gaussian Linear State Space models Drawback Belief State and Time grow quadratically in the number of landmarks State Space Models qt hidden states q0 q1 Ot observations Oo O1 P Q O p q0 T 1 t 1 p qt 1 qt T t 1 State Space Models qT qt hidden states q0 q1 OT Ot observations Oo O1 p Ot qt qT OT qt is a real valued K dimensional hidden state variable Ot is a D dimensional real valued observation vector Gaussian Linear State Space Models State Space Models A qt hidden states B Ot observations A q0 q1 A B Oo qT Ot and qt are Gaussian f and g are linear and time invariant B O1 OT qt Aqt 1 wt wt N 0 R Ot Bqt 1 vt vt N 0 S correction previously R and S were reversed q0 N 0 0 qt f qt 1 wt f determines mean of qt given mean of qt 1 wt is zero mean random noise vector Ot g qt vt similarly A transition matrix B observation matrix Inference forward step filtering Kalman Filter 1960 Kalman Filter p qt O0 Ot q1 1 qt Ot 1 Ot E qt t 1 A E qt 1 t 1 V qt t 1 A V qt 1 t 1 AT R backward step smoothing q1 1 Ot 1 time update P qt 1 O0 Ot 1 P qt O0 Ot 1 qt measurement update 1 2 q1 1 qt P qt Ot Oo Ot 1 12 11 V qt t 1 V qt t 1 B T BV qt t 1 BV qt t 1 B T R 21 22 P qt Oo Ot 1 P qt Oo Ot Ot p qt Ot Ot 1 OT P qt Oo Ot 1 P qt Oo Ot E qt t 1 B E qt t 1 E qt t E qt t 1 12 1 22 Ot E Ot t V qt t V qt t 1 12 1 22 21 Ot 1 Ot Example of use Kalman Filter Usage Tracking motion Missiles Hand motion Lip motion from videos Signal Processing Navigation Economics for prediction Reported by Welch and Bishop SIGGRAPH 2001 Dynamic Bayes Nets So far q0 Oo q1 O1 Dynamic Bayes Nets qT Weather 0 Weather 1 Weather 2 Velocity 0 Velocity 1 Velocity 2 Location 0 Location 1 Location 2 Failure 0 Failure 1 OT But are there more appealing models Weather 0 Weather 1 Weather 2 Velocity 0 Velocity 1 Velocity 2 Location 0 Location 1 Location 2 Failure 0 Failure 1 Failure 2 Obs 0 Koller and Friedman Obs 0 Obs 1 Obs 2 It s just a Bayes Net Approach to the dynamics Failure 2 Obs 1 Obs 2 1 Start with some prior for the initial state 2 Predict the next state just using the observation up to the previous time step 3 Incorporate the new observation and re estimate the current state Dynamic Bayes Nets Weather 0 Weather 1 Weather 2 Velocity 0 Velocity 1 Velocity 2 Location 0 Location 1 Location 2 Failure 0 Failure 1 Failure 2 Obs 0 It s just a Bayes Net Approach to the dynamics but first Obs 2 Obs 1 Other graphical models Any questions so far Most importantly 2 Predict the next Use state justthe using the observation up toof the previous time step Net structure the Bayes 3 Incorporate the new observation re estimate the current state Use and the independencies 1 Start with some prior for the initial state Are all GM directed Undirected models There are Undirected Graphical Models A B C A p X 1 XC Z C XC B C D E D E What are C non negative potential function Cliques Cliques A A B C p X 1 XC Z B C D E C XC D non negative potential function E A clique C is a subset C V if i j C i j E C is maximal if it is not contained in any other clique Decomposition i B a clique ii BC a maximal clique iii ABCD a clique iv ABC a maximal clique v BCDE a clique Independence Rule V1 is independent of V2 given cutset S S is called the Markov Blanket MB A B C D E e g MB B A C D i e the set of neighbors A Note to resolve the confusion The most common machine learning notation is the decomposition over maximal cliques 1 p A B C D E p A B C p B D p C E p D E Z B C D E Are undirected models useful Yes Are undirected models useful Yes Used a lot in Physics Ising model Boltzmann machine Used a lot in Physics Ising model Boltzmann machine In vision every pixel is a node In vision every pixel is a node bioinformatics Bioinformatics Why not more popular the ZZZZZZ it s the partition function p X 1 XC Z C What s Z and ways to fight it Z x XC C Approximations Sampling MCMC sampling is common Pseudo Likelihood Mean field approximation Chain Graphs Generalization of MRFs and Bayes Nets Structured as blocks Undirected edges within a block Directed edges between blocks Chain Graphs Generalization of MRFs and Bayes Nets Structured as blocks Undirected edges within a block Directed edges between blocks Directed A B C Graphical Models Chain Graphs quite intractable not very popular used in BioMedical Engineering text Undirected A Undirected Undirected Directed A A B C Directed B C D B C D Summary Chain Graphs Undirected Directed Graphical Models is a huge evolving field There are many other variations that haven t been discussed Used extensively in variety of domains Tractability issues More work to be done Questions
View Full Document
Unlocking...