SCIENCE@home

Constraint Reduction using Marginal Polytope Diagrams for MAP LP Relaxations

Zhen Zhang,Javen Qinfeng Shi,Yanning Zhang,Chunhua Shen,Anton van den Hengel

Published 2013 in arXiv.org

ABSTRACT

LP relaxation-based message passing algorithms provide an effective tool for MAP inference over Probabilistic Graphical Models. However, different LP relaxations often have different objective functions and variables of differing dimensions, which presents a barrier to effective comparison and analysis. In addition, the computational complexity of LP relaxation-based methods grows quickly with the number of constraints. Reducing the number of constraints without sacrificing the quality of the solutions is thus desirable. We propose a unified formulation under which existing MAP LP relaxations may be compared and analysed. Furthermore, we propose a new tool called Marginal Polytope Diagrams. Some properties of Marginal Polytope Diagrams are exploited such as node redundancy and edge equivalence. We show that using Marginal Polytope Diagrams allows the number of constraints to be reduced without loosening the LP relaxations. Then, using Marginal Polytope Diagrams and constraint reduction, we develop three novel message passing algorithms, and demonstrate that two of these show a significant improvement in speed over state-of-art algorithms while delivering a competitive, and sometimes higher, quality of solution.

PUBLICATION RECORD

  • Publication year

    2013

  • Venue

    arXiv.org

  • Publication date

    2013-12-16

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1312.4637
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-26 of 26 references · Page 1 of 1

CITED BY

Showing 1-6 of 6 citing papers · Page 1 of 1