ProbabilisticGraphical ModelsLecture 13 – Loopy Belief PropagationCS/CNS/EE 155Andreas Krause2AnnouncementsHomework 3 outLighter problem set to allow more time for projectNext Monday: Guest lecture by Dr. BabackMoghaddam from the JPL Machine Learning GroupPLEASE fill out feedback formsThis is a new courseYour feedback can have major impact in future offerings!!3HMMs / Kalman FiltersMost famous Graphical models:Naïve Bayes modelHidden Markov modelKalman FilterHidden Markov modelsSpeech recognitionSequence analysis in comp. bioKalman Filters controlCruise control in carsGPS navigation devicesTracking missiles..Very simple models but very powerful!!4HMMs / Kalman FiltersX1,…,XT: Unobserved (hidden) variablesY1,…,YT: ObservationsHMMs: XiMultinomial, YiarbitraryKalman Filters: Xi, YiGaussian distributionsNon-linear KF: XiGaussian, YiarbitraryY1Y2Y3Y4Y5Y6X1X2X3X4X5X65Hidden Markov ModelsInference:In principle, can use VE, JT etc.New variables Xt, Ytateach time step  need to rerunBayesian Filtering:Suppose we already have computed P(Xt| y1,…,t)Want to efficiently compute P(Xt+1| y1,…,t+1)Y1Y2Y3Y4Y5Y6X1X2X3X4X5X66Bayesian filteringStart with P(X1)At time tAssume we have P(Xt| y1…t-1)Condition: P(Xt| y1…t)Prediction: P(Xt+1, Xt| y1…t)Marginalization: P(Xt+1| y1…t)Y1Y2Y3Y4Y5Y6X1X2X3X4X5X67Kalman Filters (Gaussian HMMs)X1,…,XT: Location of object being trackedY1,…,YT: ObservationsP(X1): Prior belief about location at time 1P(Xt+1|Xt): “Motion model”How do I expect my target to move in the environment?Represented as CLG: Xt+1= A Xt+ N(0, ΣM)P(Yt| Xt): “Sensor model”What do I observe if target is at location Xt?Represented as CLG: Yt= H Xt+ N(0, ΣO)Y1Y2Y3Y4Y5Y6X1X2X3X4X5X68Bayesian Filtering for KFsCan use Gaussian elimination to perform inference in “unrolled” model Start with prior belief P(X1)At every timestep have belief P(Xt| y1:t-1)Condition on observation: P(Xt| y1:t)Predict (multiply motion model): P(Xt+1,Xt| y1:t)“Roll-up” (marginalize prev. time): P(Xt+1| y1:t)Y1Y2Y3Y4Y5Y6X1X2X3X4X5X69What if observations not “linear”?Linear observations:Yt= H Xt+ noiseNonlinear observations:10Incorporating Non-gaussian observationsNonlinear observation  P(Yt| Xt) not Gaussian Make it Gaussian! ☺First approach: Approximate P(Yt| Xt) as CLGLinearize P(Yt| Xt) around current estimate E[Xt| y1..t-1]Known as Extended Kalman Filter (EKF)Can perform poorly if P(Yt| Xt) highly nonlinearSecond approach: Approximate P(Yt, Xt) as GaussianTakes correlation in Xtinto accountAfter obtaining approximation, condition on Yt=yt(now a “linear” observation)11Factored dynamical modelsSo far: HMMs and Kalman filtersWhat if we have more than one variable at each time step?E.g., temperature at different locations, or road conditions in a road network? Spatio-temporal modelsY1Y2Y3Y4Y5Y6X1X2X3X4X5X612Dynamic Bayesian NetworksAt every timestep have a Bayesian NetworkVariables at each time step t called a “slice” St“Temporal” edges connecting St+1with StA1B1C1D1E1A2B2C2D2E2A3B3C3D3E313Flow of influence in DBNsCan we do efficient filtering in BNs?A1S1L1A2S2L2A3S3L3A4S4L4accelerationspeedlocation14Efficient inference in DBNs?A1B1C1D1A2B2C2D215Approximate inference in DBNs?A1B1C1A2B2C2D1D2A2B2C2D2How can we find principled approximations that stillallow efficient inference??DBNMarginals at time 216Assumed Density FilteringTrue marginal P(Xt) fully connected Want to find “simpler” distribution Q(Xt) such that P(Xt) ≈ Q(Xt)Optimize over parameters of Q to make Q as “close” to P as possibleSimilar to incorporating non-linear observations in KF!More details later (variational inference)!AtBtCtDtAtBtCtDtTrue marginalApproximate marginal17Big picture summaryWant to choose a model that …represents relevant statistical dependencies between variableswe can use to make inferences (make predictions, etc.)we can learn from training datas1s2s3s4s5s7s6s11s12s9s10s8s1s3s12s9States of the world,sensor measurements, …Graphical modelrepresent18What you have learned so farRepresentationBayesian NetworksMarkov NetworksConditional independence is keyInferenceVariable Elimination and Junction tree inferenceExact inference possible if graph has low treewidthLearningParameters: Can do MLE and Bayesian learning in BayesNets and Markov Nets if data fully observedStructure: Can find optimal tree19RepresentationConditional independence = FactorizationRepresent factorization/independence as graphDirected graphs: Bayesian networksUndirected graphs: Markov networksTypically, assume factors in exponential family (e.g., Multinomial, Gaussian, …)So far, we assumed all variables in the model are knownIn practiceExistence of variables can depend on dataNumber of variables can grow over timeWe might have hidden (unobserved variables)!20InferenceKey idea: Exploit factorization (distributivity)Complexity of inference depends on treewidth of underlying modelJunction tree inference “only” exponential in treewidthIn practice, often have high treewidthAlways high treewidth in DBNs Need approximate inference21LearningMaximum likelihood estimationIn BNs: independent optimization for each CPT (decomposable score)In MNs: Partition function couples parameters, but can do gradient ascent (no local optima!)Bayesian parameter estimationConjugate priors convenient to work withStructure learningNP-hard in generalCan find optimal tree (Chow Liu)So far: Assumed all variables are observedIn practice: often have missing data22The “light” sideAssumedeverything fully observablelow treewidthno hidden variablesThen everything is nice ☺Efficient exact inference in large modelsOptimal parameter estimation without local minimaCan even solve some structure learning tasks exactly23The “dark” sideIn the real world, these assumptions are often violated..Still want to use graphical models to solve interesting problems..s1s2s3s4s5s7s6s11s12s9s10s8s1s3s12s9States of the world,sensor measurements, …Graphical modelrepresent24Remaining ChallengesRepresentation:Dealing with hidden variablesApproximate inference for high-treewidth modelsDealing with missing dataThis will be focus of remaining part of the course!25Recall: Hardness of inferenceComputing conditional distributions:Exact solution: #P-completeApproximate solution: NP-hardMaximization:MPE: NP-completeMAP: NPPP-complete26InferenceCan exploit structure (conditional independence) to efficiently perform exact inference in many practical