---
_id: '3124'
abstract:
- lang: eng
  text: "We consider the problem of inference in a graphical model with binary variables.
    While in theory it is arguably preferable to compute marginal probabilities, in
    practice researchers often use MAP inference due to the availability of efficient
    discrete optimization algorithms. We bridge the gap between the two approaches
    by introducing the Discrete Marginals technique in which approximate marginals
    are obtained by minimizing an objective function with unary and pairwise terms
    over a discretized domain. This allows the use of techniques originally developed
    for MAP-MRF inference and learning. We explore two ways to set up the objective
    function - by discretizing the Bethe free energy and by learning it from training
    data. Experimental results show that for certain types of graphs a learned function
    can outperform the Bethe approximation. We also establish a link between the Bethe
    free energy and submodular functions.\r\n"
alternative_title:
- Inferning 2012
author:
- first_name: Filip
  full_name: Korc, Filip
  id: 476A2FD6-F248-11E8-B48F-1D18A9856A87
  last_name: Korc
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Christoph
  full_name: Lampert, Christoph
  id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
  last_name: Lampert
  orcid: 0000-0001-8622-7887
citation:
  ama: 'Korc F, Kolmogorov V, Lampert C. Approximating marginals using discrete energy
    minimization. In: ICML; 2012.'
  apa: 'Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals
    using discrete energy minimization. Presented at the ICML: International Conference
    on Machine Learning, Edinburgh, Scotland: ICML.'
  chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. “Approximating
    Marginals Using Discrete Energy Minimization.” ICML, 2012.
  ieee: 'F. Korc, V. Kolmogorov, and C. Lampert, “Approximating marginals using discrete
    energy minimization,” presented at the ICML: International Conference on Machine
    Learning, Edinburgh, Scotland, 2012.'
  ista: 'Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete
    energy minimization. ICML: International Conference on Machine Learning, Inferning
    2012, .'
  mla: Korc, Filip, et al. <i>Approximating Marginals Using Discrete Energy Minimization</i>.
    ICML, 2012.
  short: F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012.
conference:
  end_date: 2012-07-01
  location: Edinburgh, Scotland
  name: 'ICML: International Conference on Machine Learning'
  start_date: 2012-06-26
corr_author: '1'
date_created: 2018-12-11T12:01:31Z
date_published: 2012-06-30T00:00:00Z
date_updated: 2024-10-09T20:54:48Z
day: '30'
ddc:
- '000'
department:
- _id: ChLa
- _id: VlKo
file:
- access_level: open_access
  checksum: 3d0d4246548c736857302aadb2ff5d15
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:11:34Z
  date_updated: 2020-07-14T12:46:00Z
  file_id: '4889'
  file_name: IST-2016-565-v1+1_DM-inferning2012.pdf
  file_size: 305836
  relation: main_file
file_date_updated: 2020-07-14T12:46:00Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
publication_status: published
publisher: ICML
publist_id: '3575'
pubrep_id: '565'
quality_controlled: '1'
related_material:
  record:
  - id: '5396'
    relation: later_version
    status: public
status: public
title: Approximating marginals using discrete energy minimization
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '3257'
abstract:
- lang: eng
  text: Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that
    the relaxation is totally half-integral if f̂(x) is a polyhedral function with
    half-integral extreme points x, and this property is preserved after adding an
    arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ
    where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation
    for quadratic pseudo-Boolean functions f. We argue that total half-integrality
    is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean
    functions. Our contributions are as follows. First, we provide a complete characterization
    of totally half-integral relaxations f̂ by establishing a one-to-one correspondence
    with bisubmodular functions. Second, we give a new characterization of bisubmodular
    functions. Finally, we show some relationships between general totally half-integral
    relaxations and relaxations based on the roof duality. On the conceptual level,
    our results show that bisubmodular functions provide a natural generalization
    of the roof duality approach to higher-order terms. This can be viewed as a non-submodular
    analogue of the fact that submodular functions generalize the s-t minimum cut
    problem with non-negative weights to higher-order terms.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: Kolmogorov V. Generalized roof duality and bisubmodular functions. <i>Discrete
    Applied Mathematics</i>. 2012;160(4-5):416-426. doi:<a href="https://doi.org/10.1016/j.dam.2011.10.026">10.1016/j.dam.2011.10.026</a>
  apa: Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions.
    <i>Discrete Applied Mathematics</i>. Elsevier. <a href="https://doi.org/10.1016/j.dam.2011.10.026">https://doi.org/10.1016/j.dam.2011.10.026</a>
  chicago: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.”
    <i>Discrete Applied Mathematics</i>. Elsevier, 2012. <a href="https://doi.org/10.1016/j.dam.2011.10.026">https://doi.org/10.1016/j.dam.2011.10.026</a>.
  ieee: V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” <i>Discrete
    Applied Mathematics</i>, vol. 160, no. 4–5. Elsevier, pp. 416–426, 2012.
  ista: Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete
    Applied Mathematics. 160(4–5), 416–426.
  mla: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.”
    <i>Discrete Applied Mathematics</i>, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26,
    doi:<a href="https://doi.org/10.1016/j.dam.2011.10.026">10.1016/j.dam.2011.10.026</a>.
  short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.
corr_author: '1'
date_created: 2018-12-11T12:02:18Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2025-09-30T07:43:17Z
day: '01'
department:
- _id: VlKo
doi: 10.1016/j.dam.2011.10.026
external_id:
  arxiv:
  - '1005.2305'
  isi:
  - '000301211100006'
intvolume: '       160'
isi: 1
issue: 4-5
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1005.2305
month: '03'
oa: 1
oa_version: Preprint
page: 416 - 426
publication: Discrete Applied Mathematics
publication_status: published
publisher: Elsevier
publist_id: '3397'
quality_controlled: '1'
related_material:
  record:
  - id: '2934'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Generalized roof duality and bisubmodular functions
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 160
year: '2012'
...