VE dimension induced by Bayesian networks over the boolean domain

In this paper, we focus on the concept classes \({\mathcal {C}}_{{\mathcal{N}}}\) induced by Bayesian networks. The relationship between two-dimensional values induced by these concept classes is studied, one of which is the VC-dimension of the concept class \({\mathcal {C}}_{\cal {N}},\) denoted as \(VCdim({\mathcal {N}}), \) and other is the smallest dimensional of Euclidean spaces into which \({\mathcal {C}}_{{\mathcal {N}}}\) can be embedded, denoted as \(Edim({\mathcal {N}}). \) As a main result, we show that the two-dimensional values are equal for the Bayesian networks with n ≤ 4 variables, called the VE-dimension for that Bayesian networks.