On the properties of concept classes induced by multivalued Bayesian networks

The concept class image induced by a Bayesian network image can be embedded into some Euclidean inner product space. The Vapnik–Chervonenkis (VC)-dimension of the concept class and the minimum dimension of the inner product space are very important indicators for evaluating the classification capability of the Bayesian network. In this paper, we investigate the properties of the concept class image induced by a multivalued Bayesian network image, where each node Xi of image is a k-valued variable. We focus on the values of two dimensions: (i) the VC-dimension of the concept class image, denoted as image, and (ii) the minimum dimension of the inner product space into which image can be embedded. We show that the values of these two dimensions are kn − 1 for fully connected k-valued Bayesian networks image with n variables. For non-fully connected k-valued Bayesian networks image without V-structure, we prove that the two dimensional values are image, where mi denotes the number of parents for the ith variable. We also derive the upper and lower bounds on the minimum dimension of the inner product space induced by non-fully connected Bayesian networks.