On the properties of concept classes induced by multivalued Bayesian networks
The concept class C-N induced by a Bayesian network N 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 C-Ni induced by a multivalued Bayesian network N-k, where each node X-i of N-k is a k-valued variable. We focus on the values of two dimensions: (i) the VC-dimension of the concept class denoted as VCdim(N-k), and (ii) the minimum dimension of the inner product space into which C-Nk can be embedded. We show that the values of these two dimensions are k(n) - 1 for fully connected k-valued Bayesian networks N-F(k) with n variables. For non-fully connected k-valued Bayesian networks N-k without V-structure, we prove that the two dimensional values are (k - 1)Sigma(n)(i-1) k(mi) + 1, where m(i) denotes the number of parents for the i(th) 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. (C) 2011 Elsevier Inc. All rights reserved.
concept classes multivalued bayesian networks bayesian networks inner product space classification vc dimension