← Back to papers
2018 PGM PGM 2018

Markov Random Field MAP as Set Partitioning

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.

🧭 Keyword Pioneer — cut generation
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics
🌉 Interdisciplinary Bridge — Machine Learning and Mathematics & Optimization

Authors

James Cussens

Topics

Machine Learning > Optimization & Theory > Optimization Mathematics & Optimization > Optimization > Combinatorial Optimization Machine Learning > Core Methods > Graphical Models Machine Learning > Core Methods > Probabilistic Modeling Mathematics & Optimization > Optimization > Discrete Optimization

Keywords

combinatorial optimization map inference integer programming markov random field cutting plane set partitioning cut generation
Download PDF

Related papers

Discriminative Training of Sum-Product Networks by Extended Baum-Welch 2018
Learning Bayesian network classifiers with completed partially directed acyclic graphs 2018
Causal Structure Learning via Temporal Markov Networks 2018
A Bayesian Approach for Inferring Local Causal Structure in Gene Regulatory Networks 2018
On the Relative Expressiveness of Bayesian and Neural Networks 2018