Exact Inference in High-order Structured Prediction

Structured prediction has been widely used in various machine learning fields in the past 20 years, including applications like social network analysis, computer vision, molecular biology, natural language processing (NLP), among others. A common objective in these tasks is assigning / recovering labels, that is, given some possibly noisy observation, the goal is to output a group label for each entity in the task. In social network analysis, this could be detecting communities based on user profiles and preferences [Kelley et al., 2012]. In computer vision, researchers want the AI to decide whether a pixel is in the foreground or background [Nowozin et al., 2011]. In biology, it is sometimes desirable to cluster molecules by structural similarity [Nugent and Meila, 2010].