Abstract
Probabilistic graphical models, such as Markov random fields (MRFs), are useful for describing highdimensional distributions in terms of local dependence structures. The {probabilistic inference} is a fundamental problem related to graphical models, and sampling is a main approach for the problem. In this paper, we study probabilistic inference problems when the graphical model itself is changing dynamically with time. Such dynamic inference problems arise naturally in today’s application, e.g. multivariate timeseries data analysis and practical learning procedures.
We give a dynamic algorithm for samplingbased probabilistic inferences in MRFs, where each dynamic update can change the underlying graph and all parameters of the MRF simultaneously, as long as the total amount of changes is bounded. More precisely, suppose that the MRF has n variables and polylogarithmicbounded maximum degree, and N(n) independent samples are sufficient for the inference for a polynomial function N(⋅). Our algorithm dynamically maintains an answer to the inference problem using Õ(n N(n)) space cost, and Õ(N(n) + n) incremental time cost upon each update to the MRF, as long as the DobrushinShlosman condition is satisfied by the MRFs. This wellknown condition has long been used for guaranteeing the efficiency of Markov chain Monte Carlo (MCMC) sampling in the traditional static setting. Compared to the static case, which requires Ω(n N(n)) time cost for redrawing all N(n) samples whenever the MRF changes, our dynamic algorithm gives a ?^~(min{n, N(n)})factor speedup. Our approach relies on a novel dynamic sampling technique, which transforms local Markov chains (a.k.a. singlesite dynamics) to dynamic sampling algorithms, and an "algorithmic Lipschitz" condition that we establish for sampling from graphical models, namely, when the MRF changes by a small difference, samples can be modified to reflect the new distribution, with cost proportional to the difference on MRF.
BibTeX  Entry
@InProceedings{feng_et_al:LIPIcs.ITCS.2021.25,
author = {Weiming Feng and Kun He and Xiaoming Sun and Yitong Yin},
title = {{Dynamic Inference in Probabilistic Graphical Models}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {25:125:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13564},
URN = {urn:nbn:de:0030drops135643},
doi = {10.4230/LIPIcs.ITCS.2021.25},
annote = {Keywords: Dynamic inference, probabilistic graphical model, Gibbs sampling, Markov random filed}
}
Keywords: 

Dynamic inference, probabilistic graphical model, Gibbs sampling, Markov random filed 
Collection: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 
Issue Date: 

2021 
Date of publication: 

04.02.2021 