On the properties of concept classes induced by multivalued Bayesian networks

The concept class CNCN induced by a Bayesian network NN 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 CNkCNk induced by a multivalued Bayesian network NkNk, where each node Xi of NkNk is a k-valued variable. We focus on the values of two dimensions: (i) the VC  -dimension of the concept class CNkCNk, denoted as VCdim(Nk)VCdim(Nk), and (ii) the minimum dimension of the inner product space into which CNkCNk can be embedded. We show that the values of these two dimensions are kn − 1 for fully connected k  -valued Bayesian networks NFk with n variables. For non-fully connected k  -valued Bayesian networks NkNk without V  -structure, we prove that the two dimensional values are (k-1)∑i=1nkmi+1, 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.