Proceedings

Efficient and Robust Independence-Based Markov Network Structure Discovery

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2431-2435.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

In this paper we introduce a novel algorithm for the induction of the Markov network structure of a domain from the outcome of conditional independence tests on data. Such algorithms work by successively restricting the set of possible structures until there is only a single structure consistent with the conditional independence tests executed. Existing independence-based algorithms have well-known shortcomings, such as rigidly ordering the sequence of tests they perform, resulting in potential inefficiencies in the number of tests required, and committing fully to the test outcomes, resulting in lack of robustness in case of unreliable tests. We address both problems through a Bayesian particle filtering approach, which uses a population of Markov network structures to maintain the posterior probability distribution over them, given the outcomes of the tests performed. Instead of a fixed ordering, our approach greedily selects, at each step, the optimally informative from a pool of candidate tests according to information gain. In addition, it maintains multiple candidate structures weighed by posterior probability, which makes it more robust to errors in the test outcomes. The result is an approximate algorithm (due to the use of particle filtering) that is useful in domains where independence tests are uncertain (such as applications where little data is available) or expensive (such as cases of very large data sets and/or distributed data).

  1. [Andrieu et al., 2003] C. Andrieu, N. de Freitas, A. Doucet, and M. Jordan. An introduction to MCMC for machine learning. Ma- chine Learning, 50:5-43, 2003.
  2. [Besag et al., 1991] J. Besag, J. York, and A. Mollie. Bayesian im- age restoration with two applications in spatial statistics. Annals of the Institute of Statistical Mathematics, 43:1-59, 1991.
  3. [Bromberg et al., 2006] F. Bromberg, D. Margaritis, and V. Honavar. Efficient Markov network structure discovery using independence tests. In SIAM International Conference on Data Mining, 2006.
  4. [D.J. Newman and Merz, 1998] C.L. Blake D.J. Newman, S. Het- tich and C.J. Merz. UCI repository of machine learning databases. 1998.
  5. [Geman and Geman, 1984] S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian relation of im- ages. PAMI, 6:721-741, 1984.
  6. [Heckerman, 1995] D. Heckerman. A tutorial on learning Bayesian networks. Technical Report MSR-TR-95-06, Microsoft Re- search, 1995.
  7. [Hofmann and Tresp, 1998] R. Hofmann and V. Tresp. Nonlinear Markov networks for continuous variables. In NIPS '98, vol- ume 10, pages 521-529, 1998.
  8. [Margaritis, 2005] D. Margaritis. Distribution-free learning of Bayesian network structure in continuous domains. In AAAI. AAAI Press, 2005.
  9. [Pearl, 1988] J. Pearl. Probabilistic Reasoning in Intelligent Sys- tems: Networks of Plausible Inference. Morgan Kaufmann Pub- lishers., 1988.
  10. [Shekhar et al., 2004] S. Shekhar, P. Zhang, Y. Huang, and R. Vat- savai. Trends in spatial data mining. chapter 19, pages 357-379. AAAI Press / MIT Press, 2004.
  11. [Spirtes et al., 2000] P. Spirtes, C. Glymour, and R. Scheines. Cau- sation, Prediction, and Search. Adaptive Computation and Ma- chine Learning Series. MIT Press, 2nd edition, 2000.
  12. [Srebro and Karger, 2001] N. Srebro and D. Karger. Learning Markov networks: Maximum bounded tree-width graphs. In ACM-SIAM Symposium on Discrete Algorithms, 2001.
  13. [Tong and Koller, 2001] S. Tong and D. Koller. Active learning for structure in Bayesian networks. In IJCAI, 2001. IJCAI

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards