Analysis of Markov Boundary Induction in Bayesian Networks: A New View From Matroid Theory

Article type: Research Article

Authors: Feng, Dingcheng | Chen, Feng | Xu, Wenli

Affiliations: National Laboratory for Information Science and Technology, Tsinghua University, Beijing, 100084, China. {fdc08,chenfeng,xuwl}@tsinghua.edu.cn

Note: [] Address for correspondence: Department of Automation, Tsinghua University, Beijing 100084, China

Abstract: Learning Markov boundaries from data without having to learn a Bayesian network first can be viewed as a feature subset selection problem and has received much attention due to its significance in the wide applications of AI techniques. Popular constraint based methods suffer from high computational complexity and are usually unstable in spaces of high dimensionality. We propose a new perspective from matroid theory towards the discovery of Markov boundaries of random variable in the domain, and develop a learning algorithm which guarantees to recover the true Markov boundaries by a greedy learning algorithm. Then we use the precision matrix of the original distribution as a measure of independence to make our algorithm feasible in large scale problems, which is essentially an approximation of the probabilistic relations with Gaussians and can find possible variables in Markov boundaries with low computational complexity. Experimental results on standard Bayesian networks show that our analysis and approximation can efficiently and accurately identify Markov boundaries in complex networks from data.

Keywords: Markov boundary, conditional independence, matroid

DOI: 10.3233/FI-2011-409

Journal: Fundamenta Informaticae, vol. 107, no. 4, pp. 415-434, 2011