|
Activity Number:
|
42
|
|
Type:
|
Invited
|
|
Date/Time:
|
Sunday, August 6, 2006 : 4:00 PM to 5:50 PM
|
|
Sponsor:
|
IMS
|
| Abstract - #305310 |
|
Title:
|
Structured Prediction, Dual Extragradient, and Bregman Projections
|
|
Author(s):
|
Ben Taskar*+
|
|
Companies:
|
University of California, Berkeley
|
|
Address:
|
485 Soda Hall, Berkeley, CA, 94720,
|
|
Keywords:
|
Markov random fields ; m-estimation ; Bregman projections ; large-scale optimization
|
|
Abstract:
|
We present a simple and scalable algorithm for M-estimation of structured output models, including important classes of Markov networks and combinatorial models. We formulate the estimation problem as a convex-concave saddle-point problem that allows us to use simple projection methods based on the dual extragradient algorithm (Nesterov, 2003). The projection step can be solved using dynamic programming or combinatorial algorithms for min-cost convex flow, depending on the structure of the problem. We show that this approach provides a memory-efficient alternative to formulations based on reductions to a quadratic program (QP). We analyze the convergence of the method and present experiments on two very different structured prediction tasks---3D image segmentation and word alignment---illustrating the favorable scaling properties of our algorithm.
|
- The address information is for the authors that have a + after their name.
- Authors who are presenting talks have a * after their name.
Back to the full JSM 2006 program |
