Discriminative training of conditional random fields with probably submodular constraints
From MaRDI portal
Abstract: Problems of segmentation, denoising, registration and 3D reconstruction are often addressed with the graph cut algorithm. However, solving an unconstrained graph cut problem is NP-hard. For tractable optimization, pairwise potentials have to fulfill the submodularity inequality. In our learning paradigm, pairwise potentials are created as the dot product of a learned vector w with positive feature vectors. In order to constrain such a model to remain tractable, previous approaches have enforced the weight vector to be positive for pairwise potentials in which the labels differ, and set pairwise potentials to zero in the case that the label remains the same. Such constraints are sufficient to guarantee that the resulting pairwise potentials satisfy the submodularity inequality. However, we show that such an approach unnecessarily restricts the capacity of the learned models. Guaranteeing submodularity for all possible inputs, no matter how improbable, reduces inference error to effectively zero, but increases model error. In contrast, we relax the requirement of guaranteed submodularity to solutions that are probably approximately submodular. We show that the conceptually simple strategy of enforcing submodularity on the training examples guarantees with low sample complexity that test images will also yield submodular pairwise potentials. Results are presented in the binary and muticlass settings, showing substantial improvement from the resulting increased model capacity.
Recommendations
- Classes of submodular constraints expressible by graph cuts
- Margin losses for training conditional random fields
- Global optimization for first order Markov random fields with submodular priors
- Conditional random fields for image labeling
- Efficient Relaxations for Dense CRFs with Sparse Higher-Order Potentials
Cites work
- A theory of the learnable
- Convexity, Classification, and Risk Bounds
- Cutting-plane training of structural SVMs
- scientific article; zbMATH DE number 1332320 (Why is no real title available?)
- scientific article; zbMATH DE number 765034 (Why is no real title available?)
- Large margin methods for structured and interdependent output variables
- Pystruct-learning structured prediction in Python
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
Cited in
(4)
This page was built for publication: Discriminative training of conditional random fields with probably submodular constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2226189)
