Scalable pseudo-likelihood estimation in hybrid random fields

ABSTRACT

Learning probabilistic graphical models from high-dimensional datasets is a computationally challenging task. In many interesting applications, the domain dimensionality is such as to prevent state-of-the-art statistical learning techniques from delivering accurate models in reasonable time. This paper presents a hybrid random field model for pseudo-likelihood estimation in high-dimensional domains. A theoretical analysis proves that the class of pseudo-likelihood distributions representable by hybrid random fields strictly includes the class of joint probability distributions representable by Bayesian networks. In order to learn hybrid random fields from data, we develop the Markov Blanket Merging algorithm. Theoretical and experimental evidence shows that Markov Blanket Merging scales up very well to high-dimensional datasets. As compared to other widely used statistical learning techniques, Markov Blanket Merging delivers accurate results in a number of link prediction tasks, while achieving also significant improvements in terms of computational efficiency.

Our software implementation of the models investigated in this paper is publicly available at http://www.dii.unisi.it/~freno/. The same website also hosts the datasets used in this work that are not available elsewhere in the same preprocessing used for our experiments.

REFERENCES

• 1: J. Besag. Spatial Interaction and the Statistical Analysis of Lattice Systems. Journal of the Royal Statistical Society. Series B, 36:192--236, 1974.
• 2: J. Besag. Statistical Analysis of Non-Lattice Data. The Statistician, 24:179--195, 1975.
• 3: J. S. Breese, D. Heckerman, and C. M. Kadie. Empirical Analysis of Predictive Algorithms for Collaborative Filtering. In Proceedings of the Fourteenth Annual Conference on Uncertainty in Artificial Intelligence, pages 43--52, 1998.
• 4: Steven Carroll , Vladimir Pavlovic, Protein classification using probabilistic chain graphs and the Gene Ontology structure, Bioinformatics, v.22 n.15, p.1871-1878, August 2006 [doi>10.1093/bioinformatics/btl187]
• 5: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 6: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 7: N. Friedman and M. Goldszmidt. Learning Bayesian Networks with Local Structure. In Proceedings of the Twelfth Annual Conference on Uncertainty in Artificial Intelligence (UAI '96), pages 252--262. Morgan Kaufmann, 1996.
• 8: N. Friedman and D. Koller. Being Bayesian about Bayesian Network Structure:A Bayesian Approach to Structure Discovery in Bayesian Networks. Machine Learning, 50:95--125, 2003.
• 9: W. R. Gilks, S. Richardson, and D. Spiegelhalter. Markov Chain Monte Carlo in Practice. Chapman&Hall/CRC, 1996.
• 10: M. Gori and A. Pucci. ItemRank: A Random-Walk Based Scoring Algorithm for Recommender Engines. In 20th International Joint Conference on Artificial Intelligence (IJCAI07), pages 2766--2771, 2007.
• 11: 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
• 12: David Heckerman , Dan Geiger , David M. Chickering, Learning Bayesian Networks: The Combination of Knowledge and Statistical Data, Machine Learning, v.20 n.3, p.197-243, Sept. 1995 [doi>10.1023/A:1022623210503]
• 13: Kyu Baek Hwang , Jae Won Lee , Seung-Woo Chung , Byoung-Tak Zhang, Construction of Large-Scale Bayesian Networks by Local to Global Search, Proceedings of the 7th Pacific Rim International Conference on Artificial Intelligence: Trends in Artificial Intelligence, p.375-384, August 18-22, 2002
• 14: R. Kindermann and J. L. Snell. Markov Random Fields and Their Applications. American Mathematical Society, Providence (RI), 1980.
• 15: S. L. Lauritzen and N. Wermuth. Graphical Models for Associations between Variables, some of which are Qualitative and some Quantitative. The Annals of Statistics, 17:31--57, 1989.
• 16: D. C. Liu , J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming: Series A and B, v.45 n.3, p.503-528, Dec. 1989 [doi>10.1007/BF01589116]
• 17: Thomas M. Mitchell, Machine Learning, McGraw-Hill, Inc., New York, NY, 1997
• 18: K. Miyahara and M. J. Pazzani. Collaborative Filtering with the Simple Bayesian Classifier. In PRICAI, pages 679--689, 2000.
• 19: J. Moussouris. Gibbs and Markov Random Systems with Constraints. Journal of Statistical Physics, 10:11--33, 1974.
• 20: Richard E. Neapolitan, Learning Bayesian Networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 2003
• 21: S. Parise and M. Welling. Bayesian Model Scoring in Markov Random Fields. In Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems (NIPS), pages 1073--1080, 2006.
• 22: J Pearl, Evidential reasoning using stochastic simulation of causal models, Artificial Intelligence, v.32 n.2, p.245-257, May 1987 [doi>10.1016/0004-3702(87)90012-9]
• 23: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 24: J. Rissanen. Stochastic Complexity. Journal of the Royal Statistical Society. Series B, 49:223--239, 1987.
• 25: V. Robles , P. Larrañaga , E. Menasalvas , M. S. Pérez , V. Herves, Improvement of Naïve Bayes Collaborative Filtering Using Interval Estimation, Proceedings of the 2003 IEEE/WIC International Conference on Web Intelligence, p.168, October 13-17, 2003
• 26: G. Schwarz. Estimating the Dimension of a Model. The Annals of Statistics, 6:461--464, 1978.
• 27: P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. MIT Press, Cambridge (MA), second edition, 2001. Original work published 1993 by Springer-Verlag.
• 28: Ioannis Tsamardinos , Constantin F. Aliferis , Alexander Statnikov, Time and sample efficient discovery of Markov blankets and direct causal relations, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956838]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bayesian networks, hybrid random fields, markov random fields, modularity, scalability