Distributionally Robust Graphical Models

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 come with significant drawbacks. Conditional random fields (CRFs) are Fisher consistent, but they do not permit integration of customized loss functions into their learning process. Large-margin models, such as structured support vector machines (SSVM), 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 functions into its design as well as the statistical guarantee of Fisher consistency. We present exact learning and prediction algorithms for AGM requiring similar time complexity as existing graphical models and show its practical benefits in our experiments.