Bayesian networks have become one of the major models for statistical
inference. We study the question whether the decisions computed by a
Bayesian network can be represented within a low-dimensional inner product
space. We focus on two-label classification tasks over the Boolean domain.
As the main results, we establish upper and lower bounds on the dimension of
the "natural" inner product space for Bayesian networks with an explicitly
given (full or reduced) parameter collection. In particular, these bounds
are tight up to a factor of 2. For some nontrivial cases, we even
determinene the exact values of this dimension. Further, we consider a
variant of the logistic autoregressive Bayesian network and show that every
sufficiently expressive inner product space must have dimension at least
2^Ω(n), where n is the number of network nodes. As a major
technical contribution, this work reveals combinatorial and algebraic
structures within Bayesian networks such that known methods for the
derivation of lower bounds on the dimension of inner product spaces can be
brought into play.
