Reparameterization based consistent graph-structured linear programs

Hongbo Zhou, Qiang Cheng, Zhikun She

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A class of Maximum A Posteriori(MAP) formulations built on various graph models are of great interests for both theoretical and practical applications. Recent advances in this field have extended the connections between the linear program (LP) relaxation and various tree-reweighted message passing algorithms. At both sides, many algorithms and their optimality certificates are proved, provided no conflict exists between the node marginal maximum and the corresponding edge marginal maximum. However, these conflicts are usually inevitable for general non-trivial Markov random fields (MRFs). Our work is aimed at reducing such conflicts by reparameterizing the original energy distributions in pairwise Markov random field. All node potentials will be decomposed and attached to local edges according to their local graph structures. And thus, only edge marginals are needed in our linear program relaxation, and the node marginals are only used to exchange information among different parts of the graph. We incorporated this consistent graph-structured reparameterization into some latest LP optimality guaranteed proximal solvers, and the resulted algorithms outperform the original ones in convergence rate and also have a better behavior to converge to MAP optimality monotonously even for some highly noisy MRFs.

Original languageEnglish
Title of host publicationAPPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing
Pages974-978
Number of pages5
DOIs
StatePublished - 23 Jul 2010
Event25th Annual ACM Symposium on Applied Computing, SAC 2010 - Sierre, Switzerland
Duration: 22 Mar 201026 Mar 2010

Publication series

NameProceedings of the ACM Symposium on Applied Computing

Conference

Conference25th Annual ACM Symposium on Applied Computing, SAC 2010
CountrySwitzerland
CitySierre
Period22/03/1026/03/10

Fingerprint

Message passing

Keywords

  • MAP optimality
  • Markov random field
  • linear program

Cite this

Zhou, H., Cheng, Q., & She, Z. (2010). Reparameterization based consistent graph-structured linear programs. In APPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing (pp. 974-978). (Proceedings of the ACM Symposium on Applied Computing). https://doi.org/10.1145/1774088.1774291
Zhou, Hongbo ; Cheng, Qiang ; She, Zhikun. / Reparameterization based consistent graph-structured linear programs. APPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing. 2010. pp. 974-978 (Proceedings of the ACM Symposium on Applied Computing).
@inproceedings{a49d59a6a2754e0fbb74f6e18dc1f435,
title = "Reparameterization based consistent graph-structured linear programs",
abstract = "A class of Maximum A Posteriori(MAP) formulations built on various graph models are of great interests for both theoretical and practical applications. Recent advances in this field have extended the connections between the linear program (LP) relaxation and various tree-reweighted message passing algorithms. At both sides, many algorithms and their optimality certificates are proved, provided no conflict exists between the node marginal maximum and the corresponding edge marginal maximum. However, these conflicts are usually inevitable for general non-trivial Markov random fields (MRFs). Our work is aimed at reducing such conflicts by reparameterizing the original energy distributions in pairwise Markov random field. All node potentials will be decomposed and attached to local edges according to their local graph structures. And thus, only edge marginals are needed in our linear program relaxation, and the node marginals are only used to exchange information among different parts of the graph. We incorporated this consistent graph-structured reparameterization into some latest LP optimality guaranteed proximal solvers, and the resulted algorithms outperform the original ones in convergence rate and also have a better behavior to converge to MAP optimality monotonously even for some highly noisy MRFs.",
keywords = "MAP optimality, Markov random field, linear program",
author = "Hongbo Zhou and Qiang Cheng and Zhikun She",
year = "2010",
month = "7",
day = "23",
doi = "10.1145/1774088.1774291",
language = "English",
isbn = "9781605586380",
series = "Proceedings of the ACM Symposium on Applied Computing",
pages = "974--978",
booktitle = "APPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing",

}

Zhou, H, Cheng, Q & She, Z 2010, Reparameterization based consistent graph-structured linear programs. in APPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing. Proceedings of the ACM Symposium on Applied Computing, pp. 974-978, 25th Annual ACM Symposium on Applied Computing, SAC 2010, Sierre, Switzerland, 22/03/10. https://doi.org/10.1145/1774088.1774291

Reparameterization based consistent graph-structured linear programs. / Zhou, Hongbo; Cheng, Qiang; She, Zhikun.

APPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing. 2010. p. 974-978 (Proceedings of the ACM Symposium on Applied Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Reparameterization based consistent graph-structured linear programs

AU - Zhou, Hongbo

AU - Cheng, Qiang

AU - She, Zhikun

PY - 2010/7/23

Y1 - 2010/7/23

N2 - A class of Maximum A Posteriori(MAP) formulations built on various graph models are of great interests for both theoretical and practical applications. Recent advances in this field have extended the connections between the linear program (LP) relaxation and various tree-reweighted message passing algorithms. At both sides, many algorithms and their optimality certificates are proved, provided no conflict exists between the node marginal maximum and the corresponding edge marginal maximum. However, these conflicts are usually inevitable for general non-trivial Markov random fields (MRFs). Our work is aimed at reducing such conflicts by reparameterizing the original energy distributions in pairwise Markov random field. All node potentials will be decomposed and attached to local edges according to their local graph structures. And thus, only edge marginals are needed in our linear program relaxation, and the node marginals are only used to exchange information among different parts of the graph. We incorporated this consistent graph-structured reparameterization into some latest LP optimality guaranteed proximal solvers, and the resulted algorithms outperform the original ones in convergence rate and also have a better behavior to converge to MAP optimality monotonously even for some highly noisy MRFs.

AB - A class of Maximum A Posteriori(MAP) formulations built on various graph models are of great interests for both theoretical and practical applications. Recent advances in this field have extended the connections between the linear program (LP) relaxation and various tree-reweighted message passing algorithms. At both sides, many algorithms and their optimality certificates are proved, provided no conflict exists between the node marginal maximum and the corresponding edge marginal maximum. However, these conflicts are usually inevitable for general non-trivial Markov random fields (MRFs). Our work is aimed at reducing such conflicts by reparameterizing the original energy distributions in pairwise Markov random field. All node potentials will be decomposed and attached to local edges according to their local graph structures. And thus, only edge marginals are needed in our linear program relaxation, and the node marginals are only used to exchange information among different parts of the graph. We incorporated this consistent graph-structured reparameterization into some latest LP optimality guaranteed proximal solvers, and the resulted algorithms outperform the original ones in convergence rate and also have a better behavior to converge to MAP optimality monotonously even for some highly noisy MRFs.

KW - MAP optimality

KW - Markov random field

KW - linear program

UR - http://www.scopus.com/inward/record.url?scp=77954748925&partnerID=8YFLogxK

U2 - 10.1145/1774088.1774291

DO - 10.1145/1774088.1774291

M3 - Conference contribution

AN - SCOPUS:77954748925

SN - 9781605586380

T3 - Proceedings of the ACM Symposium on Applied Computing

SP - 974

EP - 978

BT - APPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing

ER -

Zhou H, Cheng Q, She Z. Reparameterization based consistent graph-structured linear programs. In APPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing. 2010. p. 974-978. (Proceedings of the ACM Symposium on Applied Computing). https://doi.org/10.1145/1774088.1774291