acl acl2013 acl2013-237 knowledge-graph by maker-knowledge-mining

237 acl-2013-Margin-based Decomposed Amortized Inference

Source: pdf

Author: Gourab Kundu ; Vivek Srikumar ; Dan Roth

Abstract: Given that structured output prediction is typically performed over entire datasets, one natural question is whether it is possible to re-use computation from earlier inference instances to speed up inference for future instances. Amortized inference has been proposed as a way to accomplish this. In this paper, first, we introduce a new amortized inference algorithm called the Margin-based Amortized Inference, which uses the notion of structured margin to identify inference problems for which previous solutions are provably optimal. Second, we introduce decomposed amortized inference, which is designed to address very large inference problems, where earlier amortization methods become less ef- fective. This approach works by decomposing the output structure and applying amortization piece-wise, thus increasing the chance that we can re-use previous solutions for parts of the output structure. These parts are then combined to a global coherent solution using Lagrangian relaxation. In our experiments, using the NLP tasks of semantic role labeling and entityrelation extraction, we demonstrate that with the margin-based algorithm, we need to call the inference engine only for a third of the test examples. Further, we show that the decomposed variant of margin-based amortized inference achieves a greater reduction in the number of inference calls.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Given that structured output prediction is typically performed over entire datasets, one natural question is whether it is possible to re-use computation from earlier inference instances to speed up inference for future instances. [sent-3, score-0.823]

2 Amortized inference has been proposed as a way to accomplish this. [sent-4, score-0.363]

3 In this paper, first, we introduce a new amortized inference algorithm called the Margin-based Amortized Inference, which uses the notion of structured margin to identify inference problems for which previous solutions are provably optimal. [sent-5, score-1.652]

4 Second, we introduce decomposed amortized inference, which is designed to address very large inference problems, where earlier amortization methods become less ef- fective. [sent-6, score-1.431]

5 This approach works by decomposing the output structure and applying amortization piece-wise, thus increasing the chance that we can re-use previous solutions for parts of the output structure. [sent-7, score-0.366]

6 In our experiments, using the NLP tasks of semantic role labeling and entityrelation extraction, we demonstrate that with the margin-based algorithm, we need to call the inference engine only for a third of the test examples. [sent-9, score-0.501]

7 Further, we show that the decomposed variant of margin-based amortized inference achieves a greater reduction in the number of inference calls. [sent-10, score-1.509]

8 In this paper, we focus on an inference technique called amortized inference (Srikumar et al. [sent-15, score-1.324]

9 , 2012), where previous solutions to inference problems are used to speed up new instances. [sent-16, score-0.492]

10 The main observation that leads to amortized inference is that, very often, for different examples of the same size, the structures that maximize the score are identical. [sent-17, score-1.015]

11 If we can efficiently identify that two inference problems have the same solution, then we can re-use previously computed structures for newer examples, thus giving us a speedup. [sent-18, score-0.551]

12 First, we describe a novel algorithm for amortized inference called margin-based amortization. [sent-20, score-0.996]

13 For a new inference problem, if this margin is larger than the sum of the decrease in the score of the previous prediction and any increase in the score of the second best one, then the previous solution will be the highest scoring one for the new problem. [sent-22, score-0.624]

14 Second, we argue that the idea of amortization is best exploited at the level of parts of the structures rather than the entire structure because we expect a much higher redundancy in the parts. [sent-25, score-0.369]

15 We introduce the notion of decomposed amortized inference, whereby we can attain a significant improvement in speedup by considering repeated sub-structures across the dataset and applying any amortized inference algorithm for the parts. [sent-26, score-1.823]

16 In these problems, the inference problem has been framed as an integer linear program (ILP). [sent-31, score-0.511]

17 We compare our methods with previous amortized inference methods and show that margin-based amortization combined with decomposition significantly outperforms existing methods. [sent-32, score-1.342]

18 The general setting consists of binary inference variables each of which is associated with a score. [sent-35, score-0.41]

19 The goal of inference is to find the highest scoring global assignment of the variables from a feasible set of assign- ments, which is defined by linear inequalities. [sent-36, score-0.55]

20 While efficient inference algorithms exist for special families of structures (like linear chains and trees), in the general case, inference can be computationally intractable. [sent-37, score-0.812]

21 One approach to deal with the computational complexity of inference is to use an off-the-shelf ILP solver for solving the inference problem. [sent-38, score-0.863]

22 Other approaches for solving inference include the use of cutting plane inference (Riedel, 2009), dual decomposition (Koo et al. [sent-40, score-0.958]

23 , 2012) introduced the notion of an amortized inference algorithm, defined as an inference algorithm that can use previous predictions to speed up inference time, thereby giving an amortized gain in inference time over the lifetime of the program. [sent-44, score-2.716]

24 The motivation for amortized inference comes from the observation that though the number of possible structures could be large, in practice, only a small number of these are ever seen in real data. [sent-45, score-1.015]

25 If we can efficiently characterize and identify inference instances that have the same solution, we can take advantage of previously performed computation without paying the high computational cost of inference. [sent-48, score-0.441]

26 We denote inference problems by the boldfaced letters p and q. [sent-53, score-0.463]

27 For a problem p, the goal of inference is to jointly assign values to the parts of the structure, which are represented by a collection of inference variables y ∈ {0, 1}n. [sent-54, score-0.817]

28 The inference problem is that of finding the feasible assignment to the structure which maximizes the dot product cTy. [sent-61, score-0.515]

29 An equivalence cslpaescst vofe integer lsin {eyar programs, d Aenno etqedui by [P], consists of ILPs which have the same number of inference variables and the same feasible set. [sent-65, score-0.652]

30 , 2012) introduced a set of amortized inference schemes, each of which provides a condition for a new ILP to have the same solu- tion as a previously seen problem. [sent-70, score-1.087]

31 We will briefly review one exact inference scheme introduced in that work. [sent-71, score-0.401]

32 Then the solution to q will be the same as that of p if the following condition holds for all inference variables: (2yp,i − 1)(cq,i − cp,i) ≥ 0. [sent-73, score-0.578]

33 Given a collection of previously solved problems P and a new inference problem q, TESTCONDITIONA(P, q) checks if the solution of the new problem is the same as that of some previously solved one and if so, SOLUTIONA(P, q) returns the solution. [sent-76, score-0.874]

34 3 Margin-based Amortization In this section, we will introduce a new method for amortizing inference costs over time. [sent-77, score-0.413]

35 The key observation that leads to this theorem stems from the structured margin δ for an inference problem p ∼ [P], which is defined as follows: δ =y∈Km[P]i,ny6=ypcpT(yp− y). [sent-78, score-0.685]

36 Suppose B is the solution yp for the inference problem p with coefficients cp, denoted by the red hyperplane, and A is the second-best assignment. [sent-82, score-0.658]

37 For a new coefficient vector cq, if the margin δ is greater than the sum of the decrease in the objective value of yp and the maximum increase in the objective of another solution (∆), then the solution to the new inference problem will still be yp. [sent-83, score-0.931]

38 Moving from cp to cq, consider the sum of the decrease in the value of the objective for the solution yp and ∆, the maximum change in objective value for an assignment that is not the solution. [sent-87, score-0.468]

39 This intuition is captured by our main theorem which provides a condition for problems p and q to have the same solution yp. [sent-90, score-0.431]

40 Let p denote an inference problem posed as an integer linear program belonging to an equivalence class [P] with optimal solution yp. [sent-92, score-0.766]

41 Let q ∼ [P] be another inference in≥sta cncye +in δth. [sent-96, score-0.363]

42 The margin-based amortization theorem provides a general, new amortized inference algorithm. [sent-103, score-1.444]

43 Given a new inference problem, we check whether the inequality (5) holds for any previously seen problems in the same equivalence class. [sent-104, score-0.71]

44 Even though the theorem provides a condition for two integer linear programs to have the same solution, checking the validity of the condition requires the computation of ∆, which in itself is another integer linear program. [sent-107, score-0.521]

45 In our experiments, we will define the relaxation for each problem individually and even with the relaxations, the inference algorithm based on the margin-based amortization theorem outperforms all previous amortized inference algorithms. [sent-112, score-1.947]

46 In this section, we address the following question: Can we take advantage of the redundancy in components of structures to extend amortization techniques to cases where the full structured output is not repeated? [sent-120, score-0.415]

47 By doing so, we can store partial computation for future inference problems. [sent-121, score-0.385]

48 This implies that many shorter sentences share the same structure, thus improving the performance of an amortized inference scheme for such inputs. [sent-125, score-1.026]

49 The goal of decomposed amortized inference is to extend this improvement to larger problems by increasing the size of equivalence classes. [sent-126, score-1.334]

50 To decompose an inference problem, we use the approach of Lagrangian Relaxation (Lemar´ echal, 2001) that has been used successfully for various NLP tasks (Chang and Collins, 2011; Rush and Collins, 2011). [sent-127, score-0.363]

51 The assumption is that in the absence thye c ≤on bstraints C2, the inference problem becomes computationally easier to solve. [sent-130, score-0.407]

52 First, it can make the resulting inference problem q0 easier to solve. [sent-147, score-0.407]

53 More importantly, removing constraints can also lead to the merging of multiple equivalence classes, leading to fewer, more populous equivalence classes. [sent-148, score-0.367]

54 Finally, removing constraints can decompose the inference problem q0 into smaller independent sub-problems {q1, q2, · · · } such that no constraint tshuabt- pisr oinb C1 hsa{sq qactive, v·a·r·ia}bsluecsh hfrthomat tnwooc odnifsfterraeinntt sets in the partition. [sent-149, score-0.538]

55 We can now define the decomposed amortized inference algorithm (Algorithm 1) that performs sub-gradient descent over the dual variables. [sent-154, score-1.246]

56 The input to the algorithm is a collection of previously solved problems with their solutions, a new inference problem q and an amortized inference scheme A (such as the margin-based amortization scheme). [sent-155, score-1.949]

57 Otherwise, Algorithm 1 Decomposed Amortized Inference Input: A collection of previously solved inference problems P, a new problem q, an amortized inference algorithm A. [sent-158, score-1.596]

58 endΛ i ←f end for return solution of q using a standard inference algorithm 18: end if + we initialize the dual variables Λ and try to obtain the solution iteratively. [sent-171, score-0.77]

59 We can apply the amortization scheme A to each subproblem to obtain a complete solution for the relaxed problem (lines 7–10). [sent-174, score-0.63]

60 If this solution satisfies the constraints C2 and complementary slackness conditions, then the solution is provably the maximum of the problem q. [sent-175, score-0.39]

61 In line 8 of the algorithm, we make multiple calls to the underlying amortized inference procedure to solve each sub-problem. [sent-178, score-1.038]

62 The marginbased scheme outperforms the amortized inference approaches from (Srikumar et al. [sent-182, score-0.999]

63 Decomposed amortized inference gives further gains in terms of re-using previous solutions. [sent-185, score-0.961]

64 1 Tasks We report the performance of inference on two NLP tasks: semantic role labeling and the task of extracting entities and relations from text. [sent-187, score-0.457]

65 In both cases, we used an existing formulation for structured inference and only modified the inference calls. [sent-188, score-0.772]

66 , 2008), where one inference prob- lem is generated for each verb and each inference variables encodes the decision that a given constituent in the sentence takes a specific role. [sent-200, score-0.773]

67 The scores for the inference variables are obtained from a classifier trained on the PropBank corpus. [sent-201, score-0.41]

68 For details about the formulations of the inference problem, please see (Punyakanok et al. [sent-203, score-0.363]

69 Recall from Section 3 that we need to define a relaxed version of the inference problem to efficiently compute ∆ for the margin-based approach. [sent-205, score-0.501]

70 For a problem instance with coefficients cq and cached coefficients cp, we take the sum of the highest n values of cq cp as our ∆, where n is the number of argument c candidates to be labeled. [sent-206, score-0.619]

71 To identify constraints that can be relaxed for the decomposed algorithm, we observe that most constraints are not predicate specific and apply for all predicates. [sent-207, score-0.373]

72 For every entity (which is identified by a constituent in the sentence), an inference variable is introduced for each entity type. [sent-214, score-0.363]

73 For each pair of constituents, an inference variable is introduced for each relation type. [sent-215, score-0.363]

74 Incorporating these natural constraints during inference were shown to improve performance significantly in (Roth and Yih, 2007). [sent-218, score-0.425]

75 We trained independent classifiers for entities and relations and framed the inference problem as in (Roth and Yih, 2007). [sent-219, score-0.466]

76 To compute the value of ∆ for the margin-based algorithm, for a new instance with coefficients cq and cached coefficients cp, we define ∆ to be the sum of all non-negative values of cq − cp. [sent-221, score-0.508]

77 For the decomposed inference algorithm, if the number of entities is less than 5, no decomposition is performed. [sent-222, score-0.621]

78 We relaxed the relation constraints that go across these two sets ofentities to obtain two independent inference problems. [sent-224, score-0.519]

79 , 2012), for a new inference problem p ∼ [P], we retrieve all inference problems mfr pom ∼ ∼th [eP d]a,t awbeas ree rthieavte belong trothe same equivalence class [P] as the test problem p and find the cached assignment y that has the highest score according to the coefficients of p. [sent-230, score-1.22]

80 In a second efficiency optimization, we pruned the database to remove redundant inference problems. [sent-233, score-0.363]

81 A problem is redundant if solution to that problem can be inferred from the other problems stored in the database that have the same solution and belong to the same equivalence class. [sent-234, score-0.536]

82 However, we note that the results presented in our work outperform all the previous amortization algorithms, including the approximate inference methods. [sent-241, score-0.678]

83 We report two performance metrics the percentage decrease in the number of ILP calls, and the percentage decrease in the wall-clock inference time. [sent-242, score-0.423]

84 For measuring time, since other aspects – of prediction (like feature extraction) are the same across all settings, we only measure the time taken for inference and ignore other aspects. [sent-245, score-0.392]

85 Applying the decomposed inference algorithm improves both the baseline and the margin-based approach. [sent-252, score-0.553]

86 Overall, however, the fewest number ofcalls to the solver is made when combining the decomposed inference algorithm with the margin-based scheme. [sent-253, score-0.665]

87 While the decomposed inference algorithm improves running time for SRL, it leads to a slight increase for the entityrelation problem. [sent-257, score-0.603]

88 Since this increase occurs in spite of a reduction in the number of solver calls, we believe that this aspect can be further improved with an efficient implementation of the decomposed inference algorithm. [sent-258, score-0.66]

89 To study the impact of amortization on running time, we modified our decomposition based inference algorithm to solve each sub-problem using the ILP solver instead of amortization. [sent-261, score-0.923]

90 Since we used the same im- plementation of the decomposition in all experiments, this shows that the decomposed inference algorithm crucially benefits from the underlying amortization scheme. [sent-282, score-0.934]

91 Decomposed amortized inference The decomposed amortized inference algorithm helps improve amortized inference in two ways. [sent-283, score-3.073]

92 First, since the number of structures is a function of its size, considering smaller sub-structures will allow us to cache inference problems that cover a larger subset of the space of possible sub-structures. [sent-284, score-0.538]

93 7 Conclusion Amortized inference takes advantage of the regularities in structured output to re-use previous computation and improve running time over the lifetime of a structured output predictor. [sent-290, score-0.51]

94 In this paper, we have described two approaches for amortizing inference costs over datasets. [sent-291, score-0.413]

95 The first, called the margin-based amortized inference, is a new, provably exact inference algorithm that uses the notion of a structured margin to identify previously solved problems whose solutions can be reused. [sent-292, score-1.404]

96 The second, called decomposed amortized inference, is a meta-algorithm over any amortized inference that takes advantage of previously computed sub-structures to provide further reductions in the number of inference calls. [sent-293, score-2.133]

97 We show via experiments that these methods individually give a reduction in the number of calls made to an inference engine for semantic role labeling and entityrelation extraction. [sent-294, score-0.545]

98 The importance of syntactic parsing and inference in semantic role labeling. [sent-373, score-0.39]

99 A linear programming formulation for global inference in natural language tasks. [sent-396, score-0.417]

100 Global inference for entity and relation identification via a linear programming formulation. [sent-402, score-0.417]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('amortized', 0.598), ('inference', 0.363), ('amortization', 0.315), ('theorem', 0.168), ('decomposed', 0.155), ('cq', 0.147), ('srikumar', 0.145), ('equivalence', 0.14), ('lagrangian', 0.123), ('ilp', 0.122), ('solution', 0.115), ('solver', 0.112), ('dual', 0.095), ('relaxed', 0.094), ('problems', 0.078), ('yp', 0.077), ('rush', 0.073), ('cached', 0.073), ('condition', 0.07), ('cp', 0.067), ('roth', 0.066), ('decomposition', 0.066), ('margin', 0.064), ('yih', 0.063), ('constraints', 0.062), ('relaxation', 0.061), ('punyakanok', 0.061), ('coefficients', 0.059), ('solved', 0.059), ('assignment', 0.056), ('previously', 0.056), ('structures', 0.054), ('provably', 0.054), ('feasible', 0.052), ('srl', 0.051), ('speedup', 0.051), ('solutions', 0.051), ('integer', 0.05), ('amortizing', 0.05), ('cpty', 0.05), ('cptyp', 0.05), ('cqtyp', 0.05), ('entityrelation', 0.05), ('objective', 0.05), ('variables', 0.047), ('structured', 0.046), ('calls', 0.045), ('problem', 0.044), ('ilps', 0.044), ('constraint', 0.044), ('cache', 0.043), ('inequality', 0.043), ('collins', 0.043), ('scheme', 0.038), ('entities', 0.037), ('partition', 0.035), ('algorithm', 0.035), ('cqi', 0.033), ('cqty', 0.033), ('haag', 0.033), ('lemar', 0.033), ('lifetime', 0.033), ('testconditiona', 0.033), ('typ', 0.033), ('solve', 0.032), ('maximization', 0.032), ('linear', 0.032), ('kate', 0.031), ('call', 0.031), ('decrease', 0.03), ('reduction', 0.03), ('labeling', 0.03), ('relaxations', 0.03), ('holds', 0.03), ('kundu', 0.029), ('oswald', 0.029), ('prediction', 0.029), ('schemes', 0.027), ('role', 0.027), ('programs', 0.027), ('shorter', 0.027), ('arl', 0.025), ('removing', 0.025), ('solving', 0.025), ('riedel', 0.024), ('subproblem', 0.024), ('plane', 0.024), ('sum', 0.023), ('repeated', 0.023), ('denote', 0.022), ('relaxing', 0.022), ('kennedy', 0.022), ('framed', 0.022), ('sponsored', 0.022), ('iarpa', 0.022), ('programming', 0.022), ('computation', 0.022), ('km', 0.022), ('afrl', 0.022), ('cutting', 0.022)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 237 acl-2013-Margin-based Decomposed Amortized Inference

Author: Gourab Kundu ; Vivek Srikumar ; Dan Roth

2 0.13989486 269 acl-2013-PLIS: a Probabilistic Lexical Inference System

Author: Eyal Shnarch ; Erel Segal-haLevi ; Jacob Goldberger ; Ido Dagan

Abstract: This paper presents PLIS, an open source Probabilistic Lexical Inference System which combines two functionalities: (i) a tool for integrating lexical inference knowledge from diverse resources, and (ii) a framework for scoring textual inferences based on the integrated knowledge. We provide PLIS with two probabilistic implementation of this framework. PLIS is available for download and developers of text processing applications can use it as an off-the-shelf component for injecting lexical knowledge into their applications. PLIS is easily configurable, components can be extended or replaced with user generated ones to enable system customization and further research. PLIS includes an online interactive viewer, which is a powerful tool for investigating lexical inference processes. 1 Introduction and background Semantic Inference is the process by which machines perform reasoning over natural language texts. A semantic inference system is expected to be able to infer the meaning of one text from the meaning of another, identify parts of texts which convey a target meaning, and manipulate text units in order to deduce new meanings. Semantic inference is needed for many Natural Language Processing (NLP) applications. For instance, a Question Answering (QA) system may encounter the following question and candidate answer (Example 1): Q: which explorer discovered the New World? A: Christopher Columbus revealed America. As there are no overlapping words between the two sentences, to identify that A holds an answer for Q, background world knowledge is needed to link Christopher Columbus with explorer and America with New World. Linguistic knowledge is also needed to identify that reveal and discover refer to the same concept. Knowledge is needed in order to bridge the gap between text fragments, which may be dissimilar on their surface form but share a common meaning. For the purpose of semantic inference, such knowledge can be derived from various resources (e.g. WordNet (Fellbaum, 1998) and others, detailed in Section 2.1) in a form which we denote as inference links (often called inference/entailment rules), each is an ordered pair of elements in which the first implies the meaning of the second. For instance, the link ship→vessel can be derived from tshtaen hypernym rkel sahtiiopn→ ovfe Wsseolr cdNanet b. Other applications can benefit from utilizing inference links to identify similarity between language expressions. In Information Retrieval, the user’s information need may be expressed in relevant documents differently than it is expressed in the query. Summarization systems should identify text snippets which convey the same meaning. Our work addresses a generic, application in- dependent, setting of lexical inference. We therefore adopt the terminology of Textual Entailment (Dagan et al., 2006), a generic paradigm for applied semantic inference which captures inference needs of many NLP applications in a common underlying task: given two textual fragments, termed hypothesis (H) and text (T), the task is to recognize whether T implies the meaning of H, denoted T→H. For instance, in a QA application, H reprTe→seHnts. Fthoer question, a innd a T Q a c aanpdpilidcaattei answer. pInthis setting, T is likely to hold an answer for the question if it entails the question. It is challenging to properly extract the needed inference knowledge from available resources, and to effectively utilize it within the inference process. The integration of resources, each has its own format, is technically complex and the quality 97 ProceedingSsof oiaf, th Beu 5lg1asrtia A,n Anuuaglu Mst 4ee-9tin 2g0 o1f3. th ?ec A20ss1o3ci Aastisoonci faotrio Cno fomrp Cuotamtipountaalti Loinnaglu Lisitnigcsu,is patigcess 97–102, Figure 1: PLIS schema - a text-hypothesis pair is processed by the Lexical Integrator which uses a set of lexical resources to extract inference chains which connect the two. The Lexical Inference component provides probability estimations for the validity of each level of the process. ofthe resulting inference links is often unknown in advance and varies considerably. For coping with this challenge we developed PLIS, a Probabilistic Lexical Inference System1 . PLIS, illustrated in Fig 1, has two main modules: the Lexical Integra- tor (Section 2) accepts a set of lexical resources and a text-hypothesis pair, and finds all the lexical inference relations between any pair of text term ti and hypothesis term hj, based on the available lexical relations found in the resources (and their combination). The Lexical Inference module (Section 3) provides validity scores for these relations. These term-level scores are used to estimate the sentence-level likelihood that the meaning of the hypothesis can be inferred from the text, thus making PLIS a complete lexical inference system. Lexical inference systems do not look into the structure of texts but rather consider them as bag ofterms (words or multi-word expressions). These systems are easy to implement, fast to run, practical across different genres and languages, while maintaining a competitive level of performance. PLIS can be used as a stand-alone efficient inference system or as the lexical component of any NLP application. PLIS is a flexible system, allowing users to choose the set of knowledge resources as well as the model by which inference 1The complete software package is available at http:// www.cs.biu.ac.il/nlp/downloads/PLIS.html and an online interactive viewer is available for examination at http://irsrv2. cs.biu.ac.il/nlp-net/PLIS.html. is done. PLIS can be easily extended with new knowledge resources and new inference models. It comes with a set of ready-to-use plug-ins for many common lexical resources (Section 2.1) as well as two implementation of the scoring framework. These implementations, described in (Shnarch et al., 2011; Shnarch et al., 2012), provide probability estimations for inference. PLIS has an interactive online viewer (Section 4) which provides a visualization of the entire inference process, and is very helpful for analysing lexical inference models and lexical resources usability. 2 Lexical integrator The input for the lexical integrator is a set of lexical resources and a pair of text T and hypothesis H. The lexical integrator extracts lexical inference links from the various lexical resources to connect each text term ti ∈ T with each hypothesis term hj ∈ H2. A lexical i∈nfTer wenicthe elianckh hinydpicoathteess a semantic∈ rHelation between two terms. It could be a directional relation (Columbus→navigator) or a bai ddiirreeccttiioonnaall one (car ←→ automobile). dSirinecceti knowledge resources vary lien) their representation methods, the lexical integrator wraps each lexical resource in a common plug-in interface which encapsulates resource’s inner representation method and exposes its knowledge as a list of inference links. The implemented plug-ins that come with PLIS are described in Section 2.1. Adding a new lexical resource and integrating it with the others only demands the implementation of the plug-in interface. As the knowledge needed to connect a pair of terms, ti and hj, may be scattered across few resources, the lexical integrator combines inference links into lexical inference chains to deduce new pieces of knowledge, such as Columbus −r −e −so −u −rc −e →2 −r −e −so −u −rc −e →1 navigator explorer. Therefore, the only assumption −t −he − l−e −x →ica elx integrator makes, regarding its input lexical resources, is that the inferential lexical relations they provide are transitive. The lexical integrator generates lexical infer- ence chains by expanding the text and hypothesis terms with inference links. These links lead to new terms (e.g. navigator in the above chain example and t0 in Fig 1) which can be further expanded, as all inference links are transitive. A transitivity 2Where iand j run from 1 to the length of the text and hypothesis respectively. 98 limit is set by the user to determine the maximal length for inference chains. The lexical integrator uses a graph-based representation for the inference chains, as illustrates in Fig 1. A node holds the lemma, part-of-speech and sense of a single term. The sense is the ordinal number of WordNet sense. Whenever we do not know the sense of a term we implement the most frequent sense heuristic.3 An edge represents an inference link and is labeled with the semantic relation of this link (e.g. cytokine→protein is larbeellaetdio wni othf tt hheis sW linokrd (Nee.gt .re clayttiookni hypernym). 2.1 Available plug-ins for lexical resources We have implemented plug-ins for the follow- ing resources: the English lexicon WordNet (Fellbaum, 1998)(based on either JWI, JWNL or extJWNL java APIs4), CatVar (Habash and Dorr, 2003), a categorial variations database, Wikipedia-based resource (Shnarch et al., 2009), which applies several extraction methods to derive inference links from the text and structure of Wikipedia, VerbOcean (Chklovski and Pantel, 2004), a knowledge base of fine-grained semantic relations between verbs, Lin’s distributional similarity thesaurus (Lin, 1998), and DIRECT (Kotlerman et al., 2010), a directional distributional similarity thesaurus geared for lexical inference. To summarize, the lexical integrator finds all possible inference chains (of a predefined length), resulting from any combination of inference links extracted from lexical resources, which link any t, h pair of a given text-hypothesis. Developers can use this tool to save the hassle of interfacing with the different lexical knowledge resources, and spare the labor of combining their knowledge via inference chains. The lexical inference model, described next, provides a mean to decide whether a given hypothesis is inferred from a given text, based on weighing the lexical inference chains extracted by the lexical integrator. 3 Lexical inference There are many ways to implement an inference model which identifies inference relations between texts. A simple model may consider the 3This disambiguation policy was better than considering all senses of an ambiguous term in preliminary experiments. However, it is a matter of changing a variable in the configuration of PLIS to switch between these two policies. 4http://wordnet.princeton.edu/wordnet/related-projects/ number of hypothesis terms for which inference chains, originated from text terms, were found. In PLIS, the inference model is a plug-in, similar to the lexical knowledge resources, and can be easily replaced to change the inference logic. We provide PLIS with two implemented baseline lexical inference models which are mathematically based. These are two Probabilistic Lexical Models (PLMs), HN-PLM and M-PLM which are described in (Shnarch et al., 2011; Shnarch et al., 2012) respectively. A PLM provides probability estimations for the three parts of the inference process (as shown in Fig 1): the validity probability of each inference chain (i.e. the probability for a valid inference relation between its endpoint terms) P(ti → hj), the probability of each hypothesis term to →b e i hnferred by the entire text P(T → hj) (term-level probability), eanntdir teh tee probability o hf the entire hypothesis to be inferred by the text P(T → H) (sentencelteov eble probability). HN-PLM describes a generative process by which the hypothesis is generated from the text. Its parameters are the reliability level of each of the resources it utilizes (that is, the prior probability that applying an arbitrary inference link derived from each resource corresponds to a valid inference). For learning these parameters HN-PLM applies a schema of the EM algorithm (Dempster et al., 1977). Its performance on the recognizing textual entailment task, RTE (Bentivogli et al., 2009; Bentivogli et al., 2010), are in line with the state of the art inference systems, including complex systems which perform syntactic analysis. This model is improved by M-PLM, which deduces sentence-level probability from term-level probabilities by a Markovian process. PLIS with this model was used for a passage retrieval for a question answering task (Wang et al., 2007), and outperformed state of the art inference systems. Both PLMs model the following prominent aspects of the lexical inference phenomenon: (i) considering the different reliability levels of the input knowledge resources, (ii) reducing inference chain probability as its length increases, and (iii) increasing term-level probability as we have more inference chains which suggest that the hypothesis term is inferred by the text. Both PLMs only need sentence-level annotations from which they derive term-level inference probabilities. To summarize, the lexical inference module 99 ?(? → ?) Figure 2: PLIS interactive viewer with Example 1 demonstrates knowledge integration of multiple inference chains and resource combination (additional explanations, which are not part of the demo, are provided in orange). provides the setting for interfacing with the lexical integrator. Additionally, the module provides the framework for probabilistic inference models which estimate term-level probabilities and integrate them into a sentence-level inference decision, while implementing prominent aspects of lexical inference. The user can choose to apply another inference logic, not necessarily probabilistic, by plugging a different lexical inference model into the provided inference infrastructure. 4 The PLIS interactive system PLIS comes with an online interactive viewer5 in which the user sets the parameters of PLIS, inserts a text-hypothesis pair and gets a visualization of the entire inference process. This is a powerful tool for investigating knowledge integration and lexical inference models. Fig 2 presents a screenshot of the processing of Example 1. On the right side, the user configures the system by selecting knowledge resources, adjusting their configuration, setting the transitivity limit, and choosing the lexical inference model to be applied by PLIS. After inserting a text and a hypothesis to the appropriate text boxes, the user clicks on the infer button and PLIS generates all lexical inference chains, of length up to the transitivity limit, that connect text terms with hypothesis terms, as available from the combination of the selected input re5http://irsrv2.cs.biu.ac.il/nlp-net/PLIS.html sources. Each inference chain is presented in a line between the text and hypothesis. PLIS also displays the probability estimations for all inference levels; the probability of each chain is presented at the end of its line. For each hypothesis term, term-level probability, which weighs all inference chains found for it, is given below the dashed line. The overall sentence-level probability integrates the probabilities of all hypothesis terms and is displayed in the box at the bottom right corner. Next, we detail the inference process of Example 1, as presented in Fig 2. In this QA example, the probability of the candidate answer (set as the text) to be relevant for the given question (the hypothesis) is estimated. When utilizing only two knowledge resources (WordNet and Wikipedia), PLIS is able to recognize that explorer is inferred by Christopher Columbus and that New World is inferred by America. Each one of these pairs has two independent inference chains, numbered 1–4, as evidence for its inference relation. Both inference chains 1 and 3 include a single inference link, each derived from a different relation of the Wikipedia-based resource. The inference model assigns a higher probability for chain 1since the BeComp relation is much more reliable than the Link relation. This comparison illustrates the ability of the inference model to learn how to differ knowledge resources by their reliability. Comparing the probability assigned by the in100 ference model for inference chain 2 with the probabilities assigned for chains 1 and 3, reveals the sophisticated way by which the inference model integrates lexical knowledge. Inference chain 2 is longer than chain 1, therefore its probability is lower. However, the inference model assigns chain 2 a higher probability than chain 3, even though the latter is shorter, since the model is sensitive enough to consider the difference in reliability levels between the two highly reliable hypernym relations (from WordNet) of chain 2 and the less reliable Link relation (from Wikipedia) of chain 3. Another aspect of knowledge integration is exemplified in Fig 2 by the three circled probabilities. The inference model takes into consideration the multiple pieces of evidence for the inference of New World (inference chains 3 and 4, whose probabilities are circled). This results in a termlevel probability estimation for New World (the third circled probability) which is higher than the probabilities of each chain separately. The third term of the hypothesis, discover, remains uncovered by the text as no inference chain was found for it. Therefore, the sentence-level inference probability is very low, 37%. In order to identify that the hypothesis is indeed inferred from the text, the inference model should be provided with indications for the inference of discover. To that end, the user may increase the transitivity limit in hope that longer inference chains provide the needed information. In addition, the user can examine other knowledge resources in search for the missing inference link. In this example, it is enough to add VerbOcean to the input of PLIS to expose two inference chains which connect reveal with discover by combining an inference link from WordNet and another one from VerbOcean. With this additional information, the sentence-level probability increases to 76%. This is a typical scenario of utilizing PLIS, either via the interactive system or via the software, for analyzing the usability of the different knowledge resources and their combination. A feature of the interactive system, which is useful for lexical resources analysis, is that each term in a chain is clickable and links to another screen which presents all the terms that are inferred from it and those from which it is inferred. Additionally, the interactive system communicates with a server which runs PLIS, in a fullduplex WebSocket connection6. This mode of operation is publicly available and provides a method for utilizing PLIS, without having to install it or the lexical resources it uses. Finally, since PLIS is a lexical system it can easily be adjusted to other languages. One only needs to replace the basic lexical text processing tools and plug in knowledge resources in the target language. If PLIS is provided with bilingual resources,7 it can operate also as a cross-lingual inference system (Negri et al., 2012). For instance, the text in Fig 3 is given in English, while the hypothesis is written in Spanish (given as a list of lemma:part-of-speech). The left side of the figure depicts a cross-lingual inference process in which the only lexical knowledge resource used is a man- ually built English-Spanish dictionary. As can be seen, two Spanish terms, jugador and casa remain uncovered since the dictionary alone cannot connect them to any of the English terms in the text. As illustrated in the right side of Fig 3, PLIS enables the combination of the bilingual dictionary with monolingual resources to produce cross-lingual inference chains, such as footballer−h −y −p −er−n y −m →player− −m −a −nu − →aljugador. Such inferenc−e − c−h −a −in − →s hpalavey trh− e− capability otro. overcome monolingual language variability (the first link in this chain) as well as to provide cross-lingual translation (the second link). 5 Conclusions To utilize PLIS one should gather lexical resources, obtain sentence-level annotations and train the inference model. Annotations are available in common data sets for task such as QA, Information Retrieval (queries are hypotheses and snippets are texts) and Student Response Analysis (reference answers are the hypotheses that should be inferred by the student answers). For developers of NLP applications, PLIS offers a ready-to-use lexical knowledge integrator which can interface with many common lexical knowledge resources and constructs lexical inference chains which combine the knowledge in them. A developer who wants to overcome lexical language variability, or to incorporate background knowledge, can utilize PLIS to inject lex6We used the socket.io implementation. 7A bilingual resource holds inference links which connect terms in different languages (e.g. an English-Spanish dictionary can provide the inference link explorer→explorador). 101 Figure 3 : PLIS as a cross-lingual inference system. Left: the process with a single manual bilingual resource. Right: PLIS composes cross-lingual inference chains to increase hypothesis coverage and increase sentence-level inference probability. ical knowledge into any text understanding application. PLIS can be used as a lightweight inference system or as the lexical component of larger, more complex inference systems. Additionally, PLIS provides scores for infer- ence chains and determines the way to combine them in order to recognize sentence-level inference. PLIS comes with two probabilistic lexical inference models which achieved competitive performance levels in the tasks of recognizing textual entailment and passage retrieval for QA. All aspects of PLIS are configurable. The user can easily switch between the built-in lexical resources, inference models and even languages, or extend the system with additional lexical resources and new inference models. Acknowledgments The authors thank Eden Erez for his help with the interactive viewer and Miquel Espl a` Gomis for the bilingual dictionaries. This work was partially supported by the European Community’s 7th Framework Programme (FP7/2007-2013) under grant agreement no. 287923 (EXCITEMENT) and the Israel Science Foundation grant 880/12. References Luisa Bentivogli, Ido Dagan, Hoa Trang Dang, Danilo Giampiccolo, and Bernardo Magnini. 2009. The fifth PASCAL recognizing textual entailment challenge. In Proc. of TAC. Luisa Bentivogli, Peter Clark, Ido Dagan, Hoa Trang Dang, and Danilo Giampiccolo. 2010. The sixth PASCAL recognizing textual entailment challenge. In Proc. of TAC. Timothy Chklovski and Patrick Pantel. 2004. VerbOcean: Mining the web for fine-grained semantic verb relations. In Proc. of EMNLP. Ido Dagan, Oren Glickman, and Bernardo Magnini. 2006. The PASCAL recognising textual entailment challenge. In Lecture Notes in Computer Science, volume 3944, pages 177–190. A. P. Dempster, N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of the royal statistical society, series [B], 39(1): 1–38. Christiane Fellbaum, editor. 1998. WordNet: An Electronic Lexical Database. MIT Press, Cambridge, Massachusetts. Nizar Habash and Bonnie Dorr. 2003. A categorial variation database for English. In Proc. of NAACL. Lili Kotlerman, Ido Dagan, Idan Szpektor, and Maayan Zhitomirsky-Geffet. 2010. Directional distributional similarity for lexical inference. Natural Language Engineering, 16(4):359–389. Dekang Lin. 1998. Automatic retrieval and clustering of similar words. In Proc. of COLOING-ACL. Matteo Negri, Alessandro Marchetti, Yashar Mehdad, Luisa Bentivogli, and Danilo Giampiccolo. 2012. Semeval-2012 task 8: Cross-lingual textual entailment for content synchronization. In Proc. of SemEval. Eyal Shnarch, Libby Barak, and Ido Dagan. 2009. Extracting lexical reference rules from Wikipedia. In Proc. of ACL. Eyal Shnarch, Jacob Goldberger, and Ido Dagan. 2011. Towards a probabilistic model for lexical entailment. In Proc. of the TextInfer Workshop. Eyal Shnarch, Ido Dagan, and Jacob Goldberger. 2012. A probabilistic lexical model for ranking textual inferences. In Proc. of *SEM. Mengqiu Wang, Noah A. Smith, and Teruko Mitamura. 2007. What is the Jeopardy model? A quasisynchronous grammar for QA. In Proc. of EMNLP. 102

3 0.12030669 143 acl-2013-Exact Maximum Inference for the Fertility Hidden Markov Model

Author: Chris Quirk

Abstract: The notion of fertility in word alignment (the number of words emitted by a single state) is useful but difficult to model. Initial attempts at modeling fertility used heuristic search methods. Recent approaches instead use more principled approximate inference techniques such as Gibbs sampling for parameter estimation. Yet in practice we also need the single best alignment, which is difficult to find using Gibbs. Building on recent advances in dual decomposition, this paper introduces an exact algorithm for finding the single best alignment with a fertility HMM. Finding the best alignment appears important, as this model leads to a substantial improvement in alignment quality.

4 0.10833866 157 acl-2013-Fast and Robust Compressive Summarization with Dual Decomposition and Multi-Task Learning

Author: Miguel Almeida ; Andre Martins

Abstract: We present a dual decomposition framework for multi-document summarization, using a model that jointly extracts and compresses sentences. Compared with previous work based on integer linear programming, our approach does not require external solvers, is significantly faster, and is modular in the three qualities a summary should have: conciseness, informativeness, and grammaticality. In addition, we propose a multi-task learning framework to take advantage of existing data for extractive summarization and sentence compression. Experiments in the TAC2008 dataset yield the highest published ROUGE scores to date, with runtimes that rival those of extractive summarizers.

5 0.098980203 260 acl-2013-Nonconvex Global Optimization for Latent-Variable Models

Author: Matthew R. Gormley ; Jason Eisner

Abstract: Many models in NLP involve latent variables, such as unknown parses, tags, or alignments. Finding the optimal model parameters is then usually a difficult nonconvex optimization problem. The usual practice is to settle for local optimization methods such as EM or gradient ascent. We explore how one might instead search for a global optimum in parameter space, using branch-and-bound. Our method would eventually find the global maximum (up to a user-specified ?) if run for long enough, but at any point can return a suboptimal solution together with an upper bound on the global maximum. As an illustrative case, we study a generative model for dependency parsing. We search for the maximum-likelihood model parameters and corpus parse, subject to posterior constraints. We show how to formulate this as a mixed integer quadratic programming problem with nonlinear constraints. We use the Reformulation Linearization Technique to produce convex relaxations during branch-and-bound. Although these techniques do not yet provide a practical solution to our instance of this NP-hard problem, they sometimes find better solutions than Viterbi EM with random restarts, in the same time.

6 0.092217796 210 acl-2013-Joint Word Alignment and Bilingual Named Entity Recognition Using Dual Decomposition

7 0.091500774 208 acl-2013-Joint Inference for Heterogeneous Dependency Parsing

8 0.082221419 362 acl-2013-Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers

9 0.081866242 334 acl-2013-Supervised Model Learning with Feature Grouping based on a Discrete Constraint

10 0.078670725 377 acl-2013-Using Supervised Bigram-based ILP for Extractive Summarization

11 0.078299314 382 acl-2013-Variational Inference for Structured NLP Models

12 0.074727848 291 acl-2013-Question Answering Using Enhanced Lexical Semantic Models

13 0.074408844 27 acl-2013-A Two Level Model for Context Sensitive Inference Rules

14 0.069809787 251 acl-2013-Mr. MIRA: Open-Source Large-Margin Structured Learning on MapReduce

15 0.069770359 264 acl-2013-Online Relative Margin Maximization for Statistical Machine Translation

16 0.06976518 7 acl-2013-A Lattice-based Framework for Joint Chinese Word Segmentation, POS Tagging and Parsing

17 0.069024213 228 acl-2013-Leveraging Domain-Independent Information in Semantic Parsing

18 0.068425879 160 acl-2013-Fine-grained Semantic Typing of Emerging Entities

19 0.066785187 365 acl-2013-Understanding Tables in Context Using Standard NLP Toolkits

20 0.06468717 207 acl-2013-Joint Inference for Fine-grained Opinion Extraction

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.142), (1, -0.008), (2, -0.04), (3, -0.035), (4, -0.027), (5, 0.063), (6, 0.027), (7, -0.017), (8, -0.091), (9, -0.026), (10, 0.013), (11, -0.071), (12, -0.054), (13, -0.132), (14, -0.004), (15, -0.008), (16, 0.075), (17, 0.032), (18, 0.121), (19, -0.017), (20, -0.012), (21, 0.081), (22, -0.077), (23, 0.099), (24, -0.039), (25, 0.073), (26, -0.073), (27, 0.012), (28, 0.056), (29, -0.069), (30, 0.125), (31, -0.021), (32, 0.03), (33, 0.078), (34, 0.038), (35, 0.119), (36, 0.004), (37, -0.014), (38, 0.042), (39, 0.026), (40, 0.015), (41, -0.065), (42, -0.097), (43, -0.088), (44, -0.081), (45, 0.015), (46, 0.002), (47, 0.088), (48, -0.082), (49, 0.006)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96855402 237 acl-2013-Margin-based Decomposed Amortized Inference

Author: Gourab Kundu ; Vivek Srikumar ; Dan Roth

2 0.73213571 269 acl-2013-PLIS: a Probabilistic Lexical Inference System

Author: Eyal Shnarch ; Erel Segal-haLevi ; Jacob Goldberger ; Ido Dagan

3 0.6813547 143 acl-2013-Exact Maximum Inference for the Fertility Hidden Markov Model

Author: Chris Quirk

4 0.66512972 382 acl-2013-Variational Inference for Structured NLP Models

Author: David Burkett ; Dan Klein

Abstract: unkown-abstract

5 0.62843704 260 acl-2013-Nonconvex Global Optimization for Latent-Variable Models

Author: Matthew R. Gormley ; Jason Eisner

6 0.60849005 334 acl-2013-Supervised Model Learning with Feature Grouping based on a Discrete Constraint

7 0.56633288 157 acl-2013-Fast and Robust Compressive Summarization with Dual Decomposition and Multi-Task Learning

8 0.55968016 362 acl-2013-Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers

9 0.49143115 348 acl-2013-The effect of non-tightness on Bayesian estimation of PCFGs

10 0.47229379 210 acl-2013-Joint Word Alignment and Bilingual Named Entity Recognition Using Dual Decomposition

11 0.44625288 191 acl-2013-Improved Bayesian Logistic Supervised Topic Models with Data Augmentation

12 0.42959264 208 acl-2013-Joint Inference for Heterogeneous Dependency Parsing

13 0.42788324 365 acl-2013-Understanding Tables in Context Using Standard NLP Toolkits

14 0.40479466 228 acl-2013-Leveraging Domain-Independent Information in Semantic Parsing

15 0.40156916 251 acl-2013-Mr. MIRA: Open-Source Large-Margin Structured Learning on MapReduce

16 0.40142989 131 acl-2013-Dual Training and Dual Prediction for Polarity Classification

17 0.40013558 106 acl-2013-Decentralized Entity-Level Modeling for Coreference Resolution

18 0.39424449 375 acl-2013-Using Integer Linear Programming in Concept-to-Text Generation to Produce More Compact Texts

19 0.39252582 354 acl-2013-Training Nondeficient Variants of IBM-3 and IBM-4 for Word Alignment

20 0.38117605 349 acl-2013-The mathematics of language learning

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.096), (6, 0.071), (11, 0.066), (24, 0.028), (26, 0.041), (28, 0.013), (35, 0.077), (42, 0.045), (48, 0.082), (64, 0.016), (70, 0.041), (88, 0.028), (90, 0.017), (95, 0.063), (98, 0.223)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.81469148 237 acl-2013-Margin-based Decomposed Amortized Inference

Author: Gourab Kundu ; Vivek Srikumar ; Dan Roth

2 0.76924622 67 acl-2013-Bi-directional Inter-dependencies of Subjective Expressions and Targets and their Value for a Joint Model

Author: Roman Klinger ; Philipp Cimiano

Abstract: Opinion mining is often regarded as a classification or segmentation task, involving the prediction of i) subjective expressions, ii) their target and iii) their polarity. Intuitively, these three variables are bidirectionally interdependent, but most work has either attempted to predict them in isolation or proposing pipeline-based approaches that cannot model the bidirectional interaction between these variables. Towards better understanding the interaction between these variables, we propose a model that allows for analyzing the relation of target and subjective phrases in both directions, thus providing an upper bound for the impact of a joint model in comparison to a pipeline model. We report results on two public datasets (cameras and cars), showing that our model outperforms state-ofthe-art models, as well as on a new dataset consisting of Twitter posts.

3 0.67551404 98 acl-2013-Cross-lingual Transfer of Semantic Role Labeling Models

Author: Mikhail Kozhevnikov ; Ivan Titov

Abstract: Semantic Role Labeling (SRL) has become one of the standard tasks of natural language processing and proven useful as a source of information for a number of other applications. We address the problem of transferring an SRL model from one language to another using a shared feature representation. This approach is then evaluated on three language pairs, demonstrating competitive performance as compared to a state-of-the-art unsupervised SRL system and a cross-lingual annotation projection baseline. We also consider the contribution of different aspects of the feature representation to the performance of the model and discuss practical applicability of this method. 1 Background and Motivation Semantic role labeling has proven useful in many natural language processing tasks, such as question answering (Shen and Lapata, 2007; Kaisser and Webber, 2007), textual entailment (Sammons et al., 2009), machine translation (Wu and Fung, 2009; Liu and Gildea, 2010; Gao and Vogel, 2011) and dialogue systems (Basili et al., 2009; van der Plas et al., 2009). Multiple models have been designed to automatically predict semantic roles, and a considerable amount of data has been annotated to train these models, if only for a few more popular languages. As the annotation is costly, one would like to leverage existing resources to minimize the human effort required to construct a model for a new language. A number of approaches to the construction of semantic role labeling models for new languages have been proposed. On one end of the scale is unsupervised SRL, such as Grenager and Manning (2006), which requires some expert knowledge, but no labeled data. It clusters together arguments that should bear the same semantic role, but does not assign a particular role to each cluster. On the other end is annotating a new dataset from scratch. There are also intermediate options, which often make use of similarities between languages. This way, if an accurate model exists for one language, it should help simplify the construction of a model for another, related language. The approaches in this third group often use parallel data to bridge the gap between languages. Cross-lingual annotation projection systems (Pad o´ and Lapata, 2009), for example, propagate information directly via word alignment links. However, they are very sensitive to the quality of parallel data, as well as the accuracy of a sourcelanguage model on it. An alternative approach, known as cross-lingual model transfer, or cross-lingual model adaptation, consists of modifying a source-language model to make it directly applicable to a new language. This usually involves constructing a shared feature representation across the two languages. McDonald et al. (201 1) successfully apply this idea to the transfer of dependency parsers, using part-of- speech tags as the shared representation of words. A later extension of T ¨ackstr o¨m et al. (2012) enriches this representation with cross-lingual word clusters, considerably improving the performance. In the case of SRL, a shared representation that is purely syntactic is likely to be insufficient, since structures with different semantics may be realized by the same syntactic construct, for example “in August” vs “in Britain”. However with the help of recently introduced cross-lingual word represen1190 Proce dingsS o f ita h,e B 5u1lgsta Arinan,u Aaulg Musete 4ti-n9g 2 o0f1 t3h.e ? Ac s2s0o1ci3a Atiosnso fcoirat Cio nm foprut Caotimonpaulta Lti nognuails Lti cnsg,u piasgteics 1 90–120 , tations, such as the cross-lingual clustering mentioned above or cross-lingual distributed word representations of Klementiev et al. (2012), we may be able to transfer models of shallow semantics in a similar fashion. In this work we construct a shared feature representation for a pair of languages, employing crosslingual representations of syntactic and lexical information, train a semantic role labeling model on one language and apply it to the other one. This approach yields an SRL model for a new language at a very low cost, effectively requiring only a source language model and parallel data. We evaluate on five (directed) language pairs EN-ZH, ZH-EN, EN-CZ, CZ-EN and EN-FR, where EN, FR, CZ and ZH denote English, French, Czech and Chinese, respectively. The transferred model is compared against two baselines: an unsupervised SRL system and a model trained on the output of a cross-lingual annotation projection system. In the next section we will describe our setup, then in section 3 present the shared feature representation we use, discuss the evaluation data and other technical aspects in section 4, present the results and conclude with an overview of related work. – 2 Setup The purpose of the study is not to develop a yet another semantic role labeling system any existing SRL system can (after some modification) be used in this setup but to assess the practical applicability of cross-lingual model transfer to this – – problem, compare it against the alternatives and identify its strong/weak points depending on a particular setup. 2.1 Semantic Role Labeling Model We consider the dependency-based version of semantic role labeling as described in Haji cˇ et al. (2009) and transfer an SRL model from one language to another. We only consider verbal predicates and ignore the predicate disambiguation stage. We also assume that the predicate identification information is available in most languages it can be obtained using a relatively simple heuristic based on part-of-speech tags. The model performs argument identification and classification (Johansson and Nugues, 2008) separately in a pipeline first each candidate is classified as being or not being a head of an argument phrase with respect to the predicate in question and then each of the arguments is assigned a role from a given inventory. The model is factorized over arguments the decisions regarding the classification of different arguments are made in– – – dependently of each other. With respect to the use of syntactic annotation we consider two options: using an existing dependency parser for the target language and obtaining one by means of cross-lingual transfer (see section 4.2). Following McDonald et al. (201 1), we assume that a part-of-speech tagger is available for the target language. 2.2 SRL in the Low-resource Setting Several approaches have been proposed to obtain an SRL model for a new language with little or no manual annotation. Unsupervised SRL models (Lang and Lapata, 2010) cluster the arguments of predicates in a given corpus according to their semantic roles. The performance of such models can be impressive, especially for those languages where semantic roles correlate strongly with syntactic relation of the argument to its predicate. However, assigning meaningful role labels to the resulting clusters requires additional effort and the model’s parameters generally need some adjustment for every language. If the necessary resources are already available for a closely related language, they can be utilized to facilitate the construction of a model for the target language. This can be achieved either by means of cross-lingual annotation projection (Yarowsky et al., 2001) or by cross-lingual model transfer (Zeman and Resnik, 2008). This last approach is the one we are considering in this work, and the other two options are treated as baselines. The unsupervised model will be further referred to as UNSUP and the projection baseline as PROJ. 2.3 Evaluation Measures We use the F1 measure as a metric for the argument identification stage and accuracy as an aggregate measure of argument classification performance. When comparing to the unsupervised SRL system the clustering evaluation measures are used instead. These are purity and collocation 1191 N1Ximajx|Gj∩ Ci| CO =N1Xjmiax|Gj∩ Ci|, PU = where Ci is the set of arguments in the i-th induced cluster, Gj is the set of arguments in the jth gold cluster and N is the total number of arguments. We report the harmonic mean ofthe two (Lang and Lapata, 2011) and denote it F1c to avoid confusing it with the supervised metric. 3 Model Transfer The idea of this work is to abstract the model away from the particular source language and apply it to a new one. This setup requires that we use the same feature representation for both languages, for example part-of-speech tags and dependency relation labels should be from the same inventory. Some features are not applicable to certain lan- guages because the corresponding phenomena are absent in them. For example, consider a strongly inflected language and an analytic one. While the latter can usually convey the information encoded in the word form in the former one (number, gender, etc.), finding a shared feature representation for such information is non-trivial. In this study we will confine ourselves to those features that are applicable to all languages in question, namely: part-of-speech tags, syntactic dependency structures and representations of the word’s identity. 3.1 Lexical Information We train a model on one language and apply it to a different one. In order for this to work, the words of the two languages have to be mapped into a common feature space. It is also desirable that closely related words from both languages have similar representations in this space. Word mapping. The first option is simply to use the source language words as the shared representation. Here every source language word would have itself as its representation and every target word would map into a source word that corresponds to it. In other words, we supply the model with a gloss of the target sentence. The mapping (bilingual dictionary) we use is derived from a word-aligned parallel corpus, by identifying, for each word in the target language, the word in the source language it is most often aligned to. Cross-lingual clusters. There is no guarantee that each of the words in the evaluation data is present in our dictionary, nor that the corresponding source-language word is present in the training data, so the model would benefit from the ability to generalize over closely related words. This can, for example, be achieved by using cross-lingual word clusters induced in T ¨ackstr o¨m et al. (2012). We incorporate these clusters as features into our model. 3.2 Syntactic Information Part-of-speech Tags. We map part-of-speech tags into the universal tagset following Petrov et al. (2012). This may have a negative effect on the performance of a monolingual model, since most part-of-speech tagsets are more fine-grained than the universal POS tags considered here. For example Penn Treebank inventory contains 36 tags and the universal POS tagset only 12. Since the finergrained POS tags often reflect more languagespecific phenomena, however, they would only be useful for very closely related languages in the cross-lingual setting. The universal part-of-speech tags used in evaluation are derived from gold-standard annotation for all languages except French, where predicted ones had to be used instead. Dependency Structure. Another important aspect of syntactic information is the dependency structure. Most dependency relation inventories are language-specific, and finding a shared representation for them is a challenging problem. One could map dependency relations into a simplified form that would be shared between languages, as it is done for part-of-speech tags in Petrov et al. (2012). The extent to which this would be useful, however, depends on the similarity of syntactic-semantic in– terfaces of the languages in question. In this work we discard the dependency relation labels where the inventories do not match and only consider the unlabeled syntactic dependency graph. Some discrepancies, such as variations in attachment order, may be present even there, but this does not appear to be the case with the datasets we use for evaluation. If a target language is poor in resources, one can obtain a dependency parser for the target language by means of cross-lingual model transfer (Zeman and Resnik, 2008). We 1192 take this into account and evaluate both using the original dependency structures and the ones obtained by means of cross-lingual model transfer. 3.3 The Model The model we use is based on that of Bj ¨orkelund et al. (2009). It is comprised of a set of linear classifiers trained using Liblinear (Fan et al., 2008). The feature model was modified to accommodate the cross-lingual cluster features and the reranker component was not used. We do not model the interaction between different argument roles in the same predicate. While this has been found useful, in the cross-lingual setup one has to be careful with the assumptions made. For example, modeling the sequence of roles using a Markov chain (Thompson et al., 2003) may not work well in the present setting, especially between distant languages, as the order or arguments is not necessarily preserved. Most constraints that prove useful for SRL (Chang et al., 2007) also require customization when applied to a new language, and some rely on languagespecific resources, such as a valency lexicon. Taking into account the interaction between different arguments of a predicate is likely to improve the performance of the transferred model, but this is outside the scope of this work. 3.4 Feature Selection Compatibility of feature representations is necessary but not sufficient for successful model transfer. We have to make sure that the features we use are predictive of similar outcomes in the two languages as well. Depending on the pair of languages in question, different aspects of the feature representation will retain or lose their predictive power. We can be reasonably certain that the identity of an argument word is predictive of its semantic role in any language, but it might or might not be true of, for example, the word directly preceding the argument word. It is therefore important to pre- SCPDGylOespoSntreslTabunc1lra:obsFel-daitnguplrdoaeusntpagd-elronwfu-dcsopeyrnsd c.eylafguhtorsia mepgnrhs vent the model from capturing overly specific aspects of the source language, which we do by confining the model to first-order features. We also avoid feature selection, which, performed on the source language, is unlikely to help the model to better generalize to the target one. The experiments confirm that feature selection and the use of second-order features degrade the performance of the transferred model. 3.5 Feature Groups For each word, we use its part-of-speech tag, cross-lingual cluster id, word identity (glossed, when evaluating on the target language) and its dependency relation to its parent. Features associated with an argument word include the attributes of the predicate word, the argument word, its parent, siblings and children, and the words directly preceding and following it. Also included are the sequences of part-of-speech tags and dependency relations on the path between the predicate and the argument. Since we are also interested in the impact of different aspects of the feature representation, we divide the features into groups as summarized in table 1 and evaluate their respective contributions to the performance of the model. If a feature group is enabled the model has access to the corre– sponding source of information. For example, if only POS group is enabled, the model relies on the part-of-speech tags of the argument, the predicate and the words to the right and left of the argument word. If Synt is enabled too, it also uses the POS tags of the argument’s parent, children and siblings. Word order information constitutes an implicit group that is always available. It includes the Pos it ion feature, which indicates whether the argument is located to the left or to the right of the predicate, and allows the model to look up the attributes of the words directly preceding and following the argument word. The model we compare against the baselines uses all applicable feature groups (Deprel is only used in EN-CZ and CZ-EN experiments with original syntax). 4 Evaluation 4.1 Datasets and Preprocessing Evaluation of the cross-lingual model transfer requires a rather specific kind of dataset. Namely, the data in both languages has to be annotated 1193 with the same set of semantic roles following the same (or compatible) guidelines, which is seldom the case. We have identified three language pairs for which such resources are available: EnglishChinese, English-Czech and English-French. The evaluation datasets for English and Chinese are those from the CoNLL Shared Task 2009 (Haji ˇc et al., 2009) (henceforth CoNLL-ST). Their annotation in the CoNLL-ST is not identical, but the guidelines for “core” semantic roles are similar (Kingsbury et al., 2004), so we evaluate only on core roles here. The data for the second language pair is drawn from the Prague Czech-English Dependency Treebank 2.0 (Haji ˇc et al., 2012), which we converted to a format similar to that of CoNLL-ST1 . The original annotation uses the tectogrammatical representation (Haji ˇc, 2002) and an inventory of semantic roles (or functors), most of which are interpretable across various predicates. Also note that the syntactic anno- tation of English and Czech in PCEDT 2.0 is quite similar (to the extent permitted by the difference in the structure of the two languages) and we can use the dependency relations in our experiments. For English-French, the English CoNLL-ST dataset was used as a source and the model was evaluated on the manually annotated dataset from van der Plas et al. (201 1). The latter contains one thousand sentences from the French part ofthe Europarl (Koehn, 2005) corpus, annotated with semantic roles following an adapted version of PropBank (Palmer et al., 2005) guidelines. The authors perform annotation projection from English to French, using a joint model of syntax and semantics and employing heuristics for filtering. We use a model trained on the output of this projection system as one of the baselines. The evaluation dataset is relatively small in this case, so we perform the transfer only one-way, from English to French. The part-of-speech tags in all datasets were replaced with the universal POS tags of Petrov et al. (2012). For Czech, we have augmented the map- pings to account for the tags that were not present in the datasets from which the original mappings were derived. Namely, tag “t” is mapped to “VERB” and “Y” to “PRON”. We use parallel data to construct a bilingual dictionary used in word mapping, as well as in the projection baseline. For English-Czech – 1see http://www.ml4nlp.de/code-and-data/treex2conll and English-French, the data is drawn from Europarl (Koehn, 2005), for English-Chinese from MultiUN (Eisele and Chen, 2010). The word alignments were obtained using GIZA++ (Och and Ney, 2003) and the intersection heuristic. – 4.2 Syntactic Transfer In the low-resource setting, we cannot always rely on the availability of an accurate dependency parser for the target language. If one is not available, the natural solution would be to use crosslingual model transfer to obtain it. Unfortunately, the models presented in the previous work, such as Zeman and Resnik (2008), McDonald et al. (201 1) and T ¨ackstr o¨m et al. (2012), were not made available, so we reproduced the direct transfer algorithm of McDonald et al. (201 1), using Malt parser (Nivre, 2008) and the same set of features. We did not reimplement the projected transfer algorithm, however, and used the default training procedure instead of perceptron-based learning. The dependency structure thus obtained is, of course, only a rough approximation even a much more sophisticated algorithm may not perform well when transferring syntax between such languages as Czech and English, given the inherent difference in their structure. The scores are shown in table 2. We will henceforth refer to the syntactic annotations that were provided with the datasets as original, as opposed to the annotations obtained by means of syntactic transfer. – 4.3 Baselines Unsupervised Baseline: We are using a version of the unsupervised semantic role induction system of Titov and Klementiev (2012a) adapted to SetupUAS, % Table2:SyntaciE C ZcN HNt- rE ZaCFnN HZRsfer34 692567acuracy,unlabe dat- tachment score (percent). Note that in case of French we evaluate against the output of a supervised system, since manual annotation is not available for this dataset. This score does not reflect the true performance of syntactic transfer. 1194 the shared feature representation considered in order to make the scores comparable with those of the transfer model and, more importantly, to enable evaluation on transferred syntax. Note that the original system, tailored to a more expressive language-specific syntactic representation and equipped with heuristics to identify active/passive voice and other phenomena, achieves higher scores than those we report here. Projection Baseline: The projection baseline we use for English-Czech and English-Chinese is a straightforward one: we label the source side of a parallel corpus using the source-language model, then identify those verbs on the target side that are aligned to a predicate, mark them as predicates and propagate the argument roles in the same fashion. A model is then trained on the resulting training data and applied to the test set. For English-French we instead use the output of a fully featured projection model of van der Plas et al. (201 1), published in the CLASSiC project. 5 Results In order to ensure that the results are consistent, the test sets, except for the French one, were partitioned into five equal parts (of 5 to 10 thousand sentences each, depending on the dataset) and the evaluation performed separately on each one. All evaluation figures for English, Czech or Chinese below are the average values over the five subsets. In case of French, the evaluation dataset is too small to split it further, so instead we ran the evaluation five times on a randomly selected 80% sample of the evaluation data and averaged over those. In both cases the results are consistent over the subsets, the standard deviation does not exceed 0.5% for the transfer system and projection baseline and 1% for the unsupervised system. 5.1 Argument Identification We summarize the results in table 3. Argument identification is known to rely heavily on syntactic information, so it is unsurprising that it proves inaccurate when transferred syntax is used. Our simple projection baseline suffers from the same problem. Even with original syntactic information available, the performance of argument identification is moderate. Note that the model of (van der Plas et al., 2011), though relying on more expressive syntax, only outperforms the transferred system by 3% (F1) on this task. SetupSyntaxTRANSPROJ ZEC NH Z- EFCZNRHt r a n s 3462 1. 536 142 35. 4269 Table3EZ C:N H- CFEZANHZRrgumeon rt ig identf56 7ic13 a. t27903ion,21569t10ra. 3976nsferd model vs. projection baseline, F1. Most unsupervised SRL approaches assume that the argument identification is performed by some external means, for example heuristically (Lang and Lapata, 2011). Such heuristics or unsupervised approaches to argument identification (Abend et al., 2009) can also be used in the present setup. 5.2 Argument Classification In the following tables, TRANS column contains the results for the transferred system, UNSUP for the unsupervised baseline and PROJ for projection baseline. We highlight in bold the higher score where the difference exceeds twice the maximum of the standard deviation estimates of the two results. Table 4 presents the unsupervised evaluation results. Note that the unsupervised model performs as well as the transferred one or better where the – – SetupSyntaxTRANSUNSUP ZEC NH Z- EFCZNRHt r a n s 768 93648. 34627 6 5873. 1769 TableEZ C4NHZ:- FCEZANHZRrgumoe nr itg clasi78 fi94 3c. a25136tion,8 7 r9a4263n. 07 sferd model vs. unsupervised baseline in terms of the clustering metric F1c (see section 2.3). 1195 SetupSyntaxTRANSPROJ ZEC NH Z- EFCZNRHt r a n s 657 053. 1 36456419. 372 Table5EZ C:N H- CFEZANHZRrgumeon rt ig clasif657ic1936a. t170 ion,65 9t3804ra. 20847nsferd model vs. projection baseline, accuracy. original syntactic dependencies are available. In the more realistic scenario with transferred syn- tax, however, the transferred model proves more accurate. In table 5 we compare the transferred system with the projection baseline. It is easy to see that the scores vary strongly depending on the language pair, due to both the difference in the annotation scheme used and the degree of relatedness between the languages. The drop in performance when transferring the model to another language is large in every case, though, see table 6. SetupTargetSource Table6:MoCEZdHeNZ l- FECaZNRcH urac67 y53169o. 017nthes87 o25670u. r1245ceandtrge language using original syntax. The source language scores for English vary between language pairs because of the difference in syntactic annotation and role subset used. We also include the individual F1 scores for the top-10 most frequent labels for EN-CZ transfer with original syntax in table 7. The model provides meaningful predictions here, despite low overall accuracy. Most of the labels2 are self-explanatory: Patient (PAT), Actor (ACT), Time (TWHEN), Effect (EFF), Location (LOC), Manner (MANN), Addressee (ADDR), Extent (EXT). CPHR marks the 2http://ufal.mff.cuni.cz/∼toman/pcedt/en/functors.html LabelFreq.F1Re.Pr. recall and precision for the top-10 most frequent roles. nominal part of a complex predicate, as in “to have [a plan]CPHR”, and DIR3 indicates destination. 5.3 Additional Experiments We now evaluate the contribution of different aspects of the feature representation to the performance of the model. Table 8 contains the results for English-French. FeaturesOrigTrans ferent feature subsets, using original and transferred syntactic information. The fact that the model performs slightly better with transferred syntax may be explained by two factors. Firstly, as we already mentioned, the original syntactic annotation is also produced automatically. Secondly, in the model transfer setup it is more important how closely the syntacticsemantic interface on the target side resembles that on the source side than how well it matches the “true” structure of the target language, and in this respect a transferred dependency parser may have an advantage over one trained on target-language data. The high impact of the Glos s features here 1196 may be partly attributed to the fact that the mapping is derived from the same corpus as the evaluation data Europarl (Koehn, 2005) and partly by the similarity between English and French in terms of word order, usage of articles and prepositions. The moderate contribution of the crosslingual cluster features are likely due to the insufficient granularity of the clustering for this task. For more distant language pairs, the contributions of individual feature groups are less interpretable, so we only highlight a few observations. First of all, both EN-CZ and CZ-EN benefit noticeably from the use of the original syntactic annotation, including dependency relations, but not from the transferred syntax, most likely due to the low syntactic transfer performance. Both perform better when lexical information is available, although – – the improvement is not as significant as in the case of French only up to 5%. The situation with Chinese is somewhat complicated in that adding lexical information here fails to yield an improvement in terms of the metric considered. This is likely due to the fact that we consider only the core roles, which can usually be predicted with high accuracy based on syntactic information alone. – 6 Related Work Development of robust statistical models for core NLP tasks is a challenging problem, and adaptation of existing models to new languages presents a viable alternative to exhaustive annotation for each language. Although the models thus obtained are generally imperfect, they can be further refined for a particular language and domain using techniques such as active learning (Settles, 2010; Chen et al., 2011). Cross-lingual annotation projection (Yarowsky et al., 2001) approaches have been applied ex- tensively to a variety of tasks, including POS tagging (Xi and Hwa, 2005; Das and Petrov, 2011), morphology segmentation (Snyder and Barzilay, 2008), verb classification (Merlo et al., 2002), mention detection (Zitouni and Florian, 2008), LFG parsing (Wr o´blewska and Frank, 2009), information extraction (Kim et al., 2010), SRL (Pad o´ and Lapata, 2009; van der Plas et al., 2011; Annesi and Basili, 2010; Tonelli and Pianta, 2008), dependency parsing (Naseem et al., 2012; Ganchev et al., 2009; Smith and Eisner, 2009; Hwa et al., 2005) or temporal relation prediction (Spreyer and Frank, 2008). Interestingly, it has also been used to propagate morphosyntactic information between old and modern versions of the same language (Meyer, 2011). Cross-lingual model transfer methods (McDonald et al., 2011; Zeman and Resnik, 2008; Durrett et al., 2012; Søgaard, 2011; Lopez et al., 2008) have also been receiving much attention recently. The basic idea behind model transfer is similar to that of cross-lingual annotation projection, as we can see from the way parallel data is used in, for example, McDonald et al. (201 1). A crucial component of direct transfer approaches is the unified feature representation. There are at least two such representations of lexical information (Klementiev et al., 2012; T ¨ackstr o¨m et al., 2012), but both work on word level. This makes it hard to account for phenomena that are expressed differently in the languages considered, for example the syntactic function of a certain word may be indicated by a preposition, inflection or word order, depending on the language. Accurate representation of such information would require an extra level of abstraction (Haji ˇc, 2002). A side-effect ofusing adaptation methods is that we are forced to use the same annotation scheme for the task in question (SRL, in our case), which in turn simplifies the development of cross-lingual tools for downstream tasks. Such representations are also likely to be useful in machine translation. Unsupervised semantic role labeling methods (Lang and Lapata, 2010; Lang and Lapata, 2011; Titov and Klementiev, 2012a; Lorenzo and Cerisara, 2012) also constitute an alternative to cross-lingual model transfer. For an overview of of semi-supervised approaches we refer the reader to Titov and Klementiev (2012b). 7 Conclusion We have considered the cross-lingual model transfer approach as applied to the task of semantic role labeling and observed that for closely related languages it performs comparably to annotation projection approaches. It allows one to quickly construct an SRL model for a new language without manual annotation or language-specific heuristics, provided an accurate model is available for one of the related languages along with a certain amount of parallel data for the two languages. While an1197 notation projection approaches require sentenceand word-aligned parallel data and crucially depend on the accuracy of the syntactic parsing and SRL on the source side of the parallel corpus, cross-lingual model transfer can be performed using only a bilingual dictionary. Unsupervised SRL approaches have their advantages, in particular when no annotated data is available for any of the related languages and there is a syntactic parser available for the target one, but the annotation they produce is not always sufficient. In applications such as Information Retrieval it is preferable to have precise labels, rather than just clusters of arguments, for example. Also note that when applying cross-lingual model transfer in practice, one can improve upon the performance of the simplistic model we use for evaluation, for example by picking the features manually, taking into account the properties of the target language. Domain adaptation techniques can also be employed to adjust the model to the target language. Acknowledgments The authors would like to thank Alexandre Klementiev and Ryan McDonald for useful suggestions and T ¨ackstr o¨m et al. (2012) for sharing the cross-lingual word representations. This research is supported by the MMCI Cluster of Excellence. References Omri Abend, Roi Reichart, and Ari Rappoport. 2009. Unsupervised argument identification for semantic role labeling. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, ACL ’09, pages 28–36, Stroudsburg, PA, USA. Association for Computational Linguistics. Paolo Annesi and Roberto Basili. 2010. Cross-lingual alignment of FrameNet annotations through hidden Markov models. In Proceedings of the 11th international conference on Computational Linguistics and Intelligent Text Processing, CICLing’ 10, pages 12– 25, Berlin, Heidelberg. Springer-Verlag. Roberto Basili, Diego De Cao, Danilo Croce, Bonaventura Coppola, and Alessandro Moschitti. 2009. Cross-language frame semantics transfer in bilingual corpora. In Alexander F. Gelbukh, editor, Proceedings of the 10th International Conference on Computational Linguistics and Intelligent Text Pro- cessing, pages 332–345. Anders Bj ¨orkelund, Love Hafdell, and Pierre Nugues. 2009. Multilingual semantic role labeling. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL 2009): Shared Task, pages 43–48, Boulder, Colorado, June. Association for Computational Linguistics. Ming-Wei Chang, Lev Ratinov, and Dan Roth. 2007. Guiding semi-supervision with constraint-driven learning. In ACL. Chenhua Chen, Alexis Palmer, and Caroline Sporleder. 2011. Enhancing active learning for semantic role labeling via compressed dependency trees. In Proceedings of 5th International Joint Conference on Natural Language Processing, pages 183–191, Chiang Mai, Thailand, November. Asian Federation of Natural Language Processing. Dipanjan Das and Slav Petrov. 2011. Unsupervised part-of-speech tagging with bilingual graph-based projections. Proceedings of the Association for Computational Linguistics. Greg Durrett, Adam Pauls, and Dan Klein. 2012. Syntactic transfer using a bilingual lexicon. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1–1 1, Jeju Island, Korea, July. Association for Computational Linguistics. Andreas Eisele and Yu Chen. 2010. MultiUN: A multilingual corpus from United Nation documents. In Proceedings of the Seventh International Conference on Language Resources and Evaluation (LREC’10). European Language Resources Association (ELRA). Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, XiangRui Wang, and Chih-Jen Lin. 2008. LIBLINEAR: A library for large linear classification. Journal of Machine Learning Research, 9: 1871–1874. Kuzman Ganchev, Jennifer Gillenwater, and Ben Taskar. 2009. Dependency grammar induction via bitext projection constraints. In Proceedings of the 47th Annual Meeting of the ACL, pages 369–377, Stroudsburg, PA, USA. Association for Computational Linguistics. Qin Gao and Stephan Vogel. 2011. Corpus expansion for statistical machine translation with semantic role label substitution rules. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 294–298, Portland, Oregon, USA. Trond Grenager and Christopher D. Manning. 2006. Unsupervised discovery of a statistical verb lexicon. In Proceedings of EMNLP. Jan Haji cˇ. 2002. Tectogrammatical representation: Towards a minimal transfer in machine translation. In Robert Frank, editor, Proceedings of the 6th International Workshop on Tree Adjoining Grammars 1198 and Related Frameworks (TAG+6), pages 216— 226, Venezia. Universita di Venezia. Jan Haji cˇ, Massimiliano Ciaramita, Richard Johansson, Daisuke Kawahara, Maria Ant o`nia Mart ı´, Llu ı´s M `arquez, Adam Meyers, Joakim Nivre, Sebastian Pad o´, Jan Sˇt eˇp a´nek, Pavel Stra nˇ a´k, Mihai Surdeanu, Nianwen Xue, and Yi Zhang. 2009. The CoNLL2009 shared task: Syntactic and semantic dependencies in multiple languages. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL 2009): Shared Task, pages 1–18, Boulder, Colorado. Jan Haji cˇ, Eva Haji cˇov a´, Jarmila Panevov a´, Petr Sgall, Ond ˇrej Bojar, Silvie Cinkov´ a, Eva Fuˇ c ´ıkov a´, Marie Mikulov a´, Petr Pajas, Jan Popelka, Ji ˇr´ ı Semeck´ y, Jana Sˇindlerov a´, Jan Sˇt eˇp a´nek, Josef Toman, Zde nˇka Ure sˇov a´, and Zden eˇk Zˇabokrtsk y´. 2012. Announcing Prague Czech-English dependency treebank 2.0. In Nicoletta Calzolari (Conference Chair), Khalid Choukri, Thierry Declerck, Mehmet U gˇur Doˇ gan, Bente Maegaard, Joseph Mariani, Jan Odijk, and Stelios Piperidis, editors, Proceedings of the Eight International Conference on Language Resources and Evaluation (LREC’12), Istanbul, Turkey, May. European Language Resources Association (ELRA). Rebecca Hwa, Philip Resnik, Amy Weinberg, Clara Cabezas, and Okan Kolak. 2005. Bootstrapping parsers via syntactic projection across parallel text. Natural Language Engineering, 11(3):3 11–325. Richard Johansson and Pierre Nugues. 2008. Dependency-based semantic role labeling of PropBank. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 69–78, Honolulu, Hawaii. Michael Kaisser and Bonnie Webber. 2007. Question answering based on semantic roles. In ACL Workshop on Deep Linguistic Processing. Seokhwan Kim, Minwoo Jeong, Jonghoon Lee, and Gary Geunbae Lee. 2010. A cross-lingual annotation projection approach for relation detection. In Proceedings of the 23rd International Conference on Computational Linguistics, COLING ’ 10, pages 564–571, Stroudsburg, PA, USA. Association for Computational Linguistics. Paul Kingsbury, Nianwen Xue, and Martha Palmer. 2004. Propbanking in parallel. In In Proceedings of the Workshop on the Amazing Utility of Parallel and Comparable Corpora, in conjunction with LREC’04. Alexandre Klementiev, Ivan Titov, and Binod Bhattarai. 2012. Inducing crosslingual distributed representations of words. In Proceedings of the International Conference on Computational Linguistics (COLING), Bombay, India. Philipp Koehn. 2005. Europarl: A parallel corpus for statistical machine translation. In Conference Proceedings: the tenth Machine Translation Summit, pages 79–86, Phuket, Thailand. AAMT. Joel Lang and Mirella Lapata. 2010. Unsupervised induction of semantic roles. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 939–947, Los Angeles, California, June. Association for Computational Linguistics. Joel Lang and Mirella Lapata. 2011. Unsupervised semantic role induction via split-merge clustering. In Proc. of Annual Meeting of the Association for Computational Linguistics (ACL). Ding Liu and Daniel Gildea. 2010. Semantic role features for machine translation. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), Beijing, China. Adam Lopez, Daniel Zeman, Michael Nossal, Philip Resnik, and Rebecca Hwa. 2008. Cross-language parser adaptation between related languages. In IJCNLP-08 Workshop on NLP for Less Privileged Languages, pages 35–42, Hyderabad, India, January. Alejandra Lorenzo and Christophe Cerisara. 2012. Unsupervised frame based semantic role induction: application to French and English. In Proceedings of the ACL 2012 Joint Workshop on Statistical Parsing and Semantic Processing of Morphologically Rich Languages, pages 30–35, Jeju, Republic of Korea, July. Association for Computational Linguistics. Ryan McDonald, Slav Petrov, and Keith Hall. 2011. Multi-source transfer of delexicalized dependency parsers. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, EMNLP ’ 11, pages 62–72, Stroudsburg, PA, USA. Association for Computational Linguistics. Paola Merlo, Suzanne Stevenson, Vivian Tsang, and Gianluca Allaria. 2002. A multi-lingual paradigm for automatic verb classification. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL’02), pages 207– 214, Philadelphia, PA. Roland Meyer. 2011. New wine in old wineskins?– Tagging old Russian via annotation projection from modern translations. Russian Linguistics, 35(2):267(15). Tahira Naseem, Regina Barzilay, and Amir Globerson. 2012. Selective sharing for multilingual dependency parsing. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, pages 629–637, Jeju Island, Korea, July. Association for Computational Linguistics. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Comput. Linguist., 34(4):513–553, December. 1199 Franz Josef Och and Hermann Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics, 29(1). Sebastian Pad o´ and Mirella Lapata. 2009. Crosslingual annotation projection for semantic roles. Journal of Artificial Intelligence Research, 36:307– 340. Martha Palmer, Daniel Gildea, and Paul Kingsbury. 2005. The Proposition Bank: An annotated corpus of semantic roles. Computational Linguistics, 31:71–105. Slav Petrov, Dipanjan Das, and Ryan McDonald. 2012. A universal part-of-speech tagset. In Proceedings of LREC, May. Mark Sammons, Vinod Vydiswaran, Tim Vieira, Nikhil Johri, Ming wei Chang, Dan Goldwasser, Vivek Srikumar, Gourab Kundu, Yuancheng Tu, Kevin Small, Joshua Rule, Quang Do, and Dan Roth. 2009. Relation alignment for textual entailment recognition. In Text Analysis Conference (TAC). Burr Settles. 2010. Active learning literature survey. Computer Sciences Technical Report, 1648. Dan Shen and Mirella Lapata. 2007. Using semantic roles to improve question answering. In EMNLP. David A Smith and Jason Eisner. 2009. Parser adaptation and projection with quasi-synchronous grammar features. In Proceedings of the 2009 Confer- ence on Empirical Methods in Natural Language Processing, pages 822–831. Association for Computational Linguistics. Benjamin Snyder and Regina Barzilay. 2008. Crosslingual propagation for morphological analysis. In Proceedings of the 23rd national conference on Artificial intelligence. Anders Søgaard. 2011. Data point selection for crosslanguage adaptation of dependency parsers. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, volume 2 of HLT ’11, pages 682–686, Stroudsburg, PA, USA. Association for Computational Linguistics. Kathrin Spreyer and Anette Frank. 2008. Projectionbased acquisition of a temporal labeller. Proceedings of IJCNLP 2008. Oscar T¨ ackstr o¨m, Ryan McDonald, and Jakob Uszkoreit. 2012. Cross-lingual word clusters for direct transfer of linguistic structure. In Proc. of the Annual Meeting of the North American Association of Computational Linguistics (NAACL), pages 477– 487, Montr ´eal, Canada. Cynthia A. Thompson, Roger Levy, and Christopher D. Manning. 2003. A generative model for seman- tic role labeling. In Proceedings of the 14th European Conference on Machine Learning, ECML 2003, pages 397–408, Dubrovnik, Croatia. Ivan Titov and Alexandre Klementiev. 2012a. A Bayesian approach to unsupervised semantic role induction. In Proc. of European Chapter of the Association for Computational Linguistics (EACL). Ivan Titov and Alexandre Klementiev. 2012b. Semisupervised semantic role labeling: Approaching from an unsupervised perspective. In Proceedings of the International Conference on Computational Linguistics (COLING), Bombay, India, December. Sara Tonelli and Emanuele Pianta. 2008. Frame information transfer from English to Italian. In Proceedings of LREC 2008. Lonneke van der Plas, James Henderson, and Paola Merlo. 2009. Domain adaptation with artificial data for semantic parsing of speech. In Proc. 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 125–128, Boulder, Colorado. Lonneke van der Plas, Paola Merlo, and James Henderson. 2011. Scaling up automatic cross-lingual semantic role annotation. In Proceedings of the 49th Annual Meeting of the Association for Computa- tional Linguistics: Human Language Technologies, HLT ’ 11, pages 299–304, Stroudsburg, PA, USA. Association for Computational Linguistics. Alina Wr o´blewska and Anette Frank. 2009. Crosslingual projection of LFG F-structures: Building an F-structure bank for Polish. In Eighth International Workshop on Treebanks and Linguistic Theories, page 209. Dekai Wu and Pascale Fung. 2009. Can semantic role labeling improve SMT? In Proceedings of 13th Annual Conference of the European Association for Machine Translation (EAMT 2009), Barcelona. Chenhai Xi and Rebecca Hwa. 2005. A backoff model for bootstrapping resources for non-English languages. In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, pages 85 1–858, Stroudsburg, PA, USA. David Yarowsky, Grace Ngai, and Ricahrd Wicentowski. 2001. Inducing multilingual text analysis tools via robust projection across aligned corpora. In Proceedings of Human Language Technology Conference. Daniel Zeman and Philip Resnik. 2008. Crosslanguage parser adaptation between related lan- guages. In Proceedings of the IJCNLP-08 Workshop on NLP for Less Privileged Languages, pages 35– 42, Hyderabad, India, January. Asian Federation of Natural Language Processing. Imed Zitouni and Radu Florian. 2008. Mention detection crossing the language barrier. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. 1200

4 0.66352367 154 acl-2013-Extracting bilingual terminologies from comparable corpora

Author: Ahmet Aker ; Monica Paramita ; Rob Gaizauskas

Abstract: In this paper we present a method for extracting bilingual terminologies from comparable corpora. In our approach we treat bilingual term extraction as a classification problem. For classification we use an SVM binary classifier and training data taken from the EUROVOC thesaurus. We test our approach on a held-out test set from EUROVOC and perform precision, recall and f-measure evaluations for 20 European language pairs. The performance of our classifier reaches the 100% precision level for many language pairs. We also perform manual evaluation on bilingual terms extracted from English-German term-tagged comparable corpora. The results of this manual evaluation showed 60-83% of the term pairs generated are exact translations and over 90% exact or partial translations.

5 0.64671397 83 acl-2013-Collective Annotation of Linguistic Resources: Basic Principles and a Formal Model

Author: Ulle Endriss ; Raquel Fernandez

Abstract: Crowdsourcing, which offers new ways of cheaply and quickly gathering large amounts of information contributed by volunteers online, has revolutionised the collection of labelled data. Yet, to create annotated linguistic resources from this data, we face the challenge of having to combine the judgements of a potentially large group of annotators. In this paper we investigate how to aggregate individual annotations into a single collective annotation, taking inspiration from the field of social choice theory. We formulate a general formal model for collective annotation and propose several aggregation methods that go beyond the commonly used majority rule. We test some of our methods on data from a crowdsourcing experiment on textual entailment annotation.

6 0.64331853 157 acl-2013-Fast and Robust Compressive Summarization with Dual Decomposition and Multi-Task Learning

7 0.63571042 275 acl-2013-Parsing with Compositional Vector Grammars

8 0.62978947 185 acl-2013-Identifying Bad Semantic Neighbors for Improving Distributional Thesauri

9 0.62879807 17 acl-2013-A Random Walk Approach to Selectional Preferences Based on Preference Ranking and Propagation

10 0.62645966 62 acl-2013-Automatic Term Ambiguity Detection

11 0.62527394 70 acl-2013-Bilingually-Guided Monolingual Dependency Grammar Induction

12 0.62369341 191 acl-2013-Improved Bayesian Logistic Supervised Topic Models with Data Augmentation

13 0.62331498 254 acl-2013-Multimodal DBN for Predicting High-Quality Answers in cQA portals

14 0.62298691 43 acl-2013-Align, Disambiguate and Walk: A Unified Approach for Measuring Semantic Similarity

15 0.62048626 276 acl-2013-Part-of-Speech Induction in Dependency Trees for Statistical Machine Translation

16 0.62045574 260 acl-2013-Nonconvex Global Optimization for Latent-Variable Models

17 0.619223 325 acl-2013-Smoothed marginal distribution constraints for language modeling

18 0.61906469 36 acl-2013-Adapting Discriminative Reranking to Grounded Language Learning

19 0.61888069 297 acl-2013-Recognizing Partial Textual Entailment

20 0.61851358 9 acl-2013-A Lightweight and High Performance Monolingual Word Aligner