Partial Inference in Structured Prediction

In the past decades, various forms of structured prediction have been used extensively across many fields, including computer vision, natural language processing, network analysis, computational chemistry, to name a few. In these fields, examples of structured prediction problems include foreground / background detection in a digital image [Nowozin et al., 2011], grammatical partof-speech tagging in an English sentence [Weiss and Taskar, 2010], community identification and clustering in social networks [Kelley et al., 2012], and identifying representative subsets of millions of chemical compounds [Downs and Barnard, 2002]. On a higher level, all of the structured prediction inference problems mentioned above seek to maximize some score function over the space of labels. In other words, a common goal in inference tasks is to recover the label of each entity, such that the prediction matches the observation as much as possible. Suppose we represent the structured prediction inference problem using an undirected graph G = (V, E), where each node represents an entity, and each edge represents the interaction between two nodes.