  In many structured prediction problems, complex relationships between
variables are compactly defined using graphical structures. The most prevalent
graphical prediction methods---probabilistic graphical models and large margin
methods---have their own distinct strengths but also possess significant
drawbacks. Conditional random fields (CRFs) are Fisher consistent, but they do
not permit integration of customized loss metrics into their learning process.
Large-margin models, such as structured support vector machines (SSVMs), have
the flexibility to incorporate customized loss metrics, but lack Fisher
consistency guarantees. We present adversarial graphical models (AGM), a
distributionally robust approach for constructing a predictor that performs
robustly for a class of data distributions defined using a graphical structure.
Our approach enjoys both the flexibility of incorporating customized loss
metrics into its design as well as the statistical guarantee of Fisher
consistency. We present exact learning and prediction algorithms for AGM with
time complexity similar to existing graphical models and show the practical
benefits of our approach with experiments.
