Learning Markov logic network structure via hypergraph lifting

ABSTRACT

Markov logic networks (MLNs) combine logic and probability by attaching weights to first-order clauses, and viewing these as templates for features of Markov networks. Learning MLN structure from a relational database involves learning the clauses and weights. The state-of-the-art MLN structure learners all involve some element of greedily generating candidate clauses, and are susceptible to local optima. To address this problem, we present an approach that directly utilizes the data in constructing candidates. A relational database can be viewed as a hypergraph with constants as nodes and relations as hyperedges. We find paths of true ground atoms in the hypergraph that are connected via their arguments. To make this tractable (there are exponentially many paths in the hypergraph), we lift the hypergraph by jointly clustering the constants to form higherlevel concepts, and find paths in it. We variabilize the ground atoms in each path, and use them to form clauses, which are evaluated using a pseudo-likelihood measure. In our experiments on three real-world datasets, we find that our algorithm outperforms the state-of-the-art approaches.

REFERENCES

• 1: Marenglen Biba , Stefano Ferilli , Floriana Esposito, Discriminative Structure Learning of Markov Logic Networks, Proceedings of the 18th international conference on Inductive Logic Programming, September 10-12, 2008, Prague, Czech Republic [doi>10.1007/978-3-540-85928-4_9]
• 2: Biba, M., Ferilli, S., & Esposito, F. (2008b). Structure learning of Markov logic networks through iterated local search. 18th Euro. Conf. on Art. Intel. (pp. 361--365).
• 3: Mark Craven , Seán Slattery, Relational learning with statistical predicate invention: better models for hypertext, Machine Learning, v.43 n.1/2, p.97-119, April/May 2001 [doi>10.1023/A:1007676901476]
• 4: Michael R. Genesereth , Nils J. Nilsson, Logical foundations of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 5: Lise Getoor , Ben Taskar, Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning), The MIT Press, 2007
• 6: Tuyen N. Huynh , Raymond J. Mooney, Discriminative structure and parameter learning for Markov logic networks, Proceedings of the 25th international conference on Machine learning, p.416-423, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390209]
• 7: Stanley Kok , Pedro Domingos, Learning the structure of Markov logic networks, Proceedings of the 22nd international conference on Machine learning, p.441-448, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102407]
• 8: Stanley Kok , Pedro Domingos, Statistical predicate invention, Proceedings of the 24th international conference on Machine learning, p.433-440, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273551]
• 9: Stanley Kok , Pedro Domingos, Extracting Semantic Networks from Text Via Relational Clustering, Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases - Part I, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87479-9_59]
• 10: Kok, S., Sumner, M., Richardson, M., Singla, P., Poon, H., Lowd, D., Wang, J., & Domingos, P. (2009). The Alchemy system for statistical relational AI (Technical Report). Dept. of Comp. Sci. & Eng., Univ. of Washington, Seattle, WA.
• 11: Lilyana Mihalkova , Raymond J. Mooney, Bottom-up learning of Markov logic network structure, Proceedings of the 24th international conference on Machine learning, p.625-632, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273575]
• 12: Muggleton, S., & Buntine, W. (1988). Machine invention of first-order predicates by inverting resolution. 5th Int. Conf. on Mach. Learn. (pp. 339--352).
• 13: Muggleton, S., & Feng, C. (1992). Efficient induction in logic programs. In S. Muggleton (Ed.), Inductive logic programming, 281--298.
• 14: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 15: Poon, H., & Domingos, P. (2006). Sound and efficient inference with probabilistic and deterministic dependencies. 21st Nat. Conf. on Art. Intel. (pp. 458--463).
• 16: Alexandrin Popescul , Lyle H. Ungar, Cluster-based concept invention for statistical relational learning, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014137]
• 17: Richards, B. L., & Mooney, R. J. (1992). Learning relations by pathfinding. 10th Nat. Conf. on Art. Intel. (pp. 50--55).
• 18: Matthew Richardson , Pedro Domingos, Markov logic networks, Machine Learning, v.62 n.1-2, p.107-136, February 2006 [doi>10.1007/s10994-006-5833-1]
• 19: Parag Singla , Pedro Domingos, Entity Resolution with Markov Logic, Proceedings of the Sixth International Conference on Data Mining, p.572-582, December 18-22, 2006 [doi>10.1109/ICDM.2006.65]
• 20: Singla, P., & Domingos, P. (2008). Lifted first-order belief propagation. 23th AAAI Conf. on Art. Intel. (pp. 1094--1099).

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Hypergraphs
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Markov processes

General Terms:
Algorithms, Design, Theory