Brendan Juba

Washington University in St. Louis

 

Abstract
In "abductive reasoning," a known or desired condition is given, and one seeks to find plausible (but not necessarily entailed) premises that imply the given condition. I propose a new model of abductive reasoning as finding a (possibly rare) "hypothesis" condition H for which the given condition of interest almost always holds in the distribution of data conditioned on H; we assume that we have access to a data set consisting of examples from the distribution of interest, in the same spirit as Valiant's PAC-learning model. In contrast to previous models of abductive reasoning, this model neither relies on the explicit specification of a prior distribution over the possible conditions to indicate which conditions are more plausible, nor on an explicit (logical) model of the relationships among attributes. Instead, the relationships among the attributes is directly learned from the data. Much like PAC-learning, this simple model is well suited to the analysis of algorithms. As a consequence, the model suggests an interesting picture of which representations can be found efficiently, and which are computationally intractable. In particular, k-DNF representations (for small k) can be found efficiently in this model, but recent results suggest that an efficient algorithm for finding conjunctive representations (or any stronger representation) may not exist.

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.