Kalman Filters Gaussian MNsMultivariate GaussianConditioning a GaussianGaussian is a “Linear Model”Slide 5Conditional Linear Gaussian (CLG) – general caseUnderstanding a linear Gaussian – the 2d caseTracking with a Gaussian 1Tracking with Gaussians 2 – Making observationsOperations in Kalman filterExponential family representation of Gaussian: Canonical FormCanonical formConditioning in canonical formSlide 14Prediction & roll-up in canonical formWhat if observations are not CLG?Linearization: incorporating non-linear evidenceLinearization as integrationLinearization as numerical integrationOperations in non-linear Kalman filterCanonical form & Markov NetsWhat you need to know about Gaussians, Kalman Filters, Gaussian MNs1Kalman FiltersGaussian MNsGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityDecember 1st, 2008Readings:K&F: 6.1, 6.2, 6.3, 14.1, 14.2, 14.3, 14.4,2Multivariate GaussianMean vector:Covariance matrix:3Conditioning a GaussianJoint Gaussian:p(X,Y) ~ N(;)Conditional linear Gaussian:p(Y|X) ~ N(Y|X; 2Y|X)4Gaussian is a “Linear Model”Conditional linear Gaussian:p(Y|X) ~ N(0+X; 2)5Conditioning a GaussianJoint Gaussian:p(X,Y) ~ N(;)Conditional linear Gaussian:p(Y|X) ~ N(Y|X; YY|X)6Conditional Linear Gaussian (CLG) – general caseConditional linear Gaussian:p(Y|X) ~ N(0+X; YY|X)7Understanding a linear Gaussian – the 2d caseVariance increases over time (motion noise adds up)Object doesn’t necessarily move in a straight line8Tracking with a Gaussian 1p(X0) ~ N(0,0)p(Xi+1|Xi) ~ N(Xi + ; Xi+1|Xi)9Tracking with Gaussians 2 – Making observationsWe have p(Xi)Detector observes Oi=oiWant to compute p(Xi|Oi=oi)Use Bayes rule:Require a CLG observation modelp(Oi|Xi) ~ N(W Xi + v; Oi|Xi)10Operations in Kalman filterComputeStart with At each time step t:Condition on observationPrediction (Multiply transition model)Roll-up (marginalize previous time step)I’ll describe one implementation of KF, there are othersInformation filterX1O1 = X5X3X4X2O2 = O3 = O4 = O5 =11Exponential family representation of Gaussian: Canonical Form12Canonical formStandard form and canonical forms are related:Conditioning is easy in canonical formMarginalization easy in standard form13Conditioning in canonical formFirst multiply:Then, condition on value B = y14Operations in Kalman filterComputeStart with At each time step t:Condition on observationPrediction (Multiply transition model)Roll-up (marginalize previous time step)X1O1 = X5X3X4X2O2 = O3 = O4 = O5 =15Prediction & roll-up in canonical formFirst multiply:Then, marginalize Xt:16What if observations are not CLG?Often observations are not CLGCLG if Oi = Xi + o + Consider a motion detector Oi = 1 if person is likely to be in the regionPosterior is not Gaussian17Linearization: incorporating non-linear evidencep(Oi|Xi) not CLG, but…Find a Gaussian approximation of p(Xi,Oi)= p(Xi) p(Oi|Xi)Instantiate evidence Oi=oi and obtain a Gaussian for p(Xi|Oi=oi)Why do we hope this would be any good?Locally, Gaussian may be OK18Linearization as integrationGaussian approximation of p(Xi,Oi)= p(Xi) p(Oi|Xi)Need to compute momentsE[Oi]E[Oi2]E[Oi Xi]Note: Integral is product of a Gaussian with an arbitrary function19Linearization as numerical integrationProduct of a Gaussian with arbitrary functionEffective numerical integration with Gaussian quadrature methodApproximate integral as weighted sum over integration pointsGaussian quadrature defines location of points and weightsExact if arbitrary function is polynomial of bounded degreeNumber of integration points exponential in number of dimensions dExact monomials requires exponentially fewer pointsFor 2d+1 points, this method is equivalent to effective Unscented Kalman filterGeneralizes to many more points20Operations in non-linear Kalman filterComputeStart with At each time step t:Condition on observation (use numerical integration)Prediction (Multiply transition model, use numerical integration)Roll-up (marginalize previous time step)X1O1 = X5X3X4X2O2 = O3 = O4 = O5 =21Canonical form & Markov Nets22What you need to know about Gaussians, Kalman Filters, Gaussian MNsKalman 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 approximationGaussian Markov NetsSparsity in precision matrix equivalent to graph structureContinuous and discrete (hybrid) modelMuch harder, but doable and interesting (see
View Full Document
Unlocking...