<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 12pt; color: #000000'><h1 class="page__title title" id="page-title">Efficient learning with combinatorial structure</h1><span class="event-speaker">
<a href="http://www.cs.berkeley.edu/%7Estefje/">Stefanie Jegelka</a>, </span><span class="event-speaker-from"><a href="https://amplab.cs.berkeley.edu/">University of California, Berkeley</a></span><br>Tuesday, April 8, 4:30pm<br>Computer Science 105<br><br>Learning from complex data such as images, text or biological
measurements invariably relies on capturing long-range, latent
structure. But the combinatorial structure inherent in real-world data
can pose significant computational challenges for modeling, learning and
inference.<br>
<br>
In this talk, I will view these challenges through the lens of
submodular set functions. Considered a "discrete analog of convexity",
the combinatorial concept of submodularity captures intuitive yet
nontrivial dependencies between variables and underlies many widely used
concepts in machine learning. Practical use of submodularity, however,
requires care. My first example illustrates how to efficiently handle
the important class of submodular composite models. The second example
combines submodularity and graphs for a new family of combinatorial
models that express long-range interactions while still admitting very
efficient inference procedures. As a concrete application, our results
enable effective realization of combinatorial sparsity priors on real
data, significantly improving image segmentation results in settings
where state-of-the-art methods fail. Motivated by good empirical
results, we provide a detailed theoretical analysis and identify
practically relevant properties that affect complexity and approximation
quality of submodular optimization and learning problems. <br>
<br>
Stefanie Jegelka is a postdoctoral researcher at UC Berkeley, working
with Michael I. Jordan and Trevor Darrell. She received a Ph.D. in
Computer Science from ETH Zurich in 2012, in collaboration with the Max
Planck Institute for Intelligent Systems, and completed her studies for a
Diploma in Bioinformatics with distinction at the University of
Tuebingen (Germany) and the University of Texas at Austin. She was a
fellow of the German National Academic Foundation (Studienstiftung) and
its scientific college for life sciences, and has received a Google
Anita Borg Europe Fellowship and an ICML Best Paper Award. She has also
been a research visitor at Georgetown University Medical Center and
Microsoft Research and has held workshops and tutorials on submodularity
in machine learning.</div></body></html>