|
Bayesian networks have become one of the major models used 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 main results we establish upper and lower bounds on the dimension of the
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 of Bayesian networks we even
determine the exact values of this dimension. We further consider logistic
autoregressive Bayesian networks and show that every sufficiently expressive
inner product space must have dimension at least $\Omega(n^2)$, where $n$ is
the number of network nodes. We also derive the bound $2^{\Omega(n)}$ for an
artificial variant of this network, thereby demonstrating the limits of our
approach and raising an interesting open question. 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.
|
