Bayesian Networks and Inner Product Spaces
Abstract
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.
Cite
Text
Nakamura et al. "Bayesian Networks and Inner Product Spaces." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_36Markdown
[Nakamura et al. "Bayesian Networks and Inner Product Spaces." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/nakamura2004colt-bayesian/) doi:10.1007/978-3-540-27819-1_36BibTeX
@inproceedings{nakamura2004colt-bayesian,
title = {{Bayesian Networks and Inner Product Spaces}},
author = {Nakamura, Atsuyoshi and Schmitt, Michael and Schmitt, Niels and Simon, Hans Ulrich},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2004},
pages = {518-533},
doi = {10.1007/978-3-540-27819-1_36},
url = {https://mlanthology.org/colt/2004/nakamura2004colt-bayesian/}
}