  Learning structured models using maximum margin techniques has become an
indispensable tool for com- puter 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.
Typ- ically, 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.
