← Back to papers
2016 PGM PGM 2016

The Effect of Combination Functions on the Complexity of Relational Bayesian Networks

Abstract

We study the complexity of marginal inference with Relational Bayesian Networks as parameterized by their probability formulas. We show that without combination functions, inference is #\sc\MakeLowercaseP-equivalent, displaying the same complexity as standard Bayesian networks (this is so even when relations have unbounded arity and when the domain is succinctly specified in binary notation). By allowing increasingly more expressive probability formulas using only maximization as combination, we obtain inferential complexity that ranges from #\sc\MakeLowercasep-equivalent to \sc\MakeLowercasefpspace-complete to \sc\MakeLowercaseexp-hard. In fact, by suitable restrictions to the number of nestings of combination functions, we obtain complexity classes in all levels of the counting hierarchy. Finally, we investigate the use of arbitrary combination functions and obtain that inference is \sc\MakeLowercasefexp-complete even under a seemingly strong restriction.

🚀 Conference Pioneer — PGM 2016
📈 Trend Setter — Graphical Models
🐣 Hot Topic Early Bird — combinatorial optimization
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio
🧭 Keyword Pioneer — relational bayesian network

Authors

Denis Deratani Mauá , Fabio Gagliardi Cozman

Topics

Machine Learning > Optimization & Theory > Bayesian Inference Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Theory Machine Learning > Bayesian & Probabilistic > Probabilistic Modeling Machine Learning > Core Methods > Graphical Models

Keywords

combinatorial optimization probabilistic modeling probabilistic inference marginal inference complexity analysis bayesian network inference complexity relational bayesian network combination function
Download PDF

Related papers

Compressing Bayes Net CPTs with Persistent Leaky Causes 2016
Bayesian Matrix Factorization with Non-Random Missing Data using Informative Gaussian Process Priors and Soft Evidences 2016
Statistical Matching of Discrete Data by Bayesian Networks 2016
An Exact Approach to Learning Probabilistic Relational Model 2016
Identifying the irreducible disjoint factors of a multivariate probability distribution 2016