Dynamic models 2 Switching KFs continued, Assumed density filters, DBNs, BK, extensionsAnnouncementLast week in “Your BN Hero”The moonwalkLast week in “Your BN Hero”Switching Kalman filterInference in switching KF – one stepMulti-step inferenceVisualizing growth in number of GaussiansComputational complexity of inference in switching Kalman filtersBounding number of GaussiansCollapsing Gaussians – Single Gaussian from a mixtureCollapsing mixture of Gaussians into smaller mixture of GaussiansOperations in non-linear switching Kalman filterAssumed density filteringWhen non-linear KF is not good enoughDistributed Simultaneous Localization and TrackingDonut and Banana distributionsGaussians represent “balls”Reparameterized KF for SLATExample of KF – SLAT Simultaneous Localization and TrackingWhen a single Gaussian ain’t good enoughApproximating non-linear KF with mixture of GaussiansWhat you need to know about switching Kalman filtersMore than just a switching KFDynamic Bayesian network (DBN)Transition Model:Two Time-slice Bayes Net (2-TBN)Unrolled DBN“Sparse” DBN and fast inference“Sparse” DBN and fast inference 1BK Algorithm for approximate DBN inference [Boyen, Koller ’98]Computing factored belief state in the next time stepError accumulationContraction in Markov processBK TheoremExample – BAT network [Forbes et al.]BK results [Boyen, Koller ’98]Thin Junction Tree Filters [Paskin ’03]Hybrid DBN (many continuous and discrete variables)DBN summaryKoller & Friedman: Chapter 16Boyen & Koller ’98, ’99 Uri Lerner’s Thesis: Chapters 3,9Paskin ’03 Dynamic models 2Switching KFs continued, Assumed density filters, DBNs, BK, extensionsProbabilistic Graphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityNovember 21st, 2005Announcement Special recitation lectures Pradeep will give two special lectures Nov. 22 & Dec. 1: 5-6pm, during recitation Covering: variational methods, loopy BP and their relationship Don’t miss them!!! It’s FCE time!!! Fill the forms online by Dec. 11 www.cmu.edu/fce It will only take a few minutes Please, please, please help us improve the course by providing feedbackLast week in “Your BN Hero” Gaussian distributions reviewed Linearity of Gaussians Conditional Linear Gaussian (CLG) Kalman filter HMMs with CLG distributions Linearization of non-linear transitions and observations using numerical integration Switching Kalman filter Discrete variable selects transition model depends Mixture of Gaussians represents belief state Number of mixture components grows exponentially in timeThe moonwalkLast week in “Your BN Hero” Gaussian distributions reviewed Linearity of Gaussians Conditional Linear Gaussian (CLG) Kalman filter HMMs with CLG distributions Linearization of non-linear transitions and observations using numerical integration Switching Kalman filter Discrete variable selects transition model depends Mixture of Gaussians represents belief state Number of mixture components grows exponentially in timeSwitching Kalman filter At each time step, choose one of k motion models: You never know which one!p(Xi+1|Xi,Zi+1) CLG indexed by Zi p(Xi+1|Xi,Zi+1=j) ~ N(βj0+ ΒjXi; ΣjXi+1|Xi)Inference in switching KF – one step Suppose p(X0) is Gaussian Z1takes one of two values p(X1|Xo,Z1) is CLG Marginalize X0 Marginalize Z1 Obtain mixture of two Gaussians!Multi-step inference Suppose p(Xi) is a mixture of m Gaussians Zi+1takes one of two values p(Xi+1|Xi,Zi+1) is CLG Marginalize Xi Marginalize Zi Obtain mixture of 2m Gaussians! Number of Gaussians grows exponentially!!!Visualizing growth in number of GaussiansComputational complexity of inference in switching Kalman filters Switching Kalman Filter with (only) 2 motion models Query: Problem is NP-hard!!! [Lerner & Parr `01] Why “!!!”? Graphical model is a tree: Inference efficient if all are discrete Inference efficient if all are Gaussian But not with hybrid model (combination of discrete and continuous)Bounding number of Gaussians P(Xi) has 2mGaussians, but… usually, most are bumps have low probability and overlap: Intuitive approximate inference: Generate k.m Gaussians Approximate with m GaussiansCollapsing Gaussians – Single Gaussian from a mixture Given mixture P <wi;N(µi,Σi)> Obtain approximation Q~N(µ,Σ) as: Theorem: P and Q have same first and second moments KL projection: Q is single Gaussian with lowest KL divergence from PCollapsing mixture of Gaussians into smaller mixture of Gaussians Hard problem! Akin to clustering problem… Several heuristics exist c.f., Uri Lerner’s Ph.D. thesisOperations in non-linear switching Kalman filterX1O1= X5X3X4X2O2= O3= O4= O5= Compute mixture of Gaussians for Start with At each time step t: For each of the m Gaussians in p(Xi|o1:i): Condition on observation (use numerical integration) Prediction (Multiply transition model, use numerical integration) Obtain k Gaussians Roll-up (marginalize previous time step) Project k.m Gaussians into m’ Gaussians p(Xi|o1:i+1)Assumed density filtering Examples of very important assumed density filtering: Non-linear KF Approximate inference in switching KF General picture: Select an assumed density e.g., single Gaussian, mixture of m Gaussians, … After conditioning, prediction, or roll-up, distribution no-longer representable with assumed density e.g., non-linear, mixture of k.m Gaussians,… Project back into assumed density e.g., numerical integration, collapsing,…When non-linear KF is not good enough Sometimes, distribution in non-linear KF is not approximated well as a single Gaussian e.g., a banana-like distribution Assumed density filtering: Solution 1: reparameterize problem and solve as a single Gaussian Solution 2: more typically, approximate as a mixture of GaussiansDistributed Simultaneous Localization and Tracking[Funiak, Guestrin, Paskin, Sukthankar ’05] Place cameras around an environment, don’t know where they are Could measure all locations, but requires lots of grad. student time Intuition: A person walks around If camera 1 sees person, then camera 2 sees person, learn about relative
View Full Document
Unlocking...