research-article

Free access

Parsing with soft and hard constraints on dependency length

Authors:

Noah A. SmithAuthors Info & Claims

Parsing '05: Proceedings of the Ninth International Workshop on Parsing Technology

Pages 30 - 41

Published: 09 October 2005 Publication History

Abstract

In lexicalized phrase-structure or dependency parses, a word's modifiers tend to fall near it in the string. We show that a crude way to use dependency length as a parsing feature can substantially improve parsing speed and accuracy in English and Chinese, with more mixed results on German. We then show similar improvements by imposing hard bounds on dependency length and (additionally) modeling the resulting sequence of parse fragments. This simple "vine grammar" formalism has only finite-state power, but a context-free parameterization with some extra parameters for stringing fragments together. We exhibit a linear-time chart parsing algorithm with a low grammar constant.

References

[1]

S. P. Abney. Parsing by chunks. In Principle-Based Parsing: Computation and Psycholinguistics. Kluwer, 1991.

Digital Library

[2]

D. E. Appelt, J. R. Hobbs, J. Bear, D. Israel, and M. Tyson. FASTUS: A finite-state processor for information extraction from real-world text. In Proc. of IJCAI, 1993.

[3]

E. Bertsch and M.-J. Nederhof. Regular closure of deterministic languages. SIAM J. on Computing, 29(1):81--102, 1999.

Digital Library

[4]

D. Bikel. A distributional analysis of a lexicalized statistical parsing model. In Proc. of EMNLP, 2004.

[5]

T. Brants. Cascaded Markov models. In Proc. of EACL, 1999.

Digital Library

[6]

S. A. Caraballo and E. Charniak. New figures of merit for best-first probabilistic chart parsing. Computational Linguistics, 24(2):275--98, 1998.

Digital Library

[7]

S. Chen. Bayesian grammar induction for language modeling. In Proc. of ACL, 1995.

Digital Library

[8]

K. W. Church. On memory limitations in natural language processing. Master's thesis, MIT, 1980.

[9]

M. Collins. Three generative, lexicalised models for statistical parsing. In Proc. of ACL, 1997.

Digital Library

[10]

J. Eisner. Bilexical grammars and their cubic-time parsing algorithms. In Advances in Probabilistic and Other Parsing Technologies. Kluwer, 2000.

[11]

J. Eisner, E. Goldlust, and N. A. Smith. Compiling Comp Ling: Practical weighted dynamic programming and the Dyna language. In Proc. of HLT-EMNLP, 2005.

Digital Library

[12]

J. Eisner and G. Satta. Efficient parsing for bilexical cfgs and head automaton grammars. In Proc. of ACL, 1999.

Digital Library

[13]

L. Frazier. On Comprehending Sentences: Syntactic Parsing Strategies. PhD thesis, University of Massachusetts, 1979.

[14]

E. Gibson. Linguistic complexity: Locality of syntactic dependencies. Cognition, 68:1--76, 1998.

[15]

G. Grefenstette. Light parsing as finite-state filtering. In Proc. of Workshop on Extended FS Models of Language, 1996.

[16]

D. Hindle. Noun classification from predicate-argument structure. In Proc. of ACL, 1990.

Digital Library

[17]

J. R. Hobbs and J. Bear. Two principles of parse preference. In Proc. of COLING, 1990.

Digital Library

[18]

D. Klein and C. D. Manning. Accurate unlexicalized parsing. In Proc. of ACL, 2003.

Digital Library

[19]

D. Klein and C. D. Manning. Corpus-based induction of syntactic structure: Models of dependency and constituency. In Proc. of ACL, 2004.

Digital Library

[20]

R. McDonald, K. Crammer, and F. Pereira. Online large-margin training of dependency parsers. In Proc. of ACL, 2005.

Digital Library

[21]

Y. Miyao and J. Tsujii. Maximum entropy estimation for feature forests. In Proc. of HLT, 2002.

Digital Library

[22]

M.-J. Nederhof. Practical experiments with regular approximation of context-free languages. CL, 26(1):17--44, 2000.

Digital Library

[23]

M.-J. Nederhof. Weighted deductive parsing and Knuth's algorithm. Computational Linguistics, 29(1):135--143, 2003.

Digital Library

[24]

C. Schafer and D. Yarowsky. A two-level syntax-based approach to Arabic-English statistical machine translation. In Proc. of Workshop on MT for Semitic Languages, 2003.

[25]

B. Taskar, D. Klein, M. Collins, D. Koller, and C. Manning. Max-margin parsing. In Proc. of EMNLP, 2004.

Cited By

Guo QQiu XXue XZhang Z(2019)Low-Rank and Locality Constrained Self-Attention for Sequence ModelingIEEE/ACM Transactions on Audio, Speech and Language Processing10.1109/TASLP.2019.294407827:12(2213-2222)Online publication date: 26-Nov-2019
https://dl.acm.org/doi/10.1109/TASLP.2019.2944078
Rush APetrov SChu-Carroll J(2012)Vine pruning for efficient multi-pass dependency parsingProceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies10.5555/2382029.2382100(498-507)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.5555/2382029.2382100
Wang LLui MKim SNivre JBaldwin TMerlo PBarzilay RJohnson M(2011)Predicting thread discourse structure over technical web forumsProceedings of the Conference on Empirical Methods in Natural Language Processing10.5555/2145432.2145435(13-25)Online publication date: 27-Jul-2011
https://dl.acm.org/doi/10.5555/2145432.2145435
Show More Cited By

Parsing with soft and hard constraints on dependency length

Recommendations

Improve Chinese Semantic Dependency Parsing via Syntactic Dependency Parsing
IALP '12: Proceedings of the 2012 International Conference on Asian Language Processing

We address the problem of Chinese semantic dependency parsing. Dependency parsing is traditionally oriented to syntax analysis, which we denote by syntactic dependency parsing to distinguish it from semantic dependency parsing. In this paper, firstly we ...
Dependency Parsing
Hybrid Long-Distance Functional Dependency Parsing: A hybrid, deep-syntactic Dependency Grammar parser for English, combining statistical performance ... competence approaches

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

Parsing '05: Proceedings of the Ninth International Workshop on Parsing Technology

October 2005

214 pages

Program Chairs:
Harry Bunt
Tilburg University, Netherlands
,
Robert Malouf
San Diego State University, USA
,
Alon Lavie
Carnegie-Mellon University, Pittsburgh, USA

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 09 October 2005

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
131
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)17

Reflects downloads up to 12 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guo QQiu XXue XZhang Z(2019)Low-Rank and Locality Constrained Self-Attention for Sequence ModelingIEEE/ACM Transactions on Audio, Speech and Language Processing10.1109/TASLP.2019.294407827:12(2213-2222)Online publication date: 26-Nov-2019
https://dl.acm.org/doi/10.1109/TASLP.2019.2944078
Rush APetrov SChu-Carroll J(2012)Vine pruning for efficient multi-pass dependency parsingProceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies10.5555/2382029.2382100(498-507)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.5555/2382029.2382100
Wang LLui MKim SNivre JBaldwin TMerlo PBarzilay RJohnson M(2011)Predicting thread discourse structure over technical web forumsProceedings of the Conference on Empirical Methods in Natural Language Processing10.5555/2145432.2145435(13-25)Online publication date: 27-Jul-2011
https://dl.acm.org/doi/10.5555/2145432.2145435
Søgaard AMatveeva IMoschitti AMàrquez LZanzotto F(2011)From ranked words to dependency treesProceedings of TextGraphs-6: Graph-based Methods for Natural Language Processing10.5555/2024277.2024287(60-68)Online publication date: 23-Jun-2011
https://dl.acm.org/doi/10.5555/2024277.2024287
Spitkovsky VAlshawi HJurafsky DGoldwater SManning C(2011)PunctuationProceedings of the Fifteenth Conference on Computational Natural Language Learning10.5555/2018936.2018939(19-28)Online publication date: 23-Jun-2011
https://dl.acm.org/doi/10.5555/2018936.2018939
Cherry CBergsma SLin D(2011)Joint training of dependency parsing filters through latent support vector machinesProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: short papers - Volume 210.5555/2002736.2002779(200-205)Online publication date: 19-Jun-2011
https://dl.acm.org/doi/10.5555/2002736.2002779
Bergsma SCherry CJoshi AHuang CJurafsky D(2010)Fast and accurate arc filtering for dependency parsingProceedings of the 23rd International Conference on Computational Linguistics10.5555/1873781.1873788(53-61)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1873781.1873788
Goldberg YElhadad MKaplan R(2010)An efficient algorithm for easy-first non-directional dependency parsingHuman Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics10.5555/1857999.1858114(742-750)Online publication date: 2-Jun-2010
https://dl.acm.org/doi/10.5555/1857999.1858114
Søgaard AKuhn JBunt H(2009)Using a maximum entropy-based tagger to improve a very fast vine parserProceedings of the 11th International Conference on Parsing Technologies10.5555/1697236.1697276(206-209)Online publication date: 7-Oct-2009
https://dl.acm.org/doi/10.5555/1697236.1697276
Druck GMann GMcCallum ASu K(2009)Semi-supervised learning of dependency parsers using generalized expectation criteriaProceedings 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: Volume 1 - Volume 110.5555/1687878.1687930(360-368)Online publication date: 2-Aug-2009
https://dl.acm.org/doi/10.5555/1687878.1687930
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents