More data means less inference: A pseudo-max approach to structured learning
David A. Sontag, Ofer Meshi, Amir Globerson, Tommi Jaakkola · 2010
The problem of learning to predict structured labels is of key importance in many applications. However, for general graph structure both learning and inference are intractable. Here we show that it is possible to circumvent this difficulty when the distribution of training examples is rich enough, via a method similar in spirit to pseudo-likelihood. We show that our new method achieves consistency, and illustrate empirically that it indeed approaches the performance of exact methods when sufficiently large training sets are used. Many prediction problems in machine learning applications are structured prediction tasks. For example, in protein folding we are given a protein sequence and the goal is to predict the protein’s native structure [14]. In parsing for natural language processing, we are given a sentence and the goal is to predict the most likely parse tree [2]. In these and many other applications, we can formalize the structured prediction problem as taking an input x (e.g., primary sequence, sentence) and predicting y (e.g., structure, parse) according to y = arg maxˆy∈Y θ · φ(x, ˆy), where φ(x, y) is a function that maps any input and a candidate assignment to a feature vector, Y denotes the space of all possible