Markov logic networks (MLNs) are a popular statistical relational learning formalism that com-bine Markov networks with first-order logic. Un-fortunately, inference and maximum-likelihood learning with MLNs is highly intractable. For in-ference, this problem is addressed by lifted algo-rithms, which speed up inference by exploiting symmetries. State-of-the-art lifted algorithms give tractability guarantees for broad classes of MLNs and inference tasks. For learning, we showed in recent work how to use lifted inference techniques for efficient maximum-likelihood pa-rameter learning. In this paper, we propose the first lifted structure learning algorithm that guar-antees that the learned MLNs are liftable, and thus tractable for certain queries. Our work is among the first to apply the tractable learn-ing paradigm to statistical relational models. Moreover, it is the first structure learning al-gorithm that exactly optimizes the likelihood of the MLN. An empirical evaluation on three real-world datasets shows that our algorithm learns accurate models, both in terms of likelihood and prediction quality. Furthermore, our tractable learner outperforms intractable models on pre-diction tasks suggesting that liftable models are a powerful hypothesis space, which may be suf-ficient for many standard learning problems. 1.

@inproceedings{VHaarenLTPM14,
  author = "Van Haaren, Jan and Van den Broeck, Guy and Meert, Wannes and Davis, Jesse",
  title = "Tractable learning of liftable {M}arkov logic networks",
  booktitle = "Proceedings of the ICML-14 Workshop on Learning Tractable Probabilistic Models (LTPM)",
  location="Beijing, China",
  month = Jun,
  year = "2014",
  url = "http://starai.cs.ucla.edu/papers/VHaarenLTPM14.pdf",
  code = "https://github.com/UCLA-StarAI/Forclift",
  keywords   = {workshop}
}