A Linear Programming Formulation for Global Inference in Natural Language Tasks

A Linear Programming Formulation for Global Inference in Natural Language Tasks Dan Roth Wen-tau Yih Department of Computer Science University of Illinois at Urbana-Champaign {danr, yih}@uiuc.edu Abstract Given a collection of discrete random variables representing outcomes of learned local predic- tors in natural language, e.g., named entities and relations, we seek an optimal global as- signment to the variables in the presence of general (non-sequential) constraints. Examples of these constraints include the type of argu- ments a relation can take, and the mutual activ- ity of different relations, etc. We develop a lin- ear programming formulation for this problem and evaluate it in the context of simultaneously learning named entities and relations. Our ap- proach allows us to efficiently incorporate do- main and task specific constraints at decision time, resulting in significant improvements in the accuracy and the “human-like” quality of the inferences. 1 Introduction Natural language decisions often depend on the out- comes of several different but mutually dependent predic- tions. These predictions must respect some constraints that could arise from the nature of the data or from do- main or task specific conditions. For example, in part-of- speech tagging, a sentence must have at least one verb, and cannot have three consecutive verbs. These facts can be used as constraints. In named entity recognition, “no entities can overlap” is a common constraint used in var- ious works (Tjong Kim Sang and De Meulder, 2003). Efficient solutions to problems of these sort have been given when the constraints on the predictors are sequen- tial (Dietterich, 2002). These solutions can be cate- gorized into the following two frameworks. Learning global models trains a probabilistic model under the con- straints imposed by the domain. Examples include varia- tions of HMMs, conditional models and sequential varia- tions of Markov random fields (Lafferty et al., 2001). The other framework, inference with classifiers (Roth, 2002), views maintaining constraints and learning classifiers as separate processes. Various local classifiers are trained without the knowledge of constraints. The predictions are taken as input on the inference procedure which then finds the best global prediction. In addition to the concep- tual simplicity of this approach, it also seems to perform better experimentally (Tjong Kim Sang and De Meulder, 2003). Typically, efficient inference procedures in both frame- works rely on dynamic programming (e.g., Viterbi), which works well in sequential data. However, in many important problems, the structure is more general, result- ing in computationally intractable inference. Problems of these sorts have been studied in computer vision, where inference is generally performed over low level measure- ments rather than over higher level predictors (Levin et al., 2002; Boykov et al., 2001). This work develops a novel inference with classifiers approach. Rather than being restricted on sequential data, we study a fairly general setting. The problem is defined in terms of a collection of discrete random variables rep- resenting binary relations and their arguments; we seek an optimal assignment to the variables in the presence of the constraints on the binary …

Content truncated to 500 words