7.1.2 Partially Observed Data with Known Structure
7.1.3 Unknown Structure and Parameters
7.2 Logical and Relational Learning
7.2.1 Two Learning Settings
7.2.2 The Search Space
7.2.3 Two Algorithms: Clausal Discovery and FOIL
7.2.4 From Propositional to First-Order Logic
7.2.5 An ILP Example
8 Learning Probabilistic Relational Models
8.1 Learning as Inference
8.2 The Learning Problem
8.2.1 The Data Used
8.3 Parameter Learning of Relational Models
8.3.1 Fully Observable Data
8.3.2 Partially Observed Data
8.3.3 Learning with Latent Variables
8.4 Structure Learning of Probabilistic Relational Models
8.4.1 A Vanilla Structure Learning Approach
8.4.2 Probabilistic Relational Models
8.4.3 Boosting
8.5 Bayesian Learning
9 Beyond Basic Probabilistic Inference and Learning
9.1 Lifted Satisfiability
9.2 Acting in Noisy Relational Worlds
9.3 Relational Optimization
Preface
This book aims to provide an introduction that can help newcomers to the field to get started, to understand the state-of-the-art and the current challenges and be ready for future advances. It reviews the foundations of StarAI, motivates the issues, justifies some choices that have been made, and provides some open problems. Laying bare the foundations will hopefully inspire others to join us in exploring the frontiers and the yet unexplored areas.
The target audience for this book consists of advanced undergraduate and graduate students and also researchers and practitioners who want to get an overview of the basics and the state-of-the-art in StarAI. To this aim, Part I starts with providing the necessary background in probability and logic. We then discuss the representations of relational probability models and the underlying issues. Afterward, we focus first on inference, in Part II, and then on learning, in Part III. Finally, we touch upon relational tasks that go beyond the basic probabilistic inference and learning tasks as well as some open issues.
Researchers who are already working on StarAI—we apologize to anyone whose work we are accidentally not citing—may enjoy reading about parts of StarAI they are less familiar with.
We are grateful to all the people who contributed to the development of statistical relational learning and statistical relational AI. This book is made possible by you.
We also thank the reviewers for their valuable feedback and our co-authors, who accompanied us on our StarAI adventures, such as Laura Antanas, Udi Apsel, Babak Ahmadi, Hendrik Blockeel, Wolfram Burgard, Maurice Bruynooghe, David Buchman, Hung H. Bui, Peter Carbonetto, Alexandru Cocora, Fabrizio Costa, Michael Chiang, Walter Daelemans, Jesse Davis, Nando de Freitas, Kurt De Grave, Tinne De Laet, Bart Demoen, Kurt Driessens, Saso Dzeroski, Thomas G. Dietterich, Adam Edwards, Alan Fern, Daan Fierens, Paolo Frasconi, Roman Garnett, Amir Globerson, Bernd Gutmann, Martin Grohe, Fabian Hadiji, McElory Hoffmann, Manfred Jaeger, Gerda Janssens, Thorsten Joachims, Saket Joshi, Leslie Kaelbling, Andreas Karwath, Arzoo Katiyar, Seyed M. Kazemi, Angelika Kimmig, Jacek Kisynski, Tushar Khot, Stefan Kramer, Gautam Kunapuli, Chia-Li Kuo, Tobias Lang, Niels Landwehr, Daniel Lowd, Catherine A. McCarty, Theofrastos Mantadelis, Wannes Meert, Brian Milch, Martin Mladenov, Bogdan Moldovan, Roser Morante, Plinio Moreno, Marion Neumann, Davide Nitti, Phillip Odom, Jose Oramas, David Page, Andrea Passerini, Rui Pimentel de Figueiredo, Christian Plagemann, Tapani Raiko, Christopher Re, Kate Revoredo, Achim Rettinger, Ricardo Rocha, Scott Sanner, Vitor Santos Costa, Jose Santos-Victor, Erkal Selman, Rita Sharma, Jude W. Shavlik, Prasad Tadepalli, Nima Taghipour, Ingo Thon, Hannu Toivonen, Pavel Tokmakov, Sunna Torge, Marc Toussaint, Volker Tresp, Tinne Tuytelaars, Vincent Van Asch, Guy Van den Broeck, Martijn van Otterlo, Joost Vennekens, Jonas Vlasselaer, Zhao Xu, Shuo Yang, and Luke Zettlemoyer. Thanks for all the encouragement and fun! Thanks to the StaRAI lab at Indiana for proofreading the book.
Last but not least, we also thank our families and friends for their patience and support. Thanks!
LDR and KK thank the European Commission for support of the project FP7-248258-First-MM. KK further thanks Fraunhofer Society, ATTRACT Fellowship “STREAM”, the German Science Foundation, DFG KE 1686/2-1, as part of the DFG Priority Programme 1527, and the German-Israeli Foundation for Scientific Research and Development, GIF 1180/2011. SN thanks Army Research Office (ARO) grant number W911NF-13-1-0432 under the Young Investigator Program and the National Science Foundation grant no. IIS-1343940. LDR thanks the Research Foundation Flanders, and the KULeuven BOF fund for their support. DP thanks the Natural Sciences and Engineering Research Council of Canada (NSERC) for ongoing support.
Luc De Raedt, Leuven, Belgium
Kristian Kersting, Dortmund, Germany
Sriraam Natarajan, Bloomington, USA
David Poole, Vancouver, Canada
February 2016
CHAPTER 1
Motivation
There are good arguments that an intelligent agent that makes decisions about how to act in a complex world needs to model its uncertainty; it cannot just act pretending that it knows what is true. An agent also needs to reason about individuals (objects, entities, things) and about relations among the individuals.
These aspects have often been studied separately, with models for uncertainty often defined in terms of features and random variables, ignoring relational structure, and with rich (logical) languages for reasoning about relations that ignore uncertainty. This book studies the integration of the approaches to reasoning about uncertainty and reasoning about individuals and relations.
1.1 UNCERTAINTY IN COMPLEX WORLDS
Over the last 30 years, Artificial Intelligence (AI) has evolved from being skeptical, even hostile, to the use of probability to embracing probability. Initially, many