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 researchers were skeptical about statistical AI because probability seemed to rely on too many numbers and did not deal with the complexities of a world of individuals and things. But the use of probabilistic graphical models, exploiting probabilistic independencies, has revolutionized AI. The independencies specified in such models are natural, provide structure that enables efficient reasoning and learning, and allow one to model complex domains. Many AI problems arising in a wide variety of fields such as machine learning, diagnosis, network communication, computer vision, and robotics have been elegantly encoded and solved using probabilistic graphical models.
Meanwhile, there have also been considerable advances in logical AI, where agents reason about the structure of complex worlds. One aspect of this is in the semantic web and the use of ontologies to represent meaning in diverse fields from medicine to geology to the products in a catalogue. Generally, there is an explosive growth in the amount of heterogeneous data that is being collected in the business and scientific world. Example domains include biology and chemistry, transportation systems, communication networks, social networks, and robotics. Like people, intelligent agents should be able to deal with many different types of knowledge, requiring structured representations that give a more informative view of the AI task at hand.
Moreover, reasoning about individuals and relations is all about reasoning with regularities and symmetries. We lump individuals into categories or classes (such as “person” or “course”) because the individuals in a category share common properties—e.g., there are statements that are true about all living people such as they breath, they have skin and two biological parents. Similarly for relations, there is something in common between Sam being advised by Professor Smith and Chris being advised by Professor Johnson; there are statements about publishing papers, working on a thesis and projects that are common among the “advised by” relationships. We would like to make predictions about two people about whom all we know may be only their advisory relationships. It is these commonalities and regularities that enable language to describe the world. Reasoning about regularities and symmetries is the foundation of logics built on the predicate calculus, which allows statements about all individuals.
Figure 1.1: Statistical Relational Artificial Intelligence (StarAI) combines probability, logic, and learning and covers major parts of the AI spectrum.
Thus, to deal with the real world we actually need to exploit uncertainty, independencies, and symmetries and tackle a long standing goal of AI, namely unifying first-order logic—capturing regularities and symmetries—and probability—capturing uncertainty and independence. Predicate logic and probability theory are not in conflict with each other, they are synergistic. Both extend propositional logic, one by adding relations, individuals, and quantified variables, the other by allowing for measures over possible worlds and conditional queries. This may explain why there has been a considerable body of research in combining both of them over the last 25 years, evolving into what has come to be called Statistical Relational Artificial Intelligence (StarAI); see also Fig. 1.1:
the study and design of intelligent agents that act in worlds composed of individuals (objects, things), where there can
