skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

MAP Inference Via [Formula omitted]-Sphere Linear Program Reformulation

International journal of computer vision, 2020-07, Vol.128 (7), p.1913 [Peer Reviewed Journal]

COPYRIGHT 2020 Springer ;ISSN: 0920-5691 ;EISSN: 1573-1405 ;DOI: 10.1007/s11263-020-01313-2

Full text available

Citations Cited by
  • Title:
    MAP Inference Via [Formula omitted]-Sphere Linear Program Reformulation
  • Author: Wu, Baoyuan ; Shen, Li ; Zhang, Tong ; Ghanem, Bernard
  • Subjects: Algorithms
  • Is Part Of: International journal of computer vision, 2020-07, Vol.128 (7), p.1913
  • Description: Maximum a posteriori (MAP) inference is an important task for graphical models. Due to complex dependencies among variables in realistic models, finding an exact solution for MAP inference is often intractable. Thus, many approximation methods have been developed, among which the linear programming (LP) relaxation based methods show promising performance. However, one major drawback of LP relaxation is that it is possible to give fractional solutions. Instead of presenting a tighter relaxation, in this work we propose a continuous but equivalent reformulation of the original MAP inference problem, called LS-LP. We add the [Formula omitted]-sphere constraint onto the original LP relaxation, leading to an intersected space with the local marginal polytope that is equivalent to the space of all valid integer label configurations. Thus, LS-LP is equivalent to the original MAP inference problem. We propose a perturbed alternating direction method of multipliers (ADMM) algorithm to optimize the LS-LP problem, by adding a sufficiently small perturbation [Formula omitted] onto the objective function and constraints. We prove that the perturbed ADMM algorithm globally converges to the [Formula omitted]-Karush-Kuhn-Tucker ( [Formula omitted]-KKT) point of the LS-LP problem. The convergence rate will also be analyzed. Experiments on several benchmark datasets from Probabilistic Inference Challenge (PIC 2011) and OpenGM 2 show competitive performance of our proposed method against state-of-the-art MAP inference methods.
  • Publisher: Springer
  • Language: English
  • Identifier: ISSN: 0920-5691
    EISSN: 1573-1405
    DOI: 10.1007/s11263-020-01313-2
  • Source: AUTh Library subscriptions: ProQuest Central
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait