A Linear Programming Formulation for Global Inference in Natural Language Tasks （自然语言任务中全局推理的线性规划公式）

1、A Linear Programming Formulation for Global Inference in Natural Language Tasks,Dan RothWen-tau Yih Department of Computer Science University of Illinois at Urbana-Champaign,Page 2,View of Solving NLP Problems,Page 3,Weaknesses of Pipeline Model,Propagation of errors Bi-Directional interactions betw

2、een stages,Occasionally, later stage problems are easier.,Upstream mistakes will not be corrected.,Page 4,Global Inference with Classifiers,Classifiers (for components) are trained or given in advance. There are constraints on classifiers labels (which may be known during training or only known duri

3、ng testing). The inference procedure attempts to make the best global assignment, given the local predictions and the constraints,Page 5,Ideal Inference,Page 6,Inference Procedure,Inference with classifiers is not a new idea. On sequential constraint structure: HMM, PMM, CRFLafferty et al., CSCLPuny

4、akanok xP2=NP+ xP2=1 xP3=NP+ xP3=1; xP4=NP+ xP4=1,i, j xPhrase_i = Class_j = 1,Non-overlapping Constraints: xP1= + xP3=1 xP2= + xP3= + xP4=2,Page 11,LP Formulation,Generate one integer linear program per sentence.,Page 12,Entity/Relation Recognition,John was murdered at JFK after his assassin, Kevin

5、 Identify:,John was murdered at JFK after his assassin, Kevin ,location,person,person,Kill (X, Y),Identify named entities Identify relations between entities Exploit mutual dependencies between named entities and relations to yield a coherent global prediction,Page 13,Problem Setting,R12,R21,R23,R32

6、,R13,R31,The relation between each pair of entities is represented by a relation variable; most of them are null.,The goal is to assign labels to these E and R variables.,Constraints: (R12 = kill) (E1 = person) (E2 = person) (R12 = headquarter) (E1 = organization) (E2 = location) ,Page 14,LP Formula

7、tion Indicator Variables,For each variable xE1 = per, xE1 = loc, , xR12 = kill, xR12 = born_in, , xR12 = , 0,1 For each pair of variables on an edge xR12 = kill, E1 = per, xR12 = kill, E1 = loc , , xR12 = , E1 = per, xR12 = , E1 = loc , , xR32 = , E2 = per, xR32 = , E2 = loc , 0,1,Page 15,LP Formula

8、tion Cost Function,Assignment cost cE1 = per xE1 = per + cE1 = loc xE1 = loc + + cR12 = kill xR12 = kill + + cR12 = xR12 = + ,Constraint cost cR12 = kill, E1 = per xR12 = kill, E1 = per + cR12 = kill, E1 = loc xR12 = kill, E1 = loc + + cR12 = , E1 = loc xR12 = , E1 = loc + ,Costs are given by classi

9、fiers.,-,Total cost = Assignment cost + Constraint cost,Page 16,NodeEdge Consistency Constraints,Binary Constraints Unique-label Constraints,LP Formulation Linear Constraints,Subject to:,NodeEdge Consistency Constraints,Page 17,LP Formulation,Generate one integer linear program per sentence.,Page 18

10、,Experiments Data,Methodology: 1,437 sentences from TREC data; 5,336 entities; 19,048 pairs of potential relations.,Page 19,Experimental Results F1,Entity Predictions,Relation Predictions,Improvement compared to the basic (w/o inference) and pipeline (entityrelation) models Quality of decisions is e

11、nhanced No “stupid mistakes” that violate global constraints,Page 20,Decision-time Constraint,Constraints may be known only in decision time. Question Answering: “Who killed JFK?” Find “kill” relation in candidate sentences,Find the arguments of the “kill” relation,Page 21,Computational Issues,Exhau

12、stive search wont work Even with a small number of variables and classes, the solution space is intractable n=20, k=5, 520 = 95,367,431,640,625 Heuristic search algorithms (e.g., beam search)? Do not guarantee optimal solutions In practice, may not be faster than ILP,Page 22,Generality (1/2),Linearc

13、onstraints can represent any Boolean function More components can be put in this framework Who killed whom? (determine arguments of the Kill relation) Entity1=Entity3 (co-ref classifier) Subj-Verb-Object constraints Able to handle non-sequential constraint structure E/R case has demonstrated this pr

14、operty,Page 23,Generality (2/2),Integer linear programming (ILP) is NP-hard. However, an ILP problem at this scale can be solved very quickly using commercial packages, such as CPLEX or Xpress-MP. CPLEX is able to solve a linear programming problem of 13 million variables within 5 minutes. Processing 20 sentences in a second for a named entity recognition task on P3-800MHz,Page 24,Current/Future Work,Handle stochastic (soft) constraints Example: If the relation is kill, the first argument is person with 0.95 probab