## Inner Product Spaces for Bayesian Networks

** Atsuyoshi Nakamura, Michael Schmitt, Niels Schmitt, Hans Ulrich Simon**; 6(47):1383−1403, 2005.

### Abstract

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 Ω(*n ^{2}*), where

*n*is the number of network nodes. We also derive the bound

*2*

^{Ω(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.

© JMLR 2005. (edit, beta) |