Markov Random Field MAP as Set Partitioning

James Cussens

Markov Random Field MAP as Set Partitioning

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The Markov Random Field (MRF) MAP inference problem is considered from the viewpoint of
integer programming (IP). The problem is shown to be a (pure) set partitioning problem (SPP). This
allows us to bring existing work on SPP to bear on the MAP problem. Facets (maximally strong
linear inequalities) of the closely related set packing (SP) problem are shown to be useful for MRF
MAP. These facets include odd hole and odd anti-hole inequalities which are shown to be findable
using a zero-half cut generator. Experimental results using CPLEX show that for MRF MAP
problems, generating more zero-half cuts than normal typically brings performance improvements.
Pre-processing methods to reduce the size of MRF MAP problems are also considered, and some
preliminary results on their usefulness presented.

Original language	English
Title of host publication	Proceedings of Machine Learning Research
Subtitle of host publication	PGM 2018
Pages	85-96
Number of pages	12
Volume	72
Publication status	Published - 2018
Event	The 9th International Conference on Probabilistic Graphical Models - Prague, Czech Republic Duration: 11 Sep 2018 → 14 Sep 2018 http://pgm2018.utia.cz/

Conference

Conference	The 9th International Conference on Probabilistic Graphical Models
Abbreviated title	PGM'18
Country/Territory	Czech Republic
City	Prague
Period	11/09/18 → 14/09/18
Internet address	http://pgm2018.utia.cz/

Access to Document

http://proceedings.mlr.press/v72/cussens18a/cussens18a.pdf

Cite this

@inproceedings{16582219315248ee894e91a16b834d46,

title = "Markov Random Field MAP as Set Partitioning",

abstract = "The Markov Random Field (MRF) MAP inference problem is considered from the viewpoint ofinteger programming (IP). The problem is shown to be a (pure) set partitioning problem (SPP). Thisallows us to bring existing work on SPP to bear on the MAP problem. Facets (maximally stronglinear inequalities) of the closely related set packing (SP) problem are shown to be useful for MRFMAP. These facets include odd hole and odd anti-hole inequalities which are shown to be findableusing a zero-half cut generator. Experimental results using CPLEX show that for MRF MAPproblems, generating more zero-half cuts than normal typically brings performance improvements.Pre-processing methods to reduce the size of MRF MAP problems are also considered, and somepreliminary results on their usefulness presented.",

author = "James Cussens",

year = "2018",

language = "English",

volume = "72",

pages = "85--96",

booktitle = "Proceedings of Machine Learning Research",

note = "The 9th International Conference on Probabilistic Graphical Models, PGM'18 ; Conference date: 11-09-2018 Through 14-09-2018",

url = "http://pgm2018.utia.cz/",

}

TY - GEN

T1 - Markov Random Field MAP as Set Partitioning

AU - Cussens, James

PY - 2018

Y1 - 2018

N2 - The Markov Random Field (MRF) MAP inference problem is considered from the viewpoint ofinteger programming (IP). The problem is shown to be a (pure) set partitioning problem (SPP). Thisallows us to bring existing work on SPP to bear on the MAP problem. Facets (maximally stronglinear inequalities) of the closely related set packing (SP) problem are shown to be useful for MRFMAP. These facets include odd hole and odd anti-hole inequalities which are shown to be findableusing a zero-half cut generator. Experimental results using CPLEX show that for MRF MAPproblems, generating more zero-half cuts than normal typically brings performance improvements.Pre-processing methods to reduce the size of MRF MAP problems are also considered, and somepreliminary results on their usefulness presented.

AB - The Markov Random Field (MRF) MAP inference problem is considered from the viewpoint ofinteger programming (IP). The problem is shown to be a (pure) set partitioning problem (SPP). Thisallows us to bring existing work on SPP to bear on the MAP problem. Facets (maximally stronglinear inequalities) of the closely related set packing (SP) problem are shown to be useful for MRFMAP. These facets include odd hole and odd anti-hole inequalities which are shown to be findableusing a zero-half cut generator. Experimental results using CPLEX show that for MRF MAPproblems, generating more zero-half cuts than normal typically brings performance improvements.Pre-processing methods to reduce the size of MRF MAP problems are also considered, and somepreliminary results on their usefulness presented.

M3 - Conference contribution

VL - 72

SP - 85

EP - 96

BT - Proceedings of Machine Learning Research

T2 - The 9th International Conference on Probabilistic Graphical Models

Y2 - 11 September 2018 through 14 September 2018

ER -