Abstract
Time in Bayesian Networks is concrete: In medical applications, a timestep can correspond to one second. To proceed in time, temporal inference algorithms answer conditional queries. But the interface algorithm simulates iteratively into the future making predictions costly and intractable for applications. We present an exact, GPU-optimizable approach exploiting symmetries over time during answering prediction queries by constructing a matrix for the underlying temporal process. Additionally, we construct a vector capturing the probability distribution at the current timestep. Then, we can time-warp into the future by matrix exponentiation. We show an order of magnitude speedup over the interface algorithm. The work-heavy preprocessing step can be done offline, and the runtime of prediction queries is significantly reduced. Now, we can handle application problems that could not be handled before.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ankan, A., Panda, A.: Pgmpy: probabilistic graphical models using python. In: Proceedings of the 14th Python in Science Conference (SCIPY 2015). Citeseer (2015)
Boyen, X., Koller, D.: Tractable inference for complex stochastic processes. In: Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, pp. 33–42 (1998)
Dagum, P., Galper, A., Horvitz, E.: Dynamic network models for forecasting. In: Uncertainty in Artificial Intelligence, pp. 41–48. Elsevier (1992)
Darwiche, A.: Modeling and Reasoning with Bayesian Networks. Cambridge University Press, Cambridge (2009)
Gehrke, M., Braun, T., Möller, R.: Lifted dynamic junction tree algorithm. In: Chapman, P., Endres, D., Pernelle, N. (eds.) ICCS 2018. LNCS (LNAI), vol. 10872, pp. 55–69. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-91379-7_5
Gehrke, M., Braun, T., Möller, R.: Lifted temporal maximum expected utility. In: Meurs, M.-J., Rudzicz, F. (eds.) Canadian AI 2019. LNCS (LNAI), vol. 11489, pp. 380–386. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-18305-9_33
Hartwig, M.: New methods for efficient query answering in gaussian probabilistic graphical models. Ph.D. thesis, University of Lübeck (2022)
Kersting, K., Ahmadi, B., Natarajan, S.: Counting belief propagation. arXiv preprint arXiv:1205.2637 (2012)
Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge (2009)
Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. J. Roy. Stat. Soc.: Ser. B (Methodol.) 50(2), 157–194 (1988)
Murphy, K.P.: Dynamic Bayesian networks: representation, inference and learning. University of California, Berkeley (2002)
Pearl, J.: Probabilistic reasoning using graphs. In: Bouchon, B., Yager, R.R. (eds.) IPMU 1986. LNCS, vol. 286, pp. 200–202. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-18579-8_19
Pearl, J.: Bayesian networks (2011)
Russell, S.J., Norvig, P.: Artificial Intelligence a Modern Approach. Pearson Education, Inc. (2010)
Singla, P., Domingos, P.M.: Lifted first-order belief propagation. In: AAAI, vol. 8, pp. 1094–1099 (2008)
Zhang, N.L., Poole, D.: A simple approach to Bayesian network computations. In: Proceedings of the Tenth Canadian Conference on Artificial Intelligence (1994)
Acknowledgements
The research for this paper was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - EXC 2176 ‘Understanding Written Artefacts: Material, Interaction and Transmission in Manuscript Cultures’, project no. 390893796. The research was conducted within the scope of the Centre for the Study of Manuscript Cultures (CSMC) at Universität Hamburg.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Marwitz, F.A., Möller, R., Gehrke, M. (2024). PETS: Predicting Efficiently Using Temporal Symmetries in Temporal PGMs. In: Bouraoui, Z., Vesic, S. (eds) Symbolic and Quantitative Approaches to Reasoning with Uncertainty. ECSQARU 2023. Lecture Notes in Computer Science(), vol 14294. Springer, Cham. https://doi.org/10.1007/978-3-031-45608-4_24
Download citation
DOI: https://doi.org/10.1007/978-3-031-45608-4_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-45607-7
Online ISBN: 978-3-031-45608-4
eBook Packages: Computer ScienceComputer Science (R0)