|
In connection with two-label classification tasks over the Boolean
domain, we consider the possibility to combine the key advantages
of Bayesian networks and of kernel-based learning systems.
This leads us to the basic question whether the class of decision
functions induced by a given Bayesian network can be represented
within a low-dimensional inner product space. For Bayesian networks
with an explicitly given (full or reduced) parameter collection, we
show that the ``natural'' inner product space has the smallest
possible dimension up to factor $2$ (even up to an additive term $1$
in many cases). For a slight modification of the so-called logistic
autoregressive Bayesian network with $n$ nodes, we show that every
sufficiently expressive inner product space has dimension at least
$2^{n/4}$. The main technical contribution of our work consists
in uncovering combinatorial and algebraic structures within Bayesian
networks such that known techniques for proving lower bounds on the
dimension of inner product spaces can be brought into play.
|
