David Poole - An Introduction to Lifted Probabilistic Inference

1. Chapter 1
2. Chapter 2
3. Chapter 3
4. Chapter 4
5. Chapter 5
6. Chapter 6
7. Chapter 7
8. Chapter 8
9. Chapter 9
10. Chapter 10
11. Chapter 11
12. Chapter 12
13. Chapter 13
14. Chapter 14
15. Chapter 15
16. Chapter 16

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

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/

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

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.