Efficiently solving convex relaxations for MAP estimation
<p>The problem of obtaining the maximum <em>a posteriori</em> (MAP) estimate of a discrete random field is of fundamental importance in many areas of Computer Science. In this work, we build on the tree reweighted message passing (TRW) framework of (Kolmogorov, 20...
| Κύριοι συγγραφείς: | , |
|---|---|
| Μορφή: | Conference item |
| Γλώσσα: | English |
| Έκδοση: |
Association for Computing Machinery
2008
|
| _version_ | 1826314994174656512 |
|---|---|
| author | Kumar, MP Torr, PHS |
| author_facet | Kumar, MP Torr, PHS |
| author_sort | Kumar, MP |
| collection | OXFORD |
| description | <p>The problem of obtaining the maximum <em>a posteriori</em> (MAP) estimate of a discrete random field is of fundamental importance in many areas of Computer Science. In this work, we build on the tree reweighted message passing (TRW) framework of (Kolmogorov, 2006; Wainwright et al., 2005). TRW iteratively optimizes the Lagrangian dual of a linear programming relaxation for MAP estimation. We show how the dual formulation of TRW can be extended to include cycle inequalities (Barahona & Mahjoub, 1986) and some recently proposed second order cone (SOC) constraints (Kumar et al., 2007). We propose efficient iterative algorithms for solving the resulting duals. Similar to the method described in (Kolmogorov, 2006), these algorithms are guaranteed to converge. We test our approach on a large set of synthetic data, as well as real data. Our experiments show that the additional constraints (i.e. cycle inequalities and SOC constraints) provide better results in cases where the TRW framework fails (namely MAP estimation for non-submodular energy functions).</p> |
| first_indexed | 2024-12-09T03:18:01Z |
| format | Conference item |
| id | oxford-uuid:23b59c06-76b5-445b-bf0a-d81c7f007b8a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:18:01Z |
| publishDate | 2008 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:23b59c06-76b5-445b-bf0a-d81c7f007b8a2024-10-31T10:44:34ZEfficiently solving convex relaxations for MAP estimationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:23b59c06-76b5-445b-bf0a-d81c7f007b8aEnglishSymplectic ElementsAssociation for Computing Machinery2008Kumar, MPTorr, PHS<p>The problem of obtaining the maximum <em>a posteriori</em> (MAP) estimate of a discrete random field is of fundamental importance in many areas of Computer Science. In this work, we build on the tree reweighted message passing (TRW) framework of (Kolmogorov, 2006; Wainwright et al., 2005). TRW iteratively optimizes the Lagrangian dual of a linear programming relaxation for MAP estimation. We show how the dual formulation of TRW can be extended to include cycle inequalities (Barahona & Mahjoub, 1986) and some recently proposed second order cone (SOC) constraints (Kumar et al., 2007). We propose efficient iterative algorithms for solving the resulting duals. Similar to the method described in (Kolmogorov, 2006), these algorithms are guaranteed to converge. We test our approach on a large set of synthetic data, as well as real data. Our experiments show that the additional constraints (i.e. cycle inequalities and SOC constraints) provide better results in cases where the TRW framework fails (namely MAP estimation for non-submodular energy functions).</p> |
| spellingShingle | Kumar, MP Torr, PHS Efficiently solving convex relaxations for MAP estimation |
| title | Efficiently solving convex relaxations for MAP estimation |
| title_full | Efficiently solving convex relaxations for MAP estimation |
| title_fullStr | Efficiently solving convex relaxations for MAP estimation |
| title_full_unstemmed | Efficiently solving convex relaxations for MAP estimation |
| title_short | Efficiently solving convex relaxations for MAP estimation |
| title_sort | efficiently solving convex relaxations for map estimation |
| work_keys_str_mv | AT kumarmp efficientlysolvingconvexrelaxationsformapestimation AT torrphs efficientlysolvingconvexrelaxationsformapestimation |