Learning a Loopy Model Exactly

Andreas Christian Müller, Sven Behnke

2014

Abstract

Learning structured models using maximum margin techniques has become an indispensable tool for computer vision researchers, as many computer vision applications can be cast naturally as an image labeling problem. Pixel-based or superpixel-based conditional random fields are particularly popular examples. Typically, neighborhood graphs, which contain a large number of cycles, are used. As exact inference in loopy graphs is NP-hard in general, learning these models without approximations is usually deemed infeasible. In this work we show that, despite the theoretical hardness, it is possible to learn loopy models exactly in practical applications. To this end, we analyze the use of multiple approximate inference techniques together with cutting plane training of structural SVMs. We show that our proposed method yields exact solutions with an optimality guarantees in a computer vision application, for little additional computational cost. We also propose a dynamic caching scheme to accelerate training further, yielding runtimes that are comparable with approximate methods. We hope that this insight can lead to a reconsideration of the tractability of loopy models in computer vision.

Paper Citation

in Harvard Style

Christian Müller A. and Behnke S. (2014). Learning a Loopy Model Exactly . In Proceedings of the 9th International Conference on Computer Vision Theory and Applications - Volume 2: VISAPP, (VISIGRAPP 2014) ISBN 978-989-758-004-8, pages 337-344. DOI: 10.5220/0004674503370344

in Bibtex Style

@conference{visapp14,
author={Andreas Christian Müller and Sven Behnke},
title={Learning a Loopy Model Exactly},
booktitle={Proceedings of the 9th International Conference on Computer Vision Theory and Applications - Volume 2: VISAPP, (VISIGRAPP 2014)},
year={2014},
pages={337-344},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004674503370344},
isbn={978-989-758-004-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 9th International Conference on Computer Vision Theory and Applications - Volume 2: VISAPP, (VISIGRAPP 2014)
TI - Learning a Loopy Model Exactly
SN - 978-989-758-004-8
AU - Christian Müller A.
AU - Behnke S.
PY - 2014
SP - 337
EP - 344
DO - 10.5220/0004674503370344