  Graphical models for structured domains are powerful tools, but the
computational complexities of combinatorial prediction spaces can force
restrictions on models, or require approximate inference in order to be
tractable. Instead of working in a combinatorial space, we use hinge-loss
Markov random fields (HL-MRFs), an expressive class of graphical models with
log-concave density functions over continuous variables, which can represent
confidences in discrete predictions. This paper demonstrates that HL-MRFs are
general tools for fast and accurate structured prediction. We introduce the
first inference algorithm that is both scalable and applicable to the full
class of HL-MRFs, and show how to train HL-MRFs with several learning
algorithms. Our experiments show that HL-MRFs match or surpass the predictive
performance of state-of-the-art methods, including discrete models, in four
application domains.
