Intelligent Autonomous Systems

Probabilistic Logic for Multi-Source Knowledge Bases

1/2 Day Tutorial

June 11, 2018

Baden-Baden   Germany

Instructor:Thomas C. Henderson, University of Utah

Overview of Course

Abstract: Given the uncertainty associated with statements about the world, or with sensor data, or hypothesis formation in general, it is important to be able to represent such uncertainty appropriately for each source of information, and to be able to combine those disparate types of uncertainty in a consistent manner. For example, sensor data may have associated Gaussian or other types of noise models, while computational processes may have algorithmic uncertainty due to truncation errors, round-off errors, etc. Logical sentences have commonly been used to represent knowledge, and it is useful to associate an uncertainty with such sentences. Here we address the problem of finding a suitable representation for uncertainty associated with logical sentences. Although several approaches have been proposed in the past, they generally have some significant drawbacks. Usually, these have to do with the computational complexity of the semantics of the sentences (i.e., finding the set of consistent truth assignments is exponential in the number of sentences). In this tutorial, a thorough discussion of the creation and use of probabilistic knowledge bases will be presented. Starting with a definition of the Boolean Satisfiability problem (SAT) where each conjunct in a Conjunctive Normal Form Boolean formula has 0-1 semantics, to the Probabilistic SAT problem (PSAT) where each conjunct is assigned a probability in the range [0,1], methods to define and discover a consistent probabilistic assignment will be discussed. This begins with a review of methods for augmenting propositional calculus with probabilities; i.e., given a set of sentences, S, each with a known probability, then the problem is to determine the probability of a query sentence that is a formula of literals appearing in S. First, we examine Nilsson's solution based on the semantic models of the sentences; we describe two different approaches to solving the problem as posed: (1) using a linear solver, and (2) geometrically finding the intersection of a line with the probability convex hull. Nilsson's approach provides lower and upper bounds on the solution. We then describe a new approach which finds probabilities for the atoms found in the sentences, and then uses these probabilities to compute the probability of the query sentence. This alternative approach avoids the computation of the semantic models, and provides a solution for the probability of a query given a probabilistic knowledge base. Basically, this is done by exploiting the probability of a disjunctive clause, and developing a set of nonlinear equations from the sentences and their probabilities, and then solving those equations (where the number of equations is equal to the number of sentences). Finally, we describe how this probability representation method captures logical argumentation methods in the probabilistic computation.

• Link to Tutorial Description