The Representational Power of Discrete Bayesian Networks

One of the most important fundamental properties of Bayesian networks is the representational power, reflecting what kind of functions they can or cannot represent. In this paper, we establish an association between the structural complexity of Bayesian networks and their representational power. We use the maximum number of nodes' parents as the measure for the structural complexity of Bayesian networks, and the maximum XOR contained in a target function as the measure for the function complexity. A representational upper bound is established and proved. Roughly speaking, discrete Bayesian networks with each node having at most k parents cannot represent any function containing ( k +1)-XORs. Our theoretical results help us to gain a deeper understanding on the capacities and limitations of Bayesian networks. [abs] [pdf] [ps.gz] [ps]