[Colloquium] TTIC Colloquium: David Sontag, NYU

[Dawn Ellis]

 When:     Monday, February 23rd at 11am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       David Sontag, NYU

Title:       How Good Is Structured Prediction?

Abstract:

Many machine learning tasks can be posed as structured prediction,
where the goal is to predict a labeling or structured object. For
example, the input may be an image or a sentence, and the output is a
labeling such as an assignment of each pixel in the image to
foreground or background, or the parse tree for the sentence. Despite
marginal and MAP inference for many of these models being NP-hard in
the worst-case, approximate inference algorithms are remarkably
successful and as a result structured prediction is widely used.

What makes these real-world instances different from worst-case
instances? One key difference is that in all of these applications,
there is an underlying "ground truth" which structured prediction is
aiming to find. In this talk, I will introduce a new theoretical
framework for analyzing structured prediction algorithms in terms of
their ability to achieve small Hamming error. We study the
computational and statistical trade-offs that arise in this setting,
and illustrate a setting where polynomial-time algorithms can perform
optimal prediction, despite the corresponding MAP inference task being
NP-hard.

Joint work with Amir Globerson, Tim Roughgarden, and Cafer Yildirim.


Bio:

David Sontag is an Assistant Professor of Computer Science at New York
University's Courant Institute of Mathematical Sciences. His research
focuses on machine learning and approximate inference, and on
applications to medical informatics. Prior to joining Courant, he was
a postdoctoral researcher for Microsoft Research New England, 2010-11.
David's Ph.D thesis won the award for the best doctoral thesis in
Computer Science at MIT in 2010. His research has received recognition
including a NSF CAREER award (2014) and best paper awards at several
conferences on machine learning.

Host:  Greg Shakhnarovich, greg at ttic.edu

-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150217/24f2a720/attachment.htm