AAAI 2018 Tutorial: Integrating Learning Into Reasoning

AAAI 2018 Tutorial

Integrating Learning Into Reasoning

Brendan Juba
Washington Univ. St. Louis
Loizos Michael
Open University of Cyprus


The tutorial is aimed at researchers in KRR who are interested in how to best use machine learning to generate knowledge bases that contain knowledge that is  hard to express by hand. Machine learning has been very successful at some tasks of this kind, and in many cases there is currently no alternative. The tentative nature of learned knowledge requires a semantics that is less strict than classical logics, and this tutorial will introduce participants to PAC-Semantics, a particularly simple suitable choice. In particular, in this formal framework, there are quantifiable benefits to integrating the learning and reasoning processes. We will explain what these benefits are, and illustrate some simple techniques for such integrated learning and reasoning and their analysis. Participants should come away from the tutorial with the ability to establish that an algorithm’s output is sound in a PAC sense, using standard arguments based on bounds on representation size and “concentration of measure” from independent examples.

In addition, PAC-Semantics and these integrated learning and reasoning methods offer some new perspectives on classical issues in KRR, such as nonmonotonic reasoning, the qualification problem, and elaboration tolerance. The framework also naturally yields a new formulation of abductive inference. We will explain these connections, but also highlight the issues that we believe are not addressed and still have substantial scope for interesting KRR work. Participants should come away with an appreciation for how features such as error tolerance in learning and conditional probability together give rise to nonmonotonic effects under the PAC-Semantics, as well as some interesting open questions in the area that they might be well positioned to address.

Download the slides for the tutorial (mirror 1).
Download the slides for the tutorial (mirror 2).

Presenters' Short Bio:

Brendan Juba is an Assistant Professor in the Department of Computer Science and Engineering at Washington University in St. Louis. His current research interests lie in theoretical approaches to Artificial Intelligence, founded on the theory of Algorithms and Computational Complexity. He is also interested in Theoretical Computer Science more broadly construed. Previously, Brendan worked as a postdoc under the supervision of Leslie Valiant, jointly affiliated with Harvard and MIT with the Center for Science of Information until the fall of 2012, and subsequently solely affiliated with Harvard through summer 2014. He completed his Ph.D. at MIT in 2010 under the supervision of Madhu Sudan, and his dissertation, "Universal Semantic Communication" was published by Springer in 2011. Brendan also holds a M.S. in Mathematical Sciences and B.S. in Computer Science from Carnegie Mellon University, both awarded in 2005. His work is currently supported by a 2015 AFOSR Young Investigator Award.

Loizos Michael is an Assistant Professor at Open University of Cyprus, where he founded and directs the Computational Cognition Lab, and also serves as the academic head of the cross-institutional M.Sc. Program in Cognitive Systems ( His research focuses on the development of formal computational models for cognitive processes associated with individual or collective intelligence, using techniques from computational learning theory, logic-based knowledge representation, and commonsense reasoning. Loizos received a B.Sc. in Computer Science with a minor degree in Mathematics from University of Cyprus, graduating top of the class of 2002, and receiving the Republic of Cyprus Presidential Award. He continued his education at Harvard University, where he received an M.Sc. and a Ph.D. in Computer Science in 2008, under the supervision of Leslie Valiant. Before joining Open University of Cyprus in 2009, he held a visiting faculty appointment at University of Cyprus. He served as the PC chair of the 15th European Conference on Logics in Artificial Intelligence (JELIA 2016), and he has been organizing the workshop series on Cognitive Knowledge Acquisition and Applications ( since 2015.