Fast Fourier Transform Reductions for Bayesian Network Inference

Vincent Hsiao, Dana Nau, Rina Dechter
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:6445-6458, 2022.

Abstract

Bayesian Networks are useful for analyzing the properties of systems with large populations of interacting agents (e.g., in social modeling applications and distributed service applications). These networks typically have large functions (CPTs), making exact inference intractable. However, often these models have additive symmetry. In this paper we show how summation-based CPTs, especially in the presence of symmetry, can be computed efficiently through the usage of the Fast Fourier Transform (FFT). In particular, we propose an efficient method using the FFT for reducing the size of Conditional Probability Tables (CPTs) in Bayesian Networks with summation-based causal independence (CI). We then show how to apply this reduction directly towards the acceleration of Bucket Elimination, and we subsequently provide experimental results demonstrating the computational speedup provided by our method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-hsiao22a, title = { Fast Fourier Transform Reductions for Bayesian Network Inference }, author = {Hsiao, Vincent and Nau, Dana and Dechter, Rina}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {6445--6458}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/hsiao22a/hsiao22a.pdf}, url = {https://proceedings.mlr.press/v151/hsiao22a.html}, abstract = { Bayesian Networks are useful for analyzing the properties of systems with large populations of interacting agents (e.g., in social modeling applications and distributed service applications). These networks typically have large functions (CPTs), making exact inference intractable. However, often these models have additive symmetry. In this paper we show how summation-based CPTs, especially in the presence of symmetry, can be computed efficiently through the usage of the Fast Fourier Transform (FFT). In particular, we propose an efficient method using the FFT for reducing the size of Conditional Probability Tables (CPTs) in Bayesian Networks with summation-based causal independence (CI). We then show how to apply this reduction directly towards the acceleration of Bucket Elimination, and we subsequently provide experimental results demonstrating the computational speedup provided by our method. } }
Endnote
%0 Conference Paper %T Fast Fourier Transform Reductions for Bayesian Network Inference %A Vincent Hsiao %A Dana Nau %A Rina Dechter %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-hsiao22a %I PMLR %P 6445--6458 %U https://proceedings.mlr.press/v151/hsiao22a.html %V 151 %X Bayesian Networks are useful for analyzing the properties of systems with large populations of interacting agents (e.g., in social modeling applications and distributed service applications). These networks typically have large functions (CPTs), making exact inference intractable. However, often these models have additive symmetry. In this paper we show how summation-based CPTs, especially in the presence of symmetry, can be computed efficiently through the usage of the Fast Fourier Transform (FFT). In particular, we propose an efficient method using the FFT for reducing the size of Conditional Probability Tables (CPTs) in Bayesian Networks with summation-based causal independence (CI). We then show how to apply this reduction directly towards the acceleration of Bucket Elimination, and we subsequently provide experimental results demonstrating the computational speedup provided by our method.
APA
Hsiao, V., Nau, D. & Dechter, R.. (2022). Fast Fourier Transform Reductions for Bayesian Network Inference . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:6445-6458 Available from https://proceedings.mlr.press/v151/hsiao22a.html.

Related Material