acl acl2011 acl2011-236 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Gisle Ytrestl
Abstract: This paper describes a backtracking strategy for an incremental deterministic transitionbased parser for HPSG. The method could theoretically be implemented on any other transition-based parser with some adjustments. In this paper, the algorithm is evaluated on CuteForce, an efficient deterministic shiftreduce HPSG parser. The backtracking strategy may serve to improve existing parsers, or to assess if a deterministic parser would benefit from backtracking as a strategy to improve parsing.
Reference: text
sentIndex sentText sentNum sentScore
1 no Abstract This paper describes a backtracking strategy for an incremental deterministic transitionbased parser for HPSG. [sent-3, score-0.936]
2 The method could theoretically be implemented on any other transition-based parser with some adjustments. [sent-4, score-0.164]
3 In this paper, the algorithm is evaluated on CuteForce, an efficient deterministic shiftreduce HPSG parser. [sent-5, score-0.194]
4 The backtracking strategy may serve to improve existing parsers, or to assess if a deterministic parser would benefit from backtracking as a strategy to improve parsing. [sent-6, score-1.446]
5 1 Introduction Incremental deterministic parsing has received increased awareness over the last decade. [sent-7, score-0.295]
6 Processing linguistic data linearly is attractive both from a computational and a cognitive standpoint. [sent-8, score-0.043]
7 While there is a rich research tradition in statistical parsing, the predominant approach derives from chart parsing and is inherently non-deterministic. [sent-9, score-0.123]
8 A deterministic algorithm will incrementally expand a syntactic/semantic derivation as it reads the input sentence one word/token at the time. [sent-10, score-0.305]
9 There are a number of attractive features to this approach. [sent-11, score-0.043]
10 However, there are inherent challenges to an incremental parsing algorithm. [sent-18, score-0.146]
11 Garden paths are the canonical example of 58 sentences that are typically misinterpret due to an early incorrect grammatical assumption. [sent-19, score-0.067]
12 The ability to reevaluate an earlier grammatical assumption is disallowed by a deterministic parser. [sent-21, score-0.194]
13 Optimistic Backtracking is an method designed to locate the incorrect parser decision in an earlier stage if the parser reaches an illegal state, i. [sent-22, score-0.379]
14 a state in which a valid parse derivation cannot be retrieved. [sent-24, score-0.174]
15 The Optimistic Backtracking method will try to locate the first incorrect parsing decision made by the parser, and replace this decision with the correct transition, and resume parsing from this state. [sent-25, score-0.33]
16 2 Related Work Incremental deterministic classifier-based parsing algorithms have been studied in dependency parsing (Nivre and Scholz, 2004; Yamada and Matsumoto, 2003) and CFG parsing (Sagae and Lavie, 2005). [sent-26, score-0.517]
17 Johansson and Nugues (2006) describe a non-deterministic implementation to the dependency parser outlined by Nivre and Scholz (2004), where they apply an n-best beam search strategy. [sent-27, score-0.162]
18 For a highly constrained unification-based formalism like HPSG, a deterministic parsing strategy could frequently lead to parse failures. [sent-28, score-0.349]
19 (2009) suggest an algorithm for deterministic shift-reduce parsing in HPSG. [sent-30, score-0.295]
20 Their approach allows the parser to enter an old state if pars- ing fails or ends with non-sentential success, based on the minimal distance between the best candidate Portland, OPR,ro UcSeeAdi 1n9g-s2 o4f J uthnee A 2C01L-1H. [sent-32, score-0.263]
21 c T2 2001111 A Sstsuodceinatti Soens fsoiorn C,o pmagpeusta 58ti–o6n3a,l Linguistics and the second best candidate in the sequence of transitions leading up to the current stage. [sent-34, score-0.153]
22 restricting the number of states the parser may backtrack. [sent-37, score-0.142]
23 This algorithm is expanded by using a beam-thresholding best-first search algorithm, where each state in the parse has a state probability defined by the product of the probabilities of the selecting actions that has been taken to reach the state. [sent-38, score-0.097]
24 3 CuteForce Optimistic Backtracking is in this paper used to evaluate CuteForce, an incremental deterministic HPSG parser currently in development. [sent-39, score-0.381]
25 , 2007), it employs a classifier-based oracle to guide the shift-reduce parser that incrementally builds a syntactic/semantic HPSG derivation defined by LinGO English Resource Grammar (ERG) (Flickinger, 2000). [sent-41, score-0.355]
26 Parser Layout CuteForce has a more complex transition system than MaltParser in order to facilitate HPSG parsing. [sent-42, score-0.237]
27 The sentence input buffer β is a list of tuples with token, part-of-speech tags and HPSG lexical types (i. [sent-43, score-0.065]
28 Given a set of ERG rules R and a sentence buffer β, a parser configuration is a tuple c = (α, β, ι, π) where: • α is a stack of “active” edges1 • β is a list of tuples of word forms W, part o af speech tags PfO wSo dan fdo lsexi Wcal, types LT derived from a sentence x = ((W1 , POS1, LT1), . [sent-46, score-0.251]
29 • ι is the current input position in β • π is a stack of passive edges instantiating a EπR iGs aru sleta The stack of passive edges π makes up the full HPSG representation of the input string if the string is accepted. [sent-50, score-0.325]
30 1An “active” edges in our sense is a hypothesis of an application of a binary rule where the left daughter is known (an element of π), and the specific binary ERG rule and the right daughter is yet to be found. [sent-51, score-0.218]
31 59 Transition System The shift-reduce parser has four different transitions, two of which are parameterized with a unary or binary ERG rule, which are added to the passive edges, hence building the HPSG structure. [sent-52, score-0.296]
32 π represents tahtee sH PthSeG p adresreiv oaftio tnh eof s tehnesentence) – Derivation Example Figure 1 is a derivation example from Redwoods Treebank (Oepen et al. [sent-54, score-0.085]
33 We note that the tree derivation consists of unary and binay productions, corresponding to theUNIT(R1) andPASSIVE(R2) parser transitions. [sent-56, score-0.266]
34 Further, the pre-terminal lexical types have a le suffix, and are provided together with the terminal word form in the input buffer for the parser. [sent-57, score-0.072]
35 sb-hd mc c sp-hd n c hd-cmp u c d-“sportm-dei”vlevj-nb-pas- tjrhd lnr ormncmsvilvrp“cmand”l-pvlne3s-b eilhrd-cmpuchdnb pc v pas odlr n - m le v np* le np-hdn cpd c “spvecnpia*lizle d” “software” “nar ate”hwd hny bpnhpe-npn p clrwn pe prlio dlr plr n - pl le n - mc le “RSS-” “feeds. [sent-58, score-0.166]
36 Parsing Configuration Mode CuteForce can operate in three different oracle configurations: HPSG Unification mode, CFG approximation mode and unrestricted mode. [sent-60, score-0.331]
37 In HPSG Unification mode, the parser validates that no oracle decisions lead to an invalid HPSG derivation. [sent-61, score-0.244]
38 All UNIT and PASSIVE transitions are an implicit unification. [sent-62, score-0.095]
39 For each parsing stage, the parsing oracle returns a ranked list of transitions. [sent-63, score-0.276]
40 The highest-ranked transition not violating a unification constraint will be executed. [sent-64, score-0.484]
41 If no transition yields a valid unification, parsing fails for the given sentence. [sent-65, score-0.393]
42 In CFG mode, a naive CFG approximation of the ERG is employed to guide the oracle. [sent-66, score-0.03]
43 The CFG approximation consists of CFG rules harvested from the treebanks used in training the parser for this purpose we have used existing Redwoods treebanks used in training, and augmented with derivations from WikiWoods, in total 300,000 sentences. [sent-67, score-0.252]
44 Each ERG rule instantiation, using the identifiers shown in Figure 1 as non-terminal symbols, will be treated as a CFG rule, and each parser action will be validated against the set of CFG rules. [sent-68, score-0.172]
45 If the parser action yields a CFG projection not found among the valid CFG rules in the CFG approximation, the CFG filter will block this transition. [sent-69, score-0.169]
46 If the parser arrives at a state where the CFG filter blocks all further transitions, parsing fails. [sent-70, score-0.296]
47 In unrestricted mode, the oracle chooses the highest scoring transition without any further restrictions – imposed. [sent-71, score-0.375]
48 In this setting, the parser typically reaches close to 100 % coverage the only sentences not covered in this setting are instances where the parser enters an infinite unit production loop. [sent-72, score-0.33]
49 Hence, we will only evaluate the parser in CFG and Unification mode in this paper. [sent-73, score-0.347]
50 – 4 Optimistic Backtracking Optimistic Backtracking can be added as an overlay to a transition-based parser in order to evaluate the parser in non-deterministic mode. [sent-74, score-0.345]
51 This backtracking method is, to the best of our knowledge, the only method that applies ranking rather than some probability-based algorithm for backtracking. [sent-76, score-0.548]
52 This aspect is critical for classification-based parsing oracles that do not yield a probability score in the ranking of candidate transitions. [sent-77, score-0.179]
53 Treating backtracking as a ranking problem has several attractive features. [sent-78, score-0.591]
54 It may combine global and local syntactic and semantic information related to each candidate transition, contrary to a probabilistic approach that only employs the local transition 60 probability. [sent-79, score-0.323]
55 Consider sentence (1), it’s first when the second verb (fell) is encountered that we would re-evaluate our original assumption, namely that raced may not be the head verb of the sentence. [sent-81, score-0.054]
56 That fell indeed is a verb is surely relevant information for reconsidering raced as the head of a relative clause. [sent-82, score-0.079]
57 When the parser halts, the backtracker will rank each transition produced up until the point of failure according to which transition is most likely to be the first incorrect transition. [sent-83, score-0.886]
58 When the best scoring transition is located, the parser will backtrack to this position, and replace this transition with the parsing oracle’s second-best scoring transition for this current parsing state. [sent-84, score-1.24]
59 If the parser later comes to another halt, only the transitions occurring after the first backtrack will be subject to change. [sent-85, score-0.338]
60 Hence, the backtracker will always assume that its last backtrack was correct (thus being Optimistic). [sent-86, score-0.304]
61 Having allowed the parser to backtrack unrestrictedly, we could theoretically have reached close to 100 % coverage, but the insights of parsing incrementally would have become less pronounced. [sent-87, score-0.41]
62 The search space for the backtracker is n ∗ m whTerhee n eisa cthhe nspuamcbee fro orf t hceand baidcaktter transitions, ∗an md m is the total number of parser transitions. [sent-88, score-0.345]
63 In Optimistic Backtracking we disregard the m dimension altogether by always choosing the second-best transition candidate ranked by the parsing oracle, assuming that the second-ranked transition in the given state actually was the correct transition. [sent-89, score-0.668]
64 In this paper, using CuteForce as HPSG parser, this assumption holds in about 80-90 % of the backtracks in CFG mode, in HPSG Unification mode this number is somewhat lower. [sent-91, score-0.246]
65 1 Baseline As a baseline for identifying the incorrect transition, we use a strategy inspired by Ninomiya et al. [sent-93, score-0.113]
66 (2009), namely to pick the candidate transition with the minimal probability difference between the best and the second best transition candidate. [sent-94, score-0.532]
67 In unification mode (Table 2) the parser is much more likely to fail, as the parse derivations are guaranteed to be a valid HPSG derivation. [sent-99, score-0.69]
68 Baseline backtracking yields a mere 10 % reduction in parsing failures. [sent-100, score-0.651]
69 2 Feature Model Each candidate transition is mapped to a feature vector that provides information about the transition. [sent-102, score-0.295]
70 The task for the ranker is to identify the first incorrect transition in the sequence of transitions. [sent-103, score-0.333]
71 The feature model used by the ranker employs features that can roughly be divided in three. [sent-104, score-0.057]
72 First, the transition-specific features provide information on the nature of the candidate transition and surrounding transitions. [sent-105, score-0.295]
73 Here we also have features related to the pseudo-probability of the transition (provided by the parsing oracle), and the oracle score distance between the best-scoring and second-best scoring transition for each given state. [sent-106, score-0.691]
74 Secondly we have features related to the last token that was processed by the parser before it reached an invalid state, and the information on the incomplete HPSG derivation that was built at that state. [sent-107, score-0.273]
75 Third, we have features concerning the preliminary HPSG derivation in the actual state of the transition. [sent-109, score-0.12]
76 Feature Types The list of transitions T = t0, t1, . [sent-110, score-0.095]
77 tn comprises the candidate transitions that are subject to backtracking upon parsing failure. [sent-113, score-0.782]
78 5 Evaluation In this paper we trained CuteForce with data from Redwoods Treebank, augmented with derivations from WikiWoods (Flickinger et al. [sent-116, score-0.042]
79 Training data for the backtracker is extracted by parsing derivations from WikiWoods deterministically, and record transition candidates each time parsing fails, labeling the correct backtracking candidate, backtrack to this point, and resume parsing from this state. [sent-119, score-1.477]
80 1 Results The first column (CFG-NB and UNI-NB) in Table 1 and 2 indicates the scores when the parser is run in deterministic mode, i. [sent-121, score-0.336]
81 Precision refers to the backtracker’s precision with respect to identifying the incorrect transition among the candidate transitions. [sent-126, score-0.362]
82 tra ∼nsi BtTion Csa tnhde i bsac thketra acvkeer-r ranks when trying to predict the incorrect transition, and ∼ BT Cand,1st is the number of candidates at tahned i∼n it iBalT point-of-failure. [sent-128, score-0.124]
83 nE uxmacbte Mra oftch caens i sd tahtees sto a-t tal number of parse derivations which are identical to the gold standard. [sent-129, score-0.069]
84 For Ms per Sent (milliseconds per sentence) it should be said that the code is not optimized, es- pecially with respect to the HPSG unification algorithm2. [sent-130, score-0.247]
85 2 CFG approximation The number of failed sentences is greatly reduced when backtracking is enabled. [sent-147, score-0.587]
86 Further, Optimistic Backtracker performs substantially better than baseline in identifying incorrect transitions. [sent-151, score-0.086]
87 The average number of candidate transitions ranged from 26 to 30 for the baseline and Optimistic backtracking strategy. [sent-152, score-0.7]
88 It’s interesting to observe that even with a success rate of about 1/5 in identifying the incorrect transition, the coverage is still greatly increased. [sent-153, score-0.113]
89 That backtracking manages to recover so many sentences that initially failed, even if it does not manage to identify the incorrect transition, would seem to indicate that even when mistaken, the backtracker is producing a good prediction. [sent-154, score-0.798]
90 On the other hand, the exact match score does not improve the same way as the coverage, this is directly related 2Specifically, the current unification back-end preforms non-destructive unification, i. [sent-155, score-0.247]
91 it does not take advantage of the deterministic nature of CuteForce 62 to the fact that the backtracker still has relatively low precision, as only a perfect prediction would leave the parser capable of deriving an exact match. [sent-157, score-0.539]
92 23 in picking the incorrect transition in a set of in average 30 candidates indicates that treating the backtracking as a ranking problem is promising. [sent-159, score-0.882]
93 3 HPSG Unification In unification mode the we see no substantive difference between deterministic mode, and baseline and Optimistic backtracking, and practically no improvement in the quality of the parses produced. [sent-162, score-0.665]
94 In Table 2 we see that the only striking difference between the figures for the parser in backtracking mode and deterministic mode is the efficiency the time consumption is increased by approximately a factor of 3. [sent-163, score-1.274]
95 It is however very likely that the results would be similar for other deterministic HPSG parsers. [sent-166, score-0.194]
96 In CFG mode, the number of failed parses are more than halved compared to deterministic mode. [sent-167, score-0.223]
97 It is likely that further increase could be obtained by relaxing constraints in the Optimistic algorithm. [sent-168, score-0.051]
98 Considering how little the parser benefited from backtracking in unification mode with Optimistic constraints, it seems implausible that the parser will improve considerably without a heavy relaxation of the constraints in the Optimistic algorithm. [sent-171, score-1.306]
99 If doing so, the attractive features of the parser’s inherently deterministic nature will be overshadowed by a very large number of backtracks at a heavy computational cost. [sent-172, score-0.32]
100 Deterministic shift-reduce parsing for unification-based grammars by using default unification. [sent-202, score-0.101]
wordName wordTfidf (topN-words)
[('backtracking', 0.528), ('hpsg', 0.327), ('optimistic', 0.25), ('unification', 0.247), ('transition', 0.237), ('mode', 0.205), ('backtracker', 0.203), ('cfg', 0.195), ('deterministic', 0.194), ('cuteforce', 0.162), ('parser', 0.142), ('erg', 0.132), ('redwoods', 0.122), ('backtrack', 0.101), ('parsing', 0.101), ('transitions', 0.095), ('derivation', 0.085), ('wikiwoods', 0.081), ('oracle', 0.074), ('passive', 0.072), ('incorrect', 0.067), ('overlay', 0.061), ('oepen', 0.059), ('candidate', 0.058), ('raced', 0.054), ('flickinger', 0.052), ('nivre', 0.052), ('oslo', 0.049), ('ninomiya', 0.049), ('daughter', 0.046), ('incremental', 0.045), ('buffer', 0.044), ('stack', 0.044), ('attractive', 0.043), ('scoring', 0.042), ('derivations', 0.042), ('backtracks', 0.041), ('gisle', 0.041), ('pec', 0.041), ('uio', 0.041), ('ytrest', 0.041), ('instantiating', 0.041), ('unary', 0.039), ('state', 0.035), ('maltparser', 0.034), ('resume', 0.033), ('lingo', 0.033), ('scholz', 0.031), ('rule', 0.03), ('approximation', 0.03), ('candidates', 0.03), ('relaxing', 0.029), ('ranker', 0.029), ('failed', 0.029), ('fails', 0.028), ('employs', 0.028), ('locate', 0.028), ('invalid', 0.028), ('le', 0.028), ('joakim', 0.028), ('strategy', 0.027), ('mc', 0.027), ('tahned', 0.027), ('valid', 0.027), ('parse', 0.027), ('incrementally', 0.026), ('edges', 0.026), ('stephan', 0.026), ('fell', 0.025), ('active', 0.025), ('coverage', 0.025), ('bt', 0.024), ('sagae', 0.023), ('hence', 0.023), ('bangalore', 0.022), ('adds', 0.022), ('constraints', 0.022), ('theoretically', 0.022), ('inherently', 0.022), ('unrestricted', 0.022), ('reduction', 0.022), ('unit', 0.021), ('tuples', 0.021), ('success', 0.021), ('edge', 0.021), ('yamada', 0.021), ('johansson', 0.021), ('tthhee', 0.02), ('ranking', 0.02), ('binary', 0.02), ('linear', 0.02), ('proportion', 0.02), ('indication', 0.02), ('heavy', 0.02), ('dependency', 0.02), ('treebanks', 0.019), ('baseline', 0.019), ('reached', 0.018), ('arrives', 0.018), ('cand', 0.018)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999976 236 acl-2011-Optimistic Backtracking - A Backtracking Overlay for Deterministic Incremental Parsing
Author: Gisle Ytrestl
Abstract: This paper describes a backtracking strategy for an incremental deterministic transitionbased parser for HPSG. The method could theoretically be implemented on any other transition-based parser with some adjustments. In this paper, the algorithm is evaluated on CuteForce, an efficient deterministic shiftreduce HPSG parser. The backtracking strategy may serve to improve existing parsers, or to assess if a deterministic parser would benefit from backtracking as a strategy to improve parsing.
2 0.16081156 143 acl-2011-Getting the Most out of Transition-based Dependency Parsing
Author: Jinho D. Choi ; Martha Palmer
Abstract: This paper suggests two ways of improving transition-based, non-projective dependency parsing. First, we add a transition to an existing non-projective parsing algorithm, so it can perform either projective or non-projective parsing as needed. Second, we present a bootstrapping technique that narrows down discrepancies between gold-standard and automatic parses used as features. The new addition to the algorithm shows a clear advantage in parsing speed. The bootstrapping technique gives a significant improvement to parsing accuracy, showing near state-of-theart performance with respect to other parsing approaches evaluated on the same data set.
3 0.15684812 282 acl-2011-Shift-Reduce CCG Parsing
Author: Yue Zhang ; Stephen Clark
Abstract: CCGs are directly compatible with binarybranching bottom-up parsing algorithms, in particular CKY and shift-reduce algorithms. While the chart-based approach has been the dominant approach for CCG, the shift-reduce method has been little explored. In this paper, we develop a shift-reduce CCG parser using a discriminative model and beam search, and compare its strengths and weaknesses with the chart-based C&C; parser. We study different errors made by the two parsers, and show that the shift-reduce parser gives competitive accuracies compared to C&C.; Considering our use of a small beam, and given the high ambiguity levels in an automatically-extracted grammar and the amount of information in the CCG lexical categories which form the shift actions, this is a surprising result.
4 0.11128037 110 acl-2011-Effective Use of Function Words for Rule Generalization in Forest-Based Translation
Author: Xianchao Wu ; Takuya Matsuzaki ; Jun'ichi Tsujii
Abstract: In the present paper, we propose the effective usage of function words to generate generalized translation rules for forest-based translation. Given aligned forest-string pairs, we extract composed tree-to-string translation rules that account for multiple interpretations of both aligned and unaligned target function words. In order to constrain the exhaustive attachments of function words, we limit to bind them to the nearby syntactic chunks yielded by a target dependency parser. Therefore, the proposed approach can not only capture source-tree-to-target-chunk correspondences but can also use forest structures that compactly encode an exponential number of parse trees to properly generate target function words during decoding. Extensive experiments involving large-scale English-toJapanese translation revealed a significant im- provement of 1.8 points in BLEU score, as compared with a strong forest-to-string baseline system.
5 0.11094499 107 acl-2011-Dynamic Programming Algorithms for Transition-Based Dependency Parsers
Author: Marco Kuhlmann ; Carlos Gomez-Rodriguez ; Giorgio Satta
Abstract: We develop a general dynamic programming technique for the tabulation of transition-based dependency parsers, and apply it to obtain novel, polynomial-time algorithms for parsing with the arc-standard and arc-eager models. We also show how to reverse our technique to obtain new transition-based dependency parsers from existing tabular methods. Additionally, we provide a detailed discussion of the conditions under which the feature models commonly used in transition-based parsing can be integrated into our algorithms.
6 0.10187852 309 acl-2011-Transition-based Dependency Parsing with Rich Non-local Features
7 0.092458956 298 acl-2011-The ACL Anthology Searchbench
8 0.087706275 167 acl-2011-Improving Dependency Parsing with Semantic Classes
9 0.084332928 171 acl-2011-Incremental Syntactic Language Models for Phrase-based Translation
10 0.069302961 184 acl-2011-Joint Hebrew Segmentation and Parsing using a PCFGLA Lattice Parser
11 0.065614261 58 acl-2011-Beam-Width Prediction for Efficient Context-Free Parsing
12 0.065189481 316 acl-2011-Unary Constraints for Efficient Context-Free Parsing
13 0.065066732 112 acl-2011-Efficient CCG Parsing: A* versus Adaptive Supertagging
14 0.06446223 59 acl-2011-Better Automatic Treebank Conversion Using A Feature-Based Approach
15 0.063386962 39 acl-2011-An Ensemble Model that Combines Syntactic and Semantic Clustering for Discriminative Dependency Parsing
16 0.061712276 210 acl-2011-Lexicographic Semirings for Exact Automata Encoding of Sequence Models
17 0.061131779 5 acl-2011-A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
18 0.05948361 267 acl-2011-Reversible Stochastic Attribute-Value Grammars
19 0.054934695 111 acl-2011-Effects of Noun Phrase Bracketing in Dependency Parsing and Machine Translation
20 0.052906156 173 acl-2011-Insertion Operator for Bayesian Tree Substitution Grammars
topicId topicWeight
[(0, 0.128), (1, -0.058), (2, -0.034), (3, -0.183), (4, -0.044), (5, -0.031), (6, -0.031), (7, 0.045), (8, 0.008), (9, -0.035), (10, 0.004), (11, 0.039), (12, 0.029), (13, -0.054), (14, -0.01), (15, 0.03), (16, 0.039), (17, -0.011), (18, 0.0), (19, -0.05), (20, 0.015), (21, 0.011), (22, 0.04), (23, -0.043), (24, -0.03), (25, 0.003), (26, 0.038), (27, -0.026), (28, -0.029), (29, -0.046), (30, -0.028), (31, -0.009), (32, -0.021), (33, 0.05), (34, -0.035), (35, 0.019), (36, -0.047), (37, 0.061), (38, -0.002), (39, -0.039), (40, -0.025), (41, -0.06), (42, -0.071), (43, 0.055), (44, -0.074), (45, -0.031), (46, 0.023), (47, -0.077), (48, 0.045), (49, 0.115)]
simIndex simValue paperId paperTitle
same-paper 1 0.93246162 236 acl-2011-Optimistic Backtracking - A Backtracking Overlay for Deterministic Incremental Parsing
Author: Gisle Ytrestl
Abstract: This paper describes a backtracking strategy for an incremental deterministic transitionbased parser for HPSG. The method could theoretically be implemented on any other transition-based parser with some adjustments. In this paper, the algorithm is evaluated on CuteForce, an efficient deterministic shiftreduce HPSG parser. The backtracking strategy may serve to improve existing parsers, or to assess if a deterministic parser would benefit from backtracking as a strategy to improve parsing.
2 0.7201547 107 acl-2011-Dynamic Programming Algorithms for Transition-Based Dependency Parsers
Author: Marco Kuhlmann ; Carlos Gomez-Rodriguez ; Giorgio Satta
Abstract: We develop a general dynamic programming technique for the tabulation of transition-based dependency parsers, and apply it to obtain novel, polynomial-time algorithms for parsing with the arc-standard and arc-eager models. We also show how to reverse our technique to obtain new transition-based dependency parsers from existing tabular methods. Additionally, we provide a detailed discussion of the conditions under which the feature models commonly used in transition-based parsing can be integrated into our algorithms.
3 0.71925265 282 acl-2011-Shift-Reduce CCG Parsing
Author: Yue Zhang ; Stephen Clark
Abstract: CCGs are directly compatible with binarybranching bottom-up parsing algorithms, in particular CKY and shift-reduce algorithms. While the chart-based approach has been the dominant approach for CCG, the shift-reduce method has been little explored. In this paper, we develop a shift-reduce CCG parser using a discriminative model and beam search, and compare its strengths and weaknesses with the chart-based C&C; parser. We study different errors made by the two parsers, and show that the shift-reduce parser gives competitive accuracies compared to C&C.; Considering our use of a small beam, and given the high ambiguity levels in an automatically-extracted grammar and the amount of information in the CCG lexical categories which form the shift actions, this is a surprising result.
4 0.71208227 143 acl-2011-Getting the Most out of Transition-based Dependency Parsing
Author: Jinho D. Choi ; Martha Palmer
Abstract: This paper suggests two ways of improving transition-based, non-projective dependency parsing. First, we add a transition to an existing non-projective parsing algorithm, so it can perform either projective or non-projective parsing as needed. Second, we present a bootstrapping technique that narrows down discrepancies between gold-standard and automatic parses used as features. The new addition to the algorithm shows a clear advantage in parsing speed. The bootstrapping technique gives a significant improvement to parsing accuracy, showing near state-of-theart performance with respect to other parsing approaches evaluated on the same data set.
5 0.70238227 267 acl-2011-Reversible Stochastic Attribute-Value Grammars
Author: Daniel de Kok ; Barbara Plank ; Gertjan van Noord
Abstract: An attractive property of attribute-value grammars is their reversibility. Attribute-value grammars are usually coupled with separate statistical components for parse selection and fluency ranking. We propose reversible stochastic attribute-value grammars, in which a single statistical model is employed both for parse selection and fluency ranking.
6 0.61574954 300 acl-2011-The Surprising Variance in Shortest-Derivation Parsing
7 0.61339206 243 acl-2011-Partial Parsing from Bitext Projections
9 0.59151584 112 acl-2011-Efficient CCG Parsing: A* versus Adaptive Supertagging
10 0.5772875 219 acl-2011-Metagrammar engineering: Towards systematic exploration of implemented grammars
11 0.57360357 39 acl-2011-An Ensemble Model that Combines Syntactic and Semantic Clustering for Discriminative Dependency Parsing
12 0.56663316 309 acl-2011-Transition-based Dependency Parsing with Rich Non-local Features
13 0.5633136 295 acl-2011-Temporal Restricted Boltzmann Machines for Dependency Parsing
14 0.55856806 230 acl-2011-Neutralizing Linguistically Problematic Annotations in Unsupervised Dependency Parsing Evaluation
15 0.54697007 186 acl-2011-Joint Training of Dependency Parsing Filters through Latent Support Vector Machines
17 0.52998501 184 acl-2011-Joint Hebrew Segmentation and Parsing using a PCFGLA Lattice Parser
18 0.52964723 317 acl-2011-Underspecifying and Predicting Voice for Surface Realisation Ranking
19 0.51094216 210 acl-2011-Lexicographic Semirings for Exact Automata Encoding of Sequence Models
20 0.50770032 298 acl-2011-The ACL Anthology Searchbench
topicId topicWeight
[(5, 0.019), (17, 0.059), (26, 0.021), (28, 0.01), (31, 0.019), (37, 0.071), (39, 0.076), (41, 0.075), (45, 0.012), (55, 0.02), (59, 0.034), (62, 0.011), (72, 0.016), (76, 0.28), (91, 0.055), (96, 0.111), (97, 0.012), (98, 0.025)]
simIndex simValue paperId paperTitle
same-paper 1 0.77148998 236 acl-2011-Optimistic Backtracking - A Backtracking Overlay for Deterministic Incremental Parsing
Author: Gisle Ytrestl
Abstract: This paper describes a backtracking strategy for an incremental deterministic transitionbased parser for HPSG. The method could theoretically be implemented on any other transition-based parser with some adjustments. In this paper, the algorithm is evaluated on CuteForce, an efficient deterministic shiftreduce HPSG parser. The backtracking strategy may serve to improve existing parsers, or to assess if a deterministic parser would benefit from backtracking as a strategy to improve parsing.
2 0.66262358 255 acl-2011-Query Snowball: A Co-occurrence-based Approach to Multi-document Summarization for Question Answering
Author: Hajime Morita ; Tetsuya Sakai ; Manabu Okumura
Abstract: We propose a new method for query-oriented extractive multi-document summarization. To enrich the information need representation of a given query, we build a co-occurrence graph to obtain words that augment the original query terms. We then formulate the summarization problem as a Maximum Coverage Problem with Knapsack Constraints based on word pairs rather than single words. Our experiments with the NTCIR ACLIA question answering test collections show that our method achieves a pyramid F3-score of up to 0.3 13, a 36% improvement over a baseline using Maximal Marginal Relevance. 1
3 0.59972465 175 acl-2011-Integrating history-length interpolation and classes in language modeling
Author: Hinrich Schutze
Abstract: Building on earlier work that integrates different factors in language modeling, we view (i) backing off to a shorter history and (ii) class-based generalization as two complementary mechanisms of using a larger equivalence class for prediction when the default equivalence class is too small for reliable estimation. This view entails that the classes in a language model should be learned from rare events only and should be preferably applied to rare events. We construct such a model and show that both training on rare events and preferable application to rare events improve perplexity when compared to a simple direct interpolation of class-based with standard language models.
4 0.5777688 169 acl-2011-Improving Question Recommendation by Exploiting Information Need
Author: Shuguang Li ; Suresh Manandhar
Abstract: In this paper we address the problem of question recommendation from large archives of community question answering data by exploiting the users’ information needs. Our experimental results indicate that questions based on the same or similar information need can provide excellent question recommendation. We show that translation model can be effectively utilized to predict the information need given only the user’s query question. Experiments show that the proposed information need prediction approach can improve the performance of question recommendation.
5 0.53620875 282 acl-2011-Shift-Reduce CCG Parsing
Author: Yue Zhang ; Stephen Clark
Abstract: CCGs are directly compatible with binarybranching bottom-up parsing algorithms, in particular CKY and shift-reduce algorithms. While the chart-based approach has been the dominant approach for CCG, the shift-reduce method has been little explored. In this paper, we develop a shift-reduce CCG parser using a discriminative model and beam search, and compare its strengths and weaknesses with the chart-based C&C; parser. We study different errors made by the two parsers, and show that the shift-reduce parser gives competitive accuracies compared to C&C.; Considering our use of a small beam, and given the high ambiguity levels in an automatically-extracted grammar and the amount of information in the CCG lexical categories which form the shift actions, this is a surprising result.
6 0.53472197 126 acl-2011-Exploiting Syntactico-Semantic Structures for Relation Extraction
7 0.53442031 58 acl-2011-Beam-Width Prediction for Efficient Context-Free Parsing
8 0.53384405 241 acl-2011-Parsing the Internal Structure of Words: A New Paradigm for Chinese Word Segmentation
9 0.53090852 209 acl-2011-Lexically-Triggered Hidden Markov Models for Clinical Document Coding
10 0.53089094 324 acl-2011-Unsupervised Semantic Role Induction via Split-Merge Clustering
11 0.52898622 5 acl-2011-A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
12 0.52783948 65 acl-2011-Can Document Selection Help Semi-supervised Learning? A Case Study On Event Extraction
13 0.52745986 137 acl-2011-Fine-Grained Class Label Markup of Search Queries
14 0.52740002 202 acl-2011-Learning Hierarchical Translation Structure with Linguistic Annotations
16 0.52450174 316 acl-2011-Unary Constraints for Efficient Context-Free Parsing
17 0.52365035 28 acl-2011-A Statistical Tree Annotator and Its Applications
18 0.52350503 269 acl-2011-Scaling up Automatic Cross-Lingual Semantic Role Annotation
19 0.52290249 97 acl-2011-Discovering Sociolinguistic Associations with Structured Sparsity
20 0.5225144 327 acl-2011-Using Bilingual Parallel Corpora for Cross-Lingual Textual Entailment