The Representational Power of Discrete Bayesian Networks
Charles X. Ling, Huajie Zhang;
3(Dec):709-721, 2002.
Abstract
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]
