@online{DBLP:journals/corr/abs-1904-08080,
TITLE = {Bottleneck Potentials in {Markov Random Fields}},
AUTHOR = {Abbas, Ahmed and Swoboda, Paul},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1904.08080},
EPRINT = {1904.08080},
EPRINTTYPE = {arXiv},
YEAR = {2019},
ABSTRACT = {We consider general discrete Markov Random Fields(MRFs) with additional<br>bottleneck potentials which penalize the maximum (instead of the sum) over<br>local potential value taken by the MRF-assignment. Bottleneck potentials or<br>analogous constructions have been considered in (i) combinatorial optimization<br>(e.g. bottleneck shortest path problem, the minimum bottleneck spanning tree<br>problem, bottleneck function minimization in greedoids), (ii) inverse problems<br>with $L_{\infty}$-norm regularization, and (iii) valued constraint satisfaction<br>on the $(\min,\max)$-pre-semirings. Bottleneck potentials for general discrete<br>MRFs are a natural generalization of the above direction of modeling work to<br>Maximum-A-Posteriori (MAP) inference in MRFs. To this end, we propose MRFs<br>whose objective consists of two parts: terms that factorize according to (i)<br>$(\min,+)$, i.e. potentials as in plain MRFs, and (ii) $(\min,\max)$, i.e.<br>bottleneck potentials. To solve the ensuing inference problem, we propose<br>high-quality relaxations and efficient algorithms for solving them. We<br>empirically show efficacy of our approach on large scale seismic horizon<br>tracking problems.<br>},
}