Submodular Decomposition Framework for Inference in Associative Markov\n Networks with Global Constraints

2011/03/05 by Anton Osokin, Dmitry Vetrov, Osokin, Anton +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Bayesian Modeling and Causal Inference #Computer Vision and Pattern Recognition (cs.CV) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Gene expression and cancer classification #Graph Theory and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.1103.1077

openalex publication_date 2011/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In the paper we address the problem of finding the most probable state of\ndiscrete Markov random field (MRF) with associative pairwise terms. Although of\npractical importance, this problem is known to be NP-hard in general. We\npropose a new type of MRF decomposition, submodular decomposition (SMD). Unlike\nexisting decomposition approaches SMD decomposes the initial problem into\nsubproblems corresponding to a specific class label while preserving the graph\nstructure of each subproblem. Such decomposition enables us to take into\naccount several types of global constraints in an efficient manner. We study\ntheoretical properties of the proposed approach and demonstrate its\napplicability on a number of problems.\n

Cited by

• Higher-order Segmentation via Multicuts

Related

• Discovering the Markov network structure
• Learning Chordal Markov Networks by Constraint Satisfaction
• On MAP Inference by MWSS on Perfect Graphs
• Bayesian Markov Blanket Estimation
• Structure Learning of Partitioned Markov Networks