---
_id: '703'
abstract:
- lang: eng
  text: We consider the NP-hard problem of MAP-inference for undirected discrete graphical
    models. We propose a polynomial time and practically efficient algorithm for finding
    a part of its optimal solution. Specifically, our algorithm marks some labels
    of the considered graphical model either as (i) optimal, meaning that they belong
    to all optimal solutions of the inference problem; (ii) non-optimal if they provably
    do not belong to any solution. With access to an exact solver of a linear programming
    relaxation to the MAP-inference problem, our algorithm marks the maximal possible
    (in a specified sense) number of labels. We also present a version of the algorithm,
    which has access to a suboptimal dual solver only and still can ensure the (non-)optimality
    for the marked labels, although the overall number of the marked labels may decrease.
    We propose an efficient implementation, which runs in time comparable to a single
    run of a suboptimal dual solver. Our method is well-scalable and shows state-of-the-art
    results on computational benchmarks from machine learning and computer vision.
arxiv: 1
author:
- first_name: Alexander
  full_name: Shekhovtsov, Alexander
  last_name: Shekhovtsov
- first_name: Paul
  full_name: Swoboda, Paul
  id: 446560C6-F248-11E8-B48F-1D18A9856A87
  last_name: Swoboda
- first_name: Bogdan
  full_name: Savchynskyy, Bogdan
  last_name: Savchynskyy
citation:
  ama: Shekhovtsov A, Swoboda P, Savchynskyy B. Maximum persistency via iterative
    relaxed inference with graphical models. <i>IEEE Transactions on Pattern Analysis
    and Machine Intelligence</i>. 2018;40(7):1668-1682. doi:<a href="https://doi.org/10.1109/TPAMI.2017.2730884">10.1109/TPAMI.2017.2730884</a>
  apa: Shekhovtsov, A., Swoboda, P., &#38; Savchynskyy, B. (2018). Maximum persistency
    via iterative relaxed inference with graphical models. <i>IEEE Transactions on
    Pattern Analysis and Machine Intelligence</i>. IEEE. <a href="https://doi.org/10.1109/TPAMI.2017.2730884">https://doi.org/10.1109/TPAMI.2017.2730884</a>
  chicago: Shekhovtsov, Alexander, Paul Swoboda, and Bogdan Savchynskyy. “Maximum
    Persistency via Iterative Relaxed Inference with Graphical Models.” <i>IEEE Transactions
    on Pattern Analysis and Machine Intelligence</i>. IEEE, 2018. <a href="https://doi.org/10.1109/TPAMI.2017.2730884">https://doi.org/10.1109/TPAMI.2017.2730884</a>.
  ieee: A. Shekhovtsov, P. Swoboda, and B. Savchynskyy, “Maximum persistency via iterative
    relaxed inference with graphical models,” <i>IEEE Transactions on Pattern Analysis
    and Machine Intelligence</i>, vol. 40, no. 7. IEEE, pp. 1668–1682, 2018.
  ista: Shekhovtsov A, Swoboda P, Savchynskyy B. 2018. Maximum persistency via iterative
    relaxed inference with graphical models. IEEE Transactions on Pattern Analysis
    and Machine Intelligence. 40(7), 1668–1682.
  mla: Shekhovtsov, Alexander, et al. “Maximum Persistency via Iterative Relaxed Inference
    with Graphical Models.” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>,
    vol. 40, no. 7, IEEE, 2018, pp. 1668–82, doi:<a href="https://doi.org/10.1109/TPAMI.2017.2730884">10.1109/TPAMI.2017.2730884</a>.
  short: A. Shekhovtsov, P. Swoboda, B. Savchynskyy, IEEE Transactions on Pattern
    Analysis and Machine Intelligence 40 (2018) 1668–1682.
date_created: 2018-12-11T11:48:01Z
date_published: 2018-07-01T00:00:00Z
date_updated: 2021-01-12T08:11:32Z
day: '01'
department:
- _id: VlKo
doi: 10.1109/TPAMI.2017.2730884
external_id:
  arxiv:
  - '1508.07902'
intvolume: '        40'
issue: '7'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1508.07902
month: '07'
oa: 1
oa_version: Preprint
page: 1668-1682
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_identifier:
  issn:
  - '01628828'
publication_status: published
publisher: IEEE
publist_id: '6992'
quality_controlled: '1'
scopus_import: 1
status: public
title: Maximum persistency via iterative relaxed inference with graphical models
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 40
year: '2018'
...