The Lazy Flipper: Efficient Depth-Limited Exhaustive Search in Discrete Graphical Models
Abstract
We propose a new exhaustive search algorithm for optimization in discrete graphical models. When pursued to the full search depth (typically intractable), it is guaranteed to converge to a global optimum, passing through a series of monotonously improving local optima that are guaranteed to be optimal within a given and increasing Hamming distance. For a search depth of 1, it specializes to ICM. Between these extremes, a tradeoff between approximation quality and runtime is established. We show this experimentally by improving approximations for the non-submodular models in the MRF benchmark [1] and Decision Tree Fields [2].
Cite
Text
Andres et al. "The Lazy Flipper: Efficient Depth-Limited Exhaustive Search in Discrete Graphical Models." European Conference on Computer Vision, 2012. doi:10.1007/978-3-642-33786-4_12Markdown
[Andres et al. "The Lazy Flipper: Efficient Depth-Limited Exhaustive Search in Discrete Graphical Models." European Conference on Computer Vision, 2012.](https://mlanthology.org/eccv/2012/andres2012eccv-lazy/) doi:10.1007/978-3-642-33786-4_12BibTeX
@inproceedings{andres2012eccv-lazy,
title = {{The Lazy Flipper: Efficient Depth-Limited Exhaustive Search in Discrete Graphical Models}},
author = {Andres, Björn and Kappes, Jörg H. and Beier, Thorsten and Köthe, Ullrich and Hamprecht, Fred A.},
booktitle = {European Conference on Computer Vision},
year = {2012},
pages = {154-166},
doi = {10.1007/978-3-642-33786-4_12},
url = {https://mlanthology.org/eccv/2012/andres2012eccv-lazy/}
}