Approximate inference in graphical models using LP relaxations
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/62457 |
| _version_ | 1826209622907682816 |
|---|---|
| author | Sontag, David Alexander |
| author2 | Tommi S. Jaakkola. |
| author_facet | Tommi S. Jaakkola. Sontag, David Alexander |
| author_sort | Sontag, David Alexander |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. |
| first_indexed | 2024-09-23T14:25:23Z |
| format | Thesis |
| id | mit-1721.1/62457 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:25:23Z |
| publishDate | 2011 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/624572019-04-11T09:47:53Z Approximate inference in graphical models using LP relaxations Approximate inference in graphical models using linear programming relaxations Sontag, David Alexander Tommi S. Jaakkola. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. Cataloged from PDF version of thesis. Includes bibliographical references (p. 107-114). Graphical models such as Markov random fields have been successfully applied to a wide variety of fields, from computer vision and natural language processing, to computational biology. Exact probabilistic inference is generally intractable in complex models having many dependencies between the variables. We present new approaches to approximate inference based on linear programming (LP) relaxations. Our algorithms optimize over the cycle relaxation of the marginal polytope, which we show to be closely related to the first lifting of the Sherali-Adams hierarchy, and is significantly tighter than the pairwise LP relaxation. We show how to efficiently optimize over the cycle relaxation using a cutting-plane algorithm that iteratively introduces constraints into the relaxation. We provide a criterion to determine which constraints would be most helpful in tightening the relaxation, and give efficient algorithms for solving the search problem of finding the best cycle constraint to add according to this criterion. By solving the LP relaxations in the dual, we obtain efficient message-passing algorithms that, when the relaxations are tight, can provably find the most likely (MAP) configuration. Our algorithms succeed at finding the MAP configuration in protein side-chain placement, protein design, and stereo vision problems. by David Alexander Sontag. Ph.D. 2011-04-25T16:02:02Z 2011-04-25T16:02:02Z 2010 2010 Thesis http://hdl.handle.net/1721.1/62457 711182714 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 114 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Sontag, David Alexander Approximate inference in graphical models using LP relaxations |
| title | Approximate inference in graphical models using LP relaxations |
| title_full | Approximate inference in graphical models using LP relaxations |
| title_fullStr | Approximate inference in graphical models using LP relaxations |
| title_full_unstemmed | Approximate inference in graphical models using LP relaxations |
| title_short | Approximate inference in graphical models using LP relaxations |
| title_sort | approximate inference in graphical models using lp relaxations |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/62457 |
| work_keys_str_mv | AT sontagdavidalexander approximateinferenceingraphicalmodelsusinglprelaxations AT sontagdavidalexander approximateinferenceingraphicalmodelsusinglinearprogrammingrelaxations |