VC dimension and inner product space induced by Bayesian networks Original Research Article

Bayesian networks are graphical tools used to represent a high-dimensional probability distribution. They are used frequently in machine learning and many applications such as medical science. This paper studies whether the concept classes induced by a Bayesian network can be embedded into a low-dimensional inner product space. We focus on two-label classification tasks over the Boolean domain. For full Bayesian networks and almost full Bayesian networks with n variables, we show that VC dimension and the minimum dimension of the inner product space induced by them are image. Also, for each Bayesian network image we show that image if the network image constructed from image by removing image satisfies either (i) image is a full Bayesian network with image variables, i is the number of parents of image, and image or (ii) image is an almost full Bayesian network, the set of all parents of image image and image. Our results in the paper are useful in evaluating the VC dimension and the minimum dimension of the inner product space of concept classes induced by other Bayesian networks.