Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing
Bogdan Savchynskyy, Stefan Schmidt, Joerg Kappes, Christoph Schnoerr
Abstract:
We consider the linear programming relaxation of an energy minimization problem for Markov Random Fields. The dual objective of this problem can be treated as a concave and unconstrained, but non-smooth function. The idea of smoothing the objective prior to optimization was recently proposed in a series of papers. Some of them suggested the idea to decrease the amount of smoothing (so called temperature) while getting closer to the optimum. However, no theoretical substantiation was provided. We propose an adaptive smoothing diminishing algorithm based on the duality gap between relaxed primal and dual objectives and demonstrate the efficiency of our approach with a smoothed version of Sequential Tree-Reweighted Message Passing (TRW-S) algorithm. The strategy is applicable to other algorithms as well, avoids adhoc tuning of the smoothing during iterations, and provably guarantees convergence to the optimum.
Keywords:
Pages: 746-755
PS Link:
PDF Link: /papers/12/p746-savchynskyy.pdf
BibTex:
@INPROCEEDINGS{Savchynskyy12,
AUTHOR = "Bogdan Savchynskyy and Stefan Schmidt and Joerg Kappes and Christoph Schnoerr",
TITLE = "Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "746--755"
}


hosted by DSL   •   site info   •   help