Improved moves for truncated convex models

Conference item

We consider the problem of obtaining the approximate maximum a posteriori estimate of a discrete random field characterized by pairwise potentials that form a truncated convex model. For this problem, we propose an improved st-mincut based move making algorithm. Unlike previous move making approaches, which either provide a loose bound or no bound on the quality of the solution (in terms of the corresponding Gibbs energy), our algorithm achieves the same guarantees as the standard linear programming (LP) relaxation. Compared to previous approaches based on the LP relaxation, e.g. interior-point algorithms or tree-reweighted message passing (TRW), our method is faster as it uses only the efficient st-mincut algorithm in its design. Furthermore, it directly provides us with a primal solution (unlike TRW and other related methods which attempt to solve the dual of the LP). We demonstrate the effectiveness of the proposed approach on both synthetic and standard real data problems. Our analysis also opens up an interesting question regarding the relationship between move making algorithms (such as α-expansion and the algorithms presented in this paper) and the randomized rounding schemes used with convex relaxations. We believe that further explorations in this direction would help design efficient algorithms for more complex relaxations.

Authors: Kumar, MP; Torr, PHS

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Curran Associates
• Host title: Advances in Neural Information Processing Systems 21
• Volume: 2
• Pages: 889-896
• Publication date: 2009-06-01
• Event title: 22nd Annual Conference on Neural Information Processing Systems 2008 (NeurIPS 2008)
• Event location: British Columbia, Canada
• Event website: https://nips.cc/Conferences/2008
• Event start date: 2008-12-08
• Event end date: 2008-12-11
• EISSN: 1049-5258
• ISBN: 9781605609492
• Language: English