acl acl2011 acl2011-106 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alexander M. Rush and Michael Collins
Abstract: unkown-abstract
Reference: text
sentIndex sentText sentNum sentScore
1 , 2010) • “loopy” H M M part-of-speech tagging • syntactic machine translation (Rush and Collins, 2011) NP-Hard • symmetric H M M alignment (DeNero and Macherey, 2011) • phrase-based translation • higher-order non-projective dependency parsing (Koo et al . [sent-3, score-0.335]
2 Upper bound define: • y∗ , z∗ is the optimal combined parsing and tagging solution with y∗ (i, t) = z∗(i, t) for all i, t theorem: for any value of u L(u) ≥ f (y∗) + g(z∗) L(u) provides an upper bound on the score of the optimal solution note: upper bound may be A* search Theorem 1 . [sent-27, score-0.865]
3 Convergence notation: • u(k+1)(i, t) u(k)(i, t) + αk(y(k)(i, t) z(k)(i, t)) is update u(k) is the penalty vector at iteration k • αk • ← − is the update rate at iteration k theorem: for any sequence α1, α2, α3, . [sent-29, score-0.068]
4 the algorithm converges to the tightest possible upper bound proof: by subgradient convergence (next section) Dual solutions define: • for any value of u yu= argmy∈aYxf (y) +Xi,tu(i,t)y(i,t) and •yuandzuazure=thaergdmuz∈a lZxsolugt(izo)ns−foXir,taug(iv,etn)zu(i,t) Theorem 3. [sent-34, score-0.498]
5 if the dual solutions agree, we have an optimal solution (yu, zu) Theorem 3. [sent-37, score-0.66]
6 Ym is set of tag sequences for the input corpus YY ∈ Y is×X Xa . [sent-48, score-0.092]
7 M rf energy minimization and beyond via dual decomposition . [sent-103, score-0.577]
8 Dual decomposition for parsing with non-projective head automata . [sent-108, score-0.263]
9 Approximate primal solutions and rate analysis for dual subgradient methods. [sent-126, score-0.819]
10 A hierarchy of relaxations and convex hull characterizations for mixed-integer zero–one programming problems. [sent-150, score-0.131]
wordName wordTfidf (topN-words)
[('dual', 0.397), ('zu', 0.247), ('argmy', 0.183), ('ayxf', 0.183), ('subgradient', 0.181), ('xz', 0.181), ('decomposition', 0.18), ('flies', 0.179), ('lagrangian', 0.176), ('theorem', 0.167), ('xy', 0.164), ('jet', 0.162), ('solutions', 0.133), ('animation', 0.132), ('yu', 0.131), ('decoding', 0.126), ('zf', 0.122), ('tagging', 0.121), ('primal', 0.108), ('constituency', 0.104), ('azx', 0.099), ('tightening', 0.099), ('zz', 0.099), ('yy', 0.098), ('notation', 0.093), ('tag', 0.092), ('argy', 0.089), ('np', 0.083), ('parsing', 0.083), ('ayx', 0.082), ('argmz', 0.081), ('azxg', 0.081), ('alignment', 0.076), ('proof', 0.076), ('rush', 0.076), ('solution', 0.074), ('relaxations', 0.07), ('simplex', 0.07), ('relaxation', 0.07), ('vp', 0.069), ('combinatorial', 0.067), ('optimization', 0.066), ('zl', 0.066), ('yf', 0.066), ('lazy', 0.066), ('bound', 0.066), ('parse', 0.064), ('lp', 0.064), ('mz', 0.062), ('united', 0.061), ('haeibs', 0.061), ('hbeias', 0.061), ('hceics', 0.061), ('tightest', 0.061), ('programming', 0.061), ('formal', 0.059), ('upper', 0.057), ('optimal', 0.056), ('dependency', 0.055), ('argmyaxf', 0.054), ('selects', 0.053), ('ma', 0.053), ('aim', 0.053), ('cfg', 0.051), ('fractional', 0.051), ('zg', 0.049), ('man', 0.047), ('valid', 0.047), ('goal', 0.046), ('score', 0.045), ('combined', 0.044), ('sontag', 0.042), ('approximate', 0.041), ('duality', 0.041), ('echal', 0.041), ('lemar', 0.041), ('nedi', 0.041), ('sherali', 0.041), ('optimality', 0.041), ('jaakkola', 0.039), ('constraint', 0.038), ('exact', 0.038), ('sibling', 0.038), ('linear', 0.037), ('recompute', 0.036), ('argmaxz', 0.036), ('muinl', 0.036), ('algorithms', 0.036), ('gu', 0.035), ('decode', 0.035), ('iteration', 0.034), ('guarantees', 0.033), ('komodakis', 0.033), ('stood', 0.033), ('lexicalized', 0.033), ('maximizes', 0.031), ('subproblems', 0.031), ('certificate', 0.031), ('argmaxy', 0.031), ('constraints', 0.031)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000002 106 acl-2011-Dual Decomposition for Natural Language Processing
Author: Alexander M. Rush and Michael Collins
Abstract: unkown-abstract
2 0.2934567 123 acl-2011-Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation
Author: Alexander M. Rush ; Michael Collins
Abstract: We describe an exact decoding algorithm for syntax-based statistical translation. The approach uses Lagrangian relaxation to decompose the decoding problem into tractable subproblems, thereby avoiding exhaustive dynamic programming. The method recovers exact solutions, with certificates of optimality, on over 97% of test examples; it has comparable speed to state-of-the-art decoders.
3 0.21785416 221 acl-2011-Model-Based Aligner Combination Using Dual Decomposition
Author: John DeNero ; Klaus Macherey
Abstract: Unsupervised word alignment is most often modeled as a Markov process that generates a sentence f conditioned on its translation e. A similar model generating e from f will make different alignment predictions. Statistical machine translation systems combine the predictions of two directional models, typically using heuristic combination procedures like grow-diag-final. This paper presents a graphical model that embeds two directional aligners into a single model. Inference can be performed via dual decomposition, which reuses the efficient inference algorithms of the directional models. Our bidirectional model enforces a one-to-one phrase constraint while accounting for the uncertainty in the underlying directional models. The resulting alignments improve upon baseline combination heuristics in word-level and phrase-level evaluations.
Author: Michael Auli ; Adam Lopez
Abstract: Via an oracle experiment, we show that the upper bound on accuracy of a CCG parser is significantly lowered when its search space is pruned using a supertagger, though the supertagger also prunes many bad parses. Inspired by this analysis, we design a single model with both supertagging and parsing features, rather than separating them into distinct models chained together in a pipeline. To overcome the resulting increase in complexity, we experiment with both belief propagation and dual decomposition approaches to inference, the first empirical comparison of these algorithms that we are aware of on a structured natural language processing problem. On CCGbank we achieve a labelled dependency F-measure of 88.8% on gold POS tags, and 86.7% on automatic part-of-speeoch tags, the best reported results for this task.
5 0.091995351 235 acl-2011-Optimal and Syntactically-Informed Decoding for Monolingual Phrase-Based Alignment
Author: Kapil Thadani ; Kathleen McKeown
Abstract: The task of aligning corresponding phrases across two related sentences is an important component of approaches for natural language problems such as textual inference, paraphrase detection and text-to-text generation. In this work, we examine a state-of-the-art structured prediction model for the alignment task which uses a phrase-based representation and is forced to decode alignments using an approximate search approach. We propose instead a straightforward exact decoding technique based on integer linear programming that yields order-of-magnitude improvements in decoding speed. This ILP-based decoding strategy permits us to consider syntacticallyinformed constraints on alignments which significantly increase the precision of the model.
6 0.085281849 166 acl-2011-Improving Decoding Generalization for Tree-to-String Translation
7 0.084232047 39 acl-2011-An Ensemble Model that Combines Syntactic and Semantic Clustering for Discriminative Dependency Parsing
8 0.084088475 268 acl-2011-Rule Markov Models for Fast Tree-to-String Translation
9 0.081683576 155 acl-2011-Hypothesis Mixture Decoding for Statistical Machine Translation
10 0.071846813 143 acl-2011-Getting the Most out of Transition-based Dependency Parsing
11 0.066963173 335 acl-2011-Why Initialization Matters for IBM Model 1: Multiple Optima and Non-Strict Convexity
12 0.06662032 323 acl-2011-Unsupervised Part-of-Speech Tagging with Bilingual Graph-Based Projections
13 0.065737613 152 acl-2011-How Much Can We Gain from Supervised Word Alignment?
14 0.065201201 27 acl-2011-A Stacked Sub-Word Model for Joint Chinese Word Segmentation and Part-of-Speech Tagging
15 0.064015217 309 acl-2011-Transition-based Dependency Parsing with Rich Non-local Features
16 0.063763015 30 acl-2011-Adjoining Tree-to-String Translation
17 0.06054863 187 acl-2011-Jointly Learning to Extract and Compress
18 0.060089517 206 acl-2011-Learning to Transform and Select Elementary Trees for Improved Syntax-based Machine Translations
19 0.05936468 127 acl-2011-Exploiting Web-Derived Selectional Preference to Improve Statistical Dependency Parsing
20 0.057517052 58 acl-2011-Beam-Width Prediction for Efficient Context-Free Parsing
topicId topicWeight
[(0, 0.156), (1, -0.092), (2, 0.008), (3, -0.111), (4, -0.001), (5, -0.019), (6, -0.06), (7, 0.046), (8, -0.018), (9, 0.031), (10, 0.068), (11, 0.127), (12, 0.035), (13, 0.058), (14, -0.118), (15, 0.055), (16, 0.045), (17, -0.06), (18, -0.074), (19, -0.029), (20, 0.055), (21, -0.04), (22, 0.11), (23, 0.092), (24, -0.076), (25, -0.04), (26, -0.013), (27, 0.037), (28, -0.017), (29, 0.018), (30, -0.019), (31, 0.032), (32, -0.043), (33, 0.072), (34, -0.07), (35, 0.105), (36, 0.022), (37, -0.029), (38, -0.15), (39, -0.082), (40, 0.077), (41, 0.009), (42, -0.037), (43, -0.104), (44, 0.179), (45, -0.17), (46, 0.003), (47, -0.063), (48, 0.048), (49, 0.054)]
simIndex simValue paperId paperTitle
same-paper 1 0.94740468 106 acl-2011-Dual Decomposition for Natural Language Processing
Author: Alexander M. Rush and Michael Collins
Abstract: unkown-abstract
2 0.84506166 123 acl-2011-Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation
Author: Alexander M. Rush ; Michael Collins
Abstract: We describe an exact decoding algorithm for syntax-based statistical translation. The approach uses Lagrangian relaxation to decompose the decoding problem into tractable subproblems, thereby avoiding exhaustive dynamic programming. The method recovers exact solutions, with certificates of optimality, on over 97% of test examples; it has comparable speed to state-of-the-art decoders.
3 0.58047485 235 acl-2011-Optimal and Syntactically-Informed Decoding for Monolingual Phrase-Based Alignment
Author: Kapil Thadani ; Kathleen McKeown
Abstract: The task of aligning corresponding phrases across two related sentences is an important component of approaches for natural language problems such as textual inference, paraphrase detection and text-to-text generation. In this work, we examine a state-of-the-art structured prediction model for the alignment task which uses a phrase-based representation and is forced to decode alignments using an approximate search approach. We propose instead a straightforward exact decoding technique based on integer linear programming that yields order-of-magnitude improvements in decoding speed. This ILP-based decoding strategy permits us to consider syntacticallyinformed constraints on alignments which significantly increase the precision of the model.
4 0.52152216 221 acl-2011-Model-Based Aligner Combination Using Dual Decomposition
Author: John DeNero ; Klaus Macherey
Abstract: Unsupervised word alignment is most often modeled as a Markov process that generates a sentence f conditioned on its translation e. A similar model generating e from f will make different alignment predictions. Statistical machine translation systems combine the predictions of two directional models, typically using heuristic combination procedures like grow-diag-final. This paper presents a graphical model that embeds two directional aligners into a single model. Inference can be performed via dual decomposition, which reuses the efficient inference algorithms of the directional models. Our bidirectional model enforces a one-to-one phrase constraint while accounting for the uncertainty in the underlying directional models. The resulting alignments improve upon baseline combination heuristics in word-level and phrase-level evaluations.
Author: Michael Auli ; Adam Lopez
Abstract: Via an oracle experiment, we show that the upper bound on accuracy of a CCG parser is significantly lowered when its search space is pruned using a supertagger, though the supertagger also prunes many bad parses. Inspired by this analysis, we design a single model with both supertagging and parsing features, rather than separating them into distinct models chained together in a pipeline. To overcome the resulting increase in complexity, we experiment with both belief propagation and dual decomposition approaches to inference, the first empirical comparison of these algorithms that we are aware of on a structured natural language processing problem. On CCGbank we achieve a labelled dependency F-measure of 88.8% on gold POS tags, and 86.7% on automatic part-of-speeoch tags, the best reported results for this task.
6 0.49342915 155 acl-2011-Hypothesis Mixture Decoding for Statistical Machine Translation
7 0.42895141 220 acl-2011-Minimum Bayes-risk System Combination
8 0.42374083 234 acl-2011-Optimal Head-Driven Parsing Complexity for Linear Context-Free Rewriting Systems
9 0.41687131 342 acl-2011-full-for-print
10 0.41504022 323 acl-2011-Unsupervised Part-of-Speech Tagging with Bilingual Graph-Based Projections
11 0.40234041 199 acl-2011-Learning Condensed Feature Representations from Large Unsupervised Data Sets for Supervised Learning
12 0.39839455 267 acl-2011-Reversible Stochastic Attribute-Value Grammars
13 0.38964543 166 acl-2011-Improving Decoding Generalization for Tree-to-String Translation
14 0.38868356 187 acl-2011-Jointly Learning to Extract and Compress
15 0.38773671 236 acl-2011-Optimistic Backtracking - A Backtracking Overlay for Deterministic Incremental Parsing
16 0.37773746 239 acl-2011-P11-5002 k2opt.pdf
17 0.3746666 78 acl-2011-Confidence-Weighted Learning of Factored Discriminative Language Models
18 0.37341559 217 acl-2011-Machine Translation System Combination by Confusion Forest
19 0.37183103 79 acl-2011-Confidence Driven Unsupervised Semantic Parsing
20 0.36266139 93 acl-2011-Dealing with Spurious Ambiguity in Learning ITG-based Word Alignment
topicId topicWeight
[(5, 0.018), (17, 0.043), (26, 0.03), (37, 0.074), (39, 0.057), (41, 0.073), (55, 0.024), (59, 0.025), (64, 0.374), (72, 0.023), (91, 0.057), (96, 0.11)]
simIndex simValue paperId paperTitle
same-paper 1 0.80518425 106 acl-2011-Dual Decomposition for Natural Language Processing
Author: Alexander M. Rush and Michael Collins
Abstract: unkown-abstract
2 0.54267442 206 acl-2011-Learning to Transform and Select Elementary Trees for Improved Syntax-based Machine Translations
Author: Bing Zhao ; Young-Suk Lee ; Xiaoqiang Luo ; Liu Li
Abstract: We propose a novel technique of learning how to transform the source parse trees to improve the translation qualities of syntax-based translation models using synchronous context-free grammars. We transform the source tree phrasal structure into a set of simpler structures, expose such decisions to the decoding process, and find the least expensive transformation operation to better model word reordering. In particular, we integrate synchronous binarizations, verb regrouping, removal of redundant parse nodes, and incorporate a few important features such as translation boundaries. We learn the structural preferences from the data in a generative framework. The syntax-based translation system integrating the proposed techniques outperforms the best Arabic-English unconstrained system in NIST08 evaluations by 1.3 absolute BLEU, which is statistically significant.
3 0.49152362 177 acl-2011-Interactive Group Suggesting for Twitter
Author: Zhonghua Qu ; Yang Liu
Abstract: The number of users on Twitter has drastically increased in the past years. However, Twitter does not have an effective user grouping mechanism. Therefore tweets from other users can quickly overrun and become inconvenient to read. In this paper, we propose methods to help users group the people they follow using their provided seeding users. Two sources of information are used to build sub-systems: textural information captured by the tweets sent by users, and social connections among users. We also propose a measure of fitness to determine which subsystem best represents the seed users and use it for target user ranking. Our experiments show that our proposed framework works well and that adaptively choosing the appropriate sub-system for group suggestion results in increased accuracy.
4 0.48250198 123 acl-2011-Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation
Author: Alexander M. Rush ; Michael Collins
Abstract: We describe an exact decoding algorithm for syntax-based statistical translation. The approach uses Lagrangian relaxation to decompose the decoding problem into tractable subproblems, thereby avoiding exhaustive dynamic programming. The method recovers exact solutions, with certificates of optimality, on over 97% of test examples; it has comparable speed to state-of-the-art decoders.
5 0.47727957 237 acl-2011-Ordering Prenominal Modifiers with a Reranking Approach
Author: Jenny Liu ; Aria Haghighi
Abstract: In this work, we present a novel approach to the generation task of ordering prenominal modifiers. We take a maximum entropy reranking approach to the problem which admits arbitrary features on a permutation of modifiers, exploiting hundreds ofthousands of features in total. We compare our error rates to the state-of-the-art and to a strong Google ngram count baseline. We attain a maximum error reduction of 69.8% and average error reduction across all test sets of 59. 1% compared to the state-of-the-art and a maximum error reduction of 68.4% and average error reduction across all test sets of 41.8% compared to our Google n-gram count baseline.
7 0.45653725 221 acl-2011-Model-Based Aligner Combination Using Dual Decomposition
8 0.42221275 58 acl-2011-Beam-Width Prediction for Efficient Context-Free Parsing
9 0.42216593 126 acl-2011-Exploiting Syntactico-Semantic Structures for Relation Extraction
10 0.42013931 241 acl-2011-Parsing the Internal Structure of Words: A New Paradigm for Chinese Word Segmentation
11 0.41958648 209 acl-2011-Lexically-Triggered Hidden Markov Models for Clinical Document Coding
12 0.41952527 65 acl-2011-Can Document Selection Help Semi-supervised Learning? A Case Study On Event Extraction
13 0.41850698 324 acl-2011-Unsupervised Semantic Role Induction via Split-Merge Clustering
14 0.41821477 119 acl-2011-Evaluating the Impact of Coder Errors on Active Learning
15 0.41805777 145 acl-2011-Good Seed Makes a Good Crop: Accelerating Active Learning Using Language Modeling
16 0.4179638 137 acl-2011-Fine-Grained Class Label Markup of Search Queries
17 0.41560787 196 acl-2011-Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models
18 0.41437715 202 acl-2011-Learning Hierarchical Translation Structure with Linguistic Annotations
19 0.41309699 246 acl-2011-Piggyback: Using Search Engines for Robust Cross-Domain Named Entity Recognition
20 0.41304559 300 acl-2011-The Surprising Variance in Shortest-Derivation Parsing