离散Bayes网诱导的概念类VC维数的下界

Lower Bound of VC Dimension for Concept Classes Induced by Discrete Bayesian Networks

考虑一般Bayes网中每个随机变量取任意有限值时,其诱导的概念类VC(Vapnik-Chervonenkis)维数的下界.通过分析网络中可自由设定的参数个数与相应VC维数的关系,证明任意离散非完全Bayes网的可自由设定参数个数加1后,是相应VC维数的一个下界.

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.