DYNAMIC INFERENCE IN PROBABILISTIC GRAPHICAL MODELS WEIMING FENG.KUN HE.XIAOMING SUN.AND YITONG YIN ABSTRACT.Probabilistic graphical models,such as Markov random fields(MRFs),are useful for describ- ing high-dimensional 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 the 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.mul- tivariate time-series data and practical learning procedures. We give a dynamic algorithm for sampling-based probabilistic inferences in MRFs,where each dy- namic update can change the underlying graph and all parameters of the MRF simultaneously,as long as the total amount of changes is bounded.Suppose that the MRF has n variables and bounded 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 O(nN(n))space cost, and O(N(n)+n)incremental time cost upon each update to the MRF,as long as the Dobrushin-Shlosman condition is satisfied by the MRFs.This well-known 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 (nN(n))time cost for redrawing all N(n)samples whenever the MRF changes,our dynamic algorithm gives a significant Q(minin,N(n)))-factor speedup.Our approach relies on a novel dynamic sampling technique,which transforms traditional local Markov chains(a.k.a.single- site dynamics)to dynamic sampling algorithms,in a scenario where all parameters of the graphical model are subject to simultaneous update at each time. (Weiming Feng,Yitong Yin)STATE KEY LABORATORY FOR NOVEL SOFTWARE TECHNOLOGY,NANJING UNIVERSITY.E-mail: fengwm@smail.nju.edu.cn,yinyt@nju.edu.cn (Kun He)SHENZHEN UNIVERSITY:SHENZHEN INSTITUTE OF COMPUTING SCIENCES.E-mail:hekun.threebodyofoxmail. com (Xiaoming Sun)CAS KEY LAB OF NETWORK DATA SCIENCE AND TECHNOLOGY,INSTITUTE OF COMPUTING TECHNOLOGY, CHINESE ACADEMY OF SCIENCES.E-mail:sunxiaoming@ict.ac.cn This research is supported by the National Key R&D Program of China 2018YFB1003202 and the National Science Foun- dation of China under Grant Nos.61722207 and 61672275.DYNAMIC INFERENCE IN PROBABILISTIC GRAPHICAL MODELS WEIMING FENG, KUN HE, XIAOMING SUN, AND YITONG YIN Abstract. Probabilistic graphical models, such as Markov random fields (MRFs), are useful for describ￾ing high-dimensional 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 the 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. mul￾tivariate time-series data and practical learning procedures. We give a dynamic algorithm for sampling-based probabilistic inferences in MRFs, where each dy￾namic update can change the underlying graph and all parameters of the MRF simultaneously, as long as the total amount of changes is bounded. Suppose that the MRF has n variables and bounded 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 Oe(nN(n)) space cost, and Oe(N(n)+n) incremental time cost upon each update to the MRF, as long as the Dobrushin-Shlosman condition is satisfied by the MRFs. This well-known 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 Ω(nN(n)) time cost for redrawing all N(n) samples whenever the MRF changes, our dynamic algorithm gives a significant Ωe(min{n, N(n)})-factor speedup. Our approach relies on a novel dynamic sampling technique, which transforms traditional local Markov chains (a.k.a. single￾site dynamics) to dynamic sampling algorithms, in a scenario where all parameters of the graphical model are subject to simultaneous update at each time. (Weiming Feng, Yitong Yin) State Key Laboratory for Novel Software Technology, Nanjing University. E-mail: fengwm@smail.nju.edu.cn,yinyt@nju.edu.cn (Kun He) Shenzhen University; Shenzhen Institute of Computing Sciences. E-mail: hekun.threebody@foxmail. com (Xiaoming Sun) CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences. E-mail: sunxiaoming@ict.ac.cn This research is supported by the National Key R&D Program of China 2018YFB1003202 and the National Science Foun￾dation of China under Grant Nos. 61722207 and 61672275