Learning structurally consistent undirected probabilistic graphical models

ABSTRACT

In many real-world domains, undirected graphical models such as Markov random fields provide a more natural representation of the statistical dependency structure than directed graphical models. Unfortunately, structure learning of undirected graphs using likelihood-based scores remains difficult because of the intractability of computing the partition function. We describe a new Markov random field structure learning algorithm, motivated by canonical parameterization of Abbeel et al. We provide computational improvements on their parameterization by learning per-variable canonical factors, which makes our algorithm suitable for domains with hundreds of nodes. We compare our algorithm against several algorithms for learning undirected and directed models on simulated and real datasets from biology. Our algorithm frequently outperforms existing algorithms, producing higher-quality structures, suggesting that enforcing consistency during structure learning is beneficial for learning undirected graphs.

REFERENCES

• 1: Pieter Abbeel , Daphne Koller , Andrew Y. Ng, Learning Factor Graphs in Polynomial Time and Sample Complexity, The Journal of Machine Learning Research, 7, p.1743-1788, 12/1/2006
• 2: Aragon, A. D., Rodriguez, A. L., Meirelles, O. et al. (2008). Characterization of differentiated quiescent and nonquiescent cells in yeast stationary-phase cultures. Mol. Biol. Cell, E07-07-0666+.
• 3: Besag, J. (1977). Efficiency of pseudolikelihood estimation for simple gaussian fields. Biometrika, 64, 616--618.
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: Friedman, N., Nachman, I., & Pe'er, D. (1999). Learning bayesian network structure from massive datasets: The sparse candidate algorithm. Uncertainty in Artificial Intelligence (pp. 206--215).
• 6: David Heckerman , David Maxwell Chickering , Christopher Meek , Robert Rounthwaite , Carl Kadie, Dependency networks for inference, collaborative filtering, and data visualization, The Journal of Machine Learning Research, 1, p.49-75, 9/1/2001 [doi>10.1162/153244301753344614]
• 7: Reimar Hofmann , Volker Tresp, Nonlinear Markov networks for continuous variables, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.521-527, July 1998, Denver, Colorado, United States
• 8: Lauritzen, S. L. (1996). Graphical models. Oxford Statistical Science Series. New York, USA: Oxford University Press.
• 9: Lee, S.-I., Ganapathi, V., & Koller, D. (2007). Efficient structure learning of markov networks using l₁-regularization. Advances in Neural Information Processing Systems 19 (pp. 817--824). MIT Press.
• 10: Li, F., & Yang, Y. (2005). Using modified lasso regression to learn large undirected graphs in a probabilistic framework. American Association for Artificial Intelligence (pp. 801--806).
• 11: Margolin, A., Nemenman, I., Basso, K. et al. (2005). Aracne: An algorithm for the reconstruction of gene regulatory networks in a mammalian cellular context. BMC Bioinformatics, (Suppl 1): S7.
• 12: Paget, R. D. (1999). Nonparametric markov random field models for natural texture images. Doctoral dissertation, University of Queensland.
• 13: Sushmita Roy , Margaret Werner-Washburne , Terran Lane, A system for generating transcription regulatory networks with combinatorial control of transcription, Bioinformatics, v.24 n.10, p.1318-1320, May 2008 [doi>10.1093/bioinformatics/btn126]
• 14: Schmidt, M., Niculescu-Mizil, A., & Murphy, K. (2007). Learning graphical model structure using l1-regularization paths. 22nd international conference on Artificial Intelligence (pp. 1278--1283).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Markov processes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory