acl acl2013 acl2013-165 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Matthias Buchse ; Alexander Koller ; Heiko Vogler
Abstract: Binarization ofgrammars is crucial for improving the complexity and performance of parsing and translation. We present a versatile binarization algorithm that can be tailored to a number of grammar formalisms by simply varying a formal parameter. We apply our algorithm to binarizing tree-to-string transducers used in syntax-based machine translation.
Reference: text
sentIndex sentText sentNum sentScore
1 Generic binarization for parsing and translation Matthias B u¨chse Technische Universit a¨t Dresden Alexander Koller University of Potsdam Heiko Vogler Technische Universit a¨t Dresden matthias. [sent-1, score-0.724]
2 We present a versatile binarization algorithm that can be tailored to a number of grammar formalisms by simply varying a formal parameter. [sent-8, score-0.88]
3 We apply our algorithm to binarizing tree-to-string transducers used in syntax-based machine translation. [sent-9, score-0.192]
4 1 Introduction Binarization amounts to transforming a given grammar into an equivalent grammar of rank 2, i. [sent-10, score-0.294]
5 The ability to binarize grammars is crucial for efficient parsing, because for many grammar formalisms the parsing complexity de- pends exponentially on the rank of the grammar. [sent-13, score-0.309]
6 It replaces each rule of rank greater than 2 by an equivalent collection of rules of rank 2. [sent-21, score-0.34]
7 In the case of SCFGs, not every grammar has an equivalent representation of rank 2 in the first place (Aho and Ullman, 1969). [sent-25, score-0.253]
8 Nevertheless, the rule-by-rule binarization algorithm of Huang et al. [sent-27, score-0.731]
9 In this paper, we offer a generic approach for transferring the rule-by-rule binarization technique to new grammar formalisms. [sent-29, score-0.788]
10 At the core of our approach is a binarization algorithm that can be adapted to a new formalism by changing a parameter at runtime. [sent-30, score-0.762]
11 More specifically, our algorithm requires the user to (i) encode the grammar formalism as a subclass of interpreted regular tree grammars (IRTGs, (Koller and Kuhlmann, 2011)) and (ii) supply a collection of b-rules, which represent equivalence of grammars syntactically. [sent-32, score-0.437]
12 Our algorithm then replaces, in a given grammar, each rule of rank greater than 2 by an equivalent collection of rules of rank 2, if such a collection is licensed by the b-rules. [sent-33, score-0.348]
13 We define completeness of b-rules in a way that ensures that if any equivalent collection of rules of rank 2 exists, the algorithm finds one. [sent-34, score-0.203]
14 As a consequence, the algorithm binarizes every grammar that can be binarized rule by rule. [sent-35, score-0.314]
15 To our knowledge, our binarization algorithm is the first to binarize such transducers. [sent-44, score-0.764]
16 In Section 3, we define the general outline of our approach to rule-by-rule binarization for IRTGs, and then extend this to an efficient binarization algorithm based on b-rules in Section 4. [sent-48, score-1.43]
17 In Section 5 we show how to use the algorithm to perform rule-by-rule binarization of SCFGs and tree-to-string transducers, and relate the results to existing work. [sent-49, score-0.731]
18 2 Interpreted regular tree grammars Grammar formalisms employed in parsing and SMT, such as those mentioned in the introduction, differ in the the derived objects—e. [sent-50, score-0.284]
19 Interpreted regular tree grammars (IRTGs) permit a uniform treatment of many of these formalisms. [sent-55, score-0.199]
20 , a, b); in the tree case, we alternate the construction of a sequence of trees (con2) with the construction of a single tree by placing a symbol (e. [sent-61, score-0.341]
21 For instance, in the string algebra shown in Table 1, the term con2 (a, b) evaluates to ab, and the term con2 (con2 (x2, a) , x1) evaluates to a binary operation f such that, e. [sent-109, score-0.258]
22 Bimorphisms IRTGs separate the finite control (state behavior) of a derivation from its derived object (in its term representation; generational behavior); the former is captured by a regular tree language, while the latter is obtained by applying a tree homomorphism. [sent-112, score-0.313]
23 A regular tree grammar (RTG) G over Σ is a triple (Q, q0, R) where Q is a finite set (of states), q0 ∈ Q, and R is a finite set of rules of the form q → α(q1 , . [sent-115, score-0.368]
24 ,xk) → x1 · · · xk Table 1: Algebras for strings and trees, given = an TΓ∗ (set of sequences of trees) {γ| | γ ∈ Γ} ∪ {{cγo|nk||k γ | ∈0 Γ ≤ k∪ ≤ K, k 1} γ : x1 → γ(x1) conk : (x1, . [sent-136, score-0.242]
25 This extends the usual definition of linear and nondeleting homomorphisms (G´ ecseg and Steinby, 1997) to trees with variables. [sent-146, score-0.201]
26 , hn) where G is an RTG over some signature Σ and hi is a tree homomorphism from TΣ (X) into T∆i (X). [sent-158, score-0.323]
27 An IRTG is a bimorphism whose derived trees are viewed as terms over algebras; see Fig. [sent-163, score-0.236]
28 It contains a bimorphism B = (G, h1, h2) consisting oaifn an aR bTimGo Grp hwisitmh fBou =r ru (Gles, hand homomorIRTG G = (B, A1, A2) Figure 1: IRTG, bimorphism overview. [sent-189, score-0.242]
29 phisms h1 and h2 which map derivation trees to trees over the signature of the string algebra in Table 1. [sent-191, score-0.409]
30 By evaluating these trees in the algebra, the symbols con3 and con4 are interpreted as concatenation, and we see that the first rule encodes the SCFG rule A → hBCD, DaBCi. [sent-192, score-0.262]
31 The string algebra in Table 1yields context-free languages, more complex string al147 bcocn3d←h−1[α1αα2α37−h→2dacon4bc Figure 3: D←er−iv[ation tree and semantic terms. [sent-195, score-0.355]
32 3 IRTG binarization We will now show how to apply the rule-by-rule binarization technique to IRTGs. [sent-200, score-1.398]
33 We start in this section by defining the binarization of a rule in an IRTG, and characterizing it in terms of binarization terms and variable trees. [sent-201, score-1.647]
34 We derive the actual binarization algorithm from this in Section 4. [sent-202, score-0.731]
35 This rule derives (in one step) the fragment α(x1 , x2, x3) of the derivation tree in Fig. [sent-217, score-0.227]
36 Note that the terms h01 (ξ) and h1(α) are equivalent in that they denote the same function over the string algebra, and so are the terms h02 (ξ) and h2 (α). [sent-224, score-0.228]
37 We construct a tree ξ from τ by a simple relabeling, and we read off the tree homomorphisms h01 and h02 from a decomposition we perform on t1 and t2, respectively; see Fig. [sent-241, score-0.295]
38 We call terms t1 and t2 binarization terms if they satisfy (i)–(iii). [sent-248, score-0.825]
39 We will see below that we can con148 struct binary rules equivalent to r from any given sequence of binarization terms t1, t2, and that binarization terms exist whenever equivalent binary rules exist. [sent-249, score-1.835]
40 The majority of this paper revolves around the question of finding binarization terms. [sent-250, score-0.699]
41 Rule-by-rule binarization of IRTGs follows the intuition laid out in this example closely: it means processing each suprabinary rule, attempting to replace it with an equivalent collection of binary rules. [sent-251, score-0.91]
42 =As q we ha αv(eq seen, binarizing r boils down to constructing: • a tree ξ over some binary signature Σ0 and • tar teere homomorphisms h01 , . [sent-258, score-0.329]
43 The problem of rule-by-rule binarization consists in computing a binarization of each suprabinary rule of a grammar. [sent-269, score-1.604]
44 If such a binarization does not exist, the problem does not have a solution. [sent-270, score-0.699]
45 In order to define variable trees, we assume a mapping seq that maps each finite set U of pairwise disjoint variable sets to a sequence over U which contains each element exactly once. [sent-271, score-0.217]
46 We represent S(t) as a tree v(t), which we call variable tree as follows. [sent-275, score-0.291]
47 ;I ift we assume {txhat} seq ord{exrs set}s, {ofx variables} according stuom mthee t hleatas ste qva orir-able index, we arrive at the variable tree in the center of Fig. [sent-281, score-0.206]
48 , tn binariza∈tion T terms of r if the following properties hold: (i) hi (α) and ti are equivalent; (ii) at each node the tree ti contains at most two subtrees with variables; and (iii) the terms t1, . [sent-290, score-0.505]
49 Assume for now that we have found binarization terms t1, . [sent-294, score-0.748]
50 We show how to construct a binarization (ξ, h01 , . [sent-298, score-0.73]
51 Bithec xause of condition (ii) in in the definition of binarization terms, ξ is binary. [sent-308, score-0.699]
52 In order to construct hi0 (σ) for each symbol σ in ξ, we transform ti into a tree ti0 with labels from C∆i (X) and the same structure as ξ. [sent-309, score-0.26]
53 6: first, we apply the maximal decomposition operation d; it replaces every label f ∈ ∆i |k by the tree f(x1, . [sent-312, score-0.212]
54 Thus, if we can find binarization terms, we can construct a binarization of r. [sent-320, score-1.429]
55 Conversely, for any given binarization (ξ, h01 , . [sent-321, score-0.699]
56 Lemma 1 There is a binarization of r if and only if there are binarization terms of r. [sent-329, score-1.447]
57 3 Finding binarization terms It remains to show how we can find binarization terms of r, if there are any. [sent-331, score-1.496]
58 Let bi : T∆i (Xk) → P(T∆i (Xk)) the mapping with bi (t) = {t0 ∈ T∆i (Xk) | t and t0 are equivalent, a(ntd) =at {etach∈ n Tode t0 h)as | ta ta nmdo tst two children with variables}. [sent-332, score-0.22]
59 , tn are binarization terms precisely when ti ∈ bi (hi (α)) and t1, . [sent-338, score-0.974]
60 Lemma 2 There are binarization only ifTi v(bi (hi (α))) ∅. [sent-343, score-0.699]
61 This result suggests the following procedure for obtaining binarization terms. [sent-345, score-0.699]
62 4 Effective IRTG binarization In this section we develop our binarization algorithm. [sent-358, score-1.398]
63 This parameter gives rise to a restricted version of the ruleby-rule binarization problem, which is efficiently computable while remaining practically relevant. [sent-366, score-0.699]
64 A binarization rule (brule) over ∆ is a mapping b : ∆ → P(T∆ (X)) wruhleer)e o fvoerr every f ∈ ∆|k we h∆av →e th Pat( b(f) ⊆ C∆ (Xk), a et eearcyh fno ∈de ∆of| a wtreee h ainv b(f) only two children contain variables, and b(f) is a regular tree language. [sent-368, score-0.989]
65 G, wivheenr an algebra A over ∆, a b-rule b over ∆ is called a b-rule over AA o if, f ∆or, every lte ∈ T∆ (Xk) acnaldl td0 ∈ b(t), to0v aenrd A At are equivalent tin ∈ ∈A T. [sent-373, score-0.245]
66 , h0n) of r is a binarization of r with respect to b1, . [sent-387, score-0.735]
67 , tn are binarization terms with respect to b1, . [sent-394, score-0.841]
68 The problem of rule-byrule binarization with respect to b1, . [sent-399, score-0.735]
69 , bn consists in computing a binarization with respect to b1, . [sent-402, score-0.829]
70 N Go wif we eshqouwat ihoonw h to effectively compute binarization terms with respect to b1, . [sent-414, score-0.784]
71 For the recursive case, we use cthhe th fea RctT tGha its regular tree languages are closed under substitution (G´ ecseg and Steinby, 1997, Prop. [sent-424, score-0.198]
72 We define the mapping vari : P → P(Xk) such that for every p ∈ P, every t: ∈ Lp(Gi) Xcontains exactly the vari- pab ∈les P i,n e vari (p). [sent-430, score-0.36]
73 At this point we have all the ingredients for our binarization algorithm, shown in Algorithm 1. [sent-463, score-0.699]
74 In short, it solves the problem of rule-by-rule binarization with respect to b-rules b1, . [sent-466, score-0.735]
75 , n do 12: compute RTG G0i0 for 13: b0i0 = bi(hi(α)) ∩ v−1(t0) 14: select ti ∈ L(Gi00) 15: construct binarization for t1, . [sent-513, score-0.789]
76 , tn 16: add appropriate rules to B0 Algorithm 1: Complete binarization algorithm, where G| ≤2 and G| >2 is G restricted to binary and suprabinary rules, respectively. [sent-516, score-0.953]
77 if every suprabinary rule of G has a binarization with respect to b1, . [sent-517, score-0.989]
78 5 Applications Algorithm 1 implements rule-by-rule binarization with respect to given b-rules. [sent-526, score-0.735]
79 If a rule of the given IRTG does not have a binarization with respect to these b-rules, it is simply carried over to the new grammar, which then has a rank higher than 2. [sent-527, score-0.88]
80 The number of remaining suprabinary rules depends on the b-rules (except for rules that have no binarization at all). [sent-528, score-0.917]
81 By contrast, earlier binarization algorithms for formalisms such as SCFG and LCFRS simply attempt to find an equivalent grammar of rank 2; there is no analogue of our b-rules. [sent-530, score-0.964]
82 The problem these algorithms solve corresponds to the general rule-by-rule binarization problem from Section 3. [sent-531, score-0.699]
83 SCFGs are IRTGs with two interpretations into the string algebra of Table 1, as illustrated by the example in Fig. [sent-538, score-0.189]
84 Our definition of rule-by-rule binarization with respect to b1 and b2 coincides with that of Huang et al. [sent-544, score-0.735]
85 For instance, for the SCFG rule A → hBCDE, CEBDi, the sets v(b1(h1(α))) Aan →d v(b2 (h2 (α))) are disjoint, t sheutss no binarization exists. [sent-546, score-0.797]
86 This perspective on translation naturally leads to the use of tree-to-string transducers NP → α(NNP, JJ, NN) DTcNoxn1P3cPNxoOPn23Sx3h17−h→2dasx2cxo3n5derx1 the ’s con0 con0 Figure 8: An IRTG rule encoding the rule in Fig. [sent-550, score-0.284]
87 We model the tree-to-string transducer as an IRTG G = ((G, h1, h2) , A1, A2), where A2 is the string algebra, but th)i,sA Atim,Ae A1 is the tAree algebra sinhgow anlg einb rTa,ab blue t1 t . [sent-559, score-0.236]
88 sTh tiims algebra has operations conk to concatenate sequences of trees and unary γ that maps any sequence (t1, . [sent-560, score-0.286]
89 Parsing of a binary IRTG that represents a tree-to-string transducer is O(N3 · M) for a string of length N and a tree with M no·d Mes. [sent-579, score-0.247]
90 ) We have implemented our binarization algorithm and the b-rules for the string and the tree algebra. [sent-580, score-0.897]
91 3 General approach Our binarization algorithm can be used to solve the general rule-by-rule binarization problem for a specific grammar formalism, provided that one can find appropriate b-rules. [sent-594, score-1.519]
92 , sAsn C Co fo algebras othveatr encsoamdees stehqeu grammar formalism, together with brules b1, . [sent-598, score-0.237]
93 w Wee h ausveed a ath celo cslearss l oofk ka allt I tRhTeG clsa swsit hC two string algebras and in which hi (α) contains at most one occurrence of a symbol conk for every α ∈ Σ. [sent-607, score-0.489]
94 If C is such that every grammar pfrlyom “b a given grammar formalism can be encoded as an IRTG in C, this sfoorlvmeasl itshme general rule-by-rule nbin IRarTizGat i onn C problem of that grammar formalism. [sent-623, score-0.346]
95 6 Conclusion We have presented an algorithm for binarizing IRTGs rule by rule, with respect to b-rules that the user specifies for each algebra. [sent-624, score-0.238]
96 This improves the complexity of parsing and translation with any monolingual or synchronous grammar that can be represented as an IRTG. [sent-625, score-0.188]
97 A novel algorithm for binarizing tree-to-string transducers falls out as a special case. [sent-626, score-0.192]
98 Our algorithm extends to grammars of arbitrary fanout (such as synchronous tree-adjoining grammar (Koller and Kuhlmann, 2012)), but unlike LCFRS-based approaches to binarization, it will not increase the fanout to ensure binarizability. [sent-628, score-0.37]
99 In the future, we will explore IRTG binarization with fanout increase. [sent-629, score-0.759]
100 This could be done by binarizing into an IRTG with a more complicated algebra (e. [sent-630, score-0.2]
wordName wordTfidf (topN-words)
[('binarization', 0.699), ('irtg', 0.269), ('irtgs', 0.189), ('rtg', 0.148), ('vari', 0.132), ('xk', 0.131), ('algebra', 0.128), ('hi', 0.127), ('algebras', 0.121), ('bimorphism', 0.121), ('bi', 0.11), ('scfgs', 0.11), ('suprabinary', 0.108), ('tree', 0.105), ('rule', 0.098), ('bn', 0.094), ('grammar', 0.089), ('transducers', 0.088), ('xj', 0.078), ('synchronous', 0.074), ('binarizing', 0.072), ('equivalent', 0.069), ('conk', 0.067), ('trees', 0.066), ('symbol', 0.065), ('signature', 0.064), ('koller', 0.061), ('string', 0.061), ('formalisms', 0.06), ('fanout', 0.06), ('ti', 0.059), ('tn', 0.057), ('grammars', 0.055), ('rules', 0.055), ('kuhlmann', 0.055), ('ecseg', 0.054), ('homomorphisms', 0.054), ('variable', 0.053), ('qk', 0.052), ('terms', 0.049), ('every', 0.048), ('scfg', 0.048), ('seq', 0.048), ('transducer', 0.047), ('binarized', 0.047), ('rank', 0.047), ('strings', 0.044), ('nonempty', 0.04), ('steinby', 0.04), ('hn', 0.04), ('finite', 0.04), ('regular', 0.039), ('respect', 0.036), ('let', 0.036), ('rewriting', 0.036), ('graehl', 0.036), ('ii', 0.036), ('operation', 0.035), ('iii', 0.034), ('binary', 0.034), ('binarize', 0.033), ('gv', 0.033), ('gi', 0.032), ('algorithm', 0.032), ('formalism', 0.031), ('equivalence', 0.031), ('construct', 0.031), ('knuth', 0.031), ('iv', 0.031), ('variables', 0.03), ('alphabet', 0.03), ('pj', 0.029), ('call', 0.028), ('tk', 0.028), ('knight', 0.027), ('bimorphisms', 0.027), ('brules', 0.027), ('dresden', 0.027), ('goguen', 0.027), ('homomorphism', 0.027), ('hvari', 0.027), ('lcfrss', 0.027), ('nesson', 0.027), ('nondeleting', 0.027), ('onk', 0.027), ('nnp', 0.026), ('theorem', 0.026), ('operations', 0.025), ('parsing', 0.025), ('derivation', 0.024), ('huang', 0.024), ('replaces', 0.024), ('aho', 0.024), ('fork', 0.024), ('disjoint', 0.023), ('kevin', 0.023), ('whenever', 0.023), ('tuple', 0.023), ('galley', 0.022), ('arnold', 0.022)]
simIndex simValue paperId paperTitle
same-paper 1 1.000002 165 acl-2013-General binarization for parsing and translation
Author: Matthias Buchse ; Alexander Koller ; Heiko Vogler
Abstract: Binarization ofgrammars is crucial for improving the complexity and performance of parsing and translation. We present a versatile binarization algorithm that can be tailored to a number of grammar formalisms by simply varying a formal parameter. We apply our algorithm to binarizing tree-to-string transducers used in syntax-based machine translation.
2 0.12627092 274 acl-2013-Parsing Graphs with Hyperedge Replacement Grammars
Author: David Chiang ; Jacob Andreas ; Daniel Bauer ; Karl Moritz Hermann ; Bevan Jones ; Kevin Knight
Abstract: Hyperedge replacement grammar (HRG) is a formalism for generating and transforming graphs that has potential applications in natural language understanding and generation. A recognition algorithm due to Lautemann is known to be polynomial-time for graphs that are connected and of bounded degree. We present a more precise characterization of the algorithm’s complexity, an optimization analogous to binarization of contextfree grammars, and some important implementation details, resulting in an algorithm that is practical for natural-language applications. The algorithm is part of Bolinas, a new software toolkit for HRG processing.
3 0.1189202 357 acl-2013-Transfer Learning for Constituency-Based Grammars
Author: Yuan Zhang ; Regina Barzilay ; Amir Globerson
Abstract: In this paper, we consider the problem of cross-formalism transfer in parsing. We are interested in parsing constituencybased grammars such as HPSG and CCG using a small amount of data specific for the target formalism, and a large quantity of coarse CFG annotations from the Penn Treebank. While all of the target formalisms share a similar basic syntactic structure with Penn Treebank CFG, they also encode additional constraints and semantic features. To handle this apparent discrepancy, we design a probabilistic model that jointly generates CFG and target formalism parses. The model includes features of both parses, allowing trans- fer between the formalisms, while preserving parsing efficiency. We evaluate our approach on three constituency-based grammars CCG, HPSG, and LFG, augmented with the Penn Treebank-1. Our experiments show that across all three formalisms, the target parsers significantly benefit from the coarse annotations.1 —
4 0.11551821 361 acl-2013-Travatar: A Forest-to-String Machine Translation Engine based on Tree Transducers
Author: Graham Neubig
Abstract: In this paper we describe Travatar, a forest-to-string machine translation (MT) engine based on tree transducers. It provides an open-source C++ implementation for the entire forest-to-string MT pipeline, including rule extraction, tuning, decoding, and evaluation. There are a number of options for model training, and tuning includes advanced options such as hypergraph MERT, and training of sparse features through online learning. The training pipeline is modeled after that of the popular Moses decoder, so users familiar with Moses should be able to get started quickly. We perform a validation experiment of the decoder on EnglishJapanese machine translation, and find that it is possible to achieve greater accuracy than translation using phrase-based and hierarchical-phrase-based translation. As auxiliary results, we also compare different syntactic parsers and alignment techniques that we tested in the process of developing the decoder. Travatar is available under the LGPL at http : / /phont ron . com/t ravat ar
5 0.091910578 320 acl-2013-Shallow Local Multi-Bottom-up Tree Transducers in Statistical Machine Translation
Author: Fabienne Braune ; Nina Seemann ; Daniel Quernheim ; Andreas Maletti
Abstract: We present a new translation model integrating the shallow local multi bottomup tree transducer. We perform a largescale empirical evaluation of our obtained system, which demonstrates that we significantly beat a realistic tree-to-tree baseline on the WMT 2009 English → German tlriannes olnati tohne tWasMk.T TA 2s0 an a Edndgitliisonha →l c Gonetrrmibauntion we make the developed software and complete tool-chain publicly available for further experimentation.
6 0.082689598 314 acl-2013-Semantic Roles for String to Tree Machine Translation
7 0.082198106 46 acl-2013-An Infinite Hierarchical Bayesian Model of Phrasal Translation
8 0.081370711 4 acl-2013-A Context Free TAG Variant
9 0.07739152 348 acl-2013-The effect of non-tightness on Bayesian estimation of PCFGs
10 0.061827589 226 acl-2013-Learning to Prune: Context-Sensitive Pruning for Syntactic MT
11 0.060335416 19 acl-2013-A Shift-Reduce Parsing Algorithm for Phrase-based String-to-Dependency Translation
12 0.059760887 285 acl-2013-Propminer: A Workflow for Interactive Information Extraction and Exploration using Dependency Trees
13 0.05371435 27 acl-2013-A Two Level Model for Context Sensitive Inference Rules
14 0.05369794 312 acl-2013-Semantic Parsing as Machine Translation
15 0.051277619 311 acl-2013-Semantic Neighborhoods as Hypergraphs
16 0.051212829 261 acl-2013-Nonparametric Bayesian Inference and Efficient Parsing for Tree-adjoining Grammars
17 0.049995605 222 acl-2013-Learning Semantic Textual Similarity with Structural Representations
18 0.0488359 144 acl-2013-Explicit and Implicit Syntactic Features for Text Classification
19 0.048509456 57 acl-2013-Arguments and Modifiers from the Learner's Perspective
20 0.048318885 212 acl-2013-Language-Independent Discriminative Parsing of Temporal Expressions
topicId topicWeight
[(0, 0.121), (1, -0.065), (2, -0.015), (3, -0.006), (4, -0.102), (5, 0.023), (6, 0.055), (7, -0.02), (8, -0.002), (9, -0.007), (10, 0.001), (11, 0.04), (12, 0.055), (13, -0.045), (14, -0.009), (15, -0.064), (16, 0.118), (17, 0.117), (18, -0.017), (19, 0.047), (20, -0.027), (21, 0.021), (22, 0.053), (23, 0.069), (24, -0.059), (25, -0.051), (26, -0.003), (27, -0.009), (28, -0.009), (29, 0.032), (30, -0.007), (31, -0.011), (32, -0.01), (33, -0.005), (34, 0.045), (35, -0.025), (36, -0.049), (37, 0.008), (38, -0.029), (39, -0.008), (40, -0.057), (41, 0.116), (42, 0.046), (43, 0.048), (44, 0.12), (45, -0.026), (46, -0.104), (47, 0.013), (48, -0.043), (49, -0.028)]
simIndex simValue paperId paperTitle
same-paper 1 0.95337248 165 acl-2013-General binarization for parsing and translation
Author: Matthias Buchse ; Alexander Koller ; Heiko Vogler
Abstract: Binarization ofgrammars is crucial for improving the complexity and performance of parsing and translation. We present a versatile binarization algorithm that can be tailored to a number of grammar formalisms by simply varying a formal parameter. We apply our algorithm to binarizing tree-to-string transducers used in syntax-based machine translation.
2 0.8119331 274 acl-2013-Parsing Graphs with Hyperedge Replacement Grammars
Author: David Chiang ; Jacob Andreas ; Daniel Bauer ; Karl Moritz Hermann ; Bevan Jones ; Kevin Knight
Abstract: Hyperedge replacement grammar (HRG) is a formalism for generating and transforming graphs that has potential applications in natural language understanding and generation. A recognition algorithm due to Lautemann is known to be polynomial-time for graphs that are connected and of bounded degree. We present a more precise characterization of the algorithm’s complexity, an optimization analogous to binarization of contextfree grammars, and some important implementation details, resulting in an algorithm that is practical for natural-language applications. The algorithm is part of Bolinas, a new software toolkit for HRG processing.
3 0.64947683 348 acl-2013-The effect of non-tightness on Bayesian estimation of PCFGs
Author: Shay B. Cohen ; Mark Johnson
Abstract: Probabilistic context-free grammars have the unusual property of not always defining tight distributions (i.e., the sum of the “probabilities” of the trees the grammar generates can be less than one). This paper reviews how this non-tightness can arise and discusses its impact on Bayesian estimation of PCFGs. We begin by presenting the notion of “almost everywhere tight grammars” and show that linear CFGs follow it. We then propose three different ways of reinterpreting non-tight PCFGs to make them tight, show that the Bayesian estimators in Johnson et al. (2007) are correct under one of them, and provide MCMC samplers for the other two. We conclude with a discussion of the impact of tightness empirically.
4 0.62756532 320 acl-2013-Shallow Local Multi-Bottom-up Tree Transducers in Statistical Machine Translation
Author: Fabienne Braune ; Nina Seemann ; Daniel Quernheim ; Andreas Maletti
Abstract: We present a new translation model integrating the shallow local multi bottomup tree transducer. We perform a largescale empirical evaluation of our obtained system, which demonstrates that we significantly beat a realistic tree-to-tree baseline on the WMT 2009 English → German tlriannes olnati tohne tWasMk.T TA 2s0 an a Edndgitliisonha →l c Gonetrrmibauntion we make the developed software and complete tool-chain publicly available for further experimentation.
Author: Alan Akbik ; Oresti Konomi ; Michail Melnikov
Abstract: The use ofdeep syntactic information such as typed dependencies has been shown to be very effective in Information Extraction. Despite this potential, the process of manually creating rule-based information extractors that operate on dependency trees is not intuitive for persons without an extensive NLP background. In this system demonstration, we present a tool and a workflow designed to enable initiate users to interactively explore the effect and expressivity of creating Information Extraction rules over dependency trees. We introduce the proposed five step workflow for creating information extractors, the graph query based rule language, as well as the core features of the PROP- MINER tool.
6 0.60518378 4 acl-2013-A Context Free TAG Variant
7 0.58573008 311 acl-2013-Semantic Neighborhoods as Hypergraphs
8 0.49581683 15 acl-2013-A Novel Graph-based Compact Representation of Word Alignment
9 0.49356833 312 acl-2013-Semantic Parsing as Machine Translation
10 0.48859015 46 acl-2013-An Infinite Hierarchical Bayesian Model of Phrasal Translation
11 0.48254788 36 acl-2013-Adapting Discriminative Reranking to Grounded Language Learning
12 0.48077536 314 acl-2013-Semantic Roles for String to Tree Machine Translation
13 0.47556788 361 acl-2013-Travatar: A Forest-to-String Machine Translation Engine based on Tree Transducers
14 0.46914682 261 acl-2013-Nonparametric Bayesian Inference and Efficient Parsing for Tree-adjoining Grammars
15 0.44854572 226 acl-2013-Learning to Prune: Context-Sensitive Pruning for Syntactic MT
16 0.44396302 57 acl-2013-Arguments and Modifiers from the Learner's Perspective
17 0.43882227 357 acl-2013-Transfer Learning for Constituency-Based Grammars
18 0.434277 144 acl-2013-Explicit and Implicit Syntactic Features for Text Classification
19 0.43102384 161 acl-2013-Fluid Construction Grammar for Historical and Evolutionary Linguistics
20 0.4255915 19 acl-2013-A Shift-Reduce Parsing Algorithm for Phrase-based String-to-Dependency Translation
topicId topicWeight
[(0, 0.048), (1, 0.015), (6, 0.026), (11, 0.066), (14, 0.018), (24, 0.022), (26, 0.047), (28, 0.013), (35, 0.063), (42, 0.03), (48, 0.044), (70, 0.077), (72, 0.256), (85, 0.014), (88, 0.023), (90, 0.062), (95, 0.06)]
simIndex simValue paperId paperTitle
1 0.83067983 30 acl-2013-A computational approach to politeness with application to social factors
Author: Cristian Danescu-Niculescu-Mizil ; Moritz Sudhof ; Dan Jurafsky ; Jure Leskovec ; Christopher Potts
Abstract: We propose a computational framework for identifying linguistic aspects of politeness. Our starting point is a new corpus of requests annotated for politeness, which we use to evaluate aspects of politeness theory and to uncover new interactions between politeness markers and context. These findings guide our construction of a classifier with domain-independent lexical and syntactic features operationalizing key components of politeness theory, such as indirection, deference, impersonalization and modality. Our classifier achieves close to human performance and is effective across domains. We use our framework to study the relationship between po- liteness and social power, showing that polite Wikipedia editors are more likely to achieve high status through elections, but, once elevated, they become less polite. We see a similar negative correlation between politeness and power on Stack Exchange, where users at the top of the reputation scale are less polite than those at the bottom. Finally, we apply our classifier to a preliminary analysis of politeness variation by gender and community.
same-paper 2 0.8154133 165 acl-2013-General binarization for parsing and translation
Author: Matthias Buchse ; Alexander Koller ; Heiko Vogler
Abstract: Binarization ofgrammars is crucial for improving the complexity and performance of parsing and translation. We present a versatile binarization algorithm that can be tailored to a number of grammar formalisms by simply varying a formal parameter. We apply our algorithm to binarizing tree-to-string transducers used in syntax-based machine translation.
3 0.79696441 332 acl-2013-Subtree Extractive Summarization via Submodular Maximization
Author: Hajime Morita ; Ryohei Sasano ; Hiroya Takamura ; Manabu Okumura
Abstract: This study proposes a text summarization model that simultaneously performs sentence extraction and compression. We translate the text summarization task into a problem of extracting a set of dependency subtrees in the document cluster. We also encode obligatory case constraints as must-link dependency constraints in order to guarantee the readability of the generated summary. In order to handle the subtree extraction problem, we investigate a new class of submodular maximization problem, and a new algorithm that has the approximation ratio 21 (1 − e−1). Our experiments with the NTC(1IR − −A eCLIA test collections show that our approach outperforms a state-of-the-art algorithm.
4 0.58006662 172 acl-2013-Graph-based Local Coherence Modeling
Author: Camille Guinaudeau ; Michael Strube
Abstract: We propose a computationally efficient graph-based approach for local coherence modeling. We evaluate our system on three tasks: sentence ordering, summary coherence rating and readability assessment. The performance is comparable to entity grid based approaches though these rely on a computationally expensive training phase and face data sparsity problems.
5 0.53651631 274 acl-2013-Parsing Graphs with Hyperedge Replacement Grammars
Author: David Chiang ; Jacob Andreas ; Daniel Bauer ; Karl Moritz Hermann ; Bevan Jones ; Kevin Knight
Abstract: Hyperedge replacement grammar (HRG) is a formalism for generating and transforming graphs that has potential applications in natural language understanding and generation. A recognition algorithm due to Lautemann is known to be polynomial-time for graphs that are connected and of bounded degree. We present a more precise characterization of the algorithm’s complexity, an optimization analogous to binarization of contextfree grammars, and some important implementation details, resulting in an algorithm that is practical for natural-language applications. The algorithm is part of Bolinas, a new software toolkit for HRG processing.
6 0.52253437 155 acl-2013-Fast and Accurate Shift-Reduce Constituent Parsing
8 0.5168553 250 acl-2013-Models of Translation Competitions
9 0.51478243 272 acl-2013-Paraphrase-Driven Learning for Open Question Answering
10 0.51225805 275 acl-2013-Parsing with Compositional Vector Grammars
11 0.51203525 212 acl-2013-Language-Independent Discriminative Parsing of Temporal Expressions
12 0.51082182 169 acl-2013-Generating Synthetic Comparable Questions for News Articles
13 0.51005995 361 acl-2013-Travatar: A Forest-to-String Machine Translation Engine based on Tree Transducers
14 0.50991929 46 acl-2013-An Infinite Hierarchical Bayesian Model of Phrasal Translation
15 0.50960076 343 acl-2013-The Effect of Higher-Order Dependency Features in Discriminative Phrase-Structure Parsing
16 0.50921381 249 acl-2013-Models of Semantic Representation with Visual Attributes
17 0.50914311 174 acl-2013-Graph Propagation for Paraphrasing Out-of-Vocabulary Words in Statistical Machine Translation
18 0.50846595 4 acl-2013-A Context Free TAG Variant
19 0.50806606 80 acl-2013-Chinese Parsing Exploiting Characters
20 0.50734842 139 acl-2013-Entity Linking for Tweets