  Conditional random fields (CRFs) provide a powerful tool for structured
prediction, but cast significant challenges in both the learning and inference
steps. Approximation techniques are widely used in both steps, which should be
considered jointly to guarantee good performance (a.k.a. "inferning").
Perturb-and-MAP models provide a promising alternative to CRFs, but require
global combinatorial optimization and hence they are usable only on specific
models. In this work, we present a new Local Perturb-and-MAP (locPMAP)
framework that replaces the global optimization with a local optimization by
exploiting our observed connection between locPMAP and the pseudolikelihood of
the original CRF model. We test our approach on three different vision tasks
and show that our method achieves consistently improved performance over other
approximate inference techniques optimized to a pseudolikelihood objective.
Additionally, we demonstrate that we can integrate our method in the fully
convolutional network framework to increase our model's complexity. Finally,
our observed connection between locPMAP and the pseudolikelihood leads to a
novel perspective for understanding and using pseudolikelihood.
