AI Seminar - Polynomial-time probabilistic reasoning with partial observations via implicit learning in probability logics

Title: Polynomial-time probabilistic reasoning with partial observations via implicit learning in probability logics

Abstract: Standard approaches to probabilistic reasoning require that one possesses an explicit model of the distribution in question. But, the empirical learning of models of probability distributions from partial observations is a problem for which efficient algorithms are generally not known. In this work we consider the use of bounded-degree fragments of the "sum-of-squares" logic as a probability logic. Prior work has shown that we can decide refutability for such fragments in polynomial-time. We propose to use such fragments to decide queries about whether a given probability distribution satisfies a given system of constraints and bounds on expected values. We show that in answering such queries, such constraints and bounds can be implicitly learned from partial observations in polynomial-time as well. It is known that this logic is capable of deriving many bounds that are useful in probabilistic analysis. We observe that it furthermore captures key polynomial-time fragments of resolution. Thus, these fragments are also quite expressive.

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, and is also interested in Theoretical Computer Science more broadly construed. He is the author of "Universal Semantic Communication," concerning methods for communication without a common language, published by Springer in 2011. He was the recipient of a 2015 AFOSR Young Investigator Award.