Complexity of concept classes induced by discrete Markov networks and Bayesian networks. (October 2018)

• Record Type: Journal Article
• Authors: Li, Benchong; Yang, Youlong
• Is Part Of: Pattern recognition. Volume 82(2018:Oct.)
• Page Start: 31
• Page End: 37
• Publication Date: 2018-10
• Subjects: Bayesian networks -- Classification -- Markov networks -- Toric ideal -- Vapnik–Chervonenkis dimension; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2018.04.026
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: We show that VC dimension, Euclidean dimension and dimension of the toric ideal corresponding to a nontrivial discrete MN are identical. One can compute VC dimension of the concept class induced by a discrete MN in terms of a computer algebra system directly based on our results. For a general BN, we show that dimension of the corresponding toric ideal offers an upper bound of Euclidean dimension. Abstract: 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, which can be used to measure classification capability of classifiers. One can use Vapnik–Chervonenkis dimension of the class of functions associated with a classifier to construct an estimate of its generalization error. In this paper, we study Vapnik–Chervonenkis dimension and Euclidean dimension of concept classes induced by discrete Markov networks and Bayesian networks. 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. Based on this result, one can compute the dimensional value in terms of a computer algebra system directly. Furthermore, for a general Bayesian network, we show that dimension of the corresponding toric ideal offers an upper bound of Euclidean dimension. In addition, we illustrate how to use Vapnik–Chervonenkis dimension to estimate generalization error in binary classification.