Contents
List of figures
- Chapter 1
- Chapter 2
- Chapter 3
- Chapter 4
- Chapter 5
- Chapter 6
- Chapter 7
- Chapter 8
- Chapter 9
- Chapter 10
- Chapter 11
- Chapter 12
- Chapter 13
- Chapter 14
- Chapter 15
- Chapter 16
Guide
2021 Massachusetts Institute of Technology
All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher.
This book was set in Times-Roman by the editors.
Library of Congress Cataloging-in-Publication Data
Names: Broeck, Guy van den, editor. | Kersting, Kristian, editor. | Natarajan, Sriraam, editor. | Poole, David, editor.
Title: An introduction to lifted probabilistic inference / edited by Guy van den Broeck, Kristian Kersting, Sriraam Natarajan, and David Poole.
Description: Cambridge, Massachusetts : The MIT Press, [2021] | Series: Neural information processing series | Includes bibliographical references and index.
Identifiers: LCCN 2020040684 | ISBN 9780262542593 (paperback)
Subjects: LCSH: Probabilities. | Artificial intelligence. | Heuristic algorithms.
Classification: LCC QA273 .I563 2021 | DDC 519.2dc23
LC record available at https://lccn.loc.gov/2020040684
10987654321
d_r0
List of Figures
Contributors
Babak Ahmadi
C-IAM GmbH, Cologne, Germany
Hendrik Blockeel
Department of Computer Science, KU Leuven, Belgium
https://people.cs.kuleuven.be/~hendrik.blockeel/
Hung Bui
VinAI Research, Menlo Park, USA
https://sites.google.com/site/buihhung/
Yuqiao Chen
Department of Computer Science, University of Texas at Dallas, USA
https://personal.utdallas.edu/~yuqiao.chen/
Arthur Choi
Department of Computer Science, University of Los Angeles, USA
http://web.cs.ucla.edu/~aychoi/
Jaesik Choi
Graduate School of Artificial Intelligence, KAIST, Republic of Korea
http://sailab.kaist.ac.kr/jaesik/
Adnan Darwiche
Department of Computer Science, University of Los Angeles, USA
http://web.cs.ucla.edu/~darwiche/
Jesse Davis
Department of Computer Science, KU Leuven, Belgium
https://people.cs.kuleuven.be/~jesse/
Rodrigo de Salvo Braz
SRI International, Menlo Park, USA
http://www.ai.sri.com/~braz/
Pedro Domingos
Department of Computer Science, University of Washington, Seattle, USA
https://homes.cs.washington.edu/~pedrod/
Daan Fierens
TenForce, Leuven, Belgium
https://sites.google.com/site/fierensdaan/home
Martin Grohe
Department of Computer Science, RWTH Aachen University, Aachen, Germany
https://www.lics.rwth-aachen.de/go/id/nwej/?lidx=1
Fabian Hadiji
Geodle.io Cologne, Germany
Seyed Mehran Kazemi
Borealis AI, Montreal, Canada
https://mehran-k.github.io/
Roni Khardon
Department of Computer Science, Indiana University, Bloomington, USA
http://homes.sice.indiana.edu/rkhardon/
Angelika Kimmig
Department of Computer Science, Cardiff University, Cardiff, England
http://users.cs.cf.ac.uk/KimmigA/
Jacek Kisynski
Visier Inc, Vancouver, Canada
Kristian Kersting
Computer Science Department, TU Darmstadt, Germany
https://ml-research.github.io/people/kkersting/index.html
Daniel Lowd
Department of Computer Science, University of Oregon, Eugene, USA
https://ix.cs.uoregon.edu/~lowd/
Wannes Meert
Department of Computer Science, KU Leuven, Belgium
https://people.cs.kuleuven.be/~wannes.meert/
Martin Mladenov
Google Research, Mountainview, USA
Raymond Mooney
Department of Computer Science, University of Texas at Austin, USA
https://www.cs.utexas.edu/~mooney/
Sriraam Natarajan
Department of Computer Science, University of Texas at Dallas, USA
https://personal.utdallas.edu/~sriraam.natarajan/
Mathias Niepert
NEC Labs Europe, Heidelberg, Germany
http://www.matlog.net/
David Poole
Department of Computer Science, University of British Columbia, Vancouver, Canada
https://www.cs.ubc.ca/~poole/
Scott Sanner
Department of Mechanical and Industrial Engineering, University of Toronto, Canada
https://d3m.mie.utoronto.ca/
Pascal Schweitzer
Department of Computer Science, TU Kaiserslautern, Germany
http://alg.cs.uni-kl.de/en/team/schweitzer/
Nima Taghipour
Trivago, Amsterdam, Netherlands
Guy Van den Broeck
Department of Computer Science, University of Los Angeles, USA
http://web.cs.ucla.edu/~guyvdb/
Preface
We are grateful to the entire Statistical Relational AI community for their contribution to lifted learning and inference. This book will not be possible without you. We thank the students of the statistical relational AI labs of the four authors for their help in proof-reading the book. Special thanks to Nandini Ramanan for her help in collating all the references. Thanks to Yuqial Chen, Devendra Dhami, Harsha Kokel, Srijita Das, Navdeep Kaur, Alexander Hayes, Athresh Karanam, Nandini Ramanan, Mike Skinner and Siwen Yan for proof-reading the chapters in the book.
We also thank our families and friends for their support.
Guy, Kristian, Sriraam and David
April 2020
I
OVERVIEW
Statistical Relational AI: Representation, Inference and Learning
Guy Van den Broeck, Kristian Kersting, Sriraam Natarajan, and David Poole
Abstract. Artificial intelligence (AI) is about creating agents that act in environments (Russell and Norvig, 2010; Poole and Mackworth, 2017). Acting in an environment where there is any partial observability or stochasticity is gambling on the outcomes of actions. Probability and utility are the calculi for gambling; there are numerous results that show that an agent that does not use probability will lose to one that does. The real world is complicated; non-trivial agents need to reason about individuals (things, objects, entities), properties of the individuals and relationships among individuals. Statistical relational AI (StaRAI) (De Raedt et al., 2016) is the field that studies the integration of reasoning under uncertainty and reasoning about individuals and relations. The representations used are often called relational probabilistic models.
The integration of uncertainty and relations can be approached from a number of different directions:
- First-order logic extends propositional logic with constants and variables that quantify over individuals, and relations among the individuals. Starting with first-order logic, we can add probabilities and utilities to allow for uncertainty about the truth of propositions, as well as the identity and existence of individuals. For example, probabilistic logic programs (Poole, 1993; Sato and Kameya, 1997; De Raedt et al., 2007) can be seen as adding probabilistic inputs to logic programs, which let us define probabilistic models about relations in a Turing-complete language that naturally represents relations.