Natural language research announcements

[Alice Lai <aylai2 AT illinois.edu>]

When: Wednesday Oct 21 @ 2pm 

Where: 3401 SC

Speaker: Brendan Juba (Washington University in St. Louis)

Title: Learning abductive reasoning using random examples 

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.