Complexity of concept classes induced by discrete Markov networks and Bayesian networks

作者：

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.

摘要

•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.

论文关键词：Bayesian networks,Classification,Markov networks,Toric ideal,Vapnik–Chervonenkis dimension

论文评审过程：Received 1 January 2017, Revised 5 March 2018, Accepted 26 April 2018, Available online 27 April 2018, Version of Record 15 June 2018.

论文官网地址：https://doi.org/10.1016/j.patcog.2018.04.026