Maximum Persistency via Iterative Relaxed Inference With Graphical Models

Alexander Shekhovtsov, Paul Swoboda, Bogdan Savchynskyy; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015, pp. 521-529

Abstract


We consider MAP-inference for graphical models and propose a novel efficient algorithm for finding persistent labels. Our algorithm marks each label in each node of the considered graphical model either as (i) optimal, meaning that it belongs to all optimal solutions of the inference problem; (ii) non-optimal if it provably does not belong to any solution; or (iii) undefined, which means our algorithm can not make a decision regarding the label. Moreover, we prove optimality of our approach, that it delivers in a certain sense the largest total number of labels marked as optimal or non-optimal. We demonstrate superiority of our approach on problems from machine learning and computer vision benchmarks.

Related Material


[pdf]
[bibtex]
@InProceedings{Shekhovtsov_2015_CVPR,
author = {Shekhovtsov, Alexander and Swoboda, Paul and Savchynskyy, Bogdan},
title = {Maximum Persistency via Iterative Relaxed Inference With Graphical Models},
booktitle = {Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2015}
}