The effect of combination functions on the complexity of relational Bayesian networks. (English) Zbl 1419.68172
Summary: We study the complexity of inference with Relational Bayesian Networks as parameterized by their probability formulas. We show that without combination functions, inference is pp-complete, displaying the same complexity as standard Bayesian networks (this is so even when the domain is succinctly specified in binary notation). Using only maximization as combination function, we obtain inferential complexity that ranges from pp-complete to pspace-complete to pexp-complete. And by combining mean and threshold combination functions, we obtain complexity classes in all levels of the counting hierarchy. We also investigate the use of arbitrary combination functions and obtain that inference is exp-complete even under a seemingly strong restriction. Finally, we examine the query complexity of Relational Bayesian Networks (i.e., when the relational model is fixed), and we obtain that inference is complete for pp.
MSC:
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Arora, S.; Barak, B., Computational Complexity: A Modern Approach (2009), Cambridge University Press · Zbl 1193.68112 |
| [2] | Bailey, D.; Dalmau, V.; Kolaitis, P., Phase transitions of PP-complete satisfiability problems, Discrete Appl. Math., 155, 12, 1627-1639 (2007) · Zbl 1123.68117 |
| [3] | Balcázar, J.; Book, R.; Schöning, U., The polynomial-time hierarchy and sparse oracles, J. ACM, 33, 603-617 (1986) · Zbl 0625.68033 |
| [4] | Beigel, R.; Reingold, N.; Spielman, D., PP is closed under intersection, J. Comput. Syst. Sci., 50, 1, 191-202 (1995) · Zbl 0827.68040 |
| [5] | Bulatov, A.; Dyer, M.; Goldberg, L.; Jalsenius, M.; Jerrum, M.; Richerby, D., The complexity of weighted and unweighted \(\# CSP\), J. Comput. Syst. Sci., 78, 681-688 (2012) · Zbl 1282.68110 |
| [6] | Chavira, M.; Darwiche, A.; Jaeger, M., Compiling relational Bayesian networks for exact inference, Int. J. Approx. Reason., 42, 1-2, 4-20 (2006) · Zbl 1096.68747 |
| [7] | Cozman, F.; Mauá, D., Bayesian networks specified using propositional and relational constructs: combined, data, and domain complexity, (Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)), 3519-3525 |
| [8] | Darwiche, A., Modeling and Reasoning with Bayesian Networks (2009), Cambridge University Press · Zbl 1231.68003 |
| [9] | Darwiche, A.; Provan, G., Query DAGs: a practical paradigm for implementing belief-network inference, J. Artif. Intell. Res., 6, 147-176 (1997) · Zbl 0894.68134 |
| [10] | de Campos, C.; Stamoulis, G.; Weyland, D., A Structured View on Weighted Counting with Relations to Quantum Computation and Applications (2013), Tech. rep., Electronic Colloquium on Computational Complexity |
| [11] | de Raedt, L., Logical and Relational Learning (2008), Springer-Verlag · Zbl 1203.68145 |
| [12] | de Raedt, L.; Frasconi, P.; Kersting, K.; Muggleton, S., Probabilistic Inductive Logic Programming: Theory and Applications (2008), Springer-Verlag · Zbl 1132.68007 |
| [13] | Durand, A.; Hermann, M.; Kolaitis, P., Subtractive reductions and complete problems for counting complexity classes, Theor. Comput. Sci., 340, 3, 496-513 (2005) · Zbl 1077.68033 |
| [14] | Enderton, H., A Mathematical Introduction to Logic (1972), Academic Press · Zbl 0298.02002 |
| [15] | Geiger, D.; Verma, T.; Pearl, J., Identifying independence in Bayesian networks, Networks, 20, 5, 507-534 (1990) · Zbl 0724.05066 |
| [16] | Getoor, L.; Taskar, B., Introduction to Statistical Relational Learning (2007), The MIT Press · Zbl 1141.68054 |
| [17] | Gilks, W.; Thomas, A.; Spiegelhalter, D., A language and program for complex Bayesian modelling, Statistician, 43, 169-178 (1993) |
| [18] | Grädel, E., Finite model theory and descriptive complexity, (Finite Model Theory and Its Applications (2007), Springer: Springer Berlin, Heidelberg), 125-229 |
| [19] | Grove, A.; Halpern, J.; Koller, D., Asymptotic conditional probabilities: the unary case, SIAM J. Comput., 25, 1, 1-51 (1996) · Zbl 0848.03004 |
| [20] | Jaeger, M., Relational Bayesian networks, (Proc. of the 13th Conf. of Uncertainty in AI (UAI) (1997)), 266-273 |
| [21] | Jaeger, M., Complex probabilistic modeling with recursive relational Bayesian networks, Ann. Math. Artif. Intell., 32, 1, 179-220 (2001) · Zbl 1314.68302 |
| [22] | Koller, D.; Friedman, N., Probabilistic Graphical Models (2009), The MIT Press · Zbl 1183.68483 |
| [23] | Koller, D.; Pfeffer, A., Object-oriented Bayesian networks, (Proc. of the 13th Conf. on Uncertainty in AI (UAI) (1997)), 302-313 |
| [24] | Koller, D.; Pfeffer, A., Probabilistic frame-based systems, (Proc. of the 15th National Conf. on AI (AAAI) (1998)), 580-587 |
| [25] | Kwisthout, J., The Computational Complexity of Probabilistic Inference (2011), Radboud University Nijmegen, Tech. Rep. ICIS-R11003 |
| [26] | Ladner, R., Polynomial space counting problems, SIAM J. Comput., 18, 6, 1087-1097 (1989) · Zbl 0692.68036 |
| [27] | Lunn, D.; Jackson, C.; Best, N.; Thomas, A.; Spiegelhalter, D., The BUGS Book: A Practical Introduction to Bayesian Analysis (2012), CRC Press/Chapman and Hall |
| [28] | Meyer, A.; Stockmeyer, L., The equivalence problem for regular expressions with squaring requires exponential time, (Proceedings of the 13th Annual Symposium on Switching and Automata Theory (1972)), 125-129 |
| [29] | Papadimitriou, C., Computational Complexity (1994), Addison-Wesley Publishing · Zbl 0833.68049 |
| [30] | Poole, D., Probabilistic Horn abduction and Bayesian networks, Artif. Intell., 64, 81-129 (1993) · Zbl 0792.68176 |
| [31] | Roth, D., On the hardness of approximate reasoning, Artif. Intell., 82, 1-2, 273-302 (1996) · Zbl 1506.68143 |
| [32] | Toda, S., PP is as hard as the polynomial-time hierarchy, SIAM J. Comput., 20, 5, 865-877 (1989) · Zbl 0733.68034 |
| [33] | Toda, S.; Watanabe, O., Polynomial-time 1-Turing reductions from \(\# \textsc{ph}\) to \(\# \textsc{p} \), Theor. Comput. Sci., 100, 205-221 (1992) · Zbl 0779.68037 |
| [34] | Tóran, J., Complexity classes defined by counting quantifiers, J. ACM, 38, 3, 753-774 (1991) · Zbl 0799.68080 |
| [35] | Valiant, L., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 3, 410-421 (1979) · Zbl 0419.68082 |
| [36] | Wagner, K., The complexity of combinatorial problems with succinct input representation, Acta Inform., 23, 325-356 (1986) · Zbl 0621.68032 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
