---
_id: '2518'
abstract:
- lang: eng
text: A class of valued constraint satisfaction problems (VCSPs) is characterised
by a valued constraint language, a fixed set of cost functions on a finite domain.
An instance of the problem is specified by a sum of cost functions from the language
with the goal to minimise the sum. We study which classes of finite-valued languages
can be solved exactly by the basic linear programming relaxation (BLP). Thapper
and Živný showed [20] that if BLP solves the language then the language admits
a binary commutative fractional polymorphism. We prove that the converse is also
true. This leads to a necessary and a sufficient condition which can be checked
in polynomial time for a given language. In contrast, the previous necessary and
sufficient condition due to [20] involved infinitely many inequalities. More recently,
Thapper and Živný [21] showed (using, in particular, a technique introduced in
this paper) that core languages that do not satisfy our condition are NP-hard.
Taken together, these results imply that a finite-valued language can either be
solved using Linear Programming or is NP-hard.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Kolmogorov V. The power of linear programming for finite-valued CSPs: A constructive
characterization. In: Vol 7965. Springer; 2013:625-636. doi:10.1007/978-3-642-39206-1_53'
apa: 'Kolmogorov, V. (2013). The power of linear programming for finite-valued CSPs:
A constructive characterization (Vol. 7965, pp. 625–636). Presented at the ICALP:
Automata, Languages and Programming, Riga, Latvia: Springer. https://doi.org/10.1007/978-3-642-39206-1_53'
chicago: 'Kolmogorov, Vladimir. “The Power of Linear Programming for Finite-Valued
CSPs: A Constructive Characterization,” 7965:625–36. Springer, 2013. https://doi.org/10.1007/978-3-642-39206-1_53.'
ieee: 'V. Kolmogorov, “The power of linear programming for finite-valued CSPs: A
constructive characterization,” presented at the ICALP: Automata, Languages and
Programming, Riga, Latvia, 2013, vol. 7965, no. 1, pp. 625–636.'
ista: 'Kolmogorov V. 2013. The power of linear programming for finite-valued CSPs:
A constructive characterization. ICALP: Automata, Languages and Programming, LNCS,
vol. 7965, 625–636.'
mla: 'Kolmogorov, Vladimir. The Power of Linear Programming for Finite-Valued
CSPs: A Constructive Characterization. Vol. 7965, no. 1, Springer, 2013, pp.
625–36, doi:10.1007/978-3-642-39206-1_53.'
short: V. Kolmogorov, in:, Springer, 2013, pp. 625–636.
conference:
end_date: 2013-07-12
location: Riga, Latvia
name: 'ICALP: Automata, Languages and Programming'
start_date: 2013-07-08
date_created: 2018-12-11T11:58:08Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2023-02-23T10:35:42Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-642-39206-1_53
external_id:
arxiv:
- '1207.7213'
intvolume: ' 7965'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1207.7213
month: '07'
oa: 1
oa_version: Preprint
page: 625 - 636
publication_status: published
publisher: Springer
publist_id: '4383'
quality_controlled: '1'
related_material:
record:
- id: '2271'
relation: later_version
status: public
scopus_import: 1
status: public
title: 'The power of linear programming for finite-valued CSPs: A constructive characterization'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7965
year: '2013'
...
---
_id: '2828'
abstract:
- lang: eng
text: 'We study the complexity of valued constraint satisfaction problems (VCSPs)
parametrized by a constraint language, a fixed set of cost functions over a finite
domain. An instance of the problem is specified by a sum of cost functions from
the language and the goal is to minimize the sum. Under the unique games conjecture,
the approximability of finite-valued VCSPs is well understood, see Raghavendra
[2008]. However, there is no characterization of finite-valued VCSPs, let alone
general-valued VCSPs, that can be solved exactly in polynomial time, thus giving
insights from a combinatorial optimization perspective. We consider the case of
languages containing all possible unary cost functions. In the case of languages
consisting of only {0, ∞}-valued cost functions (i.e., relations), such languages
have been called conservative and studied by Bulatov [2003, 2011] and recently
by Barto [2011]. Since we study valued languages, we call a language conservative
if it contains all finite-valued unary cost functions. The computational complexity
of conservative valued languages has been studied by Cohen et al. [2006] for languages
over Boolean domains, by Deineko et al. [2008] for {0, 1}-valued languages (a.k.a
Max-CSP), and by Takhanov [2010a] for {0, ∞}-valued languages containing all finite-valued
unary cost functions (a.k.a. Min-Cost-Hom). We prove a Schaefer-like dichotomy
theorem for conservative valued languages: if all cost functions in the language
satisfy a certain condition (specified by a complementary combination of STP and
MJN multimor-phisms), then any instance can be solved in polynomial time (via
a new algorithm developed in this article), otherwise the language is NP-hard.
This is the first complete complexity classification of general-valued constraint
languages over non-Boolean domains. It is a common phenomenon that complexity
classifications of problems over non-Boolean domains are significantly harder
than the Boolean cases. The polynomial-time algorithm we present for the tractable
cases is a generalization of the submodular minimization problem and a result
of Cohen et al. [2008]. Our results generalize previous results by Takhanov [2010a]
and (a subset of results) by Cohen et al. [2006] and Deineko et al. [2008]. Moreover,
our results do not rely on any computer-assisted search as in Deineko et al. [2008],
and provide a powerful tool for proving hardness of finite-valued and general-valued
languages.'
article_number: '10'
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Stanislav
full_name: Živný, Stanislav
last_name: Živný
citation:
ama: Kolmogorov V, Živný S. The complexity of conservative valued CSPs. Journal
of the ACM. 2013;60(2). doi:10.1145/2450142.2450146
apa: Kolmogorov, V., & Živný, S. (2013). The complexity of conservative valued
CSPs. Journal of the ACM. ACM. https://doi.org/10.1145/2450142.2450146
chicago: Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative
Valued CSPs.” Journal of the ACM. ACM, 2013. https://doi.org/10.1145/2450142.2450146.
ieee: V. Kolmogorov and S. Živný, “The complexity of conservative valued CSPs,”
Journal of the ACM, vol. 60, no. 2. ACM, 2013.
ista: Kolmogorov V, Živný S. 2013. The complexity of conservative valued CSPs. Journal
of the ACM. 60(2), 10.
mla: Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative
Valued CSPs.” Journal of the ACM, vol. 60, no. 2, 10, ACM, 2013, doi:10.1145/2450142.2450146.
short: V. Kolmogorov, S. Živný, Journal of the ACM 60 (2013).
date_created: 2018-12-11T11:59:48Z
date_published: 2013-04-02T00:00:00Z
date_updated: 2021-01-12T07:00:00Z
day: '02'
department:
- _id: VlKo
doi: 10.1145/2450142.2450146
external_id:
arxiv:
- '1110.2809'
intvolume: ' 60'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1110.2809
month: '04'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '3971'
quality_controlled: '1'
scopus_import: 1
status: public
title: The complexity of conservative valued CSPs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 60
year: '2013'
...
---
_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: '2270'
abstract:
- lang: eng
text: "Representation languages for coalitional games are a key research area in
algorithmic game theory. There is an inher-\r\nent tradeoff between how general
a language is, allowing it to capture more elaborate games, and how hard
\ it is computationally to optimize and solve such games. One prominent such
\ language is the simple yet expressive\r\nWeighted Graph Games (WGGs) representation
(Deng and Papadimitriou 1994), which maintains knowledge about synergies between
agents in the form of an edge weighted graph. We consider the problem of finding
\ the optimal coalition structure in WGGs. The agents in such games are vertices
in a graph, and the value of a coalition is the sum of the weights of the edges
present between coalition members. The optimal coalition structure is a partition
of the agents to coalitions, that maximizes the sum of utilities obtained by the
coalitions. We show that finding the optimal coalition structure is not
only hard for general graphs, but is also intractable for restricted families
such as planar graphs which are amenable for many other combinatorial problems.
\ We then provide algorithms with constant factor approximations for planar, minorfree
and bounded degree graphs."
arxiv: 1
author:
- first_name: Yoram
full_name: Bachrach, Yoram
last_name: Bachrach
- first_name: Pushmeet
full_name: Kohli, Pushmeet
last_name: Kohli
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Morteza
full_name: Zadimoghaddam, Morteza
last_name: Zadimoghaddam
citation:
ama: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. Optimal Coalition Structures
in Cooperative Graph Games. In: AAAI Press; 2013:81-87.'
apa: 'Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2013). Optimal
Coalition Structures in Cooperative Graph Games (pp. 81–87). Presented at the
AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States: AAAI
Press.'
chicago: Bachrach, Yoram, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghaddam.
“Optimal Coalition Structures in Cooperative Graph Games,” 81–87. AAAI Press,
2013.
ieee: 'Y. Bachrach, P. Kohli, V. Kolmogorov, and M. Zadimoghaddam, “Optimal Coalition
Structures in Cooperative Graph Games,” presented at the AAAI: Conference on Artificial
Intelligence, Bellevue, WA, United States, 2013, pp. 81–87.'
ista: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. 2013. Optimal Coalition
Structures in Cooperative Graph Games. AAAI: Conference on Artificial Intelligence,
81–87.'
mla: Bachrach, Yoram, et al. Optimal Coalition Structures in Cooperative Graph
Games. AAAI Press, 2013, pp. 81–87.
short: Y. Bachrach, P. Kohli, V. Kolmogorov, M. Zadimoghaddam, in:, AAAI Press,
2013, pp. 81–87.
conference:
end_date: 2013-07-18
location: Bellevue, WA, United States
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2013-07-14
date_created: 2018-12-11T11:56:41Z
date_published: 2013-12-31T00:00:00Z
date_updated: 2021-01-12T06:56:25Z
day: '31'
department:
- _id: VlKo
external_id:
arxiv:
- '1108.5248'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1108.5248
month: '12'
oa: 1
oa_version: None
page: 81-87
publication_status: published
publisher: AAAI Press
publist_id: '4674'
quality_controlled: '1'
status: public
title: Optimal Coalition Structures in Cooperative Graph Games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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: '2273'
abstract:
- lang: eng
text: We propose a new family of message passing techniques for MAP estimation in
graphical models which we call Sequential Reweighted Message Passing (SRMP). Special
cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster
Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation
is simpler than the original derivation of TRW-S, and does not involve a decomposition
into trees. This allows easy generalizations. We present such a generalization
for the case of higher-order graphical models, and test it on several real-world
problems with promising results.
author:
- first_name: Vladimir
full_name: Vladimir Kolmogorov
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Reweighted Message Passing Revisited. IST Austria; 2013.
apa: Kolmogorov, V. (2013). Reweighted message passing revisited. IST Austria.
chicago: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST
Austria, 2013.
ieee: V. Kolmogorov, Reweighted message passing revisited. IST Austria, 2013.
ista: Kolmogorov V. 2013. Reweighted message passing revisited, IST Austria,p.
mla: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST Austria,
2013.
short: V. Kolmogorov, Reweighted Message Passing Revisited, IST Austria, 2013.
date_created: 2018-12-11T11:56:42Z
date_published: 2013-09-22T00:00:00Z
date_updated: 2019-01-24T13:07:32Z
day: '22'
department:
- _id: VlKo
extern: 0
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1309.5655
month: '09'
oa: 1
publication_status: published
publisher: IST Austria
publist_id: '4671'
quality_controlled: 0
status: public
title: Reweighted message passing revisited
type: report
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: 2023-02-23T10:09:33Z
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: '2276'
abstract:
- lang: eng
text: The problem of minimizing the Potts energy function frequently occurs in computer
vision applications. One way to tackle this NP-hard problem was proposed by Kovtun
[19, 20]. It identifies a part of an optimal solution by running k maxflow computations,
where k is the number of labels. The number of “labeled” pixels can be significant
in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce
the runtime to O (log k) maxflow computations (or one parametric maxflow computation).
Furthermore, the output of our algorithm allows to speed-up the subsequent alpha
expansion for the unlabeled part, or can be used as it is for time-critical applications.
To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7]
for Tree Metrics . We also show a connection to k-submodular functions from combinatorial
optimization, and discuss k-submodular relaxations for general energy functions.
arxiv: 1
author:
- first_name: Igor
full_name: Gridchyn, Igor
id: 4B60654C-F248-11E8-B48F-1D18A9856A87
last_name: Gridchyn
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Gridchyn I, Kolmogorov V. Potts model, parametric maxflow and k-submodular
functions. In: IEEE; 2013:2320-2327. doi:10.1109/ICCV.2013.288'
apa: 'Gridchyn, I., & Kolmogorov, V. (2013). Potts model, parametric maxflow
and k-submodular functions (pp. 2320–2327). Presented at the ICCV: International
Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.288'
chicago: Gridchyn, Igor, and Vladimir Kolmogorov. “Potts Model, Parametric Maxflow
and k-Submodular Functions,” 2320–27. IEEE, 2013. https://doi.org/10.1109/ICCV.2013.288.
ieee: 'I. Gridchyn and V. Kolmogorov, “Potts model, parametric maxflow and k-submodular
functions,” presented at the ICCV: International Conference on Computer Vision,
Sydney, Australia, 2013, pp. 2320–2327.'
ista: 'Gridchyn I, Kolmogorov V. 2013. Potts model, parametric maxflow and k-submodular
functions. ICCV: International Conference on Computer Vision, 2320–2327.'
mla: Gridchyn, Igor, and Vladimir Kolmogorov. Potts Model, Parametric Maxflow
and k-Submodular Functions. IEEE, 2013, pp. 2320–27, doi:10.1109/ICCV.2013.288.
short: I. Gridchyn, V. Kolmogorov, in:, IEEE, 2013, pp. 2320–2327.
conference:
end_date: 2013-12-08
location: Sydney, Australia
name: 'ICCV: International Conference on Computer Vision'
start_date: 2013-12-01
date_created: 2018-12-11T11:56:43Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2021-01-12T06:56:28Z
day: '01'
department:
- _id: JoCs
- _id: VlKo
doi: 10.1109/ICCV.2013.288
external_id:
arxiv:
- '1310.1771'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1310.1771
month: '12'
oa: 1
oa_version: Preprint
page: 2320 - 2327
publication_status: published
publisher: IEEE
publist_id: '4668'
quality_controlled: '1'
status: public
title: Potts model, parametric maxflow and k-submodular functions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_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
arxiv: 1
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: '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: '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: '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: '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.
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. 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: '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'
...