Abstract: We considered the lower bound of VC (Vapnik-Chervonenkis) dimension for concept classes induced by general Bayesian networks where each random variable took any finite values. By analyzing the relationship between the number of parameters that could be freely set in a network and the corresponding VC dimension, we proved that adding 1 to the number of parameters that could be freely set in any discrete non-full Bayesian network was a lower bound of corresponding VC dimension.

Key words: Bayesian network, concept classes, discrete random variable, VC (Vapnik-Chervonenkis) dimension