[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

~REMINDER~

Combinatorics & Theoretical Computer Science Seminar

Tuesday, May 26, 2015
3:00 pm
Ryerson 251

Brendan Juba
Washington Univ. in St. Louis
 
Title: “Restricted distribution automatizability in PAC-Semanti”
 
Abstract: 
Machine learning is often employed as one step in a larger
application, serving for example to perform information extraction or data mining. The rules obtained by machine learning are thus used as the inputs to some further analysis. Such analyses can be cast as problems of logical reasoning. The results of the analysis can only be guaranteed to satisfy the same theoretical quality as the inputs, captured by Valiant's "PAC-Semantics" (2000).
 
In this talk, we consider the benefits of addressing a combined problem of learning and logical reasoning, as compared to the natural two-stage process of learning rules and then reasoning about those rules. We will focus on the computational benefit in the context of the reasoning problem when only partial information is available. In order to quantify the efficiency of algorithms, we need some grading of the reasoning problem's complexity that is more refined than simply the query representation and/or number of variables. Specifically, we
will consider the complexity of proofs that answer the query. We will exhibit integrated reasoning problems in these terms that can be solved far more efficiently than we believe possible for the corresponding stand-alone reasoning problems: we give quasi polynomial time algorithms whereas only subexponential time algorithms are known for the stand-alone problem.

Host by Prof. Madhur Tulsiani

(Refreshments will be served prior to the talk in Ry. 255 @ 2:30 p.m. )
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150526/11ae7a75/attachment.htm