Markov networks and Bayesian networks are two popular models for classification. Vapnik-Chervonenkis dimension and Euclidean dimension are two measures of complexity of a class of functions. In this paper, we show tha...
详细信息
Markov networks and Bayesian networks are two popular models for classification. Vapnik-Chervonenkis dimension and Euclidean dimension are two measures of complexity of a class of functions. In this paper, we show that these two dimensional values of the concept class induced by a discrete Markov network are identical, and the value equals dimension of the toric ideal corresponding to this Markov network as long as the toric ideal is nontrivial. Furthermore, for a general Bayesian network, we show that dimension of the corresponding toric ideal offers an upper bound of Euclidean dimension.
暂无评论