---
_id: '2901'
abstract:
- lang: eng
text: ' We introduce the M-modes problem for graphical models: predicting the M
label configurations of highest probability that are at the same time local maxima
of the probability landscape. M-modes have multiple possible applications: because
they are intrinsically diverse, they provide a principled alternative to non-maximum
suppression techniques for structured prediction, they can act as codebook vectors
for quantizing the configuration space, or they can form component centers for
mixture model approximation. We present two algorithms for solving the M-modes
problem. The first algorithm solves the problem in polynomial time when the underlying
graphical model is a simple chain. The second algorithm solves the problem for
junction chains. In synthetic and real dataset, we demonstrate how M-modes can
improve the performance of prediction. We also use the generated modes as a tool
to understand the topography of the probability distribution of configurations,
for example with relation to the training set size and amount of noise in the
data. '
alternative_title:
- ' JMLR: W&CP'
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Zhu
full_name: Yan, Zhu
last_name: Yan
- first_name: Dimitris
full_name: Metaxas, Dimitris
last_name: Metaxas
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. Computing the M most probable
modes of a graphical model. In: Vol 31. JMLR; 2013:161-169.'
apa: 'Chen, C., Kolmogorov, V., Yan, Z., Metaxas, D., & Lampert, C. (2013).
Computing the M most probable modes of a graphical model (Vol. 31, pp. 161–169).
Presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence,
Scottsdale, AZ, United States: JMLR.'
chicago: Chen, Chao, Vladimir Kolmogorov, Zhu Yan, Dimitris Metaxas, and Christoph
Lampert. “Computing the M Most Probable Modes of a Graphical Model,” 31:161–69.
JMLR, 2013.
ieee: 'C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, and C. Lampert, “Computing the
M most probable modes of a graphical model,” presented at the AISTATS: Conference
on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States, 2013,
vol. 31, pp. 161–169.'
ista: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M
most probable modes of a graphical model. AISTATS: Conference on Uncertainty
in Artificial Intelligence, JMLR: W&CP, vol. 31, 161–169.'
mla: Chen, Chao, et al. Computing the M Most Probable Modes of a Graphical Model.
Vol. 31, JMLR, 2013, pp. 161–69.
short: C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013,
pp. 161–169.
conference:
end_date: 2013-05-01
location: Scottsdale, AZ, United States
name: ' AISTATS: Conference on Uncertainty in Artificial Intelligence'
start_date: 2013-04-29
date_created: 2018-12-11T12:00:14Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T07:00:35Z
day: '01'
department:
- _id: HeEd
- _id: VlKo
- _id: ChLa
intvolume: ' 31'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://jmlr.org/proceedings/papers/v31/chen13a.html
month: '01'
oa: 1
oa_version: None
page: 161 - 169
publication_status: published
publisher: JMLR
publist_id: '3846'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing the M most probable modes of a graphical model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 31
year: '2013'
...
---
_id: '2272'
abstract:
- lang: eng
text: "We consider Conditional Random Fields (CRFs) with pattern-based potentials
defined on a chain. In this model the energy of a string (labeling) x1...xn is
the sum of terms over intervals [i,j] where each term is non-zero only if the
substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally
applied to many sequence tagging problems.\r\nWe present efficient algorithms
for the three standard inference tasks in a CRF, namely computing (i) the partition
function, (ii) marginals, and (iii) computing the MAP. Their complexities are
respectively O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined
length of input patterns, ℓmax is the maximum length of a pattern, and D is the
input alphabet. This improves on the previous algorithms of (Ye et al., 2009)
whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where
|Γ| is the number of input patterns.\r\nIn addition, we give an efficient algorithm
for sampling. Finally, we consider the case of non-positive weights. (Komodakis
& Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present
a modification that has the same worst-case complexity but can beat it in the
best case. "
alternative_title:
- JMLR
article_processing_charge: No
author:
- first_name: Rustem
full_name: Takhanov, Rustem
id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87
last_name: Takhanov
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Takhanov R, Kolmogorov V. Inference algorithms for pattern-based CRFs on sequence
data. In: ICML’13 Proceedings of the 30th International Conference on International.
Vol 28. ML Research Press; 2013:145-153.'
apa: 'Takhanov, R., & Kolmogorov, V. (2013). Inference algorithms for pattern-based
CRFs on sequence data. In ICML’13 Proceedings of the 30th International Conference
on International (Vol. 28, pp. 145–153). Atlanta, GA, USA: ML Research Press.'
chicago: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based
CRFs on Sequence Data.” In ICML’13 Proceedings of the 30th International Conference
on International, 28:145–53. ML Research Press, 2013.
ieee: R. Takhanov and V. Kolmogorov, “Inference algorithms for pattern-based CRFs
on sequence data,” in ICML’13 Proceedings of the 30th International Conference
on International, Atlanta, GA, USA, 2013, vol. 28, no. 3, pp. 145–153.
ista: 'Takhanov R, Kolmogorov V. 2013. Inference algorithms for pattern-based CRFs
on sequence data. ICML’13 Proceedings of the 30th International Conference on
International. ICML: International Conference on Machine Learning, JMLR, vol.
28, 145–153.'
mla: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based
CRFs on Sequence Data.” ICML’13 Proceedings of the 30th International Conference
on International, vol. 28, no. 3, ML Research Press, 2013, pp. 145–53.
short: R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International
Conference on International, ML Research Press, 2013, pp. 145–153.
conference:
end_date: 2013-06-21
location: Atlanta, GA, USA
name: 'ICML: International Conference on Machine Learning'
start_date: 2013-06-16
date_created: 2018-12-11T11:56:41Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2023-10-17T09:51:32Z
day: '01'
department:
- _id: VlKo
intvolume: ' 28'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://proceedings.mlr.press/v28/takhanov13.pdf?CFID=105472548&CFTOKEN=5c5859b5d97b4439-27B4AC58-BA92-A964-B598CAACEE6CC515
month: '06'
oa: 1
oa_version: Submitted Version
page: 145 - 153
publication: ICML'13 Proceedings of the 30th International Conference on International
publication_status: published
publisher: ML Research Press
publist_id: '4672'
quality_controlled: '1'
related_material:
record:
- id: '1794'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Inference algorithms for pattern-based CRFs on sequence data
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 28
year: '2013'
...
---
_id: '2274'
abstract:
- lang: eng
text: "Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto'92) as
protection to a shared resource. The basic idea is to ask the service requestor
to dedicate some non-trivial amount of computational work to every request. The
original applications included prevention of spam and protection against denial
of service attacks. More recently, PoWs have been used to prevent double spending
in the Bitcoin digital currency system.\r\n\r\nIn this work, we put forward an
alternative concept for PoWs -- so-called proofs of space (PoS), where a service
requestor must dedicate a significant amount of disk space as opposed to computation.
We construct secure PoS schemes in the random oracle model, using graphs with
high "pebbling complexity" and Merkle hash-trees. "
author:
- first_name: Stefan
full_name: Dziembowski, Stefan
last_name: Dziembowski
- first_name: Sebastian
full_name: Faust, Sebastian
last_name: Faust
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of Space.
IST Austria; 2013.
apa: Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2013). Proofs
of Space. IST Austria.
chicago: Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof
Z Pietrzak. Proofs of Space. IST Austria, 2013.
ieee: S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, Proofs of
Space. IST Austria, 2013.
ista: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space,
IST Austria,p.
mla: Dziembowski, Stefan, et al. Proofs of Space. IST Austria, 2013.
short: S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space,
IST Austria, 2013.
date_created: 2018-12-11T11:56:42Z
date_published: 2013-11-28T00:00:00Z
date_updated: 2024-03-20T08:31:49Z
day: '28'
ddc:
- '530'
department:
- _id: VlKo
- _id: KrPi
file:
- access_level: open_access
checksum: 37b61637b62fc079d9141c59d9f1a94f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:11Z
date_updated: 2020-07-14T12:45:36Z
file_id: '5197'
file_name: IST-2016-671-v1+1_796.pdf
file_size: 405870
relation: main_file
file_date_updated: 2020-07-14T12:45:36Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication_status: published
publisher: IST Austria
publist_id: '4670'
pubrep_id: '671'
related_material:
record:
- id: '1675'
relation: later_version
status: public
scopus_import: 1
status: public
title: Proofs of Space
type: report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2930'
abstract:
- lang: eng
text: "In this paper we investigate k-submodular functions. This natural family
of discrete functions includes submodular and bisubmodular functions as the special
cases k = 1 and k = 2 respectively.\r\n\r\nIn particular we generalize the known
Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts
that the minimum of the (bi)submodular function can be found by solving a maximization
problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron,
prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm
to construct the vertices of the polyhedron.\r\n"
acknowledgement: "We would like to thank Andrei Krokhin for encourag- ing our cooperation,
for helpful discussions, and for his critical reading of the manuscript.\r\n"
alternative_title:
- LNCS
author:
- first_name: Anna
full_name: Huber, Anna
last_name: Huber
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Huber A, Kolmogorov V. Towards minimizing k-submodular functions. In: Vol
7422. Springer; 2012:451-462. doi:10.1007/978-3-642-32147-4_40'
apa: 'Huber, A., & Kolmogorov, V. (2012). Towards minimizing k-submodular functions
(Vol. 7422, pp. 451–462). Presented at the ISCO: International Symposium on Combinatorial
Optimization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-642-32147-4_40'
chicago: Huber, Anna, and Vladimir Kolmogorov. “Towards Minimizing K-Submodular
Functions,” 7422:451–62. Springer, 2012. https://doi.org/10.1007/978-3-642-32147-4_40.
ieee: 'A. Huber and V. Kolmogorov, “Towards minimizing k-submodular functions,”
presented at the ISCO: International Symposium on Combinatorial Optimization,
Athens, Greece, 2012, vol. 7422, pp. 451–462.'
ista: 'Huber A, Kolmogorov V. 2012. Towards minimizing k-submodular functions. ISCO:
International Symposium on Combinatorial Optimization, LNCS, vol. 7422, 451–462.'
mla: Huber, Anna, and Vladimir Kolmogorov. Towards Minimizing K-Submodular Functions.
Vol. 7422, Springer, 2012, pp. 451–62, doi:10.1007/978-3-642-32147-4_40.
short: A. Huber, V. Kolmogorov, in:, Springer, 2012, pp. 451–462.
conference:
end_date: 2012-04-21
location: Athens, Greece
name: 'ISCO: International Symposium on Combinatorial Optimization'
start_date: 2012-04-19
date_created: 2018-12-11T12:00:24Z
date_published: 2012-04-01T00:00:00Z
date_updated: 2021-01-12T07:00:46Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-642-32147-4_40
intvolume: ' 7422'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1309.5469
month: '04'
oa: 1
oa_version: Preprint
page: 451 - 462
publication_status: published
publisher: Springer
publist_id: '3806'
quality_controlled: '1'
scopus_import: 1
status: public
title: Towards minimizing k-submodular functions
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7422
year: '2012'
...
---
_id: '2928'
abstract:
- lang: eng
text: ' This paper addresses the problem of approximate MAP-MRF inference in
general graphical models. Following [36], we consider a family of linear programming
relaxations of the problem where each relaxation is specified by a set of nested
pairs of factors for which the marginalization constraint needs to be enforced.
We develop a generalization of the TRW-S algorithm [9] for this problem, where
we use a decomposition into junction chains, monotonic w.r.t. some ordering on
the nodes. This generalizes the monotonic chains in [9] in a natural way. We also
show how to deal with nested factors in an efficient way. Experiments show an
improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on
a number of computer vision and natural language processing problems. '
article_processing_charge: No
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Thomas
full_name: Schoenemann, Thomas
last_name: Schoenemann
citation:
ama: Kolmogorov V, Schoenemann T. Generalized sequential tree-reweighted message
passing. arXiv. 2012.
apa: Kolmogorov, V., & Schoenemann, T. (2012). Generalized sequential tree-reweighted
message passing. arXiv. ArXiv.
chicago: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted
Message Passing.” ArXiv. ArXiv, 2012.
ieee: V. Kolmogorov and T. Schoenemann, “Generalized sequential tree-reweighted
message passing,” arXiv. ArXiv, 2012.
ista: Kolmogorov V, Schoenemann T. 2012. Generalized sequential tree-reweighted
message passing. arXiv, .
mla: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted
Message Passing.” ArXiv, ArXiv, 2012.
short: V. Kolmogorov, T. Schoenemann, ArXiv (2012).
date_created: 2018-12-11T12:00:23Z
date_published: 2012-05-29T00:00:00Z
date_updated: 2021-01-12T07:00:45Z
day: '29'
department:
- _id: VlKo
external_id:
arxiv:
- '1205.6352'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1205.6352
month: '05'
oa: 1
oa_version: Preprint
page: '16'
publication: arXiv
publication_status: published
publisher: ArXiv
publist_id: '3809'
status: public
title: Generalized sequential tree-reweighted message passing
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '2931'
abstract:
- lang: eng
text: "In this paper, we present a new approach for establishing correspondences
between sparse image features related by an unknown nonrigid mapping and corrupted
by clutter and occlusion, such as points extracted from images of different instances
of the same object category. We formulate this matching task as an energy minimization
problem by defining an elaborate objective function of the appearance and the
spatial arrangement of the features. Optimization of this energy is an instance
of graph matching, which is in general an NP-hard problem. We describe a novel
graph matching optimization technique, which we refer to as dual decomposition
(DD), and demonstrate on a variety of examples that this method outperforms existing
graph matching algorithms. In the majority of our examples, DD is able to find
the global minimum within a minute. The ability to globally optimize the objective
allows us to accurately learn the parameters of our matching model from training
examples. We show on several matching tasks that our learned model yields results
superior to those of state-of-the-art methods.\r\n"
acknowledgement: This research was funded in part by Microsoft Research.
author:
- first_name: Lorenzo
full_name: Torresani, Lorenzo
last_name: Torresani
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
citation:
ama: Torresani L, Kolmogorov V, Rother C. A dual decomposition approach to feature
correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence.
2012;35(2):259-271. doi:10.1109/TPAMI.2012.105
apa: Torresani, L., Kolmogorov, V., & Rother, C. (2012). A dual decomposition
approach to feature correspondence. IEEE Transactions on Pattern Analysis and
Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2012.105
chicago: Torresani, Lorenzo, Vladimir Kolmogorov, and Carsten Rother. “A Dual Decomposition
Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis
and Machine Intelligence. IEEE, 2012. https://doi.org/10.1109/TPAMI.2012.105.
ieee: L. Torresani, V. Kolmogorov, and C. Rother, “A dual decomposition approach
to feature correspondence,” IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 35, no. 2. IEEE, pp. 259–271, 2012.
ista: Torresani L, Kolmogorov V, Rother C. 2012. A dual decomposition approach to
feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence.
35(2), 259–271.
mla: Torresani, Lorenzo, et al. “A Dual Decomposition Approach to Feature Correspondence.”
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35,
no. 2, IEEE, 2012, pp. 259–71, doi:10.1109/TPAMI.2012.105.
short: L. Torresani, V. Kolmogorov, C. Rother, IEEE Transactions on Pattern Analysis
and Machine Intelligence 35 (2012) 259–271.
date_created: 2018-12-11T12:00:24Z
date_published: 2012-05-08T00:00:00Z
date_updated: 2021-01-12T07:00:46Z
day: '08'
department:
- _id: VlKo
doi: 10.1109/TPAMI.2012.105
intvolume: ' 35'
issue: '2'
language:
- iso: eng
month: '05'
oa_version: None
page: 259 - 271
project:
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_status: published
publisher: IEEE
publist_id: '3805'
quality_controlled: '1'
scopus_import: 1
status: public
title: A dual decomposition approach to feature correspondence
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2012'
...
---
_id: '3117'
abstract:
- lang: eng
text: We consider the problem of minimizing a function represented as a sum of submodular
terms. We assume each term allows an efficient computation of exchange capacities.
This holds, for example, for terms depending on a small number of variables, or
for certain cardinality-dependent terms. A naive application of submodular minimization
algorithms would not exploit the existence of specialized exchange capacity subroutines
for individual terms. To overcome this, we cast the problem as a submodular flow
(SF) problem in an auxiliary graph in such a way that applying most existing SF
algorithms would rely only on these subroutines. We then explore in more detail
Iwata's capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular,
we show how to improve its complexity in the case when the function contains cardinality-dependent
terms.
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Minimizing a sum of submodular functions. Discrete Applied
Mathematics. 2012;160(15):2246-2258. doi:10.1016/j.dam.2012.05.025
apa: Kolmogorov, V. (2012). Minimizing a sum of submodular functions. Discrete
Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2012.05.025
chicago: Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete
Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2012.05.025.
ieee: V. Kolmogorov, “Minimizing a sum of submodular functions,” Discrete Applied
Mathematics, vol. 160, no. 15. Elsevier, pp. 2246–2258, 2012.
ista: Kolmogorov V. 2012. Minimizing a sum of submodular functions. Discrete Applied
Mathematics. 160(15), 2246–2258.
mla: Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete
Applied Mathematics, vol. 160, no. 15, Elsevier, 2012, pp. 2246–58, doi:10.1016/j.dam.2012.05.025.
short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 2246–2258.
date_created: 2018-12-11T12:01:29Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2021-01-12T07:41:11Z
day: '01'
department:
- _id: VlKo
doi: 10.1016/j.dam.2012.05.025
intvolume: ' 160'
issue: '15'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1006.1990
month: '10'
oa: 1
oa_version: Preprint
page: 2246 - 2258
publication: Discrete Applied Mathematics
publication_status: published
publisher: Elsevier
publist_id: '3582'
quality_controlled: '1'
scopus_import: 1
status: public
title: Minimizing a sum of submodular functions
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 160
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.
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. Discrete
Applied Mathematics. 2012;160(4-5):416-426. doi:10.1016/j.dam.2011.10.026
apa: Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions.
Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026
chicago: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.”
Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2011.10.026.
ieee: V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” Discrete
Applied Mathematics, 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.”
Discrete Applied Mathematics, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26,
doi:10.1016/j.dam.2011.10.026.
short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.
date_created: 2018-12-11T12:02:18Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2023-02-23T11:04:49Z
day: '01'
department:
- _id: VlKo
doi: 10.1016/j.dam.2011.10.026
external_id:
arxiv:
- '1005.2305'
intvolume: ' 160'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 160
year: '2012'
...
---
_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. Approximating Marginals Using Discrete Energy Minimization.
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
date_created: 2018-12-11T12:01:31Z
date_published: 2012-06-30T00:00:00Z
date_updated: 2023-02-23T12:24:24Z
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: '5396'
abstract:
- lang: eng
text: We consider the problem of inference in agraphical 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 pair-wise terms
over a discretized domain. This allows the use of techniques originally devel-oped
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 out-perform the Bethe approximation. We also establish a link between the
Bethe free energy and submodular functions.
alternative_title:
- IST Austria Technical Report
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. IST Austria; 2012. doi:10.15479/AT:IST-2012-0003
apa: Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals
using discrete energy minimization. IST Austria. https://doi.org/10.15479/AT:IST-2012-0003
chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. Approximating
Marginals Using Discrete Energy Minimization. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0003.
ieee: F. Korc, V. Kolmogorov, and C. Lampert, Approximating marginals using discrete
energy minimization. IST Austria, 2012.
ista: Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete
energy minimization, IST Austria, 13p.
mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization.
IST Austria, 2012, doi:10.15479/AT:IST-2012-0003.
short: F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete
Energy Minimization, IST Austria, 2012.
date_created: 2018-12-12T11:39:06Z
date_published: 2012-07-23T00:00:00Z
date_updated: 2023-02-23T11:13:22Z
day: '23'
ddc:
- '000'
department:
- _id: VlKo
- _id: ChLa
doi: 10.15479/AT:IST-2012-0003
file:
- access_level: open_access
checksum: 7e0ba85ad123b13223aaf6cdde2d288c
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:29Z
date_updated: 2020-07-14T12:46:44Z
file_id: '5490'
file_name: IST-2012-0003_IST-2012-0003.pdf
file_size: 618744
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '13'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '36'
related_material:
record:
- id: '3124'
relation: earlier_version
status: public
status: public
title: Approximating marginals using discrete energy minimization
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...