On the Fundamental Limits of Exact Inference in Structured Prediction

Hanbyul Lee, Kevin Bello, Jean Honorio

Inference is a main task in structured prediction and it is naturally modeled with a graph. In the context of Markov random fields, noisy observations corresponding to nodes and ed…