Switching Kalman Filter Dynamic Bayesian NetworksWhat you need to know about Kalman FiltersWhat if the person chooses different motion models?The moonwalkSlide 5Switching Kalman filterInference in switching KF – one stepMulti-step inferenceVisualizing growth in number of GaussiansComputational complexity of inference in switching Kalman filtersBounding number of GaussiansCollapsing mixture of Gaussians into smaller mixture of GaussiansOperations in non-linear switching Kalman filterAnnouncementsAssumed density filteringWhen non-linear KF is not good enoughReparameterized KF for SLATWhen a single Gaussian ain’t good enoughWhat you need to knowMore than just a switching KFDynamic Bayesian network (DBN)Transition Model: Two Time-slice Bayes Net (2-TBN)Unrolled DBN“Sparse” DBN and fast inferenceEven after one time step!!“Sparse” DBN and fast inference 2BK Algorithm for approximate DBN inference [Boyen, Koller ’98]A simple example of BK: Fully-Factorized DistributionComputing Fully-Factorized Distribution at time t+1General case for BK: Junction Tree Represents DistributionComputing 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 summary1Switching Kalman FilterDynamic Bayesian NetworksGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityNovember 27th, 2006Readings:K&F: 4.5, 12.2, 12.3, 12.4, 18.1, 18.2, 18.3, 18.42 What you need to know about Kalman Filters Kalman filterProbably most used BNAssumes Gaussian distributionsEquivalent to linear systemSimple matrix operations for computationsNon-linear Kalman filterUsually, observation or motion model not CLGUse numerical integration to find Gaussian approximation3 What if the person chooses different motion models?With probability , move more or less straightWith probability 1-, do the “moonwalk”4 The moonwalk5 What if the person chooses different motion models?With probability , move more or less straightWith probability 1-, do the “moonwalk”6 Switching Kalman filterAt each time step, choose one of k motion models:You never know which one!p(Xi+1|Xi,Zi+1) CLG indexed by Zip(Xi+1|Xi,Zi+1=j) ~ N(j0 + j Xi; jXi+1|Xi)7 Inference in switching KF – one stepSuppose p(X0) is GaussianZ1 takes one of two valuesp(X1|Xo,Z1) is CLGMarginalize X0Marginalize Z1Obtain mixture of two Gaussians!8 Multi-step inferenceSuppose p(Xi) is a mixture of m GaussiansZi+1 takes one of two valuesp(Xi+1|Xi,Zi+1) is CLGMarginalize XiMarginalize ZiObtain mixture of 2m Gaussians!Number of Gaussians grows exponentially!!!9 Visualizing growth in number of Gaussians10 Computational complexity of inference in switching Kalman filtersSwitching Kalman Filter with (only) 2 motion modelsQuery:Problem is NP-hard!!! [Lerner & Parr `01]Why “!!!”?Graphical model is a tree:Inference efficient if all are discreteInference efficient if all are GaussianBut not with hybrid model (combination of discrete and continuous)11 Bounding number of GaussiansP(Xi) has 2m Gaussians, but…usually, most are bumps have low probability and overlap:Intuitive approximate inference:Generate k.m GaussiansApproximate with m Gaussians13 Collapsing mixture of Gaussians into smaller mixture of GaussiansHard problem!Akin to clustering problem…Several heuristics existc.f., K&F book14 Operations in non-linear switching Kalman filterCompute mixture of Gaussians forStart 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 GaussiansRoll-up (marginalize previous time step)Project k.m Gaussians into m’ Gaussians p(Xi|o1:i+1)X1O1 = X5X3X4X2O2 = O3 = O4 = O5 =10-708 – Carlos Guestrin 200615 AnnouncementsLectures the rest of the semester:Wed. 11/30, regular class time: Causality (Richard Scheines)Last Class: Friday 12/1, regular class time: Finish Dynamic BNs & Overview of Advanced TopicsDeadlines & Presentations:Project Poster Presentations: Dec. 1st 3-6pm (NSH Atrium)popular vote for best posterProject write up: Dec. 8th by 2pm by email 8 pages – limit will be strictly enforcedFinal: Out Dec. 1st, Due Dec. 15th by 2pm (strict deadline)no late days on final!16 Assumed density filteringExamples of very important assumed density filtering:Non-linear KFApproximate inference in switching KFGeneral picture:Select an assumed densitye.g., single Gaussian, mixture of m Gaussians, …After conditioning, prediction, or roll-up, distribution no-longer representable with assumed densitye.g., non-linear, mixture of k.m Gaussians,…Project back into assumed densitye.g., numerical integration, collapsing,…17 When non-linear KF is not good enoughSometimes, distribution in non-linear KF is not approximated well as a single Gaussiane.g., a banana-like distributionAssumed density filtering:Solution 1: reparameterize problem and solve as a single GaussianSolution 2: more typically, approximate as a mixture of Gaussians18 Reparameterized KF for SLAT[Funiak, Guestrin, Paskin, Sukthankar ’05]19 When a single Gaussian ain’t good enoughSometimes, smart parameterization is not enoughDistribution has multiple hypothesisPossible solutionsSampling – particle filteringMixture of Gaussians…See book for details…[Fox et al.]21 What you need to knowSwitching Kalman filterHybrid model – discrete and continuous vars.Represent belief as mixture of GaussiansNumber of mixture components grows exponentially in timeApproximate each time step with fewer componentsAssumed density filteringFundamental abstraction of most algorithms for dynamical systemsAssume representation for densityEvery time density not representable, project into representation22 More than just a switching KFSwitching KF selects among k motion modelsDiscrete variable can depend on pastMarkov model over hidden variableWhat if k is really large?Generalize HMMs to large number of variables23 Dynamic
View Full Document
Unlocking...